>>October (Page 4)

The method of Lagrange multipliers is a simple and sophisticated strategy of identifying the local minima or local maxima of a function subject to equality or inequality constraints. Lagrange multipliers are also referred to as undetermined multipliers. In this guide, we’ll speak about this method when provided equality constraints. 

In this guide, you will find out about the method of Lagrange multipliers and how to identify the local minimum or maximum of a function when equality constraints exist. 

After going through this guide, you will be aware of: 

  • How to identify points of local maximum or minimum of a function with equality constraints 
  • Method of Lagrange multipliers with equality constraints 

Tutorial Summarization 

This tutorial is subdivided into two portions, which are: 

  1. Method of Lagrange multipliers with equality constraints 
  2. Two solved instances 

Prerequisites 

For this guide, knowledge of the following are assumed: 

  • Derivative of functions 
  • Function of several variables, partial derivatives and gradient vectors 
  • An intro to optimization 
  • Gradient Descent 

What is the method of Lagrange Multipliers with Equality Constraints 

Let’s assume we possess the following optimization issue: 

Minimize f(x) 

Subject to: 

g_1(x) = 0 

g_2(x) = 0 

g_n(x) = 0 

The method of Lagrange multipliers first builds a function referred to as the Lagrange function as provided by the following expression: 

L(x, ?) = f(x) + ?_1 g_1(x) + ?_2 g_2(x) + … + ?_n g_n(x) 

Here, indicates a vector of Lagrange multipliers, i.e., 

?= [ ?_1, ?_2, …, ?_n]^T 

To identify the points of local minimum of f(x) subjected to the equality constraints, we identify the stationary points of the Lagrange function L(x, ?) that is, we solve the subsequent equations: 

xL = 0  

∂L/∂?_i = 0 (for i = 1..n) 

Therefore, we obtain a total of m+n equations to solve, where: 

m = number of variables in domain of f 

n = number of equality constraints 

In summary, the points of local minimum would be the answer of the following equations: 

∂L/∂x_j = 0 (for j = 1..m) 

g_i(x) = 0 (for i = 1..n) 

Solved Instances 

This section consists of two solved instances. If you solve both of them, you’ll obtain a very good idea on how to apply the strategy of Lagrange multipliers to functions of more than two variables, and a higher number of equality constraints. 

Example 1: One Equality Constraint 

Let’s find a solution to the following minimization issue: 

Minimize: f(x) = x^2 + y^2 

Subject to: x + 2y – 1 = 0 

The first step is to build the Lagrange function: 

L(x, y, ?) = x^2 + y^2 + ?(x + 2y – 1) 

We have the following three equations to find solutions to: 

∂L/∂x = 0  

2x + ? = 0      (1) 

∂L/∂y = 0 

2y + 2? = 0     (2) 

∂L/∂? = 0 

x + 2y -1 = 0    (3) 

Leveraging (1) and (2), we obtain: 

? = -2x = -y 

Plugging this in (3) provides us: 

x = 1/5 

y = 2/5 

Therefore, the local minimum point lies at (1/5, 2/5) as displayed in the right figure. The left figure displays the graph of the function. 

Instance 2: Two Equality Constraints

Assume we wish to identify the minimum of the following function subject to the provided constraints:

Minimize g(x, y) = x^2 + 4y^2

Subject to:

x + y = 0

x^2 + y^2 – 1 = 0

The solution of this problem can be identified by first building the Lagrange function:

L(x, y, ?_1, ?_2) = x^2 + 4y^2 + ?_1(x + y) + ?_2(x^2 + y^2 – 1)

We have four equations to find solutions to:

∂L/∂x = 0

2x + ?_1 + 2x ?_2 = 0    (1)

∂L/∂y = 0

8y + ?_1 + 2y ?_2 = 0    (2)

∂L/∂?_1 = 0

x + y = 0         (3)

∂L/∂?_2 = 0

x^2 + y^2 – 1 = 0    (4)

Solving the above system of equation provides us two solutions for (x,y), that is, we obtain the two points:

(1/sqrt(2), -1/sqrt(2))

(-1/sqrt(2), 1/sqrt(2))

The function combined with its constraints and local minimum are displayed below:

Relationship to Maximization Problems

If you possess a function to maximize, you can find a solution to it in a similar fashion, keeping in mind that maximization and minimization are equivalent issues i.e.,

maximize f(x) is equivalent to minimize -f(x)

Criticality of the method of Lagrange Multipliers within Machine Learning

Several popular machine learning algorithms leverage the method of Lagrange multipliers. For instance, the theoretical foundations of principal components analysis (PCA) are constructed leveraging the strategy of Lagrange multipliers with equality constraints. Likewise, the optimization issue in support vector machines SVMs is also solved leveraging this strategy. However, in SVMS, inequality constraints are additionally present.

Extensions

This part of the blog lists a few ideas for extension of this guide that you might desire to explore:

  • Optimization with inequality constraints
  • KKT conditions
  • Support vector machines

Further Reading

This section furnishes additional resources on the subject if you are seeking to delve deeper.

Concepts

Derivatives

Gradient descent for machine learning

What is gradient in machine learning

Partial derivatives and gradient vectors

How to select an optimization algorithm

Books

Thomas Calculus, 14th Edition, 2017 (based on the original works of George B. Thomas, revised by Joel Hass, Christopher Heil, Maurice Weir)

Calculus, 3rd edition, 2017 (Gilbert Strang)

Calculus, 8th edition, 2015 (James Stewart)

Conclusion

In this guide, you will find out about the method of Lagrange multipliers. Particularly, you learned:

  • Lagrange multipliers and the Lagrange function
  • How to solve an optimization problem when equality constraints are provided