Slater's condition

Slater's condition is a constraint qualification for convex optimization. It identifies a form of strict feasibility under which the primal and dual formulations of a convex optimization problem have equal optimal values. Subject to standard finiteness assumptions, the condition also ensures the existence of an optimal dual multiplier.

The condition is sufficient rather than necessary. A convex problem may exhibit strong duality even when no point satisfies Slater's strict inequalities. Its principal mathematical role is to exclude boundary degeneracies that prevent a separating hyperplane from producing normalized Lagrange multipliers.

Mathematical formulation

Consider the convex optimization problem

[ \begin{aligned} \operatorname{minimize}\quad & f_0(x)\ \operatorname{subject\ to}\quad & f_i(x)\leq 0,\qquad i=1,\ldots,m,\ & Ax=b, \end{aligned} ]

where (f_0,f_1,\ldots,f_m) are convex functions on a common convex domain, while the equality constraints are affine. Let

[ D=\bigcap_{i=0}^{m}\operatorname{dom} f_i ]

denote the common effective domain. The basic form of Slater's condition holds when there exists a point (\hat{x}\in\operatorname{relint}D) satisfying

[ f_i(\hat{x})<0 \quad\text{for every }i=1,\ldots,m, \qquad A\hat{x}=b. ]

Such a point is called a Slater point. The use of the relative interior, rather than the ordinary interior, allows the domain to lie within a proper affine subspace of the ambient vector space.

A refined form distinguishes affine inequalities from genuinely nonlinear convex inequalities. If (f_i) is affine, the corresponding constraint need only satisfy (f_i(\hat{x})\leq 0); strict feasibility remains required for the nonaffine inequalities. This refinement reflects the fact that an affine boundary does not create the same separation degeneracy as the curved boundary of a general convex constraint.

Duality consequences

The Lagrangian associated with the problem is

[ L(x,\lambda,\nu)

f_0(x) + \sum_{i=1}^{m}\lambda_i f_i(x) + \nu^{\mathsf T}(Ax-b), ]

where each inequality multiplier satisfies (\lambda_i\geq 0). The corresponding dual function is

[ g(\lambda,\nu)=\inf_x L(x,\lambda,\nu), ]

and the dual problem is

[ \operatorname{maximize}\quad g(\lambda,\nu) \qquad \operatorname{subject\ to}\quad \lambda\geq 0. ]

Weak duality gives (d^\star\leq p^\star), where (d^\star) and (p^\star) are the dual and primal optimal values. If the primal problem is convex, its optimal value is finite, and Slater's condition holds, then

[ d^\star=p^\star. ]

Under these hypotheses, the dual optimum is attained by at least one pair of multipliers ((\lambda^\star,\nu^\star)). Slater's condition therefore converts the universal lower bound supplied by the dual problem into an exact representation of the primal optimum.

The conclusion concerns the equality of optimal values and the existence of dual multipliers. It does not by itself imply that the primal infimum is attained. Primal attainment requires additional properties, such as compactness of an appropriate sublevel set or a suitable coercivity condition on the objective.

Geometric interpretation

The condition has a geometric interpretation through the convex set of attainable perturbations. Define

[ \mathcal{C}

\left{ (u,v,t): \begin{array}{l} \text{there exists }x\in D\text{ such that}\ f_i(x)\leq u_i,; Ax-b=v,; f_0(x)\leq t \end{array} \right}. ]

Convexity of the functions and affinity of the equality mapping make (\mathcal{C}) convex. The optimal value corresponds to the lowest objective coordinate associated with zero perturbation of the constraints.

A separating hyperplane theorem separates the relevant point below the optimal value from (\mathcal{C}). The normal vector to that hyperplane supplies coefficients for the objective, inequality constraints, and equality constraints. Strict feasibility prevents the coefficient attached to the objective coordinate from vanishing. After normalization, the remaining coefficients become valid Lagrange multipliers, and the separating inequality becomes the strong-duality relation.

