Artificial Intelligence , Machine Learning and Data Science Hubspot: Lagrange Multiplier Approach with Inequality Constraints

Thursday, 16 January 2025

Lagrange Multiplier Approach with Inequality Constraints

In a previous post, we introduced the method of Lagrange multipliers to find local minima or local maxima of a function with equality constraints. The same method can be applied to those with inequality constraints as well.

In this tutorial, you will discover the method of Lagrange multipliers applied to find the local minimum or maximum of a function when inequality constraints are present, optionally together with equality constraints.

After completing this tutorial, you will know

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

Let’s get started.

Lagrange Multiplier Approach with Inequality Constraints
Photo by Christine Roy, some rights reserved.

Prerequisites

For this tutorial, we assume that you already have reviewed:

as well as

A Gentle Introduction To Method Of Lagrange Multipliers

You can review these concepts by clicking on the links above.

Constrained Optimization and Lagrangians

Extending from our previous post, a constrained optimization problem can be generally considered as

$\begin{aligned} min & � (�) \\ subject to & � (�) & = 0 \\ ℎ (�) & \geq 0 \\ � (�) & \leq 0 \end{aligned}$

where $�$ is a scalar or vector values. Here, $� (�) = 0$ is the equality constraint, and $ℎ (�) \geq 0$ , $� (�) \leq 0$ are inequality constraints. Note that we always use $\geq$ and $\leq$ rather than $>$ and $<$ in optimization problems because the former defined a closed set in mathematics from where we should look for the value of $�$ . These can be many constraints of each type in an optimization problem.

The equality constraints are easy to handle but the inequality constraints are not. Therefore, one way to make it easier to tackle is to convert the inequalities into equalities, by introducing slack variables:

$\begin{aligned} min & � (�) \\ subject to & � (�) & = 0 \\ ℎ (�) - �^{2} & = 0 \\ � (�) + �^{2} & = 0 \end{aligned}$

When something is negative, adding a certain positive quantity into it will make it equal to zero, and vice versa. That quantity is the slack variable; the $�^{2}$ and $�^{2}$ above are examples. We deliberately put $�^{2}$ and $�^{2}$ terms there to denote that they must not be negative.

With the slack variables introduced, we can use the Lagrange multipliers approach to solve it, in which the Lagrangian is defined as:

$� (�, �, �, �) = � (�) - � � (�) - � (ℎ (�) - �^{2}) + � (� (�) + �^{2})$

It is useful to know that, for the optimal solution $�^{*}$ to the problem, the inequality constraints are either having the equality holds (which the slack variable is zero), or not. For those inequality constraints with their equality hold are called the active constraints. Otherwise, the inactive constraints. In this sense, you can consider that the equality constraints are always active.

The Complementary Slackness Condition

The reason we need to know whether a constraint is active or not is because of the Krush-Kuhn-Tucker (KKT) conditions. Precisely, the KKT conditions describe what happens when $�^{*}$ is the optimal solution to a constrained optimization problem:

The gradient of the Lagrangian function is zero
All constraints are satisfied
The inequality constraints satisfied complementary slackness condition

The most important of them is the complementary slackness condition. While we learned that optimization problem with equality constraint can be solved using Lagrange multiplier which the gradient of the Lagrangian is zero at the optimal solution, the complementary slackness condition extends this to the case of inequality constraint by saying that at the optimal solution $�^{*}$ , either the Lagrange multiplier is zero or the corresponding inequality constraint is active.

The use of complementary slackness condition is to help us explore different cases in solving the optimization problem. It is the best to be explained with an example.

Example 1: Mean-variance portfolio optimization

This is an example from finance. If we have 1 dollar and were to engage in two different investments, in which their return is modeled as a bi-variate Gaussian distribution. How much should we invest in each to minimize the overall variance in return?

This optimization problem, also known as Markowitz mean-variance portfolio optimization, is formulated as:

$\begin{aligned} min & � (�_{1}, �_{2}) & = �_{1}^{2} �_{1}^{2} + �_{2}^{2} �_{2}^{2} + 2 �_{1} �_{2} �_{12} \\ subject to & �_{1} + �_{2} & = 1 \\ �_{1} & \geq 0 \\ �_{1} & \leq 1 \end{aligned}$

