Formulating the dual for an instance of a SOCP with linear constraints

Question

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.

Answer 1

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 :-)

Answer 2

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.