Quadratic optimization

The quadratic optimization or quadratic programming and the closely related concept of the quadratic program with quadratic restrictions is a special problem in the mathematical optimization , which is characterized by the simplicity of the occurring functions. Quadratic programs occur, for example, when minimizing distance functions or as sub-problems of more complex optimization problems.

definition

Let there be real - matrices , a symmetric matrix , as well as real vectors and finally a real number. ${\displaystyle E;G\in \mathbb {R} ^{m\times n}}$ ${\displaystyle m\times n}$ ${\displaystyle Q\in \mathbb {R} ^{n\times n}}$ ${\displaystyle c;x\in \mathbb {R} ^{n}}$ ${\displaystyle f;h\in \mathbb {R} ^{m}}$ ${\displaystyle d\in \mathbb {R} }$

A shape optimization problem

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)={\tfrac {1}{2}}x^{T}Qx+c^{T}x+d\\{\text{unter den Nebenbedingungen }}&Ex\leq f\\&Gx=h\end{aligned}}}$

is a quadratic optimization problem or a quadratic program (English quadratic program , briefly QP ).

Is the problem of the form

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)={\tfrac {1}{2}}x^{T}Qx+c^{T}x+d&\\{\text{unter den Nebenbedingungen }}&{\tfrac {1}{2}}x^{T}P_{i}x+r_{i}^{T}x+f_{i}\leq 0&i=1,\dots ,m\\&Gx=h&\end{aligned}}}$

for symmetric matrices and series of vectors , it is called a quadratic program with quadratic constraints (English quadratically constrained quadratic program , QCQP for short ). ${\displaystyle (P_{i})_{1\leq i\leq m}}$ ${\displaystyle (r_{i})_{i};(f_{i})_{i}}$

Special cases

• Every linear optimization problem is a quadratic optimization problem. Add to it . ${\displaystyle Q=0}$
• Every quadratic optimization problem is a quadratic program with quadratic constraints. To do this, you set and arrange the vectors line by line to form the matrix . ${\displaystyle P_{i}=0}$ ${\displaystyle r_{i}}$ ${\displaystyle E}$
• If all occurring matrices are positive semidefinite , then quadratic programs and quadratic programs with quadratic constraints are convex optimization problems . ${\displaystyle Q,P_{i}}$
• Under certain circumstances, a SOCP can also be formulated as a quadratic program with quadratic constraints.

example

As an example, consider the problem

${\displaystyle {\begin{aligned}\min \ &\left\Vert x-(-1,-1)^{T}\right\Vert _{2}^{2}&\\{\text{u. d. N. }}&{\tfrac {x_{1}^{2}}{4}}+x_{2}^{2}-1\leq 0&\\&x_{1}-x_{2}\geq -1&\end{aligned}}}$

A paraphrase of the quadratic terms provides the representation given in the definition with matrix-vector products:

${\displaystyle {\begin{aligned}\min \ &{\tfrac {1}{2}}x^{T}{\bigl (}{\begin{smallmatrix}2&0\\0&2\end{smallmatrix}}{\bigr )}x+(2,2)x+2&\\{\text{u. d. N. }}&{\tfrac {1}{2}}x^{T}{\bigl (}{\begin{smallmatrix}0{,}5&0\\0&2\end{smallmatrix}}{\bigr )}x-1\leq 0&\\&(-1,1)x-1\leq 0&\end{aligned}}}$.

So it is a quadratic program with quadratic constraints. In particular, it is a convex optimization problem because all matrices that occur are positive definite.

Optimality criteria

General case

For any input parameter there is the necessary optimality criterion that if there is a local minimum of a QP or QCQP, then exist such that there is a Fritz-John point and is not equal to the zero vector. If additional certain regularity requirements such as the LICQ , the MFCQ or the Abadie CQ are met, then there is , so that a Karush-Kuhn-Tucker point is. ${\displaystyle x^{*}}$ ${\displaystyle \mu ^{*},\lambda ^{*},z^{*}}$ ${\displaystyle (z^{*},x^{*},\mu ^{*},\lambda ^{*})}$ ${\displaystyle (z^{*},\mu ^{*},\lambda ^{*})}$ ${\displaystyle x^{*}}$ ${\displaystyle \mu ^{*},\lambda ^{*}}$ ${\displaystyle (x^{*},\mu ^{*},\lambda ^{*})}$

For convex problems

If the matrices are all positive semidefinite , the problem is convex. As a regularity condition for the Karush-Kuhn-Tucker conditions, the Slater condition is also available, which supplies the regularity of all admissible points. Furthermore, every local minimum is a global minimum. In addition, each Karush-Kuhn-Tucker point is a global minimum without further regularity requirements and thus a sufficient criterion for optimality . ${\displaystyle Q,P_{i}}$

Quadratic programs with equation restrictions

Looking at the Quadratic Program, which only contains equation restrictions

${\displaystyle {\begin{aligned}\min \ &\,{\tfrac {1}{2}}x^{T}Qx+c^{T}x+d\\{\text{u.d.N. }}&\,Gx=h,\end{aligned}}}$

so every KKT point of the above problem is a solution of the linear system of equations ${\displaystyle (x^{*},\mu ^{*})}$

${\displaystyle {\begin{bmatrix}Q&G^{T}\\G&0\end{bmatrix}}{\begin{bmatrix}x\\\lambda \end{bmatrix}}={\begin{bmatrix}-\ c\\h\end{bmatrix}}}$.

If positive is semidefinite, the solution of the system of equations is a global optimal solution of the optimization problem due to the convexity of the problem. Linear systems of equations of the above form are also called saddle point problems , since they can be understood as the determination of the saddle point of the Lagrange function . ${\displaystyle Q}$

Applications

Typical applications are:

• Least squares method with or without constraints on the parameters to be determined.
• Determining the minimum distance between two sets that are polyhedra (and thus create linear inequality restrictions) or intersections of ellipsoids (and thus create quadratic inequality restrictions).
• As a sub-problem for solving a larger optimization problem, for example using the SQP method (Sequential Quadratic Programming)

Solution methods

The solution methods used are:

• Gradient method
• Inner point method
• Active set methods such as the primal dual active set algorithm .
• If the KKT conditions lead to a linear complementarity problem , then specialized algorithms such as Lemke's algorithm or Unique Sink Orientations are available.

literature

• C. Geiger, C. Kanzow: Theory and numerics of restricted optimization tasks . Springer, 2002, ISBN 3-540-42790-2 ( limited preview in Google book search).
• Stephen Boyd, Lieven Vandenberghe: Convex Optimization. Cambridge University Press, 2004, ISBN 978-0-521-83378-3 ( online ).