1
$\begingroup$

I am reading the paper "A Semidefinite Optimization Approach to Quadratic Fractional Optimization with a Strictly Constraints" by Maziar Salahi & Saeed Fallahi.

I this paper, they tried to prove that if the Slater condition holds for the primal SDP problem: \begin{equation*} \begin{aligned} \min_{X} \mathrm{tr}(C^\top X)\\ \text{s.t.}~\mathrm{tr}(A^\top X) = 1\\ \mathrm{tr}(B^\top X) \preceq 0 \\ X \succeq 0 \end{aligned} \end{equation*} as well as its dual problem: \begin{equation*} \begin{aligned} \max_{\lambda,\eta} \eta\\ \text{s.t.}~C^\top -\eta A^\top + \lambda B^\top = Z\\ \lambda\geq 0 \\ Z \succeq 0 \end{aligned} \end{equation*} then both problems attain their optimal values and the duality gap is zero.

Because trace is a linear function, in order to show the strong duality, I know one has to show the Slater condition holds for the primal problem.

My Question is: why should I also have to show the Slater condition holds for the dual problem?

$\endgroup$
2
$\begingroup$

If either the primal or the dual satisfies Slater's condition, strong duality holds. However, the problem for which Slater's condition holds can still be unbounded, so you cannot conclude that "both problems attain their optimal values". To show that the primal problem is bounded you could give a feasible point for the dual or vice versa. That is not the only way. Instead, you can conclude that the primal is bounded if $C$ is positive semidefinite.

$\endgroup$
4
  • $\begingroup$ Thank you very much for your replying, I was wondering, "If either the primal or the dual satisfies Slater's condition, strong duality holds." is only correct for LP problem? Because in most text books, they only require primal problem satisfies Slater's condition. $\endgroup$
    – Stephen Ge
    Feb 5 at 4:02
  • 1
    $\begingroup$ @StephenGe it is correct for any convex problem. If the primal problem is closed, it is the dual of the dual problem, so you could apply the text book argument problem to the dual, by treating it as the primal. $\endgroup$
    – LinAlg
    Feb 5 at 14:39
  • $\begingroup$ Thank you again, LinAlg! I was wondering, is there any recommended text books or websites about how to prove this "dual of dual is primal" statement? $\endgroup$
    – Stephen Ge
    Feb 6 at 15:33
  • $\begingroup$ @StephenGe I quickly checked, and surprisingly most textbooks only show it for specific problems. You could check out this answer though. $\endgroup$
    – LinAlg
    Feb 6 at 17:17

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.