Topic 28. Lagrange Multipliers¶

Author: Ian Syndergaard

Introduction¶

Constrained optimization is a common engineering problem. Constrained optimization refers to minimizing a cost function (or maximizing a reward function) given that the variables being optimized must meet some condition (called a constraint). In this tutorial, we will refer to the cost function as $f(x,y,z,...)$.

There is a special class of constraints called equality constraints. An equality constraint is a constraint which can be written in the form $h(x,y,z,...) = 0$, where $(x,y,z,...)$ are the variables being optimized. In other words, there is a function of the variables which must equal zero.

example¶

Imagine that you want to start an icecream making business. In order to make icecream, you must purchase ingredients, the price of which will be denoted by $i$. You must also hire a worker and pay him for his work. The amount he is paid for his work will be denoted by $w$. You then wish to maximize your revenue selling icecream. The revenue will be denoted by $R$. Note that the more ingredients you buy and the more your employee works, the more icecream you can make and sell, and thus the higher your revenue can be. Thus, $R$ is a function of $i$ and $w$ (i.e. $R(i,w)$ ). We will let our cost function be $f(i,w) = - R(i,w)$. Thus, minimizing $f(i,w)$ will maximize the revenue.

As posed, this is an unconstrained optimization problem. However, in real life we would have constraints that we must abide by. For example, imagine that while creating this icecream business we must abide by a budget. Let's say we wish to invest $10,000. We now have the constraint$ i + w = $10,000 $.

Note that our constraint is not yet of the form $h(i,w) = 0$. However, this is easily accomplished by rearanging our constraint as $i + w - \$10,000 = 0$. Thus, $h(i,w) = i + w - \$10,000$. We now have an optimization problem with an equality constraint: minimize $f(i,w)$ subject to $h(i,w) = 0$.

Explanation of the theory using an example¶

Let's say that we wish to minimize $f(x,y) = sin(x) + \frac{1}{2} y^2$ with respect to $x$ and $y$. We also require that $x$ and $y$ lie on a circle of radius two centered at $(x,y) = (0,3)$. In other words, we have the constraint $x^2 + (y-3)^2 = 2^2$.

The following is a plot of $f(x,y)$ superimposed with the constraint.

We are looking for the point on the circle which has the lowest value of $f$. It's easy to point to that spot on the plot, but actually solving for it will require some clever mathematics.

Let's look at this plot as a set of countour lines (also called level curves). We will also include our constraint in black.

Note that we can find an $x$ and $y$ which meet our constraint and which will yield $f(x,y)$ for any level curve that intersects the constraint.

For example, we could find values for $x$ and $y$ which would yield $f(x,y) = 10$; however, there are no values of $x$ and $y$ which meet the constraint and yield $f(x,y) = 0.6$. (Note that $f(x,y) = 0.6$ is the lowest level curve in this plot, and it does not intersect the constraint. We simply cannot do as well as $f(x,y) = 0.6$ while meeting our constraint.)

Note also that the lowest level curve we could ever reach is one that is tangent to the constraint. In other words, at the constrained optimum, the cost function and the constraint are tangent!

In order to find the point (or points) where the cost function and the constraint are tangent, we can use the gradients of the cost function ($\nabla f(x,y)$) and the constraint ($\nabla h(x,y)$). The gradient field of the cost function is depicted below.

Note that the gradient field is always perpendicular to the cost function.

This is true in general. The gradient is, by definition, in the direction of steepest ascent. If you start at a level curve and you wish to ascend as rapidly as possible, you should head perpendicular to the level curve. If you travel in any other direction, a portion of the travel will move you along the level curve, and thus a portion of that travel was "wasted". Therefore, the direction of steepest ascent (or descent) is always perpendicular to the level curve.

Let's consider now the gradient of the constraint, $\nabla h(x,y)$.

Of course, $\nabla h(x,y)$ is perpendicular to the constraint as we have already discussed. Let's now put these all together. We will plot the cost function with its gradient field and the constraint with its gradient. We will also zoom in on the point of tangency.

The level curve depicted here isn't quite tangent to the constraint, but it's close (a contour at a slightly lower value for $f(x,y)$ would be tangent). However, it illustrates that at a point of tangency, the gradient of the cost function and the gradient of the constraint are proportional. That is, they either point in the same direction or they point in opposite directions.

Because this is true at all points of tangency, we can find all points of tangency by calculating the gradient of the cost function, $\nabla f(x,y)$, and the gradient of the constraint, $\nabla h(x,y)$, and setting them equal to each other with a proportionality constant, $\lambda$.

That is,

$$\nabla f(x,y) = \lambda \nabla h(x,y)$$

The proportionality constant, $\lambda$, is called a Lagrange Multiplier.

For our example problem, $\nabla f(x,y) = \begin{bmatrix} cos(x) \\ y \end{bmatrix}$
and $\nabla h(x,y) = \begin{bmatrix} 2x \\ 2(y-3) \end{bmatrix}$

Thus,

$$\begin{bmatrix} cos(x) \\ y \end{bmatrix} = \lambda \begin{bmatrix} 2x \\ 2(y-3) \end{bmatrix}$$

We also have the constraint:

$$x^2 + (y-3)^2 = 2^2$$

Thus, we have a system of three equations and three unknowns. Their solution is the point (or points) of tangency between cost function and constraint. Thus the solution (or one of the solutions if there are multiple solutions) is the constrained optimum.

$$cos(x) = \lambda 2x$$ $$y = \lambda 2(y-3)$$ $$x^2 + (y-3)^2 = 2^2$$

This system of equations has two solutions:

$$\lambda_1 = 1.263, x_1 = 0.3692, y_1 = 4.966$$ and $$\lambda_2 = -0.3411, x_2 = -0.9052, y_2 = 1.217$$ One of these solutions corresponds to the constrained minimum. The other corresponds to the constrained maximum (becuase the cost function and the constraint are also tangent at the constrained maximum). $$f(x_1,y_1) = 12.6896$$ $$f(x_2,y_2) = -0.04653$$

Thus, the constrained minimum is at $(x_2,y_2) = (-0.9052,1.217)$.

An Engineering Application¶

Challenge Problem¶