Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes

Abstract

Solving large scale nonlinear optimization problems requires either significant computing resources or the development of specialized algorithms. For Linear Programming (LP) problems, decomposition methods can take advantage of problem structure, gradually constructing the full problem by generating variables or constraints. We first present a direct adaptation of the Column Generation (CG) methodology for nonlinear optimization problems, such that when optimizing over a structured set ${\mathcal {X}}$ plus a moderate number of complicating constraints, we solve a succession of (1) restricted master problems on a smaller set ${\mathcal {S}}\subset {\mathcal {X}}$ and (2) pricing problems that are Lagrangean relaxations wrt the complicating constraints. The former provides feasible solutions and feeds dual information to the latter. In turn, the pricing problem identifies a variable of interest that is then taken into account into an updated subset ${\mathcal {S}}'\subset {\mathcal {X}}$. Our approach is valid whenever the master problem has zero Lagrangean duality gap wrt to the complicating constraints, and not only when ${\mathcal {S}}$ is the convex hull of the generated variables as in CG for LPs, but also with a variety of subsets such as the conic hull, the linear span, and a special variable aggregation set. We discuss how the structure of ${\mathcal {S}}$ and its update mechanism influence the number of iterations required to reach near-optimality and the difficulty of solving the restricted master problems, and present linearized schemes that alleviate the computational burden of solving the pricing problem. We test our methods on synthetic portfolio optimization instances with up to 5 million variables including nonlinear objective functions and second order cone constraints. We show that some CGs with linearized pricing are 2–3 times faster than solving the complete problem directly and are able to provide solutions within 1% of optimality in 6 h for the larger instances, whereas solving the complete problem runs out of memory.

Appendices

Appendix A: Proof of Example 4

We necessarily have $y_2=x_3=x_4=x_5=x_6=0$, $y_1=1-x_1$ and $x_2=1$, which turns the SDP constraint into $x_1\geqslant 0$ and we have $\omega ({\mathcal {X}})=0$. The conic dual of the latter problem is

$$\begin{aligned} \omega ':=\max _{\lambda }\left\{ -\lambda _1-\lambda _2 : \begin{pmatrix} \lambda _1&{}\lambda _4&{}\lambda _5\\ \lambda _4&{}\lambda _2&{}\lambda _6\\ \lambda _5&{}\lambda _6&{}\lambda _3 \end{pmatrix} \succeq 0,\quad 1-\lambda _2+2\lambda _5=0,\quad \lambda _1=0 \right\} . \end{aligned}$$

We necessarily have $\lambda _1=\lambda _4=\lambda _5=0$, $\lambda _2=1$, which turns the SDP constraint into $\lambda _3\geqslant \lambda _6^2$ and we have $\omega '=-1<0=\omega ({\mathcal {X}})$, proving that $P({\mathcal {X}})$ does not satisfy Assumption 1.

Now, by construction ${\mathcal {S}}\subset {\mathcal {X}}$ and $P({\mathcal {S}})$ is a feasible LP that always satisfies Assumption 1. $\square$

Appendix B: Proof of Proposition 1

We prove that some $({{\tilde{x}}}, {{\tilde{y}}})$ is strictly feasible for $P({\mathcal {S}})$. Because $-g({{\bar{x}}},{{\bar{y}}})\in \text {relint }{\mathcal {C}}$ and ${\mathcal {C}}$ is proper, there is $\rho >0$ such that ${\mathcal {B}}(-g({{\bar{x}}},\bar{y}),\rho )\subset \text {relint }{\mathcal {C}}$. Consider $({{\hat{x}}},\hat{\theta })$ strictly feasible for ${\mathcal {S}}$ and $\epsilon >0$ and ${\tilde{x}}$ as follows:

$$\begin{aligned} \epsilon = \min \left\{ 1, \frac{\rho }{L || {{\hat{x}}} - {{\bar{x}}} ||}\right\} ,&\quad {{\tilde{x}}} = {{\bar{x}}} + \epsilon ({{\hat{x}}} - {{\bar{x}}}). \end{aligned}$$

