Girish Mahajan (Editor)

Slater's condition

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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

Contents

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.

Details

Given the problem

Minimize  f 0 ( x ) subject to:    f i ( x ) ≤ 0 , i = 1 , … , m A x = b

with f 0 , … , f m convex (and therefore a convex optimization problem). Then Slater's condition implies that strong duality holds if there exists an x ∗ ∈ relint ⁡ ( D ) (where relint is the relative interior and D = ∩ i = 0 m dom ⁡ ( f i ) ) such that

f i ( x ∗ ) < 0 , i = 1 , … , m and A x ∗ = b .

If the first k constraints, f 1 , … , f k are linear functions, then strong duality holds if there exists an x ∗ ∈ relint ⁡ ( D ) such that

f i ( x ∗ ) ≤ 0 , i = 1 , … , k , f i ( x ∗ ) < 0 , i = k + 1 , … , m , and A x ∗ = b .

Generalized Inequalities

Given the problem

Minimize  f 0 ( x ) subject to:    f i ( x ) ≤ K i 0 , i = 1 , … , m A x = b

where f 0 is convex and f i is K i -convex for each i . Then Slater's condition says that if there exists an x ∗ ∈ relint ⁡ ( D ) such that

f i ( x ∗ ) < K i 0 , i = 1 , … , m and A x ∗ = b

then strong duality holds.

References

Slater's condition Wikipedia
(Text) CC BY-SA