1
$\begingroup$

Consider the following second-order cone program (SOCP): $$ \begin{array}{rl} \min_x & c^\top x\\ \mathrm{s.t.} & \|A_ix+b_i\|_2 \leq c_i^\top x+d_i \ \forall i \end{array} $$

Suppose I solve the dual of a second-order cone program (SOCP) for the dual variables $\lambda_i,u_i$: $$ \begin{array}{rl} \max_{\lambda,u} & -(\lambda^\top d + \sum_i u_i^\top b_i)\\ \mathrm{s.t.} & \sum_i A_i^\top u_i -\lambda_i c_i = 0\ \forall i\\ &\|u_i\|_2\leq\lambda_i \ \forall i \end{array} $$

Is there a standard technique for recovering the primal variable $x$ from $(\lambda,u)$, assuming the SOCP exhibits strong duality?


Note: I am using the notation of this document.

When I attempt to plug $\lambda$ back into the Lagrange multiplier expression, everything seems to just cancel out! I managed to solve the dual of my SOCP using an elegant optimization technique but am struggling to translate to the original primal problem.

$\endgroup$
  • 3
    $\begingroup$ Justin, would you mind making your question self-contained? Just in case the page you linked to gets removed at some point in the future... $\endgroup$ – GoHokies Nov 14 '16 at 19:18
  • $\begingroup$ No problem, will do so after a few meetings today... $\endgroup$ – Justin Solomon Nov 14 '16 at 19:52
  • $\begingroup$ Note that if you solve the SOCP as a linear conic program, then $u_1,\ldots,u_m$ are also dual variables. Do you have access to these too? $\endgroup$ – Richard Zhang Nov 14 '16 at 20:47
  • $\begingroup$ Yes, I have access to the $u$'s and the $\lambda$'s. $\endgroup$ – Justin Solomon Nov 14 '16 at 20:50
  • $\begingroup$ OK, edited to make the question self-contained. But now I'm hoping you guys can help me solve it :-) $\endgroup$ – Justin Solomon Nov 14 '16 at 20:56
3
$\begingroup$

The standard technique is to solve the optimality conditions as a linear system of equations. Let us rewrite your problem into standard form $$ \begin{align*} \text{maximize } & -c^{T}x\text{ s.t. }\begin{bmatrix}-c_{i}^{T}\\ -A_{i} \end{bmatrix}x+\begin{bmatrix}t_{i}\\ z_{i} \end{bmatrix}=\begin{bmatrix}d_{i}\\ b_{i} \end{bmatrix},\;\begin{bmatrix}t_{i}\\ z_{i} \end{bmatrix}\in\mathrm{SOC},\\ \text{minimize } & \sum_{i=1}^{m}\begin{bmatrix}d_{i}\\ b_{i} \end{bmatrix}^{T}\begin{bmatrix}\lambda_{i}\\ u_{i} \end{bmatrix}\text{ s.t. }\sum_{i=1}^{m}\begin{bmatrix}-c_{i}^{T}\\ -A_{i} \end{bmatrix}^{T}\begin{bmatrix}\lambda_{i}\\ u_{i} \end{bmatrix}=-c,\;\begin{bmatrix}\lambda_{i}\\ u_{i} \end{bmatrix}\in\mathrm{SOC}. \end{align*} $$ The classical optimality conditions are written $$ \begin{align*} \sum_{i=1}^{m}\begin{bmatrix}-c_{i}^{T}\\ -A_{i} \end{bmatrix}^{T}\begin{bmatrix}\lambda_{i}\\ u_{i} \end{bmatrix} & =-c,\\ \begin{bmatrix}-c_{i}^{T}\\ -A_{i} \end{bmatrix}x+\begin{bmatrix}t_{i}\\ z_{i} \end{bmatrix} & =\begin{bmatrix}b_{i}\\ d_{i} \end{bmatrix}\;\forall i\in\{1,\ldots,m\},\\ \begin{bmatrix}\lambda_{i} & u_{i}^{T}\\ u_{i} & \lambda_{i}I \end{bmatrix}\begin{bmatrix}t_{i}\\ z_{i} \end{bmatrix} & =0\qquad\forall i\in\{1,\ldots,m\}, \end{align*} $$ see Theorem 16, Alizadeh & Goldfarb, Second-order cone programming, Math. Program., 2001. Notice that the system of equations is linear over $x,t_{i},z_{i}$ with $\lambda_{i},u_{i}$ fixed. Substituting $\lambda_{i}\gets\lambda_{i}^{\star}$ and $u_{i}\gets u_{i}^{\star}$ and solving the linear equations $$ \begin{bmatrix}\lambda_{i} & u_{i}^{T}\\ u_{i} & \lambda_{i}I \end{bmatrix}\left(\begin{bmatrix}c_{i}^{T}\\ A_{i} \end{bmatrix}x+\begin{bmatrix}b_{i}\\ d_{i} \end{bmatrix}\right)=0 \qquad \forall i\in\{1,\ldots,m\} $$ yields the primal-optimal solution $x^{\star},t_{i}^{\star},z_{i}^{\star}$, assuming that the equations are full-rank or overdetermined (given strong duality, a zero-residual solution must exist). If the equations are underdetermined, then we would have to reimpose the constraint $[t_i^\star, z_i^\star]\in \mathrm{SOC}$ and solve a SOCP feasibility problem.

$\endgroup$
  • $\begingroup$ Thanks for sharing this! To make sure I understand properly, what is SOC here? It looks like your notation differs a bit from the Alizadeh/Goldfarb paper (sorry, I'm new to this area!). $\endgroup$ – Justin Solomon Nov 15 '16 at 3:28
  • $\begingroup$ SOC = second order cone. My notation was adopted to match the ones in the prompt. $\endgroup$ – Richard Zhang Nov 15 '16 at 4:32
  • $\begingroup$ Yes, I guessed this much :-) . So, (t; z) in SOC means $||z||\leq t$? If so, could their be a typo in the first line of math? It looks like $t_i=-c_i^\top x - d_i$ -- maybe there should be a minus rather than a plus before the $(t_i,z_i)$? $\endgroup$ – Justin Solomon Nov 15 '16 at 4:56
  • $\begingroup$ Fixed. Actually, the dual problem in the prompt has a sign error. Also thought about it a little more and realized that the optimality conditions may not be enough. I'd have to think about it more. $\endgroup$ – Richard Zhang Nov 15 '16 at 22:29
  • $\begingroup$ Thanks! Can you correct the sign error on the prompt as well? $\endgroup$ – Justin Solomon Nov 15 '16 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.