Slater's Condition in General

Slater’s condition is a fundamental constraint qualification in convex optimization that guarantees strong duality. It essentially demands that there’s room to perturb the constraints without the problem becoming infeasible, and as classically stated, imposes interiority conditions on the set of feasible perturbations. However, we don’t actually need to rely on the topological structure to capture the idea behind Slater’s condition. In this post, we’ll review the classical result, then explore a generalization that works in vector spaces without any topological structure.

Classical Slater’s condition

Review of some definitions

Before stating the classical result, let’s recall some key concepts about optimization in vector spaces. Throughout, all vector spaces are real vector spaces (vector spaces over $\mathbf{R}$).

Dual space. For a topological vector space $V$, the topological dual (or simply dual) $V^{\ast }$ consists of all continuous linear functionals $\ell :V\to \mathbf{R}$. A linear functional is continuous if and only if it is bounded on some neighborhood of the origin, i.e., there exists a neighborhood $U$ of the origin and $M>0$ such that $|⟨\ell ,v⟩|\le M$ for all $v\in U$. (In normed spaces, this is equivalent to $|⟨\ell ,v⟩|\le M\Vert v\Vert$ for all $v\in V$.) In finite dimensions, all linear functionals are continuous.

Positive cones and order. A subset $P$ of a vector space $Z$ is a cone if $\alpha p\in P$ for all $p\in P$ and $\alpha \ge 0$. (Note that we require $0\in P$.) A convex cone $P$ defines a partial order on $Z$ by declaring $z_1{\ge }_P{z}_2$ (or simply $z_1\ge z_2$) if and only if $z_1-z_2\in P$. We call $P$ a positive cone when used to define such an order. When $Z$ is a topological vector space and $P$ has nonempty interior, we write $z_1{>}_P{z}_2$ (or simply $z_1>z_2$) if $z_1-z_2\in \mathrm{int}(P)$.

For example, in ${\mathbf{R}}^m$, the standard positive cone is ${\mathbf{R}}_{+}^m=\{z\in {\mathbf{R}}^m:z_i\ge 0\text{ for all }i\}$, giving the componentwise order. In function spaces, we might take $P=\{f:f(t)\ge 0\text{ for all }t\}$.

Dual cone. Given a cone $P$ in a normed space $Z$, the dual cone is

The dual cone consists of continuous linear functionals that are “nonnegative” on $P$. When $P={\mathbf{R}}_{+}^m$, we have $P^{\ast }={\mathbf{R}}_{+}^m$ as well.

Cone-convex functions. A function $G:X\to Z$ (where $Z$ is ordered by cone $P$) is $P$-convex if for any $x_1,x_2\in X$ and $\theta \in [0,1]$,

Equivalently, $G$ is $P$-convex if the set $\{(x,z):G(x){\le }_{P}z\}$ is convex in $X\oplus Z$.

The classical theorem

We can now state the classical form of Slater’s condition for convex optimization problems in normed spaces, as appears in Exercise 8.7 of Luenberger [1].

I was assigned this exercise as a homework problem in Winter 2024. I do not know if there is a standard proof for this result, but both the proof that I found and the official solution took the same general strategy, which I outline below.

Proof strategy

The basic idea is to prove this is to apply the Hahn–Banach separation theorem to separate the point $(F^{\star },0,0)$ from the set $\mathcal{A}\subseteq \mathbf{R}\oplus Z\oplus Y$ given by

The set $\mathcal{A}$ contains all triples $(t,z,y)$ for which there exists a feasible point achieving objective value strictly less than $t$ under constraint perturbations $(z,y)$. Since $F$, $G$, and $\Omega$ are convex and $H$ is affine, $\mathcal{A}$ is a convex set.

The Hahn–Banach separation theorem guarantees a separating hyperplane is $\mathcal{A}$ has nonempty interior. This hyperplane is given by a nonzero linear functional $(s,\lambda ,\nu )\in \mathbf{R}\oplus Z^{\ast }\oplus Y^{\ast }$ satisfying

Once $s>0$ and $\lambda \in P^{\ast }$ are established (proofs omitted), we can divide by $s$ and define ${\lambda }^{\star }=\lambda /s\in P^{\ast }$ and ${\nu }^{\star }=\nu /s$. Equality is obtained due to weak duality.

