5 Lagrange Multipliers
In constrained optimization, the goal is to minimize a function f \in C^2(\mathbb{R}^n) (twice continuously differentiable) subject to m equality constraints defined by h_k \in C^2(\mathbb{R}^n). This problem can be formulated as:
\begin{aligned} \text{Minimize:} \qquad & f(\bm{x}) \\ \text{Subject to:} \qquad & h_k(\bm{x}) = 0, \quad k = 1, \dots, m \end{aligned}
This means that we want to find the point \bm{x} that minimizes the objective function f(\bm{x}) while also satisfying the m constraints given by h_k(\bm{x}) = 0 for each k.
The challenging analytical problem of constrained minimization can be simplified using the Lagrange multiplier theorem. The idea is to incorporate the constraints directly into the optimization problem through additional variables called Lagrange multipliers.
Let f be the function to be minimized, and let \bm{h} represent the constraint functions (so that f, \bm{h} \in C^2(\mathbb{R}^n)). If \bm{x}^\star is a local minimum of f that satisfies all the constraints (i.e., \bm{h}(\bm{x}^\star) = \bm{0}), then if \nabla \bm{h}(\bm{x}^\star) has maximum rank, there exist m scalars \lambda_1, \dots, \lambda_m such that:
\nabla f(\bm{x}^\star) = \sum_{k=1}^{m} \lambda_k \nabla h_k(\bm{x}^\star)
This equation indicates that at the optimal point \bm{x}^\star, the gradient of the objective function f is a linear combination of the gradients of the constraint functions h_k. The scalars \lambda_k are called Lagrange multipliers.
Lagrangian Function
The problem is transformed into a simpler form using the Lagrangian function \mathcal{L}, which incorporates both the objective function and the constraints:
\mathcal{L}(\bm{x}, \bm{\lambda}) = f(\bm{x}) - \sum_{k=1}^{m} \lambda_k h_k(\bm{x})
Here, \bm{\lambda} = (\lambda_1, \dots, \lambda_m) is the vector of Lagrange multipliers. The goal now is to find stationary points of the Lagrangian \mathcal{L} by solving a system of equations derived from the first-order conditions.
Solving the Constrained Minimization Problem
To solve the problem, we need to find the points \bm{x}^\star that satisfy the Lagrange multiplier conditions. This involves solving the following system of equations:
\left\{ \begin{aligned} \nabla_{\bm{x}} \mathcal{L}(\bm{x}, \bm{\lambda}) & = \nabla f(\bm{x}) - \sum_{k=1}^{m} \lambda_k \nabla h_k(\bm{x}) = \bm{0} \\ \nabla_{\bm{\lambda}} \mathcal{L}(\bm{x}, \bm{\lambda}) & = -\bm{h}(\bm{x}) = \bm{0} \end{aligned} \right.
The first equation corresponds to finding points where the gradient of the Lagrangian \mathcal{L} with respect to \bm{x} is zero. The second equation ensures that the constraints h_k(\bm{x}) = 0 are satisfied.
All points \bm{x}^\star that solve this system are candidates for being local minima, maxima, or saddle points. Since we are searching for stationary points of the Lagrangian, further analysis is required to determine whether these points are indeed minima or maxima.
Second-Order Conditions
To determine whether a candidate point \bm{x}^\star is a local minimum in a constrained optimization problem, we must examine the second-order conditions. These conditions involve the Hessian matrix of the Lagrangian function. The second-order condition checks whether this Hessian is positive definite when restricted to the null space of the Jacobian of the constraints, \nabla \bm{h}(\bm{x}). This is necessary to ensure that the second derivative of the objective function along feasible directions is positive, which would confirm the existence of a local minimum.
Sufficient Condition
Mathematically, the second-order condition is expressed as:
\bm{z}^T \nabla_{\bm{x}}^2 \mathcal{L}(\bm{x}^\star, \bm{\lambda}) \bm{z} > 0 \quad \text{for all} \, \bm{z} \in \ker\{\nabla \bm{h}(\bm{x}^\star)\}
Here:
\bm{z} is any vector in the null space (or kernel) of the constraint Jacobian, \ker\{\nabla \bm{h}(\bm{x}^\star)\}.
The condition means that in the directions allowed by the constraints, the Hessian of the Lagrangian should be positive.
This condition ensures that the Lagrangian’s second derivative is positive in the feasible directions, confirming that the point \bm{x}^\star is a local minimum rather than a maximum or saddle point.
Necessary Condition
For \bm{x}^\star to be a local minimum, a necessary second-order condition is that the Hessian \nabla_{\bm{x}}^2 \mathcal{L}(\bm{x}^\star, \bm{\lambda}) is semi-positive definite in the feasible directions, which implies:
\bm{z}^T \nabla_{\bm{x}}^2 \mathcal{L}(\bm{x}^\star, \bm{\lambda}) \bm{z} \geq 0 \quad \forall \, \bm{z} \in \ker\{\nabla \bm{h}(\bm{x}^\star)\}
In other words, the Hessian of the Lagrangian must not have negative curvature along any direction that lies in the kernel of the constraint gradients. This is a necessary condition but not sufficient to confirm a local minimum.
Example 5.1 (constrained minimization problem) Let’s consider the problem on where we want to minimize the function f:\Bbb{R}^2\rightarrow R using the constraint h defined as
f(x,y) = \mathrm{e}^{x^2-y^2},\qquad h(x,y) = x - y^2
In order to solve this problem we at first need to build the lagrangian (having only one constraint \bm{\lambda} reduces to a scalar) and so
\mathcal{L}(x,y,\lambda) = \mathrm{e}^{x^2-y^2} - \lambda \big(x-y^2\big)
We now need to compute the stationary points of the lagrangian and this means solving the following non linear system of equations:
\left\{ \begin{aligned} \nabla_x \mathcal{L}(x,y,\lambda) &= 2 x \mathrm{e}^{x^2-y^2} - \lambda = 0 \\ \nabla_y \mathcal{L}(x,y,\lambda) &= -2 y \mathrm{e}^{x^2-y^2} + 2 \lambda y = 0 \\ \nabla_\lambda \mathcal{L}(x,y,\lambda) &= -x + y^2 = 0 \end{aligned} \right.
\begin{aligned} \implies \quad & \big(x,y,\lambda\big)=\big(0,0,0\big), \\ \implies \quad & \big(x,y,\lambda\big)= \left(\frac{1}{2}, \frac{1}{\sqrt{2}}, \mathrm{e}^{-\frac{1}{4}}\right), \\ \implies \quad & \big(x,y,\lambda\big)= \left(\frac{1}{2}, -\frac{1}{\sqrt{2}}, \mathrm{e}^{-\frac{1}{4}}\right) \end{aligned}
To determine now it this points are local maximum or minimum we have to firstly define the general gradient of the constraint map and then the hessian of the Lagrangian in respect to the variable \bm{x} =(x,y):
\begin{aligned} \nabla h(x,y) & = (1,-2y) \\ \nabla^2_{(x,y)} \mathcal{L} & = \begin{bmatrix} (4x^2+2)\mathrm{e}^{x^2-y^2} & -4xy \mathrm{e}^{x^2-y^2} \\ -4xy \mathrm{e}^{x^2-y^2} & (4y^2-2)\mathrm{e}^{x^2-y^2} + 2\lambda \end{bmatrix} \end{aligned}
Now we have to check each stationary point independently:
when x=y=\lambda = 0 we have that \nabla h = (1,0) while \nabla^2_{(x,y)} \mathcal{L} = \begin{bmatrix} 2 & 0 \\ 0 & -2 \end{bmatrix} By computing the null space of the vector (1,0) we can see that all the vectors in the form (0,\alpha) match the definition; we can now check if the point is of maximum/minimum be determining if the matrix \nabla^2_{(x,y)}\mathcal{L} is positive or negative defined: \big(0 \ \ \alpha\big) \begin{bmatrix} 2 & 0 \\ 0 & -2 \end{bmatrix} \begin{pmatrix} 0 \\ \alpha \end{pmatrix} = -2\alpha^2 \leq 0 for all \alpha\in\Bbb{R}. The hessian matrix is negative defined and so the point (x,y) = (0,0) is a local maximum.
evaluating for the second point x = \frac{1}{2},\quad y = \frac{1}{\sqrt{2}}, \quad\textrm{and}\quad \lambda = \mathrm{e}^{-\frac{1}{4}} we can compute the gradient \nabla h = (1, - \sqrt 2) of the constraint map that determines a null space of the form (\alpha \sqrt{2},\alpha). Given the hessian matrix of the transform we can see that it’s positive defined, in fact \mathrm{e}^{-\frac 1 4} \begin{pmatrix} \alpha \sqrt 2 & \alpha \end{pmatrix} \begin{bmatrix} 3 & -\sqrt 2 \\ -\sqrt 2 & 2 \end{bmatrix} \begin{pmatrix} \alpha \sqrt 2 \\ \alpha \end{pmatrix} = 4 \mathrm{e}^{-\frac 12} \alpha^2 > 0 for all \alpha \in \Bbb{R}. This means that the point is a local minimum.
considering instead the last point x = \frac{1}{2},\quad y = - \frac{1}{\sqrt 2} \quad\textrm{and}\quad \lambda = \mathrm{e}^{-\frac{1}{4}} we have a similar gradient \delta h = (1,\sqrt 2) that determines a kernel in the form (\alpha \sqrt 2,-\alpha). Evaluating the hessian on the null space base we can see that the matrix is positive defined, in fact \mathrm{e}^{-\frac{1}{4}} \begin{pmatrix} \alpha \sqrt 2 & -\alpha \end{pmatrix} \begin{bmatrix} 3 & -\sqrt 2 \\ -\sqrt 2 & 2 \end{bmatrix} \begin{pmatrix} \alpha \sqrt 2 \\ -\alpha \end{pmatrix} = 4 \mathrm{e}^{-\frac 12} \alpha^2 > 0 for all \alpha \in \Bbb{R}
We can see that the both points
\left(\frac 12, \frac 1{\sqrt 2}\right) \quad\textrm{and}\quad \left(\frac 12, -\frac 1{\sqrt 2}\right)
are local minimum and they are both also global minimum because we can see that
f\left(\frac{1}{2}, \frac 1{\sqrt{2}}\right) = f\left(\frac{1}{2}, - \frac 1{\sqrt{2}}\right) = \mathrm{e}^{-\frac{1}{4}}.
Example 5.2 (determination of the non-linear system) Given the problem
\begin{aligned} \textrm{minimize:} \qquad & f(x,y,z) = x - y + z^2 \\ \textrm{subject to:} \qquad & h_1(x,y,z) = x^2 + y^2 - 2 = 0 \\ & h_2(x,y,z) = x+z-1 = 0 \end{aligned}
the solution can be computed by firstly determining the lagrangian \mathcal{L} = f - \lambda_1 h_1 - \lambda_2 h_2
of the problem that’s
\mathcal{L}(x,y,z, \lambda_1, \lambda_2) = x-y+z^2 - \lambda_1\big(x^2+y^2-2\big) - \lambda_2\big(x+z-1\big)
The first order necessary condition related to the Lagrange multipliers states that a point, to be a minimum, must be a stationary one and so the candidate minimum points for this problem can be computed by solving the following system of non-linear equation:
\begin{cases} 1 - 2\lambda_1 x - \lambda_2 = 0 & : \dfrac{\partial}{\partial x}\mathcal{L} \\[1em] -1 - 2\lambda_1 y = 0 & : \dfrac{\partial}{\partial y} \mathcal{L} \\[1em] 2z - \lambda_2 = 0 & : \dfrac{\partial}{\partial z} \mathcal{L} \\[1em] x^2 + y^2 = 2 & : -\dfrac{\partial}{\partial \lambda_1} \mathcal{L} =h_1 \\[1em] x + z = 1 & : -\dfrac{\partial}{\partial \lambda_2}\mathcal{L} = h_2 \end{cases}
5.1 Summary of constrained minimization with proofs
Consider the following constrained optimization problem:
\begin{aligned} \text{Minimize:}\qquad & f(\bm{x}) \\ \text{Subject to:}\qquad & h_i(\bm{x}) = 0 \quad \text{for} \quad i = 1,2,\ldots,m \end{aligned} \tag{5.1}
The sufficient condition for optimality states that if the Hessian matrix, \bm{H}, is positive definite at the point (\bm{x}^\star, \bm{\lambda}^\star), then \bm{x}^\star is a strict local minimizer of the original constrained problem.
The following theorem formalizes this sufficient condition for optimality.
Theorem 5.1 (of Lagrange Multipliers) Let f \in C^2(\mathbb{R}^n, \mathbb{R}) and \bm{h} \in C^2(\mathbb{R}^n, \mathbb{R}^m) with \bm{x}^\star be a local minimum of problem Equation 5.1, i.e.,
- f(\bm{x}^\star) is a minimum
- subject to \bm{h}(\bm{x}^\star) = \bm{0}.
- and \nabla \bm{h}(\bm{x}^\star) is full rank
and define the Lagrangian
\mathcal{L}(\bm{x}^\star, \bm{\lambda}) = f(\bm{x}^\star) - \sum_{k=1}^m \lambda_k h_k(\bm{x}^\star)
then there exist scalars \lambda_k, k = 1, \dots, m, such that:
first order necessary condition: \nabla_x \mathcal{L}(\bm{x}^\star, \bm{\lambda}) = \nabla f(\bm{x}^\star) - \sum_{k=1}^m \lambda_k \nabla h_k(\bm{x}^\star) = 0. \tag{A}
second order condition:
for all \bm{z} \in \mathbb{R}^n such that \nabla \bm{h}(\bm{x}^\star)\bm{z} = \bm{0} and \bm{z}\neq \bm{0}, it holds that:necessary: \bm{z}^T \left( \nabla^2 f(\bm{x}^\star) - \sum_{k=1}^m \lambda_k \nabla^2 h_k(\bm{x}^\star) \right) \bm{z} \geq 0, \tag{B}
i.e., the matrix \nabla^2_x \big( f(\bm{x}^\star) - \bm{\lambda} \cdot \bm{h}(\bm{x}^\star) \big) is positive semi-definite in the kernel of \nabla \bm{h}(\bm{x}^\star).
sufficient:
\bm{z}^T \left( \nabla^2 f(\bm{x}^\star) - \sum_{k=1}^m \lambda_k \nabla^2 h_k(\bm{x}^\star) \right) \bm{z} \geq \epsilon \|\bm{z}\|^2>0, \tag{C}
i.e., the matrix \nabla^2_x \big( f(\bm{x}^\star) - \bm{\lambda} \cdot \bm{h}(\bm{x}^\star) \big) is positive definite in the kernel of \nabla \bm{h}(\bm{x}^\star).