Slater condition

The Slater condition or Slater constraint qualification or Slater CQ for short is an important prerequisite for the necessary optimality criteria to apply in convex optimization . The Slater condition is a condition on the regularity of the problem posed. If the Slater condition is fulfilled and a point is a local minimum , then the Karush-Kuhn-Tucker conditions are also fulfilled at this point. Thus the Slater condition is an important prerequisite for checking whether a given point is an optimum. ${\displaystyle {\tilde {x}}}$

In addition, the Slater condition is used in the Lagrange duality as a prerequisite for strong duality .

It is named after Morton L. Slater (1921-2002), a mathematician at Sandia National Laboratories .

definition

Strong version

Given a convex optimization problem of the shape

${\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g_{i}(x)\leq 0&i=1,\dots ,k\\&l_{j}(x)=a_{j}^{T}x-b_{j}\leq 0&j=1,\dots ,l\\&h_{k}(x)=a_{k}^{T}x-b_{k}=0&k=1,\dots ,m\end{aligned}}}$

with convex objective function , convex and non- affine inequality restrictions as well as affine inequality and equation restriction functions and . Let the domain of the problem be the largest convex set on which all and are well-defined and convex. The problem satisfies Slater's condition if there is at least one relatively internal point of such that ${\displaystyle f}$ ${\displaystyle g_{i}(x)}$ ${\displaystyle l_{j}(x)}$ ${\displaystyle h_{k}(x)}$ ${\displaystyle D\subset \mathbb {R} ^{n}}$ ${\displaystyle g_{i}(x)}$ ${\displaystyle f}$ ${\displaystyle {\tilde {x}}}$ ${\displaystyle D}$

• all convex inequality constraints are strictly fulfilled: ${\displaystyle g_{i}({\tilde {x}})<0}$
• all affine inequality and equation constraints are satisfied: and . ${\displaystyle l_{j}({\tilde {x}})\leq 0}$ ${\displaystyle h_{k}({\tilde {x}})=0}$

Weak variant

Occasionally there is also the weaker variant that all inequality constraints must be strictly met for at least one relatively internal point : and the equation restrictions must be met. This case is included in the above case, but is often found in the literature because it is easier to show. However, it does not cover all cases of strong duality in linear programs, for example. ${\displaystyle {\tilde {x}}}$ ${\displaystyle g_{i}({\tilde {x}})<0,l_{j}({\tilde {x}})<0}$

For generalized inequalities

If one uses generalized inequalities and K-convex functions and thus obtains restrictions such as

${\displaystyle g_{i}(x)\preccurlyeq _{K_{i}}0}$,

so one replaces the really smaller with the strictly generalized inequality . Thus, for convex problems with generalized inequalities, the Slater condition applies if there is a relatively inner point such that all equation restrictions in are satisfied and for all inequality restrictions is that . ${\displaystyle \prec _{K_{i}}}$ ${\displaystyle {\tilde {x}}}$ ${\displaystyle {\tilde {x}}}$ ${\displaystyle g_{i}({\tilde {x}})\prec _{K_{i}}0}$

For almost convex functions

Is a form optimization problem

${\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)\\{\text{unter den Nebenbedingungen }}&g(x)\in -K\\&x\in R\end{aligned}}}$

given for a trim cone with non-blank heart and figures and . Thereby normalized real vector spaces are defined and the function is defined by is almost convex with respect to the cone . be an arbitrary non-empty subset of . ${\displaystyle K}$ ${\displaystyle f:V\mapsto \mathbb {R} }$ ${\displaystyle g:V\mapsto Y}$ ${\displaystyle V,Y}$ ${\displaystyle K:V\mapsto \mathbb {R} \times Y}$ ${\displaystyle K(x)=(f(x),g(x))}$ ${\displaystyle \mathbb {R} _{+}\times K}$ ${\displaystyle R}$ ${\displaystyle V}$

Then the problem satisfies Slater's condition if there is a feasible point (i.e. ) such that is. Here is the inside of the crowd . This formulation contains both the case with generalized inequalities (then is a real cone ) and the weak variant. ${\displaystyle {\tilde {x}}}$ ${\displaystyle {\tilde {x}}\in R,\,g({\tilde {x}})\in -K}$ ${\displaystyle g({\tilde {x}})\in \operatorname {int} (-K)}$ ${\displaystyle \operatorname {int} (M)}$ ${\displaystyle M}$ ${\displaystyle K}$

example

As an example, consider the functions and . The set is the restriction set of a convex problem. Assume that the objective function has the entire domain as its domain . Then a strictly admissible point has to be found regarding which is admissible regarding . The point fulfills this requirement, so the problem fulfills the Slater condition. ${\displaystyle g_{1}(x)=(x_{1}/2)^{2}+x_{2}^{2}-1,\,g_{2}(x)=x_{1}^{2}+(x_{2}/2)^{2}-1}$ ${\displaystyle l_{1}(x)=x_{1}-x_{2}}$ ${\displaystyle \{x\in \mathbb {R} ^{2}\,|\,g_{1}(x)\leq 0,g_{2}(x)\leq 0,l_{1}(x)\leq 0\}}$ ${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle D=\mathbb {R} ^{2}}$ ${\displaystyle g_{1},g_{2}}$ ${\displaystyle l_{1}}$ ${\displaystyle (-0.5,-0.5)}$

Relationship to other constraint qualifications

The Slater condition implies the Abadie CQ , but the reverse is not true. The main difference to other constraint qualifications is that the Slater condition is a condition on the problem posed and not, as with other CQ, on a certain point. This makes the Slater condition easier to check and gives the regularity of all feasible points of the problem. Its use is limited by the fact that it only applies to convex problems.

literature

• Florian Jarre, Josef Stoer: Optimization. Springer, Berlin 2004, ISBN 3-540-43575-1 .
• C. Geiger, C. Kanzow: Theory and numerics of restricted optimization tasks . Springer, 2002. ISBN 3-540-42790-2 . http://books.google.de/books?id=spmzFyso_b8C

Web links

• Book Convex Optimization by Stephen Boyd and Lieven Vandenberghe (PDF )

Individual evidence

1. ^ Slater, Lagrange Multipliers Revisited (Report), Cowles Commission Discussion Paper No. 403, 1950