Weak Slater's condition

Question

The famous Slater's condition states that if a convex optimization problem has a feasible point $x_0$ in the relative interior of the problem domain and every inequality constraint $f_i(x) \le 0$ is strict at $x_0$, i.e. $f_i(x_0) < 0$, then strong duality holds for the problem. I know how to prove this.

The weak Slater's condition is same as its strong form, but it only requires every non-affine inequality constraint $f_i(x) \le 0$ is strict at $x_0$. The weak condition also implies strong duality. But I don't know how to prove it.

Answer 1

Notice that Slater's condition does not assume that $A$ is full row rank, this is done only in the proof to simplify it (to get a contradiction at the end of the proof). Hence you can convert the affine constraints to the form $Cx\leq 0$, then add a slack variable $s\geq 0$ and get $Cx=-s$. In the same way the proof has a rank assumption on $A$ you can assume the same on the concatenation $(C|A)$. More importantly, notice that all the conditions together eventually imply that the de facto relative interior is not empty, this is the real meaning of the differentiation between affine and non-affine constraints. Recall that the constraints eventually define "true" feasible region, and splitting that region between a set $D$ and other constraints is a notation difference only (for convenience purposes).

At the end of the day, Slater's condition means that the "true" feasible set is convex. Because if the intersection of the set $D$ with a non-affine constraint is of the form $f_i(x)=0$, we have a non convex de facto set. If the same intersection between $D$ and an affine constraint is of the form $f_j(x)=0$, we still have a convex feasible region. And since the proof of strong duality relies on strict separation we must have a feasible convex set with non-empty interior.

Answer 2

Indeed, since weaker form of Slater condition requires less, it implies the stronger form, and neither can I find a proof of it in Boyd's textbook.

My solution is that if there are $p_1$ inequalities that are affine and $p_2$ inequalities that are not necessarily affine, we can always divide $D$ into $2^{p_1}$ subregions, $D_0,\cdots,D_{p_1-1}$, in which

$D_i=\{\mathbf{x}|\mathbf{x}\in D,\quad f_{i}(\mathbf{x})=0\quad if\quad i\equiv 0({\rm mod}2^{i-1})\quad otherwise \quad f_i(\mathbf{x})<0\quad {\rm for}\quad i=1,\cdots,p_1\}$

And for every non-empty subregion, a subproblem $P_i$ can be defined, by turning all non-strict affine inequalities to equality constraints. Similary, we can define $L_i$, $p^*_i$, $d^*_i$.

I will neglect details here, but it's not hard to prove that in each region $L=L_i$, and it can be further proved that for each non-empty region $D_i$, $p^*\leqslant p^*_i$, $d^*_i \leqslant d^*$.

The feasible point $\mathbf{x_0}$ definitely belongs to one of the subregions $D_i$, meaning that this region is non-empty. More importantly, existence of $\mathbf{x_0}$ makes strong Slater condition hold for problem $P_i$, thus $p^*\leqslant p^*_i = d^*_i \leqslant d^*$. Due to weak duality $p^*\geqslant d^*$, we can only have $p^*=d^*$, which means strong duality holds.