5
$\begingroup$

I am reading the following tutorial on Lagrangian multipliers (http://www.cs.berkeley.edu/~klein/papers/lagrange-multipliers.pdf). My goal is to gain an intuitive understanding of why the Lagrangian method works. In summary, the tutorial link above and other tutorials have helped me understand that constraint optimization boils down to having parallel normal vectors for the function to be maximized and the constraint function. This leads us to formulate the Lagrangian function as follows:

$$ \Lambda (x,\lambda ) =f(x)-\lambda g(x) .\tag 1 $$

where we are looking for points that satisfy

$$ \triangledown \Lambda (x,\lambda ) = 0 .\tag 2 $$

I understand we can extend this to multiple dimensions, and eventually also using KKT conditions inequality constraints ... but my question is related to how to interpret the Lagrangian function $\Lambda(x,\lambda)$ itself.

The reason this question arises for me is, the tutorial goes on to explain that we can look at the Lagrangian as an "encoding of the problem" (Section 3.1 in the document). Quoting from the document: "You could imagine using the Lagrangian to do constrained maximization in the following way. You move $x$ around ${ R }^{ n }$ looking for a maximum value of $f$. However, you have no control over $\lambda$, which gets set in the worst possible way for you. Therefore, when you choose $x$, $\lambda$ is chosen to minimize $\Lambda$. Formally, the problem is to find the $x$ which gives

$$ {f}^{*} = \max _{ x }{ (\min _{ \lambda }{ \Lambda (x,\lambda )) } } .\tag 3 $$

I understand that we conceptually want to find the maximum value of $f(x)$ subject to $g(x)$ and thus, moving $x$ around in the ${ R }^{ n }$ to find the maximum value makes sense. It is clear to me that when the constraint is met, $\Lambda(x,\lambda)=f(x)$. This means that if the constraints are met, then ${ f }^{ * }=\max _{ x }{ f(x) }$ so indeed we are finding the maximum of the original cost function when the constraints are met. When the constraints are not met, if we minimize $\Lambda(x,\lambda)$ we will get $-\infty$ so maximizing that doesn't mean much. I guess in my head, what is preventing us from maximizing $\Lambda(x,\lambda)$? If the conditions are met, we still find the maximum value of $f(x)$ and if the conditions are not met, the max will be infinity? Is it as simple as, we are trying to prevent the maximum from being infinity? Another way to state my question is, why is Equation (3) above a valid formulation of the problem, and NOT Equation (4) given below:

$$ {f}^{*} = \max _{ x }{ (\max _{ \lambda }{ \Lambda (x,\lambda )) } } .\tag 4 <-- NOT CORRECT $$

I realize that if I just wanted to crunch out Lagrangians I probably don't really need to understand this, but for my application the "dual" problem is important, so a good understanding of this is important to me.

Thanks in advance!

$\endgroup$
1
  • $\begingroup$ It would be nice if someone can confirm this, but if you think about it like this maybe it makes sense. In Equation (3), notice that it is minimizing $\Lambda(x,\lambda)$ with respect to $\lambda$, and so in effect is controlling $\lambda$ such that the effect of $g(x)$ is minimal, resulting in attaining the maximum of the original function $f(x)$ when the constraints are met. $\endgroup$
    – Kiran K.
    Commented May 31, 2014 at 12:19

1 Answer 1

6
$\begingroup$

So suppose you want to maximize $f(x)$ subject to the constraint $g(x) = 0$. One way to think about this is to maximize $f(x) - K (g(x))^2$, where $K$ is very large, and then see what happens as $K \to \infty$.

So to optimize $f(x) - K (g(x))^2$, we obtain $$ \nabla f(x) - 2K g(x) \cdot \nabla g(x) = 0 .\tag 1$$ If $K$ is very large, then any reasonable solution will satisfy that $2K g(x)$ is reasonably sized. Since $K$ is large, $g(x)$ will be very small, that is, effectively zero.

Then we see that the Lagrange multiplier $\lambda = \lim_{K\to\infty} 2K g(x)$ (remembering that $f$ and $g$ also depend upon $K$). Thus the Lagrange multiplier is the extent to which the system tries to change $g(x)$ from being zero.

So, for example, if you solve an Euler-Lagrange equation to find the equations of motion of a system of particles held together by rigid rods, then the Lagrange multiplier represents the internal tension in the rigid rods required to keep the particles in their fixed relative positions.

P.S. in equation (1), the dot product represents $$ \frac{\partial f}{\partial x_i} - \sum_j 2 K g_j \frac{\partial g_j}{\partial x_i} = 0 .$$ Thus $\lambda$ is a vector with the same dimension as the output of $g$.

$\endgroup$
6
  • $\begingroup$ Sorry to be dense, but I understand mathematically you can provide the substitution for $\lambda=\lim _{ K->\infty }{ 2Kg(x) }$ and the rest of your explanation is clear. Other than substitution, is there some sort of intuition behind thinking about the problem in terms of maximizing $f(x)-K{ (g(x)) }^{ 2 }$? I suppose that may help me understand how thinking about the problem like this justifies Equation (3) rather than Equation (4) listed in the question statement above. $\endgroup$
    – Kiran K.
    Commented May 31, 2014 at 11:56
  • $\begingroup$ The idea is that if you are trying to maximize $f(x) - K(g(x))^2$, and $K$ is large, then this necessarily forces $g(x)$ to be small. Because if $g(x)$ is large, then moving $x$ in a direction where $g(x)$ gets smaller will make $f(x) - K(g(x))^2$ become much larger, whereas $f(x)$ will change by a smaller amount. $\endgroup$ Commented May 31, 2014 at 14:14
  • $\begingroup$ I believe that this method can also used to numerically find constrained maxima. $\endgroup$ Commented May 31, 2014 at 14:15
  • $\begingroup$ Thank you very much again! I think I understand with your clarifying comment. $\endgroup$
    – Kiran K.
    Commented Jun 1, 2014 at 1:05
  • $\begingroup$ @StephenMontgomery-Smith, How do you know that $\lim_{K\to \infty}2Kg(x)$ exists and is finite? $\endgroup$
    – user56834
    Commented Oct 14, 2017 at 7:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .