Slater's condition explained

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

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

• Some

k functions (say f _{1,\ldots,f} _{k} ) are affine;

• There exists

x \in \operatorname{relint} D such that f _{i(x)} \le 0 for all i =1 ,\ldots,k , and f _{i(x)} < 0 for all i = k +1 ,\ldots,m .

Application to convex optimization

Consider the optimization problem

Minimize f _{0(x)} subjectto: f _{i(x)} \le 0 , i = 1 ,\ldots,m Ax = b where 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 ^{*} 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 ^{*} \in \operatorname{relint}(D) (where relint denotes the relative interior of the convex setD : = \cap ^{m} _{i =0} \operatorname{dom}(f _{i)} ) such thatf ^{*)} _{i(x} < 0 , i = 1 ,\ldots,m, (the convex, nonlinear constraints)Ax ^{*} = b. ^[4]

Generalized Inequalities

Given the problem

Minimize f _{0(x)} subjectto: f _{i(x)} \le _{K _{i}} 0 , i = 1 ,\ldots,m Ax = 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 ^{*} \in \operatorname{relint}(D) such thatf ^{*)} _{i(x} < _{K _{i}} 0 , i = 1 ,\ldots,m andAx ^{*} = b then strong duality holds.

See also

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

Notes and References

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