Complementarity condition

The complementarity condition , also complementary slip called (English complementary slackness ) is a statement of the mathematical optimization , the developed relationships between the optimum points of two optimization problems that dual to each other with respect to the Lagrangian duality are. The complementarity condition is a necessary optimality criterion and is used for inner point methods and the Karush-Kuhn-Tucker conditions .

statement

General case

Problem

Two optimization problems are given as in the following table:

Primal problem	Dual problem
${\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g_{i}(x)\leq 0&i=1,\dotsc ,p\\&h_{j}(x)=0&j=1,\dotsc ,q\\&x\in X&\end{aligned}}}$	${\displaystyle {\begin{aligned}{\text{Maximiere }}&q(\lambda ,\mu )&\\{\text{unter den Nebenbedingungen }}&\lambda _{i}\geq 0&i=1,\dotsc ,p\end{aligned}}}$

It is

${\displaystyle q(\lambda ,\mu )=\inf _{x\in X}\left(f(x)+\sum _{i=1}^{p}\lambda _{i}g_{i}(x)+\sum _{j=1}^{q}\mu _{j}h_{j}(x)\right)}$

the dual function and ${\displaystyle f,g_{i},h_{j}:\mathbb {R} ^{n}\mapsto \mathbb {R} }$

statement

The complementarity condition is now

${\displaystyle \lambda _{i}^{*}g_{i}(x^{*})=0{\text{ für alle }}i=1,\dotsc ,p}$

for permissible . An alternative formulation in vector notation with and is ${\displaystyle x^{*},\lambda ^{*}}$ ${\displaystyle g(x)=(g_{1}(x),\dots ,g_{p}(x))^{T}}$ ${\displaystyle \lambda =(\lambda _{1},\dots ,\lambda _{p})^{T}}$

${\displaystyle (\lambda ^{*})^{T}g(x^{*})=0}$.

If the -th Lagrange multiplier (the -th inequality restriction) is not equal to zero, the -th inequality restriction (the -th Lagrange multiplier) must therefore be equal to zero: ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$

${\displaystyle {\begin{aligned}\lambda _{i}^{*}>0\implies g_{i}(x^{*})=0\\g_{i}(x^{*})<0\implies \lambda _{i}^{*}=0\end{aligned}}}$.

So at least one of the two factors must always be zero. This follows from the fact that and applies because both are dual or primal. ${\displaystyle \lambda _{i}^{*}\geq 0}$ ${\displaystyle g_{i}(x^{*})\leq 0}$

validity

Applies the strong duality (d. E. Are the optimum value of the primal and the dual problem the same), the optimum value is in and accepted, and it is finite, so the complementarity condition applies. ${\displaystyle x^{*}}$ ${\displaystyle (\lambda ^{*},\mu ^{*})}$

Alternatively, the KKT conditions also contain the formulation that if is optimal for the primal problem, is finite and certain regularity conditions (also called constraint qualifications ) exist , so that the complementarity condition applies. The regularity conditions guarantee the strong duality (mostly only in the point ) and thus enable the primal optimal solution to be supplemented by the dual optimal solution. ${\displaystyle x^{*}}$ ${\displaystyle f(x^{*})}$ ${\displaystyle \lambda _{i}^{*}\geq 0}$ ${\displaystyle x^{*},\lambda ^{*}}$ ${\displaystyle x^{*}}$

For linear programs

Problem

If the optimization problems are linear programs , the primal and the dual problem take on a special form and the complementary slack is simplified.

Primal problem	Dual problem
${\displaystyle {\begin{aligned}{\text{Minimiere }}&c^{T}x&\\{\text{unter den Nebenbedingungen }}&Ax=b\\&x\geq 0\end{aligned}}}$	${\displaystyle {\begin{aligned}{\text{Maximiere }}&b^{T}y&\\{\text{unter den Nebenbedingungen }}&A^{T}y\leq c\end{aligned}}}$

There is and . ${\displaystyle x,c\in \mathbb {R} ^{n}\,,\,b,y\in \mathbb {R} ^{m}}$ ${\displaystyle A\in \mathbb {R} ^{m\times n}}$

statement

