1
$\begingroup$

I'm trying to understand the difference between the following two definitions of a SOCP (second-order cone program). The first way I've seen a primal-dual SOCP define is as follows:

The primal problem is, \begin{equation} \begin{aligned} &\min_x && c^T x \\ &\text{s.t.} && Ax=b \\ &&& x \in K \end{aligned} \tag{P1} \end{equation}

and dual problem, \begin{equation} \begin{aligned} &\max_y && b^T y \\ &\text{s.t.} && A^Ty + s = c \\ &&& s \in K^* \end{aligned} \tag{D1} \end{equation}

where $K$ and $K^{*}$ are second-order cones. The second way I've seen an SOCP defined is as follows (as given under the "Linear Cone Programs" section of the following webpage: http://cvxopt.org/userguide/coneprog.html):

The primal problem is, \begin{equation} \begin{aligned} &\min_x && c^T x \\ &\text{s.t.} && Ax=b \\ &&& Gx + s = h \\ &&& s \in K \end{aligned} \tag{P2} \end{equation}

and the dual problem is, \begin{equation} \begin{aligned} &\max_{z,y} &&-h^{T}z-b^{T}y \\ &\text{s.t.} && G^{T}z+A^{T}y+c=0 \\ &&& z \in K^{*} \end{aligned} \tag{D2} \end{equation}

How exactly can the above two primal-dual problems define the same thing? I'm rather confused, and any help would be much appreciated.

$\endgroup$
  • 1
    $\begingroup$ There's something wrong with your third problem above---it's missing an objective function. $\endgroup$ – Michael Grant Feb 16 '18 at 19:41
  • $\begingroup$ Why do we only require $z \in K^*$ in D2? I would have thought there'd be three dual variables, $z, y, w$ where $w$ is the dual variable corresponding to $s \in K$, so that (if I'm not mistaken) the Lagrangian would be $\langle x, G^T z + A^T y + c, x \rangle + \langle s, z + w \rangle - z^T h - y^T b$? $\endgroup$ – jjjjjj Feb 17 '18 at 16:46
1
$\begingroup$

Just looking at P1 and P2, consider taking $G = -I$ and $h=0$. Thus, the the second constraint in P2 gives $$ -Ix + s = 0 \iff x = s $$ so now we can formulate P2 as \begin{align} & \underset{x}{\text{minimize}} && c^T x \\ & \text{subject to} && Ax = b \\ &&& x \succeq_K 0 \end{align}

so P2 is a more general form of P1. I'm not sure if we can go the other way...

$\endgroup$

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.