Fact-checked by Grok 2 weeks ago

Slater's condition

Slater's condition is a constraint qualification in convex optimization, named after Morton L. Slater, that ensures strong duality holds between a convex primal optimization problem and its Lagrangian dual. Specifically, for a convex problem minimizing a convex objective subject to convex inequality and affine equality constraints, the condition requires the existence of a strictly feasible point—a point in the domain where all inequality constraints are strictly satisfied (i.e., f_i(x) < 0 for i = 1, \dots, m) and all equality constraints hold exactly (i.e., h_j(x) = 0 for j = 1, \dots, p).^[1] Introduced in 1950 in the context of Lagrange multipliers for nonlinear programming, Slater's condition provides a sufficient criterion to avoid duality gaps, guaranteeing that the primal optimal value equals the dual optimal value and that primal and dual optimal solutions exist under mild assumptions.^[2] This qualification is particularly valuable because it simplifies proofs of optimality and enables the use of dual methods in algorithms like interior-point methods and augmented Lagrangian approaches.^[1] A weaker variant applies when inequality constraints are affine, allowing non-strict satisfaction for those while maintaining the strict feasibility for nonlinear ones.^[1] In practice, Slater's condition is checked by verifying the nonempty relative interior of the feasible set, and its satisfaction is common in many real-world convex models, such as linear and semidefinite programming, where it underpins sensitivity analysis and error bounds.^[3] Violations can lead to positive duality gaps, as illustrated in counterexamples where the feasible set lacks interior points, highlighting the condition's role in ensuring reliable duality theory.^[1]

Background Concepts

Convex Sets and Functions

A convex set is a fundamental concept in convex analysis, defined as follows: a set C \subseteq \mathbb{R}^n is convex if, for any x, y \in C and \lambda \in [0, 1], the point \lambda x + (1 - \lambda) y also belongs to C. This property ensures that the line segment connecting any two points in the set lies entirely within the set. Convex sets form the building blocks for many optimization problems, as they guarantee that local minima are global. Key properties of convex sets include their closure under affine combinations, meaning that for any finite collection of points x_1, \dots, x_m \in C and coefficients \lambda_1, \dots, \lambda_m \in \mathbb{R} with \sum \lambda_i = 1, the point \sum \lambda_i x_i \in C. Another characterization involves the epigraph, though this is more directly tied to functions; for sets, convexity aligns with the set being the intersection of half-spaces. Representative examples include half-spaces, Euclidean balls, polyhedra, and the entire space \mathbb{R}^n, all of which satisfy the segment condition. A convex function extends this notion to mappings: a function f: \mathbb{R}^n \to \mathbb{R} (or extended-real-valued) is convex if its domain \dom f is convex and, for any x, y \in \dom f and \lambda \in [0, 1],

f(\lambda x + (1 - \lambda) y) \leq \lambda f(x) + (1 - \lambda) f(y).

Equivalently, f is convex if and only if its epigraph \epi f = \{(x, t) \in \mathbb{R}^n \times \mathbb{R} \mid f(x) \leq t\} is a convex set. This epigraph perspective highlights the geometric interpretation, where the function lies below its chords. Properties include preservation under nonnegative linear combinations and pointwise suprema of convex functions. Examples encompass linear functions f(x) = a^\top x + b, which are both convex and concave; norms \| \cdot \|, satisfying the triangle inequality; and the indicator function of a convex set C, defined as I_C(x) = 0 if x \in C and +\infty otherwise. The relative interior of a convex set C, denoted \ri C, refines the interior concept for sets of lower dimension: it consists of points x \in C such that there exists \epsilon > 0 with the open ball B(x, \epsilon) relative to the affine hull \aff C contained in C. The affine hull \aff C is the smallest affine set containing C. For full-dimensional sets in \mathbb{R}^n, \ri C coincides with the interior; otherwise, it captures the "interior" within the subspace. An example is a closed line segment [a, b] in \mathbb{R}^2, where \ri [a, b] = (a, b), the open segment; similarly, an open ball in a subspace serves as the relative interior of its closure.

Lagrange Multipliers and Duality

