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 zero, and if the dual value is finite then it is attained.
Let f 1 , … , f m {\displaystyle f_{1},\ldots ,f_{m}} be real-valued functions on some subset D {\displaystyle D} of R n {\displaystyle \mathbb {R} ^{n}} . We say that the functions satisfy the Slater condition if there exists some x {\displaystyle x} in the relative interior of D {\displaystyle D} , for which f i ( x ) < 0 {\displaystyle f_{i}(x)<0} for all i {\displaystyle i} in 1 , … , m {\displaystyle 1,\ldots ,m} . We say that the functions satisfy the relaxed Slater condition if:
Some k {\displaystyle k} functions (say f 1 , … , f k {\displaystyle f_{1},\ldots ,f_{k}} ) are affine;
There exists x ∈ relint ⁡ D {\displaystyle x\in \operatorname {relint} D} such that f i ( x ) ≤ 0 {\displaystyle f_{i}(x)\leq 0} for all i = 1 , … , k {\displaystyle i=1,\ldots ,k} , and f i ( x ) < 0 {\displaystyle f_{i}(x)<0} for all i = k + 1 , … , m {\displaystyle i=k+1,\ldots ,m} .
Consider the optimization problem
where f 0 , … , f m {\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 x ∗ {\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 x ∗ ∈ relint ⁡ ( D ) {\displaystyle x^{*}\in \operatorname {relint} (D)} (where relint denotes the relative interior of the convex set D := ∩ i = 0 m dom ⁡ ( f i ) {\displaystyle D:=\cap _{i=0}^{m}\operatorname {dom} (f_{i})} ) such that
Given the problem
where f 0 {\displaystyle f_{0}} is convex and f i {\displaystyle f_{i}} is K i {\displaystyle K_{i}} -convex for each i {\displaystyle i} . Then Slater's condition says that if there exists an x ∗ ∈ relint ⁡ ( D ) {\displaystyle x^{*}\in \operatorname {relint} (D)} such that
then strong duality holds.
Duality
Karush–Kuhn–Tucker conditions
Lagrange multiplier
