Active set methods

Active set methods are a class of iterative algorithms for solving quadratic optimization problems .

Mathematical problem definition

Every square program can be converted into a standardized form:

${\displaystyle {\begin{array}{rcl}\min _{x\in \mathbb {R} ^{n}}&{\frac {1}{2}}x^{T}Hx+c^{T}x&=f(x)\\s.t.&a_{i}^{T}x\geq b_{i}&\forall i\in {\mathcal {I}}\\&a_{j}^{T}x=b_{j}&\forall j\in {\mathcal {E}}\end{array}}}$

where is the number of decision variables. In the objective function , the Hessian matrix corresponds to the quantities and indicates the inequality and equality conditions. Often it is required that the matrix is positive, semidefinite , since the optimization problem is then convex . ${\displaystyle n}$ ${\displaystyle f(x)}$ ${\displaystyle H}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {E}}}$ ${\displaystyle H}$

Active set

A constraint is active at one point if it holds. ${\displaystyle i\in {\mathcal {I}}}$ ${\displaystyle x}$ ${\displaystyle a_{i}^{T}x=b_{i}}$

The active set is the set of all active conditions at a valid point : ${\displaystyle {\mathcal {A}}(x)}$ ${\displaystyle x}$

${\displaystyle {\mathcal {A}}(x):=\{j\in {\mathcal {E}}\cup i\in {\mathcal {I}}:a_{i}^{T}x=b_{i}\}}$

algorithm

Active set methods require an initial valid solution . The algorithms then compute a valid point in each iteration until an optimum is reached. A set is managed that indicates which constraints should be active in the current iteration. ${\displaystyle x_{0}}$ ${\displaystyle x_{k}}$ ${\displaystyle W_{k}}$

 1  Gegeben: gültiger Punkt  ${\displaystyle x_{0}}$,  ${\displaystyle W_{0}\subseteq {\mathcal {A}}(x_{0})}$
 2
 3  for k=0,1,.. do
 4  berechne eine Suchrichtung  ${\displaystyle p_{k}}$
 5  if  ${\displaystyle p_{k}=0}$
 6    berechne Lagrange-Multiplikatoren  ${\displaystyle \lambda _{i}}$
 7    if  ${\displaystyle \forall i:\lambda _{i}\geq 0}$
 8      terminiere und gib  ${\displaystyle x_{k}}$ aus
 9    else
10      finde Ungleichheitsbedingung  ${\displaystyle i\in W_{k}\cap {\mathcal {I}}}$ mit  ${\displaystyle \lambda _{i}<0}$
11       ${\displaystyle W_{k+1}=W_{k}\backslash i}$
12    end
13  else
14    berechne Schrittlänge  ${\displaystyle \alpha _{k}}$
15    if  ${\displaystyle \alpha _{k}<1}$
16      finde Nebenbedingung j die  ${\displaystyle \alpha _{k}}$ beschränkt
17       ${\displaystyle W_{k+1}=W_{k}\cup j}$
18    end
19     ${\displaystyle x_{k+1}=x_{k}+\alpha _{k}p_{k}}$
20  end

Calculation of the search direction ${\displaystyle p_{k}}$

The constraints in define a subspace. If the optimal solution of the objective function is in this subspace, the search direction can be defined as. Substituting this into the objective function, the direction is obtained by solving a quadratic sub-problem : ${\displaystyle W_{k}}$ ${\displaystyle x}$ ${\displaystyle p_{k}=x-x_{k}}$ ${\displaystyle p_{k}}$

${\displaystyle {\begin{array}{rcl}\min _{x\in \mathbb {R} ^{n}}&{\frac {1}{2}}p_{k}^{T}Hp_{k}+g_{k}^{T}p_{k}\\s.t.&A^{T}p_{k}=0&\forall i\in W_{k}\end{array}}}$

where the gradient is at the current solution and the columns of the matrix are the vectors . ${\displaystyle g_{k}=Hx_{k}+c}$ ${\displaystyle A}$ ${\displaystyle a_{i},i\in W_{k}}$

This sub-problem can be solved in several ways. One possibility is a null space approach:

If you have a matrix whose columns form a basis for the core of the matrix , you can parameterize the valid area of ​​the sub-problem through . You now solve the system of equations ${\displaystyle Z}$ ${\displaystyle A^{T}}$ ${\displaystyle p_{k}=Zu}$

${\displaystyle Mu=-Z^{T}g_{k}}$,

where is the reduced Hessian matrix, one gets the search direction in the original problem. ${\displaystyle M=Z^{T}HZ}$

Calculation of the Lagrange multiplier ${\displaystyle \lambda _{i}}$