The tricky part is showing that $\mathcal{A}$ has nonempty interior, which is necessary to apply the Hahn–Banach separation theorem. This is the part that uses the various interiority conditions in the hypotheses.

Proof that $\mathrm{int}(\mathcal{A})\ne \varnothing$

We construct an explicit open set contained in $\mathcal{A}$. Since $G(x_1)<0$ and $0\in \mathrm{int}(H(\Omega ))$, we have room to perturb each of the constraints individually. The most natural thing to try is to see if we can perturb each of the constraints in any direction, and satisfy some uniform bound $M$ on $F$. That is, we want to find an open set of the form $(M,+\infty )\times U_Z\times U_Y$ about $(F(x_1),0,0)$, lying in $\mathcal{A}$.

Individual perturbations. Let $v=-G(x_1)\in \mathrm{int}(P)$. Since $Z$ is a normed space, there exists $ϵ>0$ such that the open ball $B(v,ϵ)\subseteq P$. So, the constraint $G(x)\le z$ is still feasible with any perturbation $z\in B(0,ϵ)$ (in particular, take $x=x_1$).

Since $0\in \mathrm{int}(H(\Omega ))$ and $Y$ is finite-dimensional, we can choose a basis for $Y$ and identify $Y\cong {\mathbf{R}}^k$ (where $k=\dim (Y)$) such that the unit cube $[-1,1{]}^k\subseteq H(\Omega )$. So, $H(x)=y$ is still feasible with perturbations $y$ in the interior of the unit cube.

The challenge is that if we perturb the equality constraint, moving from $H(x_1)=0$ to $H(x)=y$, then we must change $x$. A prior, this might consume the available slack $ϵ$ that we have for the inequality constraint, or $F$ could blow up as we take $y$ close to the boundary of the cube. We need to show that these effects can be controlled.

Quantifying the impact of equality constraint perturbations. To bound the impact of perturbations to the equality constraint, we need only investigate the effect of perturbations in the extreme directions (the vertices of $[-1,1{]}^k$). This works because $H$ is affine and $\Omega$, $F$, and $G$ are convex. To make this more precise, let $\mathcal{V}=\{-1,1{\}}^k$ be the vertices. For each $y\in \mathcal{V}$, select a representative $x_y\in \Omega$ such that $H(x_y)=y$.

Consider the convex hull $\mathrm{conv}(\{x_1\}\cup \{x_y{\}}_{y\in \mathcal{V}})$. This consists of points $x(\beta )$ given by

for $\beta \ge 0$ with ${\sum }_{y\in \mathcal{V}}{\beta }_y\le 1$. Since $\Omega$ is convex, $x(\beta )\in \Omega$ for each $\beta$. Furthermore, $H(x(\beta ))={\sum }_{y\in \mathcal{V}}{\beta }_{y}y$ by affinity of $H$, which generates the entire cube.

Crucially, the behavior of $F$ and $G$ at $x(\beta )$ is controlled by their values at the representatives $x_y$. Applying convexity gives

where we define $R(x(\beta ))={\sum }_{y\in \mathcal{V}}{\beta }_y[G(x_y)-G(x_1)]$. Note that as long as $R(x(\beta ))\in B(0,ϵ)$, then we are guaranteed $G(x)\le 0$ by our earlier construction.

Controlling the impact of equality constraint perturbations. Since $\{x_1\}\cup \{x_y{\}}_{y\in \mathcal{V}}$ is finite, the values of $F$ and $G$ at these points are necessarily bounded. We define the maximum costs associated with these extreme directions as

For any $x\in {\mathcal{B}}_1$, we have $F(x)\le M_F$ and $\Vert G(x)-G(x_1)\Vert \le M_G$. While the objective is therefore uniformly bounded, it’s possible that $M_G>ϵ$, so that $R(x)\notin B(0,ϵ)$ and, possibly, $G(x)\nleqq 0$.

To remedy this, we scale down the cube $[-1,1{]}^k$. Choose a scaling factor $\theta \in (0,1)$ such that $\theta M_G\le ϵ/3$. (If $M_G=0$, then any $\theta \in (0,1)$ works.) Now define the set

It isn’t hard to see that $H(\mathcal{B})$ covers the scaled cube $[-\theta ,\theta {]}^k$. For any given $x\in \mathcal{B}$, we certainly have $F(x)\le M_F$. But we also have

So, $G(x)\in B(-v,ϵ/3)$ and we have some extra space to further perturb the inequality constraints while keeping $x$ feasible.