In constrained optimization, the method of Lagrange multipliers addresses problems involving equality constraints by transforming them into unconstrained problems through the introduction of auxiliary variables. Consider the optimization problem of minimizing an objective function f: \mathbb{R}^n \to \mathbb{R} subject to equality constraints g_i(x) = 0 for i = 1, \dots, m, where each g_i: \mathbb{R}^n \to \mathbb{R} is smooth. The Lagrange multiplier theorem asserts that if x^* is a local optimum satisfying a suitable constraint qualification, such as linear independence of the gradients \{\nabla g_i(x^*)\}, then there exist multipliers \mu = (\mu_1, \dots, \mu_m) \in \mathbb{R}^m, not all zero, such that

\nabla f(x^*) = \sum_{i=1}^m \mu_i \nabla g_i(x^*).

This condition equates the gradient of the objective to a linear combination of the constraint gradients, indicating that at the optimum, the level sets of f are tangent to the constraint manifold.^[4] The Lagrangian function formalizes this approach:

\mathcal{L}(x, \mu) = f(x) + \sum_{i=1}^m \mu_i g_i(x).

The theorem corresponds to the stationarity condition \nabla_x \mathcal{L}(x^*, \mu) = 0, along with the constraints g_i(x^*) = 0. In geometric terms, the multipliers \mu_i represent the sensitivity of the optimal value to perturbations in the constraints. This method originated in the context of equality-constrained problems and provides necessary conditions for optimality under differentiability assumptions.^[4] For problems with inequality constraints g_i(x) \leq 0, i = 1, \dots, m, the Lagrange multiplier method extends to the Karush-Kuhn-Tucker (KKT) conditions, which incorporate nonnegativity of the multipliers to account for the one-sided nature of inequalities. The KKT conditions require: (i) primal feasibility, g_i(x^*) \leq 0 for all i; (ii) dual feasibility, \mu_i \geq 0 for all i; (iii) complementary slackness, \mu_i g_i(x^*) = 0 for all i; and (iv) stationarity,

\nabla f(x^*) + \sum_{i=1}^m \mu_i \nabla g_i(x^*) = 0.

These conditions generalize the equality case, treating active inequalities (where g_i(x^*) = 0) similarly to equalities while inactive ones (g_i(x^*) < 0) receive zero multipliers. The Lagrangian remains \mathcal{L}(x, \mu) = f(x) + \sum_{i=1}^m \mu_i g_i(x), and under regularity assumptions, a point (x^*, \mu^*) satisfying KKT is a saddle point of \mathcal{L}: x^* minimizes \mathcal{L}(x, \mu^*) over x, while \mu^* maximizes \mathcal{L}(x^*, \mu) over \mu \geq 0. The KKT conditions were formalized in the seminal work on nonlinear programming.^[5]^[6] Lagrangian duality builds on this framework to derive bounds and alternative formulations of the primal problem \min \{ f(x) \mid g(x) \leq 0 \}. The dual function is defined as

\theta(\mu) = \inf_x \mathcal{L}(x, \mu),

which is concave in \mu and often computable when the infimum is unconstrained. The dual problem is then \max \{ \theta(\mu) \mid \mu \geq 0 \}, providing a lower bound on the primal optimal value. Weak duality holds universally: for any primal feasible x and dual feasible \mu \geq 0, f(x) \geq \theta(\mu), implying the primal optimum is at least the dual optimum. This duality gap measures the difference between these values.^[6] A zero duality gap occurs when the primal and dual optimal values coincide, establishing strong duality. In such cases, strong duality guarantees the existence of dual multipliers \mu^* \geq 0 that, together with the primal optimum x^*, satisfy the KKT conditions. This equivalence enables solving the often simpler dual problem to certify primal optimality or recover solutions via the saddle-point property. Strong duality typically requires convexity of the primal problem and a constraint qualification to ensure the infimum in \theta(\mu) is attained.^[6]

Core Formulation

Standard Inequality Constraints

