Equality constrained norm minimization

928 Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

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