Denote the i-th component of the vector . Then the complementarity condition for admissible is ${\displaystyle [x]_{i}}$ ${\displaystyle x}$ ${\displaystyle x^{*},y^{*}}$

${\displaystyle (x^{*})^{T}(A^{T}y^{*}-c)=0{\text{ bzw. }}[x^{*}]_{i}\cdot [A^{T}y^{*}-c]_{i}=0}$.

So follows

${\displaystyle {\begin{aligned}\left[x^{*}\right]_{i}>0\implies \left[A^{T}y^{*}\right]_{i}=\left[c\right]_{i}\\\left[A^{T}y^{*}-c\right]_{i}<0\implies \left[x^{*}\right]_{i}=0\end{aligned}}}$.

If the dual problem is formulated with a slack variable , then the constraints are ${\displaystyle s\in \mathbb {R} ^{n}}$

${\displaystyle A^{T}y+s=c\,,\,s\geq 0,}$

this is the complementarity condition

${\displaystyle (x^{*})^{T}s^{*}=0{\text{ bzw. }}[x^{*}]_{i}\cdot [s]_{i}=0}$

and

${\displaystyle {\begin{aligned}\left[x^{*}\right]_{i}>0\implies \left[s^{*}\right]_{i}=0\\\left[s^{*}\right]_{i}>0\implies \left[x^{*}\right]_{i}=0\end{aligned}}}$.

This explains the naming as complementary slack: Either the slack variable is zero or the primal variable is zero.

validity

The formulation of the complementarity condition is based on the fact that strong duality holds for linear programs and the optimal value is finite if and only if both the primal and the dual problem have a feasible point.

The formulation is therefore that if the primal and the dual problem have admissible solutions, admissible solutions (or depending on the formulation ) exist that satisfy the complementarity condition. They are then optimal solutions to the primal and dual problem. ${\displaystyle x^{*},y^{*}}$ ${\displaystyle s^{*}}$ ${\displaystyle x^{*},y^{*}}$

Conversely, every finite primal-dual optimal pair fulfills the complementarity condition. ${\displaystyle x^{*},y^{*}}$

example

We consider the primal linear program

${\displaystyle {\begin{aligned}{\text{Minimiere }}&(-1,0,0)x\\{\text{unter den Nebenbedingungen }}&(1,1,1)x=1\\&x\geq 0\end{aligned}}}$

and the associated dual program

${\displaystyle {\begin{aligned}{\text{Maximiere }}&y_{1}\\{\text{unter den Nebenbedingungen }}&{\begin{pmatrix}1\\1\\1\end{pmatrix}}y\leq {\begin{pmatrix}-1\\0\\0\end{pmatrix}}\end{aligned}}}$

Both problems have an allowable point, so strong duality applies. The optimal dual objective function value is . From the strong duality one deduces that is. The complementary slip now delivers ${\displaystyle y_{1}=-1}$ ${\displaystyle c^{T}x=b^{T}y}$ ${\displaystyle x_{1}=1}$

${\displaystyle {\begin{aligned}x_{2}\cdot (y_{1}-0)=0\\x_{3}\cdot (y_{1}-0)=0\end{aligned}}}$

and with it . Thus, the complementary slip provides the complete primal optimum point here. Conversely, given primal and dual points, one can also check whether these are optimal points: If they are optimal, they must satisfy the complementary slack. ${\displaystyle x_{2}=x_{3}=0}$

Derivation

Be primal optimal and dual optimal. Then and , since the optimal points are allowable. So is . Because of the strong duality is ${\displaystyle x^{*}}$ ${\displaystyle (\lambda ^{*},\mu ^{*})}$ ${\displaystyle g_{i}(x^{*})\leq 0}$ ${\displaystyle \lambda _{i}^{*}\geq 0}$ ${\displaystyle \lambda ^{*}g_{i}(x^{*})\leq 0}$

${\displaystyle {\begin{aligned}f(x^{*})=q(\lambda ^{*},\mu ^{*})=\inf _{x\in X}\left(f(x)+\sum _{i=1}^{p}\lambda _{i}^{*}g_{i}(x)+\sum _{j=1}^{q}\mu _{j}^{*}h_{j}(x)\right)\\\leq f(x^{*})+\sum _{i=1}^{p}\underbrace {\lambda _{i}^{*}g_{i}(x^{*})} _{\leq 0}+\sum _{j=1}^{q}\underbrace {\mu _{j}^{*}h_{j}(x^{*})} _{=0}\leq f(x^{*})\end{aligned}}}$

