Slater's condition

Not to be confused with Slater determinant.

In mathematics, Slater's condition (or Slater condition) is a sufficient condition for strong duality to hold for a convex optimization problem, named after Morton L. Slater. ^[1] Informally, Slater's condition states that the feasible region must have an interior point (see technical details below).

Slater's condition is a specific example of a constraint qualification. ^[2] In particular, if Slater's condition holds for the primal problem, then the duality gap is 0, and if the dual value is finite then it is attained.

Formulation

Let ${\displaystyle f_{1},\ldots ,f_{m}}$ be real-valued functions on some subset ${\displaystyle D}$ of ${\displaystyle \mathbb {R} ^{n}}$. We say that the functions satisfy the Slater condition if there exists some ${\displaystyle x}$ in the relative interior of ${\displaystyle D}$, for which ${\displaystyle f_{i}(x)<0}$ for all ${\displaystyle i}$ in ${\displaystyle 1,\ldots ,m}$. We say that the functions satisfy the relaxed Slater condition if: ^[3]

• Some ${\displaystyle k}$ functions (say ${\displaystyle f_{1},\ldots ,f_{k}}$) are affine;
• There exists ${\displaystyle x\in \operatorname {relint} D}$ such that ${\displaystyle f_{i}(x)\leq 0}$ for all ${\displaystyle i=1,\ldots ,k}$, and ${\displaystyle f_{i}(x)<0}$ for all ${\displaystyle i=k+1,\ldots ,m}$.

Application to convex optimization

Consider the optimization problem

${\displaystyle {\text{Minimize }}\;f_{0}(x)}$

${\displaystyle {\text{subject to: }}\ }$

${\displaystyle f_{i}(x)\leq 0,i=1,\ldots ,m}$

${\displaystyle Ax=b}$

where ${\displaystyle f_{0},\ldots ,f_{m}}$ are convex functions. This is an instance of convex programming. Slater's condition for convex programming states that there exists an ${\displaystyle x^{*}}$ that is strictly feasible, that is, all m constraints are satisfied, and the nonlinear constraints are satisfied with strict inequalities.

If a convex program satisfies Slater's condition (or relaxed condition), and it is bounded from below, then strong duality holds. Mathematically, this states that strong duality holds if there exists an ${\displaystyle x^{*}\in \operatorname {relint} (D)}$ (where relint denotes the relative interior of the convex set ${\displaystyle D:=\cap _{i=0}^{m}\operatorname {dom} (f_{i})}$) such that

${\displaystyle f_{i}(x^{*})<0,i=1,\ldots ,m,}$ (the convex, nonlinear constraints)

${\displaystyle Ax^{*}=b.\,}$ ^[4]

Generalized Inequalities

Given the problem

${\displaystyle {\text{Minimize }}\;f_{0}(x)}$

${\displaystyle {\text{subject to: }}\ }$

${\displaystyle f_{i}(x)\leq _{K_{i}}0,i=1,\ldots ,m}$

${\displaystyle Ax=b}$

where ${\displaystyle f_{0}}$ is convex and ${\displaystyle f_{i}}$ is ${\displaystyle K_{i}}$-convex for each ${\displaystyle i}$. Then Slater's condition says that if there exists an ${\displaystyle x^{*}\in \operatorname {relint} (D)}$ such that

${\displaystyle f_{i}(x^{*})<_{K_{i}}0,i=1,\ldots ,m}$ and

${\displaystyle Ax^{*}=b}$

then strong duality holds. ^[4]

See also

• Duality
• Karush–Kuhn–Tucker conditions
• Lagrange multiplier

References

1. Slater, Morton (1950). Lagrange Multipliers Revisited (PDF). Cowles Commission Discussion Paper No. 403 (Report). Reprinted in Giorgi, Giorgio; Kjeldsen, Tinne Hoff, eds. (2014). Traces and Emergence of Nonlinear Programming. Basel: Birkhäuser. pp. 293–306. ISBN   978-3-0348-0438-7.
2. Takayama, Akira (1985). Mathematical Economics . New York: Cambridge University Press. pp.  66–76. ISBN   0-521-25707-7.
3. Nemirovsky and Ben-Tal (2023). "Optimization III: Convex Optimization" (PDF).
4. Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press. ISBN   978-0-521-83378-3 . Retrieved October 3, 2011.