If the search direction is, is already optimal in the current subspace. One then has to remove a suitable inequality condition from . The Lagrange multipliers are obtained by solving a system of linear equations: ${\displaystyle p_{k}=0}$ ${\displaystyle x_{k}}$ ${\displaystyle W_{k}}$ ${\displaystyle \lambda _{i}}$

${\displaystyle \sum _{i\in W_{k}\cap {\mathcal {I}}}a_{i}\lambda _{i}=g_{k}=Hx_{k}+c}$

If all are, meet and the Karush-Kuhn-Tucker conditions , which are necessary criteria for optimality. If the Hessian matrix is ​​also positive semidefinite, these conditions are sufficient and is the optimal solution to the problem. If you remove an inequality condition with a negative Lagrange multiplier , you get a search direction in the next iteration. ${\displaystyle \lambda _{i}\geq 0}$ ${\displaystyle x_{k}}$ ${\displaystyle \lambda }$ ${\displaystyle H}$ ${\displaystyle x_{k}}$ ${\displaystyle W_{k}}$

Calculating the stride length ${\displaystyle \alpha _{k}}$

If you have a search direction , you have to calculate the maximum stride length . A full step length with leads directly to the minimum in the subspace defined by . However, the stride length is often limited by a constraint . ${\displaystyle p_{k}}$ ${\displaystyle \alpha _{k}}$ ${\displaystyle \alpha _{k}=1}$ ${\displaystyle W_{k}}$ ${\displaystyle i\notin W_{k}}$

All secondary conditions in with are also fulfilled for all at the point , since then the inequality ${\displaystyle i\notin W_{k}}$ ${\displaystyle a_{i}^{T}p_{k}\geq 0}$ ${\displaystyle x_{k}+\alpha _{k}p_{k}}$ ${\displaystyle \alpha _{k}\geq 0}$

${\displaystyle a_{i}^{T}(x_{k}+\alpha _{k}p_{k})=a_{i}^{T}x_{k}+\alpha _{k}a_{i}^{T}p_{k}\geq a_{i}^{T}x_{k}\geq b_{i}}$

applies. All constraints with are only met at the new point if the inequality for these constraints ${\displaystyle i\notin W_{k}}$ ${\displaystyle a_{i}^{T}p_{k}<0}$

${\displaystyle a_{i}^{T}x_{k}+\alpha _{k}a_{i}^{T}p_{k}\geq b_{i}}$

applies. This is equivalent to the condition

${\displaystyle \alpha _{k}\leq {\frac {b_{i}-a_{i}^{T}x_{k}}{a_{i}^{T}p_{k}}}\qquad \forall \{i\notin W_{k}|a_{i}^{T}p_{k}<0\}}$

In order to get as close as possible to the optimum in the current subspace, the maximum step length can be calculated using this formula:

${\displaystyle \alpha _{k}=\min(1,\min _{i\notin W_{k},a_{i}^{T}p_{k}<0}{\frac {b_{i}-a_{i}^{T}x_{k}}{a_{i}^{T}p_{k}}})}$

The constraint that limits this length is included in the set because this constraint is now active. ${\displaystyle W_{k+1}}$

literature

• Jorge Nocedal , Stephen J. Wright: Numerical Optimization. Second edition. Springer, New York 2006, ISBN 978-0387-30303-1 , Chapter 16.5.
• Roger Fletcher : Practical methods of optimization. Second edition. John Wiley & Sons, 1987, ISBN 978-0-471-49463-8 , chapter 10.3.

Individual evidence

1. ↑ Jorge Nocedal , Stephen J. Wright: Numerical Optimization. Second edition. Springer, New York 2006, ISBN 978-0387-30303-1 , p. 449.
2. ↑ Jorge Nocedal , Stephen J. Wright: Numerical Optimization. Second edition. Springer, New York 2006, ISBN 978-0387-30303-1 , p. 472.
3. ↑ Jorge Nocedal , Stephen J. Wright: Numerical Optimization. Second edition. Springer, New York 2006, ISBN 978-0387-30303-1 , p. 468.
4. ^ Roger Fletcher : Stable reduced Hessian updates for indefinite quadratic programming. Mathematical Programming (87.2) 2000, pp. 251-264.
5. ↑ Jorge Nocedal , Stephen J. Wright: Numerical Optimization. Second edition. Springer, New York 2006, ISBN 978-0387-30303-1 , pp. 469f.
6. ↑ Jorge Nocedal , Stephen J. Wright: Numerical Optimization. Second edition. Springer, New York 2006, ISBN 978-0387-30303-1 , pp. 468f.