0
$\begingroup$

I'm new to convex analysis and got stuck when formulating a dual problem for a rotated conic programming problem. The problem is as follows.

$\min \ \ 2x_1+2x_2+x_3-3x_4$

$s.t. \ \ x_1 \leq 7$

$ \ \ \ \ \ \ \ \ 2x_1+x_3-x_2+0.5x_4=4$

$\ \ \ \ \ \ \ \ x_1+x_2-2x_4\leq 15$

$\ \ \ \ \ \ \ \ 2x_1x_2\geq x_3^2+x_4^2$

I followed the procedure here to derive the dual for this problem. First I write the Lagrangian:

$L=(2x_1+2x_2+x_3-3x_4)-y_1(7-x_1)-y_2(2x_1+x_3-x_2+0.5x_4-4)-y_3(15-x_1-x_2+2x_4)-(z_1x_1+z_2x_2+z_3x_3+z_4x_4),$

where $y$ is the multiplier of the affine constraints and $z$ is the one for the conic constraint. By finding the partial derivative of the corresponding variables, the dual can be written as:

$\max \ \ -7y_1+4y_2-15y_3$

$s.t. \ \ \ \ \ \ 2+y_1-2y_2+y_3-z_1=0$

$\ \ \ \ \ \ \ \ \ \ \ \ 1+y_2+y_3-z_2=0$

$\ \ \ \ \ \ \ \ \ \ \ \ 1-y_2-z_3=0$

$\ \ \ \ \ \ \ \ \ \ \ \ -3-0.5y_2-2y_3-z_4=0$

$\ \ \ \ \ \ \ \ \ \ \ \ 2z_1z_2\geq z_3^2+z_4^2$

Then I solve these two problems in MOSEK, and the primal yields -16.168 and the dual yields 18.723, both optimal. I know the strong duality holds only if Slater's condition holds, but since both the primal and dual are feasible, they should at least satisfy the weak duality, that is to say, the optimum of the primal problem should be greater than the dual problem, which is not the case of this one.

I think my dual might be wrong. The link I followed was for a non-rotated SOCP, and that might not work for this one. But I cannot find any other practical detail about writing the dual. Could you please help me with that?

$\endgroup$
1
$\begingroup$

You just made some minor errors. The method itself is generally OK.

First, the only way I can get $-16.168$ as primal objective is if I change the coefficient at $x_2$ in the objective from $2$ to $1$. That is actually consistent with your dual, otherwise one constant in the dual is wrong. So I assume that was a typo.

Next, when you form the dual, you have to remember the constraints $y_1,y_3\geq 0$. If you add them, then your dual and primal objectives match.

You can also read about conic duality in https://docs.mosek.com/modeling-cookbook/duality.html

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