1
$\begingroup$

In these slides (5) the dual function for the norm minimization problem:

$ \min_x \|x\| \quad \mbox{s.t.} \quad Ax =b $

is defined as:

$ g(v) = \inf_x (\|x\| - ν^\intercal Ax + b^\intercal ν) $

what I don't understand is why the signs are reserved. The Lagrangian is according to the same author

$ \|x\| + v^\intercal (Ax - b) $

so the dual function should have been

$ g(v) = \inf_x (\|x\| + ν^\intercal Ax - b^\intercal ν) $

Is this correct?

  • 0
    I think it doesnt change anything. Because you have finally a lagrange multiplier which is a free parameter and it doesnt matter if it is $-v^T$ or $v^T$. finally if you get $v^T$ in one type of optimization you will get $-v^T$ in another.2012-08-25

1 Answers 1

2

$g^{'}(v) = \inf_x (\|x\| + ν^\intercal Ax - b^\intercal ν)$ is equivalent to $g(v) = \inf_x (\|x\| - ν^\intercal Ax + b^\intercal ν)$

except for the final $v^T$ that you will obtain which leads to $\min ||{x}||$. It means $x_{min}$ which minimizes $||x||$ conditioned on $ Ax =b$ will be exactly the same if you use $g^{'}(v)$ or $g(v)$