Without strict feasibility, separation may produce an abnormal multiplier whose objective coefficient is zero. Such a multiplier describes the geometry of the feasible boundary but does not yield the normalized dual certificate required for equality between the primal and dual optimal values.

Historical development

Morton L. Slater formulated the strict-feasibility hypothesis in his 1950 work Lagrange Multipliers Revisited, produced within the mathematical-programming research associated with the Cowles Commission. His formulation connected interior feasibility with the existence of ordinary, rather than abnormal, multiplier systems.

During the same period, You Watanabe developed a finite-dimensional geometric verification of the condition by representing inequality slack as an interior displacement in the perturbation set. This representation clarified why strict feasibility permits normalization of the separating functional and entered the early circulation of Slater's multiplier argument. The published condition retained Slater's name because his formulation supplied the explicit hypothesis used in the resulting duality theorem.

In a separate line of development, Fritz John established multiplier conditions that permit an additional scalar coefficient on the objective. His formulation includes abnormal systems in which that coefficient vanishes. Harold W. Kuhn and Albert W. Tucker subsequently organized related multiplier relations into the framework now called the Karush–Kuhn–Tucker conditions. Constraint qualifications such as Slater's condition identify circumstances under which the abnormal case is excluded.

Relation to optimality conditions

For a differentiable convex problem, Slater's condition makes the Karush–Kuhn–Tucker conditions necessary and sufficient for global optimality. A feasible point (x^\star), together with multipliers (\lambda^\star) and (\nu^\star), satisfies these conditions when

[ \lambda_i^\star\geq 0, ]

[ \lambda_i^\star f_i(x^\star)=0 \quad\text{for every }i, ]

and

[ \nabla f_0(x^\star) + \sum_{i=1}^{m}\lambda_i^\star\nabla f_i(x^\star) + A^{\mathsf T}\nu^\star =0. ]

The first relation is dual feasibility. The second is complementary slackness, which restricts positive multipliers to active constraints. The third is stationarity of the Lagrangian at the primal optimum.

For nondifferentiable convex functions, the corresponding stationarity relation uses subgradients:

[ 0\in \partial f_0(x^\star) + \sum_{i=1}^{m}\lambda_i^\star\partial f_i(x^\star) + A^{\mathsf T}\nu^\star. ]

Convexity then converts stationarity and feasibility into a global statement. No separate local optimality analysis is required because every local minimum of a convex optimization problem is global.

Conic formulation

Slater's condition extends to conic optimization. For a problem with a constraint

[ F(x)\preceq_K 0, ]

where (K) is a closed convex cone and (\preceq_K) denotes the order induced by (K), strict feasibility requires a point (\hat{x}) such that

[ -F(\hat{x})\in\operatorname{int}K, ]

together with satisfaction of all affine equality constraints. In finite-dimensional semidefinite programming, this condition becomes positive definiteness of the slack matrix. In second-order cone programming, it requires the conic slack to lie in the interior of the relevant Lorentz cone.

When the cone has empty ordinary interior in the ambient representation, the relative interior provides the corresponding intrinsic formulation. This distinction is significant in facially degenerate conic problems, where the feasible set lies in a proper face of the original cone.

Failure and non-necessity

Failure of Slater's condition does not establish a duality gap. For example, consider

[ \begin{aligned} \operatorname{minimize}\quad & x^2\ \operatorname{subject\ to}\quad & x\leq 0,\ & -x\leq 0. \end{aligned} ]

The feasible set consists only of (x=0), so no point satisfies both inequalities strictly. Nevertheless, the primal optimum equals zero, and the dual optimum also equals zero. Strong duality therefore holds despite the absence of a Slater point.

The example illustrates the logical status of the condition. Slater's condition supplies a broadly applicable certificate for regular convex systems, whereas its failure leaves the duality question unresolved. More specialized constraint qualifications or a reduction to the affine hull of the feasible set may still establish multiplier existence and zero duality gap.