Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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. – Seyhmus Güngören Aug 25 '12 at 12:39
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.