Because ${{\bar{x}}}\in {\mathcal {S}}$ and $({{\hat{x}}},{{\hat{\theta }}})$ is strictly feasible for ${\mathcal {S}}$, there exists ${{\bar{\theta }}}$ such that $\phi ({{\bar{x}}}, {{\bar{\theta }}})=0$, $-\gamma ({{\bar{x}}}, {{\bar{\theta }}})\in {\mathcal {K}}$, $\phi ({{\hat{x}}}, {{\hat{\theta }}})=0$ and $-\gamma ({{\hat{x}}}, {{\hat{\theta }}})\in \text {relint }{\mathcal {K}}$. $\phi$ being linear, defining ${{\tilde{\theta }}} = {{\bar{\theta }}}+\epsilon ({{\hat{\theta }}} - \bar{\theta })$, we immediately have $\phi ({{\tilde{x}}},{{\tilde{\theta }}})=0$. Further, $\epsilon >0$, ${\mathcal {K}}$ is proper, $-\gamma ({{\bar{x}}},\bar{\theta }) \in {\mathcal {K}}$ and $-\gamma ({{\hat{x}}},{{\hat{\theta }}}) \in \text {relint }{\mathcal {K}}$ so we obtain $-\epsilon \gamma ({{\hat{x}}},{{\hat{\theta }}})-(1-\epsilon ) \gamma ({{\bar{x}}},\bar{\theta })\in \text {relint }{\mathcal {K}}$. Because $\gamma$ is ${\mathcal {K}}$-convex and $\epsilon \in ]0,1]$ we obtain $-\gamma ({{\tilde{x}}},{{\tilde{\theta }}})\in \text {relint }{\mathcal {K}}$. We just proved that $({{\tilde{x}}},{{\tilde{\theta }}})$ is strictly feasible for ${\mathcal {S}}$. We finish by proving that $({{\tilde{x}}}, {\bar{y}})$ is strictly feasible for $P({\mathcal {S}})$: By definition we have $\rho \geqslant L\epsilon || {{\hat{x}}} - {{\bar{x}}} ||=L||{{\tilde{x}}}- {{\bar{x}}}|| =L||({{\tilde{x}}}- {{\bar{x}}};{{\bar{y}}}- {{\bar{y}}})||$. Because g is L-Lipschitz, we obtain that $\rho \geqslant ||g({{\tilde{x}}},{{\bar{y}}}) - g({{\bar{x}}},{{\bar{y}}})||$, meaning that $-g({{\tilde{x}}},{{\bar{y}}}) \in {\mathcal {B}}(-g({\bar{x}}, {{\bar{y}}}),\rho )\subset \text {relint }{\mathcal {C}}$. Because $P({\mathcal {S}})$ is convex, Slater’s condition holds, thus finishing the proof. $\square$

Appendix C: Proof of Proposition 2

If $L({\mathcal {X}},\lambda ^k)$ satisfies the P-property wrt y, the problem in y given some $x\in {\mathcal {X}}$ is equivalent to the problem in y given $x=x^k$, i.e. for any $x\in {\mathcal {X}}$ we have

$$\begin{aligned}&\arg \min \limits _{y}\left\{ f\left( x,y\right) +\left\langle \lambda ^k , g\left( x,y\right) \right\rangle \right\} \\ \nonumber =&\arg \min \limits _{y}\left\{ f\left( x^k,y\right) + \left\langle \lambda ^k , g\left( x^k,y\right) \right\rangle \right\} . \end{aligned}$$

(13)

Because $P({\mathcal {S}}^k)$ satisfies Assumption 1, $(x^k,y^k)$ is optimal for $L({\mathcal {S}}^k,\lambda ^k)$, i.e.

$$\begin{aligned} \omega ({\mathcal {S}}^k,\lambda ^k)= \min _{x\in {\mathcal {S}}^k,y}\left\{ f\left( x,y\right) +\left\langle \lambda ^k , g\left( x,y\right) \right\rangle \right\} =f\left( x^k,y^k\right) +\left\langle \lambda ^k , g\left( x^k,y^k\right) \right\rangle . \end{aligned}$$