The first curly bracket follows from the identity shown above, the second from the fact that da is permissible. If now is finite, then equality holds in the inequality and it follows ${\displaystyle h_{j}(x^{*})=0}$ ${\displaystyle x^{*}}$ ${\displaystyle f(x^{*})}$

${\displaystyle \sum _{i=1}^{p}\lambda _{i}^{*}g_{i}(x^{*})=0}$,

which implies the claim that each of the summands is less than or equal to zero.

Generalizations

The complementary slip can also be formulated more generally for mappings between complete real vector spaces that are provided with a scalar product and on which a generalized inequality or an order cone is defined. The functions map into the vector space provided with the scalar product , and the functions map into the vector space provided with the scalar product . The primal and dual problems are then ${\displaystyle \preccurlyeq _{K}}$ ${\displaystyle g_{i}}$ ${\displaystyle V_{i}}$ ${\displaystyle \langle \cdot ;\cdot \rangle _{i}}$ ${\displaystyle h_{j}}$ ${\displaystyle V_{j}}$ ${\displaystyle \langle \cdot ;\cdot \rangle _{j}}$

Primal problem	Dual problem
${\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g_{i}(x)\preccurlyeq _{K_{i}}0&i=1,\dotsc ,p\\&h_{j}(x)=0&j=1,\dotsc ,q\\&x\in X&\end{aligned}}}$	${\displaystyle {\begin{aligned}{\text{Maximiere }}&q(\lambda ,\mu )&\\{\text{unter den Nebenbedingungen }}&\lambda _{i}\succcurlyeq _{K_{i}^{*}}0&i=1,\dotsc ,p\end{aligned}}}$.

It is

${\displaystyle q(\lambda ,\mu )=\inf _{x\in X}\left(f(x)+\sum _{i=1}^{p}\langle \lambda ;g(x)\rangle _{i}+\sum _{j=1}^{q}\langle \mu _{j};h_{j}(x)\rangle _{j}\right)}$

the dual function and the dual cone too . ${\displaystyle K^{*}}$ ${\displaystyle K}$

If strong duality applies and if the points are as well as optimal and if the objective function value is finite, then applies ${\displaystyle x^{*}}$ ${\displaystyle (\lambda ^{*},\mu ^{*})}$

${\displaystyle \langle \lambda _{i}^{*};g_{i}(x^{*})\rangle _{i}=0{\text{ für }}i=1,\dots ,p}$.

It follows

${\displaystyle {\begin{aligned}\lambda _{i}^{*}>_{K_{i}^{*}}0&\implies g_{i}(x^{*})=0\\g_{i}(x^{*})<_{K_{i}}0&\implies \lambda _{i}^{*}=0\end{aligned}}}$

The derivation for this general case is largely analogous to the procedure above, making use of the fact that if is, it follows that . ${\displaystyle a\preccurlyeq _{K}0,b\succcurlyeq _{K^{*}}0}$ ${\displaystyle \langle a;b\rangle \leq 0}$

If the problem is formulated with cones of order, so the inequality restrictions are of the form or , the same applies as above ${\displaystyle g_{i}(x)\in -K_{i}}$ ${\displaystyle \lambda \in K_{i}^{*}}$

${\displaystyle \langle \lambda _{i}^{*};g_{i}(x^{*})\rangle _{i}=0{\text{ für }}i=1,\dots ,p}$.

The statement

${\displaystyle \lambda _{i}^{*}\in \operatorname {int} (K_{i}^{*})\implies g_{i}(x^{*})=0}$

but only applies if the cone has a non-empty interior. Applies analogously ${\displaystyle K_{i}^{*}}$

${\displaystyle g_{i}(x^{*})\in \operatorname {int} (-K_{i})\implies \lambda _{i}^{*}=0}$

only when the inside of is not empty. ${\displaystyle K_{i}}$

literature

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