Slater's condition arises in the context of convex optimization problems formulated as minimizing a convex objective function f(x) over a feasible set defined by convex inequality constraints g_i(x) \leq 0 for i = 1, \dots, m, where each g_i is a convex function. This standard setup assumes no equality constraints, focusing solely on inequalities to characterize the feasible region. The condition itself requires the existence of a point x in the relative interior of the domain of f such that g_i(x) < 0 for all i = 1, \dots, m, ensuring strict feasibility with respect to the inequalities. Named after Morton L. Slater, who introduced it in 1950 while studying quadratic programming, this strict inequality feasibility plays a pivotal role in guaranteeing desirable theoretical properties.^[7] As a constraint qualification, Slater's condition verifies that the feasible set possesses a nonempty relative interior, which supports the validity of dual-based analyses. Under the convexity of f and the g_i, along with Slater's condition, strong duality obtains between the primal and Lagrangian dual problems, and the Karush-Kuhn-Tucker (KKT) conditions become both necessary and sufficient for global optimality.

Strict Feasibility Condition

Strict feasibility, central to Slater's condition in convex optimization, refers to the existence of a point x in the relative interior of the domain of the objective function f and the constraint functions g_i such that all inequality constraints are satisfied strictly, i.e., g_i(x) < 0 for all i = 1, \dots, m, and any equality constraints Ax = b hold exactly. This notion ensures that the feasible set possesses a nonempty relative interior, which is crucial for duality results, as it contrasts with mere nonempty interior by accounting for affine constraints and lower-dimensional domains where the feasible set may lie in a subspace. The relative interior requirement arises because, in convex sets, the relative interior consists of points that can be approached from all directions within the affine hull, preventing boundary-dominated feasible regions that could lead to duality gaps. Verification of strict feasibility varies by constraint type. For polyhedral constraints, defined by linear inequalities, the condition holds whenever the feasible set is nonempty, as the relative interior of a nonempty polyhedron coincides with its interior relative to its affine hull. In nonlinear cases, where g_i are convex but not affine, direct verification often involves solving a phase-I feasibility problem, such as minimizing the maximum violation \max_i \max(0, g_i(x)) subject to equality constraints, to check if a value of zero is attainable with room for strict inequality; alternatively, interior-point methods can iteratively seek such a point by starting from an approximate feasible solution.^[8] Edge cases highlight when strict feasibility fails. It does not hold if all feasible points lie on the boundary of some inequality, such as in the problem of minimizing a constant subject to x \leq 0 and -x \leq 0, where the feasible set is the single point x = 0, having empty relative interior.^[9] Conversely, it holds for bounded feasible sets with interior points, like minimizing a convex function over a ball intersected with linear equalities, ensuring a strictly feasible point exists within the relative interior. In computational practice, strict feasibility is often approximated using barrier functions, which penalize proximity to the constraint boundaries by adding terms like -\sum_i \log(-g_i(x)) to the objective, guiding optimization toward the interior of the feasible set even if an exactly strictly feasible starting point is unavailable. Small perturbations to the constraints, such as replacing g_i(x) \leq 0 with g_i(x) \leq -\epsilon for small \epsilon > 0, can also simulate strict feasibility in numerical solvers, though this may introduce minor inaccuracies in the solution.^[8]

Applications in Optimization

Strong Duality Guarantee

