II.1.4.6: Majorizing Constraints

Consider the nonlinear programming problem of minimizing $f_0$ over $x\in\mathcal{X}$ under the functional constraints $f_i(x)\leq 0$ for $i=1,\cdots,n$.

Suppose $g_i$ majorizes $f_i$ on $\mathcal{X}$. Consider the algorithm $$x^{(k+1)}\in\mathop{\mathbf{argmin}}\limits_{x\in\mathcal{X}}\{g_0(x,x^{(k)})\mid g_i(x,x^{(k)})\leq 0\}.$$ Lipp and Boyd [2014] propose this algorthm for the case in which the $f_i$ are DC (differences of convex functions), as a generalization of the Convex-Concave procedure of II.1.3.2. We show the algorithm is stable. Remember that $x\in\mathcal{X}$ is feasible if it satisfies the functional constraints.

Result: If $x^{(k)}$ is feasible, then $x^{(k+1)}$ is feasible and $f_0(x^{(k+1)})\leq f_0(x^{(k)})$.

Proof: By majorization, for $i=1,\cdots,n$ we have $$f_i(x^{(k+1)})\leq g_i(x^{(k+1)},x^{(k)})\leq 0.$$ Second, the sandwich inequality says $$f_0(x^{(k+1)})\leq g_0(x^{(k+1)},x^{(k)})\leq g_0(x^{(k)},x^{(k)})=f_0(x^{(k)}).$$ QED

Note that it may not be necessary to majorize all functions $f_i$. Or, in other words, for some we can choose the trivial majorization $g_i(x,y)=f_i(x)$.