Conical program

A conical program is a specific problem in mathematical optimization where a cone is also used in the formulation of the permissible points , which is what led to this naming. Some problem classes can be formulated as conical programs.

definition

Abstract definition

Let a real vector space be given with a scalar product and a closed, pointed and convex cone with a non-empty interior. Furthermore, let and be a linear subspace of . Then the optimization problem is called ${\displaystyle V_{1}}$ ${\displaystyle \langle {\cdot },{\cdot }\rangle _{1}}$ ${\displaystyle K}$ ${\displaystyle B,C\in V_{1}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle V_{1}}$

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{1}\\{\text{unter den Nebenbedingungen }}&X\in {\mathcal {K}}\\&X\in {\mathcal {L}}+B\end{aligned}}}$

a conical program or conical optimization problem. We are looking for an element of a vector space that lies both in a cone and in an affine subspace and is minimal with respect to the scalar product.

Convex definition

Analogous to the linear programs, conical programs can also be specified in a standard form and an inequality form. To do this, one considers the generalized inequality induced by the cone and another vector space with a scalar product ${\displaystyle \preccurlyeq _{K}}$ ${\displaystyle V_{2}}$ ${\displaystyle \langle {\cdot },{\cdot }\rangle _{2}}$

Standard shape

A conical program in standard form (or normal form) can now be defined as follows: can also be written as. If one considers a linear function , the linear subspace can be described by this function. Thus the following definition of a conical program can be given: ${\displaystyle X\in {\mathcal {K}}}$ ${\displaystyle X\succcurlyeq _{K}0}$ ${\displaystyle L:V_{1}\mapsto V_{2}}$ ${\displaystyle {\mathcal {L}}}$

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{1}\\{\text{unter den Nebenbedingungen }}&-X\preccurlyeq _{K}0_{V_{1}}\\&L(X)-b=0_{V_{2}}\end{aligned}}}$.

Here is and . ${\displaystyle X,C\in V_{1}}$ ${\displaystyle b\in V_{2}}$

In particular, all functions that occur are either linear or K-convex , so it is a more general convex optimization problem .

Inequality form

Alternatively, the linear subspace can also be understood as an image of a linear function . This then leads to the problem ${\displaystyle {\mathcal {L}}}$ ${\displaystyle L^{*}:V_{2}\mapsto V_{1}}$

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)=\langle {c},{x}\rangle _{2}\\{\text{unter den Nebenbedingungen }}&L^{*}(x)-B\preccurlyeq _{K}0_{V_{1}}\end{aligned}}}$,

a conical problem in inequality form. Here is and . ${\displaystyle x,c\in V_{2}}$ ${\displaystyle B\in V_{1}}$

Mixed forms

More generally, optimization problems with a linear objective function that contain a linear-affine equation constraint and a linear-affine inequality constraint with generalized inequality are referred to as conical optimization problems. This corresponds to a mixture of standard form / normal form and inequality form.

Examples

• Every linear optimization problem is a conical optimization problem. To do this select a vector space to and as a cone , the so-called positive orthant . The generalized inequality is then the "component-wise greater than". The standard scalar product is chosen as the scalar product and the solution set of the equation as the affine subspace . ${\displaystyle V_{1}}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle K:=\{x\in \mathbb {R} ^{n}\,|\,\forall i:x_{i}\geq 0\}}$ ${\displaystyle Ax=b}$
• Semidefinite programs are conical programs on the vector space of the symmetrical matrices provided with the Frobenius scalar product . The cone is the set of positive semidefinite matrices , the affine space is also defined by the Frobenius scalar product. ${\displaystyle S^{n}}$ ${\displaystyle S_{+}^{n}}$
• The SOCPs ( Second Order Cone Program ) use the second-order cone, which is also called the Lorentz cone .

duality

Duality of conical programs

Looking at the problem

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{1}\\{\text{unter den Nebenbedingungen }}&X\succcurlyeq _{K}0\\&X\in {\mathcal {L}}+B\end{aligned}}}$

as a primary problem, that's the name of the problem

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(Y)=\langle {B},{Y}\rangle _{1}\\{\text{unter den Nebenbedingungen }}&Y\succcurlyeq _{K^{D}}0\\&Y\in {\mathcal {L}}^{\perp }+C\end{aligned}}}$

the dual conical problem. Here is the dual cone of and the orthogonal space of . In particular, the dual program of the dual program is again the primal program. ${\displaystyle K^{D}}$ ${\displaystyle K}$ ${\displaystyle {\mathcal {L}}^{\perp }}$ ${\displaystyle {\mathcal {L}}}$

It then holds for every admissible point of the primal problem and every admissible point of the dual problem that ${\displaystyle X}$ ${\displaystyle Y}$

${\displaystyle \langle {C},{X}\rangle _{1}+\langle {B},{Y}\rangle _{1}\geq \langle {B},{C}\rangle _{1}}$

If the optimal value of the primal problem is finite and the Slater condition is fulfilled (see below), then the dual problem has an optimal solution and it is ${\displaystyle p^{*}}$ ${\displaystyle Y^{*}}$

${\displaystyle p^{*}+\langle {B},{Y^{*}}\rangle _{1}=\langle {B},{C}\rangle _{1}}$.

If both the primal and the dual problem satisfy the Slater condition, then there are optimal solutions with ${\displaystyle X^{*},Y^{*}}$

${\displaystyle \langle {C},{X^{*}}\rangle _{1}+\langle {B},{Y^{*}}\rangle _{1}=\langle {B},{C}\rangle _{1}}$.

Lagrange duality