In convex optimization problems of the form \min \{ f_0(x) \mid f_i(x) \leq 0, \, i=1,\dots,m; \, Ax = b \}, where f_0, f_i are convex functions and A is a matrix, Slater's condition ensures strong duality holds when the problem is strictly feasible, meaning there exists \tilde{x} in the relative interior of the domain such that f_i(\tilde{x}) < 0 for all i with nonlinear f_i and A\tilde{x} = b.^[10] Under this condition, the optimal primal value p^* = \inf \{ f_0(x) \mid x \in \mathcal{P} \} equals the optimal dual value d^* = \sup \{ g(\lambda, \nu) \mid \lambda \geq 0 \}, where g(\lambda, \nu) is the dual function, and both optima are attained if p^* > -\infty.^[10] A proof of strong duality under Slater's condition can be established using the separating hyperplane theorem applied to the epigraph of the value function. Consider the convex set \mathcal{A} = \{ (f_1(x), \dots, f_m(x), Ax - b, f_0(x)) \mid x \in \dom f_0 \}; Slater's condition implies that a point on the relative boundary of \mathcal{A} allows a non-vertical supporting hyperplane at (0, p^*), which corresponds to the Lagrangian multipliers achieving the dual optimum, ensuring p^* = d^*.^[11] Alternatively, strong duality follows from Sion's minimax theorem applied to the convex-concave Lagrangian L(x, \lambda, \nu) = f_0(x) + \sum_i \lambda_i f_i(x) + \nu^T (Ax - b), where Slater's condition guarantees the existence of a saddle point, yielding \min_x \max_{\lambda \geq 0, \nu} L(x, \lambda, \nu) = \max_{\lambda \geq 0, \nu} \min_x L(x, \lambda, \nu).^[12] The zero duality gap provided by Slater's condition has significant implications: it allows the often simpler, unconstrained dual problem to be solved in place of the primal, providing certificates of optimality via complementary slackness and enabling sensitivity analysis without resolving the primal.^[10] This contrasts with weak duality, which always holds for convex problems (i.e., d^* \leq p^*) but may result in a positive gap without qualification conditions like Slater's.^[10] A representative example is linear programming, where the problem \min \{ c^T x \mid Ax \leq b \} satisfies Slater's condition via simple feasibility (as constraints are affine), ensuring strong duality p^* = d^* whenever the primal or dual is feasible, with explicit dual multipliers attaining the bound.^[10]

KKT Conditions Sufficiency

In convex optimization problems where the objective function and inequality constraints are convex, and Slater's condition holds, the Karush-Kuhn-Tucker (KKT) conditions provide sufficient criteria for a point to be globally optimal. Specifically, if a feasible point x^* admits nonnegative Lagrange multipliers \mu^* \geq 0 satisfying the full set of KKT conditions—including stationarity, primal feasibility, dual feasibility, and complementary slackness—then x^* minimizes the objective function over the entire feasible set.^[13]^[14] The sufficiency of these conditions stems from the convexity of the problem combined with Slater's condition, which guarantees strong duality between the primal and dual formulations. Under strong duality, any KKT point achieves the common optimal value of both problems, confirming global primality optimality without duality gaps.^[13]^[15] To apply this in practice, optimality verification involves checking feasibility of x^* and solving for multipliers via the stationarity equation:

\nabla f(x^*) + \sum_{i=1}^m \mu_i^* \nabla g_i(x^*) = 0,

while confirming \mu^* \geq 0, g_i(x^*) \leq 0 for all i, and complementary slackness \mu_i^* g_i(x^*) = 0 for each constraint. This process identifies whether x^* qualifies as a global optimum under the problem's convexity and strict feasibility.^[14]^[16] A representative example is the quadratic program \min_{x} \frac{1}{2} x^T Q x + c^T x subject to linear inequalities A x \leq b, where Q \succeq 0 ensures convexity. When Slater's condition is satisfied—such as by the existence of a strictly feasible point where A x < b—any x^* meeting the KKT conditions yields the unique global minimum, as the multipliers can be computed to satisfy stationarity and the remaining conditions.^[15]^[13] Without Slater's condition, KKT conditions remain sufficient for optimality at points where they hold due to underlying convexity, but in degenerate cases lacking strict feasibility, they may fail to characterize all global optima, potentially requiring alternative qualifications for necessity.^[13]^[14]

Extensions and Generalizations

Conic Optimization

In conic optimization, Slater's condition is generalized to problems involving constraints defined over convex cones, extending the classical inequality case where the cone is the nonnegative orthant \mathbb{R}_+^m. The standard primal conic program takes the form

\begin{align*} \minimize &\quad c^\top x \\ \text{subject to} &\quad Ax - b \in K, \end{align*}