which the last two are to bound the weight of each investment to between 0 and 1 dollar. Let’s assume $�_{1}^{2} = 0.25$ , $�_{2}^{2} = 0.10$ , $�_{12} = 0.15$ Then the Lagrangian function is defined as:

$\begin{aligned} � (�_{1}, �_{2}, �, �, �) = & 0.25 �_{1}^{2} + 0.1 �_{2}^{2} + 0.3 �_{1} �_{2} \\ - � (�_{1} + �_{2} - 1) \\ - � (�_{1} - �^{2}) - � (�_{1} - 1 + �^{2}) \end{aligned}$

and we have the gradients:

$\begin{aligned} \frac{� �}{� �_{1}} & = 0.5 �_{1} + 0.3 �_{2} - � - � - � \\ \frac{� �}{� �_{2}} & = 0.2 �_{2} + 0.3 �_{1} - � \\ \frac{� �}{� �} & = 1 - �_{1} - �_{2} \\ \frac{� �}{� �} & = �^{2} - �_{1} \\ \frac{� �}{� �} & = 1 - �_{1} - �^{2} \end{aligned}$

From this point onward, the complementary slackness condition have to be considered. We have two slack variables $�$ and $�$ and the corresponding Lagrange multipliers are $�$ and $�$ . We now have to consider whether a slack variable is zero (which the corresponding inequality constraint is active) or the Lagrange multiplier is zero (the constraint is inactive). There are four possible cases:

$� = � = 0$ and $�^{2} > 0$ , $�^{2} > 0$
$� \neq 0$ but $� = 0$ , and $�^{2} = 0$ , $�^{2} > 0$
$� = 0$ but $� \neq 0$ , and $�^{2} > 0$ , $�^{2} = 0$
$� \neq 0$ and $� \neq 0$ , and $�^{2} = �^{2} = 0$

For case 1, using $� � / � � = 0$ , $� � / � �_{1} = 0$ and $� � / � �_{2} = 0$ we get

$\begin{aligned} �_{2} & = 1 - �_{1} \\ 0.5 �_{1} + 0.3 �_{2} & = � \\ 0.3 �_{1} + 0.2 �_{2} & = � \end{aligned}$

which we get $�_{1} = - 1$ , $�_{2} = 2$ , $� = 0.1$ . But with $� � / � � = 0$ , we get $�^{2} = - 1$ , which we cannot find a solution ( $�^{2}$ cannot be negative). Thus this case is infeasible.

For case 2, with $� � / � � = 0$ we get $�_{1} = 0$ . Hence from $� � / � � = 0$ , we know $�_{2} = 1$ . And with $� � / � �_{2} = 0$ , we found $� = 0.2$ and from $� � / � �_{1}$ we get $� = 0.1$ . In this case, the objective function is 0.1

For case 3, with $� � / � � = 0$ we get $�_{1} = 1$ . Hence from $� � / � � = 0$ , we know $�_{2} = 0$ . And with $� � / � �_{2} = 0$ , we get $� = 0.3$ and from $� � / � �_{1}$ we get $� = 0.2$ . In this case, the objective function is 0.25

For case 4, we get $�_{1} = 0$ from $� � / � � = 0$ but $�_{1} = 1$ from $� � / � � = 0$ . Hence this case is infeasible.

Comparing the objective function from case 2 and case 3, we see that the value from case 2 is lower. Hence that is taken as our solution to the optimization problem, with the optimal solution attained at $�_{1} = 0$ , $�_{2} = 1$ .

As an exercise, you can retry the above with $�_{12} = - 0.15$ . The solution would be 0.0038 attained when $�_{1} = \frac{5}{13}$ , with the two inequality constraints inactive.

Want to Get Started With Calculus for Machine Learning?

Take my free 7-day email crash course now (with sample code).

Click to sign-up and also get a free PDF Ebook version of the course.

Example 2: Water-filling algorithm

This is an example from communication engineering. If we have a channel (say, a wireless bandwidth) in which the noise power is $�$ and the signal power is $�$ , the channel capacity (in terms of bits per second) is proportional to $\log_{2} (1 + � / �)$ . If we have $�$ similar channels, each has its own noise and signal level, the total capacity of all channels is the sum $\sum_{�} \log_{2} (1 + �_{�} / �_{�})$ .

