Constrained Optimization with Lagrange Multipliers

Welcome back! In our last session, we explored the concept of convexity, which gives us a powerful guarantee: for a convex function, any local minimum is also a global minimum. This simplifies optimisation immensely. However, most real-world problems, and indeed many machine learning models, don't just involve minimising a function in a wide-open space. Often, our solutions must satisfy certain conditions or limitations.

This lesson tackles exactly that scenario. We will move from unconstrained to constrained optimisation. You will learn how to formally set up such a problem and master the method of Lagrange multipliers, a cornerstone technique for finding the maxima or minima of a function subject to one or more equality constraints. This method is not just a mathematical curiosity; it forms the theoretical backbone for deriving key machine learning algorithms, most notably Support Vector Machines, which we will study in depth later in the course.

1. Framing the Problem: Optimisation Under Constraints

Imagine you are trying to find the highest point on a mountain. That's an unconstrained optimisation problem. Now, imagine you have to find the highest point, but you are only allowed to walk along a specific, winding trail. This is a constrained optimisation problem.

We formalise this by defining two components:

An objective function, $f (x)$ , which is the function we want to maximise or minimise (e.g., the altitude).
A constraint function, $g (x) = c$ , which defines the path or surface we are restricted to (e.g., the equation of the trail).

Our goal is to find the point $x$ on the constraint curve that yields the highest or lowest value of $f (x)$ .

The image below provides a fantastic visualisation of this. The 3D surface on the left is our objective function, $f (x, y)$ . The contour plot on the right shows its level curves. We want to find the extreme values of this function not everywhere, but only along the paths defined by the green line ( $x + y = 0$ ) and the magenta circle ( $x^{2} + y^{2} = 1$ ).

On the left, a 3D plot of an objective function. On the right, its contour plot along with a linear constraint (green line) and a circular constraint (magenta circle). The optimal points are located where the contours of the objective function are tangent to the constraint curve.

Notice the key feature highlighted by the red dots: at the points where the function reaches a maximum or minimum on the constraint, the contour line of the function just "kisses" the constraint curve. They are tangent at that point. This single geometric insight is the key to the entire method.

2. The Geometric Insight: Tangency and Gradients

Why is this tangency so important? Let's explore this idea visually. The following videos provide an excellent intuition for how this geometric observation leads directly to a powerful algebraic method.

Lagrange Multipliers | Geometric Meaning & Full Example

This video by Dr. Trefor Bazett gives a superb geometric walkthrough of the core idea behind Lagrange multipliers.

Please watch these segments carefully: First, focus on the section from the introduction of contour plots to the tangency argument. This will build the intuition that the maximum/minimum occurs where the level curve of the objective function is tangent to the constraint curve. Next, watch how this tangency condition translates into a statement about gradients from this section. The key takeaway is that if two curves are tangent, their normal vectors (the gradients) must be parallel.

As Dr. Bazett explained, the core idea is this:

At any point, the gradient of a function, $\nabla f$ , points in the direction of the steepest ascent and is perpendicular (normal) to the level curve at that point.
Similarly, the gradient of the constraint function, $\nabla g$ , is normal to the constraint curve $g (x) = c$ .
If the level curve of $f$ is tangent to the constraint curve $g$ , their tangent lines are identical. This means their normal vectors—the gradients—must be parallel.

Two vectors are parallel if one is a scalar multiple of the other. This gives us the central equation of the Lagrange multiplier method:

\nabla f (x) = λ \nabla g (x)

Here, $λ$ (lambda) is a scalar constant called the Lagrange multiplier. It's the "proportionality constant" that relates the two gradient vectors.

3. The Method of Lagrange Multipliers

The geometric insight gives us the "magic" equation. To solve a constrained optimisation problem, we now have a concrete procedure. We need to find the points $x$ and the value of $λ$ that satisfy two conditions simultaneously:

The gradient alignment condition: $\nabla f (x) = λ \nabla g (x)$
The original constraint: $g (x) = c$

This set of equations forms a system that we can solve. For a problem in two dimensions (with variables $x$ and $y$ ), this expands into a system of three equations with three unknowns ( $x, y, λ$ ).

Calculus III - Lagrange Multipliers

This tutorial from Paul's Online Math Notes provides a clear, formal statement of the method.

Please read the section titled Method of Lagrange Multipliers. This text formalises the two steps and shows how the single vector equation for the gradients breaks down into multiple scalar equations, one for each variable.

4. A Worked Example