where K is a closed convex cone, A is a linear map, b is a point in the space, and x is the optimization variable.^[13] The generalized Slater condition, also known as strict feasibility, requires the existence of a point x such that Ax - b lies in the relative interior of K, denoted \ri(K). This condition ensures that the feasible set has nonempty relative interior, providing a robust qualification for duality properties in the conic setting. For convex conic programs satisfying this condition, strong duality holds, meaning the primal and dual optimal values coincide, and the optima are attained.^[13]^[17] Prominent examples include semidefinite programming (SDP), where K is the cone of positive semidefinite matrices \mathcal{S}_+^n, and the relative interior consists of positive definite matrices. In second-order cone programming (SOCP), K is the second-order cone \mathcal{Q}^{m+1} = \{(y,t) \in \mathbb{R}^m \times \mathbb{R} \mid \|y\|_2 \leq t \}, with relative interior \{(y,t) \mid \|y\|_2 < t, t > 0 \}. These cases illustrate how the generalized condition adapts to structured cones, enabling numerical solvability via interior-point methods.^[13] The importance of this generalization lies in its coverage of SDP and SOCP, which underpin applications in robust control, signal processing, and machine learning, where conic constraints model spectral or norm-based requirements more flexibly than linear inequalities.^[13]

Nonsmooth and Nonconvex Variants

In nonsmooth convex optimization problems, where the objective function f and inequality constraints g_i are convex but possibly nondifferentiable, the Karush-Kuhn-Tucker (KKT) conditions are formulated using subdifferentials: at a local minimizer x^*, there exist nonnegative multipliers \mu_i \geq 0 such that $0 \in \partial f(x^*) + \sum_i \mu_i \partial g_i(x^*), along with complementary slackness \mu_i g_i(x^*) = 0 and primal feasibility.^[18] Slater's condition adapts to this setting by requiring the existence of a point in the relative interior of the domain where the inequalities are strictly satisfied, i.e., there exists \bar{x} such that g_i(\bar{x}) < 0 for all i with nonempty relative interior of the feasible set. For convex nonsmooth problems, such as those involving maximum functions or other nondifferentiable terms, Slater's condition ensures strong duality. Specifically, if the primal value is finite and a strict feasibility point exists in the relative interior, the duality gap vanishes, leveraging convex analysis results like the Fenchel-Moreau theorem, which characterizes lower semicontinuous convex functions as their own biconjugates to attain equality in Fenchel duality.^[19]^[20] In nonconvex variants, the classical Slater's condition often fails to guarantee global strong duality due to the lack of convexity, leading to potential duality gaps. However, approximate versions using error bounds or calm constraint assumptions provide local guarantees; for instance, in sequential quadratic programming (SQP) methods for nonconvex problems, local strict feasibility around a solution ensures the existence of multipliers for the local KKT conditions. Modern extensions, such as the Luo-Tseng error bound developed in the 1990s, establish local error bounds relating the distance to the solution set to a residual function under a weakened Slater-like condition, enabling local convergence analysis even in nonconvex settings.^[21] These adaptations highlight the incompleteness of the classical Slater's condition in nonconvex cases, where global duality typically does not hold, but local analogs suffice for stationarity and algorithmic purposes. As an example in the nonsmooth convex case, consider \min_x |x| subject to x \geq 1; Slater's condition holds trivially via any \bar{x} > 1, yielding strong duality with optimal value 1 attained at x=1, where $0 \in \partial |x|(1) + \mu \partial (1 - x)(1) for \mu = 1. In nonconvex problems, the Mangasarian-Fromovitz constraint qualification offers an alternative, ensuring necessary KKT conditions by requiring a suitable linear independence of active constraint gradients without relying on strict feasibility or convexity.^[22]

References