In consequence, $y^k\in \arg \min _{y}\{f(x^k,y)+\langle \lambda ^k , g(x^k,y)\rangle \}$. Using equality (13) finishes the proof. $\square$

Appendix D: Proof of Lemma 1

First, for any $t\in [0,1]$ and any pair $(u^1,u^2)\in {\mathcal {U}}\times {\mathcal {U}}$ we have: $t\varphi (u^1) +(1-t)\varphi (u^2) -\varphi (t u^1+(1-t)u^2) \in {\mathcal {K}}$. Given that $\lambda \in {\mathcal {K}}^*$ we have $\langle \lambda , t\varphi (u^1) +(1-t)\varphi (u^2) -\varphi (t u^1+(1-t)u^2) \rangle \geqslant 0$, meaning that

$$\begin{aligned}&t \underbrace{ \left\langle \lambda , \varphi \left( u^1\right) \right\rangle }_{ \psi \left( u^1\right) } +(1-t) \underbrace{ \left\langle \lambda , \varphi \left( u^2\right) \right\rangle }_{ \psi \left( u^2\right) } \geqslant \underbrace{ \left\langle \lambda , \varphi \left( t u^1+(1-t)u^2\right) \right\rangle }_{ \psi \left( t u^1+(1-t)u^2\right) } \quad .\square \end{aligned}$$

Appendix E: Proof of Lemma 2

The linear approximation of $\psi$ at ${{\bar{u}}}$ is ${{\bar{\psi }}}[\bar{u}](u):= \psi ({{\bar{u}}})+ \langle \nabla \psi [{{\bar{u}}} ],u-{{\bar{u}}}\rangle$. By definition, for every $u\in {\mathcal {U}}$:

$$\begin{aligned} \left\langle \nabla \psi \left[ {{\bar{u}}} \right] ,u-{{\bar{u}}}\right\rangle =&\lim \limits _{\epsilon \rightarrow 0} \frac{\psi \left( {{\bar{u}}} +\epsilon \left( u-{{\bar{u}}}\right) \right) -\psi \left( {{\bar{u}}}\right) }{\epsilon }\\ =&\lim \limits _{\epsilon \rightarrow 0} \frac{ \left\langle \lambda , \varphi \left( {{\bar{u}}} +\epsilon \left( u-\bar{u}\right) \right) \right\rangle -\left\langle \lambda , \varphi \left( {{\bar{u}}}\right) \right\rangle }{\epsilon }\\&= \left\langle \lambda , \lim \limits _{\epsilon \rightarrow 0} \frac{ \varphi \left( {{\bar{u}}} +\epsilon \left( u-{{\bar{u}}}\right) \right) -\varphi \left( {{\bar{u}}}\right) }{\epsilon } \right\rangle = \left\langle \lambda , D\varphi \left( {{\bar{u}}} \right) \left( u-{{\bar{u}}}\right) \right\rangle , \end{aligned}$$

implying that ${{\bar{\psi }}}[{{\bar{u}}}](u)= \langle \lambda , \varphi (\bar{u})\rangle + \langle \lambda , D\varphi ({{\bar{u}}} ) (u-{{\bar{u}}}) \rangle =\langle \lambda , {{\bar{\varphi }}}[{{\bar{u}}}](u)\rangle$. $\square$

Appendix F: Proof of Lemma 3

By convexity of ${\mathcal {U}}$ and optimality of $u^*$, for any $\epsilon \in ]0,1]$ and any $u\in {\mathcal {U}}$ we have $\varphi (u^ *)\leqslant \varphi (u^ *+\epsilon (u-u^ *))$, i.e.

$$\begin{aligned} \frac{\varphi \left( u^ *+\epsilon \left( u-u^*\right) \right) -\varphi \left( u^*\right) }{\epsilon }\geqslant 0,&\quad \forall \epsilon \in ]0,1], \forall u \in {\mathcal {U}}, \end{aligned}$$