Assume we are using a battery that can give only 1 watt of power and this power have to distribute to the $�$ channels (denoted as $�_{1}, \dots, �_{�}$ ). Each channel may have different attenuation so at the end, the signal power is discounted by a gain $�_{�}$ for each channel. Then the maximum total capacity we can achieve by using these $�$ channels is formulated as an optimization problem

$\begin{aligned} max & � (�_{1}, \dots, �_{�}) & = \sum_{� = 1}^{�} \log_{2} (1 + \frac{�_{�} �_{�}}{�_{�}}) \\ subject to & \sum_{� = 1}^{�} �_{�} & = 1 \\ �_{1}, \dots, �_{�} & \geq 0 \end{aligned}$

For convenience of differentiation, we notice $\log_{2} � = \log � / \log 2$ and $\log (1 + �_{�} �_{�} / �_{�}) = \log (�_{�} + �_{�} �_{�}) - \log (�_{�})$ , hence the objective function can be replaced with

$� (�_{1}, \dots, �_{�}) = \sum_{� = 1}^{�} \log (�_{�} + �_{�} �_{�})$

Assume we have $� = 3$ channels, each has noise level of 1.0, 0.9, 1.0 respectively, and the channel gain is 0.9, 0.8, 0.7, then the optimization problem is

$\begin{aligned} max & � (�_{1}, �_{2}, �_{�}) & = \log (1 + 0.9 �_{1}) + \log (0.9 + 0.8 �_{2}) + \log (1 + 0.7 �_{3}) \\ subject to & �_{1} + �_{2} + �_{3} & = 1 \\ �_{1}, �_{2}, �_{3} & \geq 0 \end{aligned}$

We have three inequality constraints here. The Lagrangian function is defined as

$\begin{aligned} � (�_{1}, �_{2}, �_{3}, �, �_{1}, �_{2}, �_{3}) \\ = & \log (1 + 0.9 �_{1}) + \log (0.9 + 0.8 �_{2}) + \log (1 + 0.7 �_{3}) \\ - � (�_{1} + �_{2} + �_{3} - 1) \\ - �_{1} (�_{1} - �_{1}^{2}) - �_{2} (�_{2} - �_{2}^{2}) - �_{3} (�_{3} - �_{3}^{2}) \end{aligned}$

The gradient is therefore

$\begin{aligned} \frac{� �}{� �_{1}} & = \frac{0.9}{1 + 0.9 �_{1}} - � - �_{1} \\ \frac{� �}{� �_{2}} & = \frac{0.8}{0.9 + 0.8 �_{2}} - � - �_{2} \\ \frac{� �}{� �_{3}} & = \frac{0.7}{1 + 0.7 �_{3}} - � - �_{3} \\ \frac{� �}{� �} & = 1 - �_{1} - �_{2} - �_{3} \\ \frac{� �}{� �_{1}} & = �_{1}^{2} - �_{1} \\ \frac{� �}{� �_{2}} & = �_{2}^{2} - �_{2} \\ \frac{� �}{� �_{3}} & = �_{3}^{2} - �_{3} \end{aligned}$

But now we have 3 slack variables and we have to consider 8 cases:

$�_{1} = �_{2} = �_{3} = 0$ , hence none of $�_{1}^{2}, �_{2}^{2}, �_{3}^{2}$ are zero
$�_{1} = �_{2} = 0$ but $�_{3} \neq 0$ , hence only $�_{3}^{2} = 0$
$�_{1} = �_{3} = 0$ but $�_{2} \neq 0$ , hence only $�_{2}^{2} = 0$
$�_{2} = �_{3} = 0$ but $�_{1} \neq 0$ , hence only $�_{1}^{2} = 0$
$�_{1} = 0$ but $�_{2}, �_{3}$ non-zero, hence only $�_{2}^{2} = �_{3}^{2} = 0$
$�_{2} = 0$ but $�_{1}, �_{3}$ non-zero, hence only $�_{1}^{2} = �_{3}^{2} = 0$
$�_{3} = 0$ but $�_{1}, �_{2}$ non-zero, hence only $�_{1}^{2} = �_{2}^{2} = 0$
all of $�_{1}, �_{2}, �_{3}$ are non-zero, hence $�_{1}^{2} = �_{2}^{2} = �_{3}^{2} = 0$