[1]
[PDF] Lecture 8: Strong Duality - People @EECS
Feb 9, 2012 · If the problem is convex, then A is also convex. If Slater's condition holds, then the inte- rior of A intersects the left-half plane, and ...
[2]
[PDF] Untitled - Cowles Foundation for Research in Economics - Yale ...
LAGRANGE MULTIPLIERS REVISITED. A Contribution to Non-Linear Programming by Morton Slater. November 7, 1950. 1. Introduction. 1. The present paper was inspired ...
[3]
[PDF] KKT conditions 13.1 Continued from last lecture on duality
Also note that the dual problem is always a convex optimization problem (maximizing a concave function), even when the primal problem is non-convex. By ...
[4]
[PDF] Constrained Optimization and Lagrange Multiplier Methods
Professor Bertsekas has done research in a broad variety of subjects from optimization theory, control theory, parallel and distributed computa- tion, data ...
[5]
Nonlinear Programming - Project Euclid
Nonlinear Programming Chapter. Author(s) HW Kuhn, AW Tucker. Editor(s) Jerzy Neyman. Berkeley Symp. on Math. Statist. and Prob., 1951: 481-492 (1951)
[6]
None
Nothing is retrieved...<|control11|><|separator|>
[7]
[PDF] Lagrange Multipliers Revisited - EliScholar
This Discussion Paper is brought to you for free and open access by the Cowles Foundation at EliScholar – A. Digital Platform for Scholarly Publishing at ...Missing: PDF | Show results with:PDF
[8]
[PDF] Interior Point Algorithms for Constrained Convex Optimization
Approximate indicator function by a differentiable, closed, and convex ... Strict feasibility: Ax∗(t) = b, fi(x∗(t)) < 0, i = 1,...,m. 2. Centrality ...<|separator|>
[9]
What is the intuition behind Slater's condition in optimization? (And ...
Dec 29, 2016 · Slater's condition relates to existence of Lagrange multipliers in a convex program. Lagrange multipliers exist when there is a nonvertical ...KKT and Slater's condition - Math Stack ExchangeWeak Slater's condition - optimization - Math Stack ExchangeMore results from math.stackexchange.com
[10]
[PDF] Duality - Convex Optimization
▷ conditions that guarantee strong duality in convex problems are called constraint ... ▷ recall that Slater implies strong duality, and dual optimum is attained.
[11]
How to prove strong duality by Slater's condition without the ...
Feb 11, 2021 · Overall we have shown that there exists a non-vertical supporting hyperplane to A at its boundary, and therefore strong duality holds. Share.What is the intuition behind Slater's condition in optimization? (And ...Geometric interpretation of duality and Slater's conditionMore results from math.stackexchange.com
[12]
[PDF] Convex Analysis, Duality and Optimization - Semantic Scholar
Mar 7, 2010 · Step 3: Minimize w.r.t. x0 on both sides, but note that the RHS does not depend on x0 at all. Page 48. Strong Duality. Theorem (Sion, 1958). Let ...
[13]
None
Below is a merged summary of the KKT Conditions, Sufficiency for Convex Problems, and Slater's Condition based on the provided segments from "Convex Optimization" by Boyd & Vandenberghe, primarily sourced from https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf. To retain all information in a dense and organized manner, I will use a combination of narrative text and a table to capture detailed references, theorems, and specific page numbers where applicable. The response consolidates overlapping information while preserving unique details from each segment.
[14]
[PDF] The KKT Conditions
If the constraints are convex, regularity can be replaced by Slater's condition. Theorem (necessity of the KKT conditions under Slater's condition) Let x∗ be a ...
[15]
[PDF] Lecture 12: KKT conditions - Statistics & Data Science
1. For any optimization problem, if x∗ and u∗,v∗ satisfy KKT conditions for the problem, then satisfying those KKT conditions is sufficient ...
[16]
[PDF] The Karush-Kuhn-Tucker (KKT) conditions
If strong duality holds (e.g., Slater's condition holds) then x? and λ? obey the KKT conditions. We trivially have (K1) and (K2) simply because x? and λ ...
[17]
Genericity Results in Linear Conic Programming—A Tour d'Horizon
Sep 29, 2016 · In particular we give an easy proof of the fact that Slater's condition holds generically in linear conic programming. We further discuss ...
[18]
[PDF] Subgradients - Stanford University
Apr 7, 2022 · Understanding notions of stationarity in nonsmooth optimization: A guided tour of various constructions of subdifferential for nonsmooth ...
[19]
[PDF] Strong Duality via Convex Conjugacy - Stanford Computer Science
This second characterization leads to a simple proof that Slater's condition is sufficient for strong duality attain. 1 Introduction. The topic of our analysis ...
[20]
https://epubs.siam.org/doi/book/10.1137/1.9781611970524
[21]
A Note on Error Bounds for Convex and Nonconvex Programs
Luo and P. Tseng, “Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem,” SIAM J. on Optimization, ...
[22]
The Fritz John necessary optimality conditions in the presence of ...
Volume 17, Issue 1, January 1967, Pages 37-47 The Fritz John necessary optimality conditions in the presence of equality and inequality constraints.