SOCP: Recovering primal from dual

Question

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.

Answer 1

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.