Misplaced Pages

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. 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. 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:

• 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.\,}$

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.

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.

• Convex optimization