which implies that when $\epsilon \rightarrow 0$, for any $u \in {\mathcal {U}}$ we have $\left\langle \nabla \varphi \left( u^ *\right) ,u-u^ *\right\rangle \geqslant 0$, i.e.

$$\begin{aligned} \underbrace{ \varphi \left( u^*\right) +\left\langle \nabla \varphi \left( u^ *\right) ,u-u^ *\right\rangle }_{ \bar{\varphi }\left[ u^*\right] (u) } \geqslant \underbrace{ \varphi \left( u^*\right) +\left\langle \nabla \varphi \left( u^ *\right) ,u^*-u^ *\right\rangle }_{ \bar{\varphi }\left[ u^*\right] \left( u^*\right) },&\quad \forall u \in {\mathcal {U}}, \end{aligned}$$

meaning that $u^*$ is optimal for $\min _{u\in {\mathcal {U}}} \bar{\varphi }[u^*](u)$ and implying $\omega ^ *= {{\bar{\omega }}}[u^ *]$. $\square$

Appendix G: Proof of Proposition 3

First, notice that the following holds:

$$\begin{aligned} {{\bar{f}}} \left[ x^k,y^k\right] (x,y)=&f\left( x^k,y^k\right) +\left\langle \nabla _x f\left( x^k,y^k\right) ,x-x^k\right\rangle +\left\langle \nabla _y f\left( x^k,y^k\right) ,y-y^k\right\rangle \\ {{\bar{g}}} \left[ x^k,y^k\right] (x,y)=&g\left( x^k,y^k\right) +D_x g\left( x^k,y^k\right) \left( x-x^k\right) +D_y g\left( x^k,y^k\right) \left( y-y^k\right) \end{aligned}$$

In consequence, we have that:

$$\begin{aligned} \nonumber \bar{\omega }\left[ x^{k},y^k\right] \left( {\mathcal {X}},\lambda ^{k}\right) =&f\left( x^k,y^k\right) -\left\langle \nabla _x f\left( x^k,y^k\right) ,x^k\right\rangle -\left\langle \nabla _y f\left( x^k,y^k\right) ,y^k\right\rangle \\ \nonumber&+\left\langle \lambda ^{k} , g\left( x^k,y^k\right) -D_x g\left( x^k,y^k\right) x^k -D_y g\left( x^k,y^k\right) y^k\right\rangle \\ \nonumber&+\min \limits _{x\in {\mathcal {X}}} \left\{ \left\langle \nabla _x f\left( x^k,y^k\right) ,x\right\rangle +\left\langle \lambda ^{k} , D_x g\left( x^k,y^k\right) x\right\rangle \right\} \\&+\min \limits _{y} \left\{ \left\langle \nabla _y f\left( x^k,y^k\right) ,y\right\rangle +\left\langle \lambda ^{k} , D_y g\left( x^k,y^k\right) y\right\rangle \right\} , \end{aligned}$$

(14)

which is separable in x and y. Wlog we can assume that (14) attains its minimum, otherwise the master problem is unbounded and we can stop. Under this assumption, the first order optimality conditions in y for the master problem $P({\mathcal {S}}^k)$ are $\nabla _y f(x^k,y^k)+D_y g ( x^k,y^k)^*\lambda ^k =0$, in turn implying that for any y: $\langle \nabla _y f(x^k,y^k),y\rangle +\langle \lambda ^k,D_y g ( x^k,y^k) y\rangle =0$, meaning that the objective function of (14) is identically zero. $\square$

Appendix H: Proof of Proposition 5

Let us define the following subsets of [p]:

$$\begin{aligned} {\mathcal {J}}_+:=\left\{ j\in [p]: \gamma _j<0, \alpha _j>0 \right\} ,&\quad {\mathcal {J}}_-:=\left\{ j\in [p]: \gamma _j>0, \alpha _j<0 \right\} ,\\ {\mathcal {J}}_0:=\left\{ j\in [p]: \gamma _j, \alpha _j\geqslant 0 \right\} ,&\quad {\mathcal {J}}_\mu :=\left\{ j\in [p]: \gamma _j, \alpha _j\leqslant 0 \right\} . \end{aligned}$$

