1
$\begingroup$

I have an optimization problem with second-order cone constraints and linear inequalities and inequalities (shown below). I want to formulate the dual, but have been having trouble.

$\begin{equation} \underset{p,t}{\text{min }}\sum_{j=1}^nq_j{p}_j\\ \text{subject to}\\ \sum_j{p_j}=1\\ -p_j \leq 0, \quad \forall j\\ \sum_j{t_j} \leq 5\\ \lVert \left( \begin{array}{c} 2p_j-a_j \\ p_j-2t_j \end{array} \right) \lVert_2 \leq p_j+2t_j,\quad \forall j \end{equation} $

where $a_j$ and $q_j$ are parameters. My question is, what is the dual formulation for the above? Here's work I've done so far. First I simplify the L2 norm by defining new variables as follows:

$\begin{equation} \underset{p,t,u,v,w}{\text{min }}\sum_{j=1}^n{p}_j\\ \text{subject to}\\ \sum_j{p_j}=1\\ -p_j \leq 0, \quad \forall j\\ \sum_j{t_j} \leq 5\\ u_j=2p_j-a_j ,\quad \forall j\\ v_j=p_j-2t_j,\quad \forall j\\ w_j=p_j+2t_j,\quad \forall j\\ \lVert \left( \begin{array}{c} u_j \\ v_j \end{array} \right) \lVert_2 \leq w_j,\quad \forall j \end{equation} $

Now I look at literature for second-order cone programming duality to see if I can directly reformulate the dual. I found that this paper shows the dual for a SOCP program with linear equality constraints as follows:

$\begin{equation} \text{(SOCP) } \underset{x}{\text{min }} f^\top x\\ \text{subject to}\\ \lVert A_i x - b_i \lVert_2 \leq c_ix-d_i, \quad \forall i\\ Hx=h \end{equation}$

and they show that the dual of this program is

$\begin{equation} \underset{\gamma,\mu,\lambda}{\text{max }} b^\top z + d^\top \omega + h^\top \nu\\ \text{subject to}\\ f=A^\top z + C^\top \omega + H^\top \nu\\ \lVert z^i \lVert_2 \leq \omega_i,\quad \forall i \end{equation}$

However, the components in the L2-norm in my problem seem to stump me.

$\endgroup$
  • $\begingroup$ I suspect something is amiss: your objective is $\sum_j p_j$, but your first constraint fixes that quantity at $1$. Therefore, if the problem is feasible, the objective is $1$, regardless. $\endgroup$ – Michael Grant Feb 12 '14 at 15:46
  • $\begingroup$ Ahh yes, that is true - I just edited and added a coefficient for the objective function. I didn't originally add to post because of either simplification or carelessness, probably the latter. $\endgroup$ – holger3000 Feb 12 '14 at 16:01
1
$\begingroup$

My preference is to build the Lagrangian right from the original problem if at all possible. Define the multipliers as follows:

  • $v$ for the equality constraint
  • $w_p\in\mathbb{R}^n_+$ for the $p$ inequalities
  • $w_t\in\mathbb{R}_+$ for the $t$ inequality
  • $(y_{j,1},y_{j,2},z_j)\in\mathbb{R}^3$ for each of the second-order cone constraints, each of which lies the same second-order cone $\|[y_{j,1}~y_{j,2}]\|\leq z_j$.

The Lagrangian is $$L = q^Tp - v(\vec{1}^Tp-1) - w_p^T p - w_t(5-\vec{1}^Tt) - \textstyle\sum_j (y_{j,1}(2p_j-a_j)+y_{j,2}(p_j-2t_j)+z_j(p_j+2t_j))$$ From this I can construct the dual by differentiating with respect to each primal variable to reveal the implicit equality constraints. This is what I obtained: $$\begin{array}{ll} \text{maximize} & v - 5 w_t + a^T \bar{y}_1 \\ \text{subject to} & q - v\vec{1} - w_p - 2 \bar{y}_1 - \bar{y}_2 - \bar{z} = 0 \\ & w_t\vec{1} + 2 \bar{y}_2 - 2 \bar{z} = 0 \\ & w_p \geq 0, ~ w_t \geq 0 \\ & \|[y_{j,1}~y_{j,2}]\|\leq z_j, ~ j=1,2,\dots,n \end{array}$$ where $\bar{y}_1$ is a vector containing the $y_{1,j}$ terms, $\bar{y}_2$ is a vector containing the $y_{2,j}$ terms, and $\bar{z}$ is a vector containing the $z_j$ terms.

It's not pretty, and I would double-check. But then again, your second-order cone constraints aren't pretty either :-)

$\endgroup$
2
$\begingroup$

The MOSEK modeling manual at http://docs.mosek.com/generic/modeling-a4.pdf has lot information about SOCP aka conic quadratic problems.

I would bring my problem to the form (3.28) and then I know the dual is (3.30). You can also use this reversely i.e. bring your problem to the form (3.30) and then the dual is (3.28). See page 27 and 28.

$\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.