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$
5
  • 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, 2016 at 19:18
  • $\begingroup$ No problem, will do so after a few meetings today... $\endgroup$ Nov 14, 2016 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$ Nov 14, 2016 at 20:47
  • $\begingroup$ Yes, I have access to the $u$'s and the $\lambda$'s. $\endgroup$ Nov 14, 2016 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$ Nov 14, 2016 at 20:56

1 Answer 1

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$
7
  • $\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$ Nov 15, 2016 at 3:28
  • $\begingroup$ SOC = second order cone. My notation was adopted to match the ones in the prompt. $\endgroup$ Nov 15, 2016 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$ Nov 15, 2016 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$ Nov 15, 2016 at 22:29
  • $\begingroup$ Thanks! Can you correct the sign error on the prompt as well? $\endgroup$ Nov 15, 2016 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.