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)$