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.
Best Answer
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.