# SOCP: Recovering primal from dual

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.

• 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... – GoHokies Nov 14 '16 at 19:18
• No problem, will do so after a few meetings today... – Justin Solomon Nov 14 '16 at 19:52
• 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? – Richard Zhang Nov 14 '16 at 20:47
• Yes, I have access to the $u$'s and the $\lambda$'s. – Justin Solomon Nov 14 '16 at 20:50
• OK, edited to make the question self-contained. But now I'm hoping you guys can help me solve it :-) – Justin Solomon Nov 14 '16 at 20:56

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.
• 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)$? – Justin Solomon Nov 15 '16 at 4:56