>>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

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

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

Concepts

Derivatives

What is gradient in machine learning

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

An intro to the method of Lagrange Multipliers

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.

An intro to multiple-model machine learning

An ensemble learning strategy consisting of bringing together the predictions from several contributing models.

An intro to optimization mathematical programming

Regardless of it is a supervised learning problem or an unsupervised problem, there will be some optimization algorithm operating in the background. Nearly any classification, regression or clustering issue can be cast as an optimization problem.

How to create a bagging ensemble of deep learning models in Keras

Ensemble learning are strategies that bring together the predictions from several models.

Twelve practical applications of machine learning (ML) in healthcare

Whenever the discussion about human morality, their health, and the science of medicine pops up, any technologies that can impart a more effective, supportive, and quicker analysis to put out a precise treatment plan in time are massively valuable.

RPA use cases

Robotic Process Automation (RPA) holds a plethora of advantages in various industrial segments as it is supportive of high-occurrence, manual, repetitious, rules-based procedures, which are vital for the organization.

RPA in Finance

Robotic Process Automation (RPA) is currently inciting a revolution in the ways in which finance organizations function.

Object detection for self-driving vehicles

In our prior blog, Introduction to Object Detection, we found out about the fundamentals of object detection. We also obtained a bird’s eye view perspective of the YOLO (You only look once) algorithm.

Making sense of data migration strategy and best practices

Databases are the pulse of every enterprise in the modern planet. Data facilitates them to make educated and valuable decisions.

Learning through play

Disciplining children to clean up after themselves can be quite challenging. As a matter of fact, even some adults find this quite difficult. However, we encounter an even bigger challenge in attempting to get our artificial intelligence agents to perform the same.