I was trying to solve the optimization problem:

$$ \min \| p \|^2 \text{ subject to } l(p) = \epsilon$$

or to simplifying notation:

$$ \min f(x) \text{ subject to } g(x) = 0 $$

using Lagrange multipliers. Then I noticed that using the auxiliary equation we get:

$$ \min f(x) + \lambda g(x)$$

of course that satisfies the usual constraint that the objective and constraint are parallel:

$$ \nabla f(x) = - \nabla \lambda g(x) $$

but so does:

$$ \min \alpha f(x) + g(x)$$

where we get:

$$ \alpha = \frac{1}{\lambda} $$

however this second seems like a very different thing because it corresponds to constraint optimization problem:

$$ \min g(x) \text{ subject to } f(x) = 0 $$

which seems to me a completely different problem but in the light of the auxiliary equation and the parallel line/gradient condition they seem equivalent, even symmetric. Is this symmetry expected or is it just special because I only have 1 objective and 1 constraint but if I included more constraints (or even inequalities) it wouldn't hold.

I tried it out and even though I don't really understand why this works with more than 1 constraint it seems the auxiliary equation would have more constraints with each a different Lagrange multiplier so we can't just do the $\alpha = \frac{1}{\lambda}$ trick:

$$ f(x) + \lambda_1 g(x) + \lambda_2 h(x) $$

so it seems we can't do that trick. Is this right or did I miss something simple? It seemed too simple so I just wanted to double check I was right.

  • 1
    $\begingroup$ There's not a symmetry between the functions themselves (really, they can be anything), but rather the problems of optimizing each relative to the other being fixed. See en.wikipedia.org/wiki/Duality_(optimization) $\endgroup$ – Matthew Leingang Apr 20 '18 at 16:13
  • 1
    $\begingroup$ They are only related in the above in the sense that $\nabla f(x)$ and $\nabla g(x)$ lie on the same line at an extremum. However, this only works when you have a single constraint. Another way to think of it is that $\nabla f(x)$ is normal to the surface $g(x) = 0$. For a single $g$ this reduces to lying on the same line. $\endgroup$ – copper.hat Apr 20 '18 at 16:33
  • $\begingroup$ @copper.hat why doesn't that intuition work for 2 constraints? Perhaps the issue is that I don't understand very well how things look like or change when we have more constraints... $\endgroup$ – Pinocchio Apr 20 '18 at 16:39
  • $\begingroup$ A hyperplane has a natural dual notion of a normal. Informally, if two or more constraints are active, then the (affine approximation to) local feasible surface is no longer a hyperplane, so the geometric view is that you have containment rather than colinearity. $\endgroup$ – copper.hat Apr 20 '18 at 17:24

This hasn't gotten so much to do with duality as it has with multiobjective optimization. You are treating $f$ and $g$ as objectives, and you can solve a multiobjective optimization problem with a weighted sum method or by constraining one of the objectives and optimizing the other(s).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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