Not to be confused with the above duality is the Lagrange duality , applied to the convex shape of a conical problem. Is a conical problem given by in normal form

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{1}\\{\text{unter den Nebenbedingungen }}&-X\preccurlyeq _{K}0_{V_{1}}\\&L(X)-b=0_{V_{2}}\end{aligned}}}$,

this is the Lagrange function

${\displaystyle L(X,\Lambda ,\mu )=\langle {C},{X}\rangle _{1}+\langle {-X},{\Lambda }\rangle _{1}+\langle {-L(X)+b},{\mu }\rangle _{2}}$.

If the operator to be adjoint , then follows with the linearity of the scalar product ${\displaystyle L^{*}}$ ${\displaystyle L}$

${\displaystyle L(X,\Lambda ,\mu )=\langle {C},{X}\rangle _{1}-\langle {X},{\Lambda }\rangle _{1}+\langle {b},{\mu }\rangle _{2}-\langle {X},{L^{*}(\mu )}\rangle _{1}}$.

This function is linear in , and since linear functions are unbounded if and only if they are constantly equal to zero, the objective function of the dual program is ${\displaystyle X}$

${\displaystyle q(\Lambda ,\mu )={\begin{cases}\langle {b},{\mu }\rangle _{2}&{\text{ falls }}C-\Lambda -L^{*}(\mu )=0\\-\infty &{\text{ sonst }}\end{cases}}}$

If you write this case distinction as a secondary condition in the dual problem and take it as a slack variable , then this is the dual problem ${\displaystyle \Lambda }$ ${\displaystyle -\Lambda \preccurlyeq _{K}0_{V_{1}}}$

${\displaystyle {\begin{aligned}{\text{maximiere }}&s(\mu )=\langle {b},{\mu }\rangle _{2}\\{\text{unter den Nebenbedingungen }}&L^{*}(\mu )-C\preccurlyeq _{K^{D}}0_{V_{1}}\end{aligned}}}$,

what is a conical program in inequality form. A minimization problem is obtained by reversing the sign of the objective function.

For a conical problem in inequality form

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)=\langle {c},{x}\rangle _{2}\\{\text{unter den Nebenbedingungen }}&L^{*}(x)-B\preccurlyeq _{K}0_{V_{1}}\end{aligned}}}$

is the Lagrange function

${\displaystyle L(x,\Lambda )=\langle {c},{x}\rangle _{2}+\langle {L(\Lambda )},{x}\rangle _{2}-\langle {\Lambda },{B}\rangle _{1}}$

and with an analogous approach to the above is the dual problem

${\displaystyle {\begin{aligned}{\text{Maximiere }}&s(\Lambda )=-\langle {\Lambda },{B}\rangle _{1}\\{\text{unter den Nebenbedingungen }}&-\Lambda \preccurlyeq _{K^{D}}0_{V_{1}}\\&L(\Lambda )+c=0_{V_{2}}\end{aligned}}}$,

which again is a conical program in normal form. Dual problems of conical problems are always conical problems again. If you also form the dual problem of a dual problem, you get back to the original problem

If the Slater condition applies (see below), then strong duality applies , that is, the optimal values ​​of the primal and the dual problem match. A weaker result is that the objective function value of the dual problem is always smaller than the objective function value of the primal problem. This statement is also known as weak duality.

Connection of the concepts of duality

The two concepts of duality above are not identical, but they are very closely related. If, for example, one considers a linear subspace that is described by the solution of the linear equation , then the orthogonal space is described by the operator to be adjoint . The condition is therefore equivalent to for . So is ${\displaystyle {\mathcal {L}}}$ ${\displaystyle L(Y)=0}$ ${\displaystyle {\mathcal {L}}^{\perp }}$ ${\displaystyle L}$ ${\displaystyle L^{*}(y)}$ ${\displaystyle Y\in {\mathcal {L}}^{\perp }+C}$ ${\displaystyle Y=L^{*}(y)+C}$ ${\displaystyle y\in V_{2}}$

${\displaystyle \langle {B},{Y}\rangle _{1}=\langle {B},{L^{*}(y)+C}\rangle _{1}=\langle {b},{y}\rangle _{2}+\langle {B},{C}\rangle _{1}}$,

where is. Now you can optimize instead of using , the term can be ignored because it only affects the optimal value, but not the optimal point. The new objective function is now . If one understands as a slip variable with , then is equivalent to . Thus the dual abstract problem is a problem in inequality form and vice versa. ${\displaystyle L(B)=b}$ ${\displaystyle Y}$ ${\displaystyle y}$ ${\displaystyle \langle {B},{C}\rangle _{1}}$ ${\displaystyle \langle {b},{y}\rangle _{2}}$ ${\displaystyle Y}$ ${\displaystyle -Y\preccurlyeq _{K}}$ ${\displaystyle Y=L^{*}(y)+C}$ ${\displaystyle -L^{*}(y)\preccurlyeq _{K}C}$

Slater condition

The Slater condition for conical programs in the abstract form is

${\displaystyle ({\mathcal {L}}+B)\cap \operatorname {Int} ({\mathcal {K}})\neq \emptyset }$.

Here is the inner part of a crowd . So there must be at least one point that lies both in the interior of the cone and in the affine space . ${\displaystyle \operatorname {Int} }$ ${\displaystyle {\mathcal {L}}+B}$

For conical programs in the convex form, the Slater condition is satisfied if there is a point which satisfies the equation restriction and which is feasible with respect to the strict inequality induced by the cone (this corresponds to the requirement that the point inside the cone should lie). Such points are also called strictly allowable points. ${\displaystyle \prec _{K}}$

literature

• Florian Jarre, Josef Stoer: Optimization. Springer, Berlin 2004, ISBN 3-540-43575-1 .
• Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3 . ( online )