Finite-dimensional convex program, Lagrangian dual, and Slater condition

A subset is convex when it contains the segment joining each pair of its points (A convex subset of ${\mathbb{R}}^m$ contains every line segment between two of its points). A function $F:{\mathbb{R}}^n\to (-\mathrm{\infty },+\mathrm{\infty }]$ is proper if it never equals $-\mathrm{\infty }$ and is finite at at least one point. Its domain is $\mathrm{dom}F=\{x:F(x)<+\mathrm{\infty }\}$. Its epigraph is $\mathrm{epi}F=\{(x,t):F(x)\le t\}$. It is closed convex when its epigraph is a closed convex set. For a nonempty convex set $S$, $\mathrm{aff}S$ is its smallest containing affine subspace and $\mathrm{ri}S$ is its interior relative to $\mathrm{aff}S$.

Let $n\ge 1$, let $m,p\in \mathbb{N}$ with zero allowed, let $f_0,g_1,\dots ,g_m$ be proper closed convex functions on ${\mathbb{R}}^n$, let $A\in {\mathbb{R}}^{p\times n}$ have full row rank, and let $b\in {\mathbb{R}}^p$. Full row rank means that the rows are linearly independent, vacuously when $p=0$. The common domain is $D=\mathrm{dom}{f}_0\cap {\bigcap }_{i=1}^m\mathrm{dom}{g}_i$. The primal problem is to minimize $f_0(x)$ over $x\in D$ satisfying $Ax=b$ and $g_i(x)\le 0$. An inequality is removable if, with $D_{-i}=\mathrm{dom}{f}_0\cap {\bigcap }_{j\mathrm{\ne }i}\mathrm{dom}{g}_j$, $D_{-i}\subseteq \mathrm{dom}{g}_i$ and $g_i(x)\le 0$ for every $x\in D_{-i}$. Then $D=D_{-i}$, so removing that function and its inequality leaves the feasible set unchanged. While a removable inequality exists, delete the one with smallest original index, recomputing $D_{-i}$ using the currently retained family after each deletion. Stop when none is removable, then relabel the remaining inequalities consecutively in their original order and let $m$ denote their number. An inequality that is nonpositive only on $D$ but whose function domain restricts $D$ is not removable. Unless stated otherwise, the inequalities below are the remaining ones after only these domain-preserving deletions. The primal value is

For $\lambda \in {\mathbb{R}}_{+}^m$ and $\nu \in {\mathbb{R}}^p$, the extended Lagrangian is

The dual function and dual value are

The dual supremum is attained when some admissible $(\lambda ,\nu )$ has $q(\lambda ,\nu )=d^{\ast }$; the optimal duality gap is $p^{\ast }-d^{\ast }$ when both values are finite.

Slater's condition means that there is $x_s\in \mathrm{ri}(\mathrm{dom}{f}_0)\cap {\bigcap }_i\mathrm{ri}(\mathrm{dom}{g}_i)$ with $A{x}_s=b$ and $g_i(x_s)<0$ for every remaining inequality. Relative interior is used in the affine hull of each domain, so the domain need not have ambient interior.

The equality rows are assumed independent after consistent redundant rows are removed. The theorem on this page assumes a finite attained primal value; Slater's strict inequalities alone do not assert primal attainment. The deletion convention depends on the indexed representation; Slater's condition is tested on the resulting family, not asserted to be invariant under other deletion orders or equivalent constraint representations.