3
$\begingroup$

I have the following question about the Lagrange Method of Optimization (https://en.wikipedia.org/wiki/Lagrange_multiplier) - even though I learned about this in my engineering classes, I still don't understand the following points about this.

As I understand, the Lagrange method of optimization is a technique used to find the optimal point of a a function subject to constraints.

Suppose we have an objective function $f(x,y)$ that we want to optimize subject to the constraint $g(x,y) = c$, where $c$ is a constant. We can form the Lagrangian as:

\begin{equation} L(x,y,\lambda) = f(x,y) - \lambda(g(x,y)-c) \end{equation}

where $\lambda$ is the Lagrange multiplier.

We can then find the optimal value of $x$ and $y$ by taking the partial derivatives of the Lagrangian with respect to $x$, $y$, and $\lambda$ and set them equal to zero:

\begin{equation} \frac{\partial L}{\partial x} = 0 \end{equation}

\begin{equation} \frac{\partial L}{\partial y} = 0 \end{equation}

\begin{equation} \frac{\partial L}{\partial \lambda} = 0 \end{equation}

Solving these equations give us the optimal values of $x$, $y$, and $\lambda$. We can then use these values to find the maximum or minimum value of the objective function.

Assuming my understanding is correct, I have the following questions:

  • How do we know that the min/max point of $L(x,y,\lambda)$ will always be the same as the min/max point of $L(x,y)$ ?
  • We are often told that the Lagrange method often results in a simpler optimization problem compared to the original optimization problem. But how do we know that this is always the case? Isn't setting up and solving the system of equations required for the Lagrange method also difficult?
  • And as such, what are the disadvantages of the Lagrange method? Are there any generic types of constrained optimization problems in which the Lagrange method will either produce in invalid answer (e.g. candidate solution not in the feasible set) or become too difficult to solve (and some other optimization method is better suited)?

Thanks!

$\endgroup$
3
  • $\begingroup$ Regarding your second bulleted question, what solution method for the optimization problem are you comparing the Lagrange method to? $\endgroup$
    – Lee Mosher
    Commented May 24, 2023 at 2:34
  • $\begingroup$ @ Lee Mosher: Thank you for your reply! I was not referring to a specific optimization problem but in general solving the optimization problem $\endgroup$
    – stats_noob
    Commented May 24, 2023 at 2:43
  • $\begingroup$ To your second point, the Lagrange method is so useful because it changes the problem to an unconstrained problem, for which one can use many more methods and the optimality criteria are much simpler. Setting up the equations is really just taking a gradient so it's not that bad. If you know of a way to solve general constrained optimization problems that is easier than that, then use it I guess. $\endgroup$
    – whpowell96
    Commented May 24, 2023 at 2:48

1 Answer 1

1
$\begingroup$

How do we know that the min/max point of $L(x, y, \lambda)$ will always be the same as the min/max point of $L(x,y)$?

For the Lagrangian:

\begin{equation} L(x,y,\lambda) = f(x,y) - \lambda(g(x,y)-c) \end{equation}

you have given us the conditions:

\begin{equation} \frac{\partial L}{\partial x} = 0 \qquad \frac{\partial L}{\partial y} = 0 \qquad \frac{\partial L}{\partial \lambda} = 0 \qquad (*) \end{equation}

Notice that the third condition is,

\begin{equation} \frac{\partial L}{\partial \lambda} = g(x,y)-c = 0 \implies g(x,y)=c \end{equation}

Therefore, the third condition is ensuring that the constraints are satisfied, and if we assume some structure on $f(x,y)$ the first two conditions ensure that this is a maximum/minimum. If we don't have additional structure on $f(x,y)$ then the first two conditions could be a local minimum/maximum. Notice that if $\frac{\partial L}{\partial \lambda} = 0$ then $L(x,y,\lambda) = f(x,y)$. So min/max of $L$ will be the same as $f$.

We are often told that the Lagrange method often results in a simpler optimization problem compared to the original optimization problem. But how do we know that this is always the case? Isn't setting up and solving the system of equations required for the Lagrange method also difficult?

It always depends on the structure of the problem. As a simple example:

\begin{align} \min & \quad x^Tx \\ s.t. & \quad Ax = b \end{align}

The Lagrangian is

\begin{align} L(x, \lambda) = x^Tx + \lambda^T(Ax - b) \end{align}

Using

\begin{align} \frac{\partial L}{\partial x} = 2x + A^T\lambda = 0 \implies x = - \frac{1}{2}A^T\lambda \end{align}

Substituting this back into the Lagrangian we get the dual function

\begin{align} g(\lambda) = L(- \frac{1}{2}A^T\lambda, \lambda) = -\frac{1}{4}\lambda^{T}AA^{T}\lambda - b^{T}\lambda \end{align}

In this example, we have converted the quadratic constraint problem into a problem without any constraints and still a quadratic. This is easier to solve than the original problem since we don't have any constraints anymore. Additionally, notice that the dimension of the decision variable for the problem has changed from the dimension of $x$ to the dimension of $\lambda$. So there could be a large reduction in the number of variables by solving the dual problem. For example, SVMs exploit the dual formulation and the "kernel trick" to be able to have a reduction in the dimension.

It is not always the case that solving the dual problem is easier. If we have a convex problem and we take the dual of the dual then we get back the original problem (under appropriate assumptions). So we can't just keep taking the dual forever and get increasingly easier problems. It depends on the structure of the problem.

And as such, what are the disadvantages of the Lagrange method? Are there any generic types of constrained optimization problems in which the Lagrange method will either produce an invalid answer (e.g. candidate solution not in the feasible set) or become too difficult to solve (and some other optimization method is better suited)?

The Lagrangian is the bedrock for building many algorithms because it gives the conditions that are necessary and sufficient (under appropriate assumptions) for optimality. I'm not sure what it means by "produce an invalid answer" since it is just giving you conditions of the optimal point. I guess a disadvantage is that for nonconvex problems you have to verify that the point is indeed optimal and not a local extrema. If you have a continuum of points that satisfy the conditions then filtering the points to find the optimal might be as hard as the original problem. Also, it is not clear what you mean "become too difficult to solve". The Lagrangian is not an algorithm, it does not tell you how to go about finding the solution. It just tells you what properties a solution must have, i.e., the gradient is 0.

$\endgroup$
2
  • 1
    $\begingroup$ I'll complete @dgadjov's answer: it happens that the optimality conditions do not hold at a (local) solution. This may be the case when the problem is infeasible, or does not satisfy some form of regularity (also called constraint qualification: typically when the Jacobian of of the constraints is not full rank), or the functions are not differentiable everywhere, or the problem is unbounded. These aren't necessarily textbook scenarios, but they pop up in the real world more often than we would think ;) $\endgroup$ Commented May 24, 2023 at 6:00
  • $\begingroup$ Without appealing directly to the optimality conditions, one can show that the unconstrained minima of $L(x,y,\lambda)$ are the same as the constrained minima of $f(x,y)$ by noting that if $g(x,y)-c\ neq 0$, then one could decrease $L$ by varying $\lambda$. $\endgroup$
    – whpowell96
    Commented May 24, 2023 at 15:58

You must log in to answer this question.

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