The open set. We now define $U_Z=B(0,ϵ/3)$ and $U_Y=(-{\theta }^{\star },{\theta }^{\star }{)}^k$, so that we get the open set $W=(M_F,+\infty )\times B(0,ϵ/3)\times (-{\theta }^{\star },{\theta }^{\star }{)}^k$. We verify that $W$ is, indeed, contained in $\mathcal{A}$. Let $(t,z,y)\in W$.

Since $y\in U_Y$, there exists $x\in \mathcal{B}\subseteq \Omega$ such that $H(x)=y$. For this $x$, we have $F(x)\le M_F<t$.

For the inequality constraint, we need $G(x)\le z$, or equivalently, $z-G(x)\in P$. Since $G(x)\le -v+R(x)$, we have

Since $\Vert z\Vert <ϵ/3$ and $\Vert R(x)\Vert \le ϵ/3$, the triangle inequality gives $\Vert z-R(x)\Vert <2ϵ/3$. Therefore, $v+(z-R(x))\in B(v,2ϵ/3)\subseteq B(v,ϵ)\subseteq P$. We conclude $z-G(x)\in P$, hence $G(x)\le z$.

Thus, $(t,z,y)\in \mathcal{A}$. Since $W\subseteq \mathcal{A}$ and $W$ is open, $\mathrm{int}(\mathcal{A})\ne \varnothing$.

A more general Slater’s condition

The core idea of Slater’s condition is that we can perturb the constraints in any direction without losing feasibility or blowing up $F$. As it turns out, this idea can be captured without reference to a topology. We can instead use purely algebraic constructs and obtain a more general form of Slater’s condition that applies in arbitrary (real) vector spaces.

More definitions

We first need to introduce some additional concepts that make sense in arbitrary vector spaces, without requiring any topology.