Immediately we can tell case 8 is infeasible since from $� � / � �_{�} = 0$ we can make $�_{1} = �_{2} = �_{3} = 0$ but it cannot make $� � / � � = 0$ .

For case 1, we have
$\frac{0.9}{1 + 0.9 �_{1}} = \frac{0.8}{0.9 + 0.8 �_{2}} = \frac{0.7}{1 + 0.7 �_{3}} = �$
from $� � / � �_{1} = � � / � �_{2} = � � / � �_{3} = 0$ . Together with $�_{3} = 1 - �_{1} - �_{2}$ from $� � / � � = 0$ , we found the solution to be $�_{1} = 0.444$ , $�_{2} = 0.430$ , $�_{3} = 0.126$ , and the objective function $� (�_{1}, �_{2}, �_{3}) = 0.639$ .

For case 2, we have $�_{3} = 0$ from $� � / � �_{3} = 0$ . Further, using $�_{2} = 1 - �_{1}$ from $� � / � � = 0$ , and
$\frac{0.9}{1 + 0.9 �_{1}} = \frac{0.8}{0.9 + 0.8 �_{2}} = �$
from $� � / � �_{1} = � � / � �_{2} = 0$ , we can solve for $�_{1} = 0.507$ and $�_{2} = 0.493$ . The objective function $� (�_{1}, �_{2}, �_{3}) = 0.634$ .

Similarly in case 3, $�_{2} = 0$ and we solved $�_{1} = 0.659$ and $�_{3} = 0.341$ , with the objective function $� (�_{1}, �_{2}, �_{3}) = 0.574$ .

In case 4, we have $�_{1} = 0$ , $�_{2} = 0.652$ , $�_{3} = 0.348$ , and the objective function $� (�_{1}, �_{2}, �_{3}) = 0.570$ .

Case 5 we have $�_{2} = �_{3} = 0$ and hence $�_{3} = 1$ . Thus we have the objective function $� (�_{1}, �_{2}, �_{3}) = 0.0 .536$ .

Similarly in case 6 and case 7, we have $�_{2} = 1$ and $�_{1} = 1$ respectively. The objective function attained 0.531 and 0.425 respectively.

Comparing all these cases, we found that the maximum value that the objective function attained is in case 1. Hence the solution to this optimization problem is
$�_{1} = 0.444$ , $�_{2} = 0.430$ , $�_{3} = 0.126$ , with $� (�_{1}, �_{2}, �_{3}) = 0.639$ .

Extensions and Further Reading

While in the above example, we introduced the slack variables into the Lagrangian function, some books may prefer not to add the slack variables but to limit the Lagrange multipliers for inequality constraints as positive. In that case you may see the Lagrangian function written as

$� (�, �, �, �) = � (�) - � � (�) - � ℎ (�) + � � (�)$

but requires $� \geq 0; � \geq 0$ .

The Lagrangian function is also useful to apply to primal-dual approach for finding the maximum or minimum. This is particularly helpful if the objectives or constraints are non-linear, which the solution may not be easily found.

Some books that covers this topic are:

Convex Optimization by Stephen Boyd and Lieven Vandenberghe, 2004
Chapter 4 of Deep Learning by Ian Goodfellow et al, 2016

Summary

In this tutorial, you discovered how the method of Lagrange multipliers can be applied to inequality constraints. Specifically, you learned:

Lagrange multipliers and the Lagrange function in presence of inequality constraints
How to use KKT conditions to solve an optimization problem when inequality constraints are given

Artificial Intelligence , Machine Learning and Data Science Hubspot

Thursday, 16 January 2025

Lagrange Multiplier Approach with Inequality Constraints

Prerequisites

Constrained Optimization and Lagrangians

The Complementary Slackness Condition

Example 1: Mean-variance portfolio optimization

Want to Get Started With Calculus for Machine Learning?

Example 2: Water-filling algorithm

Extensions and Further Reading

Summary

No comments:

Post a Comment

Lagrange Multiplier Approach with Inequality Constraints

Report Abuse

Labels

"Donate for a Noble Cause