1

I am trying to derive the solution of the problem below but am having trouble

enter image description here

This is my solution

$L = c^Tx + v(1^Tx - 1) - \lambda^Tx \\ \ \ \ = (c + v1 - \lambda)^Tx - v $

The dual is thus

$\min v \\ st. v1 = \lambda - c \\ \lambda \ge 0$

I dont know how to arrive at theirs. I also don't understand my solution. I have seen the solution from boyd's book on convex optimization but I want to do it through the dual for practice.

Kong
  • 884
  • 1
    First of all, yours should be $\text{maximize}~{-v}$, not $\text{minimize}~v$. Second, we can eliminate $\lambda$ by noting that $v\vec{1}=\lambda -c$ is identical to $v\vec{1}\succeq -c$. Finally, choose $y=-v$ and you're basically done. – Michael Grant Apr 16 '18 at 22:22
  • 1
    No, because one is a minimization and one is a maximization. They may be equivalent but they are not the same. And you don't get equal primal and dual objective values if you flip the objective direction like that. – Michael Grant Apr 16 '18 at 22:24
  • @MichaelGrant thank you very much. i learnt in class to minimize the negative of the dual (to make the objective function positive). I need to read up more. – Kong Apr 16 '18 at 22:33
  • 1
    That's a different matter. Many algorithms are designed only for minimization—which means that if you want to maximize something, you have to minimize its negative instead. But when talking about optimization problems you're really not free to flip the sense of the optimization problem like that. – Michael Grant Apr 16 '18 at 22:35
  • @MichaelGrant And thank you, I see it now (if I vizualize on a 2D plot) that my dual value will not be the same as the primal one if I flip the point across the x-axis – Kong Apr 16 '18 at 22:35

0 Answers0