Algebraic dual space. For any vector space $V$, the algebraic dual $V^{\#}$ is the space of all linear functionals $V\to \mathbf{R}$. This is in contrast to the topological dual $V^{\ast }$, which you’ll recall consists of continuous linear functionals only. We have $V^{\ast }\subseteq V^{\#}$ in general, with equality when $V$ is finite-dimensional.

Algebraic dual cone. For a cone $P$ in a vector space $V$, the algebraic dual cone is

A key fact is that if $P$ has nonempty interior (when $V$ is a topological vector space), then every functional in $P^{\#}$ is automatically continuous, so $P^{\#}=P^{\ast }$ in this case.

Core. The core of a set $C$ in a vector space $V$, denoted $\mathrm{core}(C)$, is the set of points $x\in C$ such that for every $v\in V$, there exists $\delta >0$ with $x+tv\in C$ for all $t\in [0,\delta ]$. This just says that starting from any $x\in \mathrm{core}(C)$, you can pick any direction and you’ll be able to travel at least some distance in that direction without leaving $C$.

The core generalizes the notion of interior. In a topological vector space, if $C$ has nonempty interior, then $\mathrm{int}(C)\subseteq \mathrm{core}(C)$. For convex sets in finite-dimensional spaces, $\mathrm{int}(C)=\mathrm{core}(C)$ (they coincide). For convex sets in infinite-dimensional spaces, the core can be nonempty even when the interior is empty.

The General Result

With these definitions in hand, we can state the generalized Slater condition. I am actually not aware of any sources that provide this result. I will add a reference if I can find one!

Proof of the general result

In the proof of the classical result, we spent a lot of time checking that we could jointly perturb the equality and inequality constraints while maintaining feasibilty and a uniform bound on $F$. In this case, however, the core condition permits us to jointly perturb the constraints for free. The proof strategy is then to analyze the sensitivity of the optimal cost to small changes in the constraints. The generalized Slater’s condition guarantees that this sensitivity is well-behaved and finite in every possible direction of perturbation. This allows the construction of a linear underestimator for the cost behavior using the Hahn–Banach theorem, which gives the Lagrange multipliers necessary to prove strong duality.

The value function. Consider the value function $v:Z\oplus Y\to \mathbf{R}\cup \{+\infty \}$ given by

This function measures the optimal value of the problem when we perturb the constraints by $(z,y)$. Clearly $v$ is convex and $\mathrm{dom}(v)=\mathcal{C}$. Without loss of generality, we can translate $F$ so that $v(0,0)=F^{\star }=0$.

Directional derivative of $v$ at $(0,0)$. Define the directional derivative of $v$ at the origin as

Since $v$ is convex and we have assumed $v(0,0)=0$, the ratio $v(tz,ty)/t$ is nondecreasing in $t$ for $t>0$. This ensures that the limit exists (though a priori it might be $+\infty$) and equals the infimum, i.e.,

In fact, $g$ is finite-valued. Since $(0,0)\in \mathrm{core}(\mathrm{dom}(v))$, for any direction $(z,y)\in Z\oplus Y$, there exists $\delta >0$ such that $(\delta z,\delta y)\in \mathrm{dom}(v)$. This means $v(\delta z,\delta y)<+\infty$, so

Therefore, $g$ is finite-valued on all of $Z\oplus Y$.

Verifying that $g$ is sublinear. We next verify that $g$ is sublinear. It is positively homogeneous because, by a change of variables,

for all $(z,y)$ and $\alpha >0$. It is also subadditive since convexity of $v$ gives

Thus $g:Z\oplus Y\to \mathbf{R}$ is a sublinear function (finite-valued, positively homogeneous, and subadditive).

Applying Hahn–Banach. Since $g$ is a sublinear function mapping to $\mathbf{R}$, the Hahn–Banach theorem guarantees the existence of a linear functional $L:Z\oplus Y\to \mathbf{R}$ such that $L(z,y)\le g(z,y)$ for all $(z,y)\in Z\oplus Y$. Write $L(z,y)=-⟨{\lambda }^{\star },z⟩-⟨{\nu }^{\star },y⟩$ for some $({\lambda }^{\star },{\nu }^{\star })\in Z^{\#}\oplus Y^{\#}$.

$(-{\lambda }^{\star },-{\nu }^{\star })$ is a subgradient. We have $g(z,y)\le v(z,y)$ for all $(z,y)$ (take $t=1$ in the infimum defining $g$). Thus,

Rearranging, we obtain the subgradient inequality

This shows that $(-{\lambda }^{\star },-{\nu }^{\star })\in \partial v(0,0)$ is a subgradient of $v$ at the origin.

${\lambda }^{\star }\in P^{\#}$. We must check that $⟨{\lambda }^{\star },p⟩\ge 0$ for all $p\in P$. For any $p\in P$, we have $p{\ge }_{P}0$, so $v(p,0)\le v(0,0)=0$. This holds due to monotonicity: the value function $v$ is nonincreasing in its first argument, since the feasible set grows as $z$ increases with respect to ${\ge }_P$. Applying (3), we also have $v(p,0)\ge -⟨{\lambda }^{\star },p⟩$. Combining these gives $0\ge v(p,0)\ge -⟨{\lambda }^{\star },p⟩$, which implies $⟨{\lambda }^{\star },p⟩\ge 0$. Thus, ${\lambda }^{\star }\in P^{\#}$.

Strong duality. For any $x\in \Omega$, we have $(G(x),H(x))\in \mathrm{dom}(v)$, so substituting $(z,y)=(G(x),H(x))$ into the subgradient inequality (3) yields

Since $v(G(x),H(x))\le F(x)$ by definition, we have

By weak duality, the right side is at most $F^{\star }=0$, so we have equality. Thus strong duality holds with Lagrange multipliers $({\lambda }^{\star },{\nu }^{\star })$.

Use in the classical result

The general Slater’s condition can be used to prove the classical Slater’s condition.

Suppose $Z$ is a normed space, $Y$ is finite-dimensional, and we have

• the existence of $x_1$ with $G(x_1)<0$ (strict inequality) and $H(x_1)=0$, and
• the condition $0\in \mathrm{int}(H(\Omega ))$.

This is the classical Slater’s condition. We can show that this implies the general Slater’s condition, that $(0,0)\in \mathrm{core}(\mathcal{C})$. We leave this as an exercise. Applying the general theorem, we obtain multipliers $({\lambda }^{\star },{\nu }^{\star })\in P^{\#}\times Y^{\#}$ for which strong duality holds. Moreover, these multipliers actually lie in $P^{\ast }\times Y^{\ast }$. This is because $G(x_1)<0$ implies $\mathrm{int}(P)\ne \varnothing$ (so $P^{\ast }=P^{\#}$) and $Y$ is finite-dimensional (so $Y^{\ast }=Y^{\#}$).

References