The best way to understand this method is to apply it. Since you prefer to "write things down" to learn, I encourage you to follow along with this next example with pen and paper, performing the calculations yourself.

We will solve a classic problem: finding the dimensions of a box with the largest possible volume, given a fixed surface area.

Calculus III - Lagrange Multipliers

Let's work through Example 1 from Paul's Online Math Notes. It provides a detailed, step-by-step solution that is excellent for active learning.

Read through Example 1 carefully. As you read, focus on the following steps: Identify the objective function f(x,y,z) (the volume) and the constraint equation g(x,y,z)=c (the surface area). Set up the system of four equations: three from the gradient condition (f_x = \lambda g_x, etc.) and one from the constraint itself. Solve the system. This is often the most challenging part and requires algebraic manipulation. Pay close attention to the strategy used here: multiplying by variables to create a common term (xyz) and then setting equations equal to eliminate \lambda. Interpret the result. Once you find the values for x, y, z, you have a candidate for the maximum. The text shows how to verify it's a maximum by testing another point.

This example demonstrates how the abstract concept of parallel gradients translates into a concrete algebraic process for finding the optimal solution.

5. The Lagrangian Function: A Bridge to Machine Learning

There is a very elegant way to encapsulate the entire method into a single function, which is the standard formulation used in machine learning. We define a new function, called the Lagrangian:

L (x, λ) = f (x) - λ (g (x) - c)

Now, watch what happens when we treat this as a standard unconstrained optimisation problem and find the point where the gradient of $L$ is zero, with respect to both $x$ and $λ$ .

The partial derivative with respect to $x$ : $\nabla_{x} L = \nabla f (x) - λ \nabla g (x) = 0 ⟹ \nabla f (x) = λ \nabla g (x)$
The partial derivative with respect to $λ$ : $\frac{\partial L}{\partial λ} = - (g (x) - c) = 0 ⟹ g (x) = c$

Remarkably, finding the stationary point of the Lagrangian gives us back the exact two conditions of the Lagrange multiplier method! This is not just a clever trick; it is the foundation for a powerful theoretical framework called duality, which is central to algorithms like SVMs.

14 Lagrange Multipliers

This short document from the University of Toronto provides the machine learning perspective on Lagrange multipliers, focusing on the Lagrangian function.

Read the first page, from the beginning up to the start of section 14.1. Focus on the definition of the Lagrangian function (note they use E(x) for the objective and a slightly different sign convention, but the principle is identical) and how its partial derivatives reproduce the necessary conditions.

6. What's Next? Multiple and Inequality Constraints

The method of Lagrange multipliers is very general.

Multiple Equality Constraints: If you have more than one constraint, say $g_{1} (x) = c_{1}$ and $g_{2} (x) = c_{2}$ , you simply introduce a separate multiplier for each. The gradient condition becomes $\nabla f = λ_{1} \nabla g_{1} + λ_{2} \nabla g_{2}$ . You can see an example of this in Example 5 of the Paul's Online Math Notes resource.
Inequality Constraints: What if the constraint is an inequality, like $g (x) \leq c$ ? This is even more common in machine learning (e.g., a budget you cannot exceed). This requires an extension of the method called the Karush-Kuhn-Tucker (KKT) conditions. The core idea is that the optimal solution is either inside the boundary (where the constraint is "inactive") or on the boundary (where it is "active" and acts like an equality). We will dive into the KKT conditions in detail when we study Support Vector Machines.

Conclusion

In this lesson, we have added a crucial tool to our optimisation toolkit. We've moved from the open landscapes of unconstrained problems to the bounded paths of constrained optimisation.

Here are the key takeaways:

A constrained optimisation problem consists of an objective function to be minimised/maximised, subject to one or more constraint equations.
The geometric intuition is that at an optimal point, the level curve of the objective function is tangent to the curve of the constraint.
This tangency implies that the gradients of the two functions must be parallel, leading to the core equation $\nabla f = λ \nabla g$ .
The method of Lagrange multipliers involves solving the system of equations formed by the gradient condition and the original constraint.
The Lagrangian function $L (x, λ)$ provides a compact way to formulate the problem, and its unconstrained optimisation yields the solution to the original constrained problem.

We now have a solid understanding of convexity and a powerful method for handling equality constraints. In the next lesson, we will finally get our hands dirty with an algorithm. We will learn how to implement gradient descent, the workhorse algorithm used to solve the unconstrained optimisation problems that lie at the heart of training many machine learning models.

Recommended resources