Slater gives zero duality gap and an attained dual certificate

For perturbations $u\in {\mathbb{R}}^m$ and $v\in {\mathbb{R}}^p$, define $P(u,v)=\inf \{f_0(x):x\in D,g_i(x)\le u_i(1\le i\le m),Ax-b=v\}\mathrm{.}$ This value function is convex. Indeed, for two perturbations with finite values, choose feasible points with objective within $ϵ$ of their respective infima. A convex combination of those points lies in $D$, its inequalities and equality residual are bounded by the same convex combination of perturbations, and convexity of $f_0$ bounds its objective. Letting $ϵ\downarrow 0$ proves the convex inequality. If one perturbation value is $-\mathrm{\infty }$, arbitrarily low feasible objective values and the same convex-combination argument give value $-\mathrm{\infty }$ at each strict convex combination with another feasible perturbation.

Let $S=\mathrm{aff}D$ and $Y=A(S)-b$. Since the Slater point $x_s$ lies in every relative-interior domain, $x_s$ has a relative neighborhood in $S$ contained in $D$. Each $g_i$ is finite and convex on its domain and continuous near $x_s$ in its affine hull by [F4]; after intersecting finitely many neighborhoods, there are a relative neighborhood $U_s\subseteq D$ of $x_s$ and $\eta >0$ with $g_i(y)<-\eta$ on $U_s$ for every $i$ (take any $\eta >0$ if $m=0$). The affine map $y\mapsto Ay-b$ from $S$ onto $Y$ has a linear right inverse on its direction space: choose preimages of a finite basis of $Y$. Consequently, its image of $U_s$ contains a relative neighborhood $W$ of $0$ in $Y$. For every $v\in W$, choose the corresponding $y\in U_s$; for every $u\in {\prod }_i(-\eta ,\mathrm{\infty })$, that $y$ satisfies $g_i(y)<u_i$ and $Ay-b=v$. Thus $P(u,v)<+\mathrm{\infty }$ on a relative neighborhood of $0$ in $Z={\mathbb{R}}^m\times Y$.

The value $P(0,0)=p^{\ast }$ is finite. The convexity from step 1.1 and the neighborhood from step 1.2 imply that $P$ never equals $-\mathrm{\infty }$: if $P(z)=-\mathrm{\infty }$ for some perturbation $z$, choose a small $\theta >0$ so $-\theta z\mathrm{/}(1-\theta )$ lies in that neighborhood. Convexity would give $P(0)\le \theta P(z)+(1-\theta )P(-\theta z\mathrm{/}(1-\theta ))=-\mathrm{\infty }$, contrary to finiteness. Hence $P$ is proper and $0\in \mathrm{ri}(\mathrm{dom}P)$ relative to $Z$. By [F3] there is a linear functional $\mathrm{\ell }(u,v)=a^{T}u+c(v)$ on $Z$ such that $P(u,v)\ge p^{\ast }+a^{T}u+c(v)$.

Relaxing one inequality right-hand side cannot increase the infimum, so $P(t{e}_i,0)\le P(0,0)=p^{\ast }$ for small $t>0$. The support inequality in step 2.1 gives $P(t{e}_i,0)\ge p^{\ast }+t{a}_i$, hence $a_i\le 0$. Define ${\lambda }_{\ast }=-a\ge 0$ and extend $c$ from the finite-dimensional subspace $Y$ to a linear functional on ${\mathbb{R}}^p$ by extending a basis; write the negative of this extension as ${\nu }_{\ast }^T$. For any $x\in D$, the perturbation $(g(x),Ax-b)$ is feasible using $x$ itself, so $f_0(x)\ge P(g(x),Ax-b)\ge p^{\ast }+a^{T}g(x)+c(Ax-b)\mathrm{.}$ Thus $L(x,{\lambda }_{\ast },{\nu }_{\ast })\ge p^{\ast }$ for all $x$, and $q({\lambda }_{\ast },{\nu }_{\ast })\ge p^{\ast }$.

At the primal minimizer, weak duality [F2] and feasibility give $p^{\ast }\le q({\lambda }_{\ast },{\nu }_{\ast })\le L(x_{\ast },{\lambda }_{\ast },{\nu }_{\ast })=p^{\ast }+{\sum }_i{\lambda }_{\ast ,i}{g}_i(x_{\ast })\le p^{\ast }\mathrm{.}$ Every inequality is therefore equality. Since every summand ${\lambda }_{\ast ,i}{g}_i(x_{\ast })$ is nonpositive, their sum being zero forces each one to be zero. Thus $q({\lambda }_{\ast },{\nu }_{\ast })=p^{\ast }=d^{\ast }$, the dual supremum is attained, and complementarity holds.