First notice that we can fix beforehand the following variables:

$$\begin{aligned} z^*_j = {\left\{ \begin{array}{ll} \mu _j&{}\text { If } j\in {\mathcal {J}}_\mu \\ 0&{}\text { If } j\in {\mathcal {J}}_0. \end{array}\right. } \end{aligned}$$

Next, for every $j\in {\mathcal {J}}_-$, we use the change of variable $z_j\leftarrow \mu _j-z_j$, obtaining the following problem:

$$\begin{aligned} \omega ^*:= \sum \limits _{j\in {\mathcal {J}}_-\cup {\mathcal {J}}_\mu } \gamma _j\mu _j + \min \limits _{z}\quad&\sum \limits _{j\in {\mathcal {J}}_+\cup {\mathcal {J}}_-} {{\hat{\gamma }}}_jz_j \\ \text {s.t.:}\quad&\sum \limits _{j\in {\mathcal {J}}_+\cup {\mathcal {J}}_-} {{\hat{\alpha }}}_jz_j \leqslant {{\hat{\beta }}} \\&z_j\in \left[ 0,\mu _j\right] ,&\forall j \in {\mathcal {J}}_+\cup {\mathcal {J}}_- \end{aligned}$$

where ${{\hat{\beta }}}:= \beta -\sum _{j\in {\mathcal {J}}_-\cup {\mathcal {J}}_\mu } \alpha _j \mu _j$ and:

$$\begin{aligned} {{\hat{\alpha }}}_j:= {\left\{ \begin{array}{ll} \alpha _j&{} \text { if } j\in {\mathcal {J}}_+\\ -\alpha _j&{} \text { if } j\in {\mathcal {J}}_- \end{array}\right. }{} & {\quad\quad\quad} {{\hat{\gamma }}}_j:= {\left\{ \begin{array}{ll} \gamma _j &{}\text { if } j\in {\mathcal {J}}_+\\ -\gamma _j&{}\text { if } j\in {\mathcal {J}}_-. \end{array}\right. } \end{aligned}$$

The latter is a knapsack problem with positive capacity ${{\hat{\beta }}}$ and weights ${{\hat{\alpha }}}_j$ that can be solved by sorting the remaining indices $j\in {\mathcal {J}}_+\cup {\mathcal {J}}_-$ in increasing disutility ${{\hat{\gamma }}}_j/{{\hat{\alpha }}}_j$ and filling the capacity constraint until no variable is available or the capacity constraint is tight. $\square$

Appendix I: Proof of Proposition 6

It is enough to show that $(u^*,( \pi ^*,\hat{\lambda },{\hat{\lambda }}_0))$ satisfies the KKT conditions for (9):

$$\begin{aligned} \phi \left( u^*\right) \leqslant 0,\quad -\left( \gamma \left( u^*\right) ,\gamma _0\right) \in {\mathcal {L}}_2 \end{aligned}$$

(15a)

$$\begin{aligned} \pi ^*\geqslant 0,\quad \phi \left( u^*\right) ^\top \pi ^*= 0 \end{aligned}$$

(15b)

$$\begin{aligned} \left( {{\hat{\lambda }}},{\hat{\lambda }}_0\right) \in {\mathcal {L}}_2 \end{aligned}$$

(15c)

$$\begin{aligned} \gamma \left( u^*\right) ^\top \hat{\lambda }+\gamma _0 {{\hat{\lambda }}}_0 = 0 \end{aligned}$$

(15d)

$$\begin{aligned} \nabla \varphi \left( u^*\right) + D\phi \left( u^*\right) ^\top \pi ^*+ D\gamma \left( u^*\right) ^\top {{\hat{\lambda }}} = 0. \end{aligned}$$

(15e)

(15a) and (15b) are trivially satisfied. Given that $-\gamma _0,\lambda ^*\geqslant 0$, the remaining conditions are equivalent to:

$$\begin{aligned} \left( \lambda ^*\right) ^2\left( \left| \left| \gamma \left( u^*\right) \right| \right| _2^2 -\gamma ^2_0\right) \leqslant 0\\ \lambda ^*\left( \left| \left| \gamma \left( u^*\right) \right| \right| _2^2 -\gamma ^2_0\right) = 0\\ \nabla \varphi \left( u^*\right) + D\phi \left( u^*\right) ^\top \pi ^*+ 2\lambda ^*D\gamma \left( u^*\right) ^\top \gamma \left( u^*\right) = 0, \end{aligned}$$

which are all implied by the KKT conditions for (10) at $(u^*,(\pi ^*,\lambda ^*))$. $\square$

Appendix J: Sparsity patterns for the enhanced models

Primal-dual interior point and Newton step Given a barrier parameter $\mu >0$ and an optimization problem $\min _{u}\{\varphi (u):\phi (u)\leqslant 0,\,Ru=s\}$, the barrier problem is defined as $\min _{u}\{\varphi (u)-\mu \sum _{i=1}^p\ln (-\phi _i(u)):Ru=s\}$. The first order optimality conditions for the barrier problem are the following perturbed conditions:

$$\begin{aligned} \nabla \varphi (u)+R^\top \pi +\beta ^\top D\phi (u)=0\\ \mu +\beta _i\phi _i(u)=0\\ Ru=s. \end{aligned}$$

The heavy works at each iteration of a primal-dual interior point algorithm occur during the Newton step, which consists in approximately solve the latter system of equations by solving in $(\Delta u,\Delta \beta , \Delta \pi )$ its following first-order approximation:

$$\begin{aligned} \begin{pmatrix} \!\nabla ^2 \varphi (u) \!+\!\sum \limits _{i=1}^p\beta _i\nabla ^2\phi (u) &{}\!\!\!\!D\phi (u)^\top &{}\!\!R^\top \\ \!\!\!\!\!\!-\text {diag}(\beta )D\phi (u) &{}\!\!\!-\text {diag}(\phi (u)) &{}\!\!\!0\\ \!\!R&{}\!\!\!\!\!\!\!0&{}\!\!\!0 \end{pmatrix} \begin{pmatrix} \Delta u\\ \Delta \beta \\ \Delta \pi \end{pmatrix} \!+\! \begin{pmatrix} \nabla \varphi (u)\!+\!R^\top \pi \!+\!\beta ^\top D\phi (u)\\ \left( \mu \!+\!\beta _i\phi _i(u)\right) _{i\in [p]}\\ Ru-s \end{pmatrix} \!=\!0 \end{aligned}$$

Monolithic formulation After the sparsity patterns in Figs. 8, 9, Figure 10 summarizes the number of nonzero coefficients present in the Newton step’s system.

Fig. 8

Number of nonzeroes per block: Non-enhanced model vs. enhanced

The non-enhanced version has $n^2+10n+T+2$ nonzeroes, with $3n+T+2$ unknowns, while the enhanced version sums $n(4S+8)+S(S(T+1)+2T+7)+2+T$ nonzeroes, with $3n+2ST+4S+T+2$ unknowns. We summarize these results in Table 10 to illustrate the benefits of using the enhanced version instead of the original version (recall that we used $S=20$):

Table 10 Benefits of enhancing the master problem on our instances

We can see that we can divide at least by a factor 100 the number of nonzero coefficients in our instances at the cost of having less than a percent of additional unknowns.

Fig. 9

Sparsity pattern of the Newton step’s matrix for P without numerical enhancement

Fig. 10

Sparsity pattern of the Newton step’s matrix for P with numerical enhancement

Pricing problems We only cover here the pricing problem when the variance constraint is considered as conic because the pricing when considering it as a single nonlinear constraint becomes very similar to the monolithic formulation. Given that the problem is splittable in each $x^t$ (and $x^0=y$), we successively solve the pricing for each $t\in \{0,...,T\}$, which is the problem for which we study the sparsity pattern. As per Fig. 11, Fig. 12 summarizes the number of nonzero coefficients present in the Newton step’s system.

Fig. 11

Number of nonzeroes per block: Non-enhanced model vs. enhanced

The non-enhanced version has $n_t^2+8n_t+1$ nonzeroes, with $3n_t+1$ unknowns, while the enhanced version sums $n_t(8+2S)+S(S+2)+1$ nonzeroes, with $3n_t+2S+1$ unknowns. We summarize these results in Table 11 to illustrate the benefits of using the enhanced version instead of the original version, where we can see again that we can divide at least by a factor 100 the number of nonzero coefficients in our instances at the cost of having less than a percent of additional unknowns.

Fig. 12

Sparsity patterns for the t-th pricing problem

Table 11 Benefits of enhancing the pricing problems on our instances

Appendix K: Proof of Proposition 7

The KKT conditions for (12) are

$$\begin{aligned} \phi \left( {{\tilde{u}}}\right) \leqslant 0,\quad -{{\tilde{\gamma }}}\left( {{\tilde{w}}}\right) \in {\mathcal {K}},\quad {{\tilde{v}}}=V{{\tilde{u}}},\quad {{\tilde{w}}}= W{{\tilde{u}}} \end{aligned}$$

(16a)

$$\begin{aligned} {{\tilde{\pi }}}\geqslant 0,\quad {{\tilde{\lambda }}}\in {\mathcal {K}}^*\end{aligned}$$

(16b)

$$\begin{aligned} \phi \left( {{\tilde{u}}}\right) ^\top {{\tilde{\pi }}} = 0,\quad \left\langle {{\tilde{\gamma }}}\left( {{\tilde{w}}}\right) ,{{\tilde{\lambda }}}\right\rangle = 0 \end{aligned}$$

(16c)

$$\begin{aligned} \nabla {{\tilde{\varphi }}}\left( \tilde{v}\right) - {{\tilde{\alpha }}} = 0,\quad D{{\tilde{\gamma }}}\left( {{\tilde{w}}}\right) ^*{{\tilde{\lambda }}} - {{\tilde{\beta }}} = 0 \end{aligned}$$

(16d)

$$\begin{aligned} D\phi \left( {{\tilde{u}}}\right) ^\top \tilde{\pi }+V^*{{\tilde{\alpha }}} +W^*{{\tilde{\beta }}} = 0. \end{aligned}$$

(16e)

Conditions (16a)–(16b)–(16c) represent respectively primal and dual feasibility and complementary slackness for (11) at $({{\tilde{u}}},(\tilde{\pi },{{\tilde{\lambda }}}))$. We now prove that (16d)–(16e) imply the last remaining KKT condition for (11): stationarity. Replacing (16d) in (16e) we obtain:

$$\begin{aligned} D\phi \left( {{\tilde{u}}}\right) ^\top \tilde{\pi }+V^*\nabla {{\tilde{\varphi }}}\left( {{\tilde{v}}}\right) +W^*D{{\tilde{\gamma }}}\left( {{\tilde{w}}}\right) ^*{{\tilde{\lambda }}} = 0. \end{aligned}$$

(17)

For any (u, v, w) such that $Vu=v$ and $Wu = w$, we have $\varphi (u) = {{\tilde{\varphi }}}(Vu)$ and $\gamma (u) = {{\tilde{\gamma }}}(Wu)$, implying that

$$\begin{aligned} \nabla \varphi (u)&= V^*\nabla {{\tilde{\varphi }}} \left( Vu\right) =V^*\nabla {{\tilde{\varphi }}} \left( v\right) \end{aligned}$$

(18a)

$$\begin{aligned} D\gamma (u)&= D{{\tilde{\gamma }}}\left( Wu\right) W = D\tilde{\gamma }\left( w\right) W. \end{aligned}$$

(18b)

Using (18) at $(u,v,w)=(\tilde{u},{{\tilde{v}}},{{\tilde{w}}})$ and replacing in (17) we get $D\phi ({{\tilde{u}}})^\top {{\tilde{\pi }}} +\nabla \varphi ({{\tilde{u}}}) +D\gamma ({{\tilde{u}}})^*{{\tilde{\lambda }}} = 0$. $\square$