2 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}=(h_1,\ldots,h_m)^T collect the constraints. Throughout these notes, gradients of scalar functions are row vectors and D\bm h is the m\times n Jacobian whose kth row is directly \nabla h_k. Vectors in \mathbb R^n are regarded as columns, so D\bm h(\bm x)\bm d contains the directional derivatives of all constraints along \bm d. If \bm{x}^\star is a local minimum of f on the feasible set, \bm{h}(\bm{x}^\star)=\bm{0}, and the constraint Jacobian D\bm{h}(\bm{x}^\star)\in\mathbb{R}^{m\times n} has full row rank m, then 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)^T is the column 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 relevant space is the tangent space to the feasible set at the candidate point, which, at a regular point, is the null space of the constraint Jacobian. Positive semidefiniteness of the Lagrangian Hessian on this space is necessary at a local minimum, whereas positive definiteness on this space is a second-order sufficient condition for a strict 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)\}\setminus\{\bm{0}\}
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, together with feasibility and the first-order Lagrange equations, ensures that \bm{x}^\star is a strict local minimum of the constrained problem.
Necessary Condition
For \bm{x}^\star to be a regular local minimum, a necessary second-order condition is that the Hessian \nabla_{\bm{x}}^2 \mathcal{L}(\bm{x}^\star, \bm{\lambda}) is positive semidefinite on the tangent space, 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 tangent direction. This is a necessary condition, but in general it is not sufficient to establish a local minimum.
Example 2.1 (constrained minimization problem) Let’s consider the problem in which we want to minimize the function f:\mathbb{R}^2\rightarrow\mathbb{R} using the constraint h defined as
f(x,y) = \mathrm{e}^{x^2-y^2},\qquad h(x,y) = x - y^2
We first build the Lagrangian. Since there is only one constraint, the multiplier is a scalar:
\mathcal{L}(x,y,\lambda) = \mathrm{e}^{x^2-y^2} - \lambda \big(x-y^2\big)
The constrained stationary points are obtained by solving the following nonlinear system:
\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 classify these stationary points, we compute the Jacobian of the constraint and the Hessian of the Lagrangian with respect to \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}
We now examine each stationary point separately:
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} The tangent space is the null space of (1,0), hence it consists of vectors of the form (0,\alpha). Restricting the Hessian quadratic form to this space gives: \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\mathbb{R}. The reduced Hessian is negative definite on the tangent space, so (x,y)=(0,0) is a strict local maximum of the constrained problem.
evaluating for the second point x = \frac{1}{2},\quad y = \frac{1}{\sqrt{2}}, \quad\text{and}\quad \lambda = \mathrm{e}^{-\frac{1}{4}} we obtain \nabla h=(1,-\sqrt{2}), whose null space consists of vectors (\alpha\sqrt{2},\alpha). Restricting the Hessian to this tangent space gives \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 1 4} \alpha^2 > 0 for all \alpha \in \mathbb{R}. This means that the point is a strict local minimum.
considering instead the last point x = \frac{1}{2},\quad y = - \frac{1}{\sqrt 2} \quad\text{and}\quad \lambda = \mathrm{e}^{-\frac{1}{4}} we have \nabla h=(1,\sqrt{2}), whose kernel consists of vectors (\alpha\sqrt{2},-\alpha). Restricting the Hessian to this tangent space gives \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 1 4} \alpha^2 > 0 for all \alpha \in \mathbb{R}. Thus this point is also a strict local minimum.
We can see that the both points
\left(\frac 12, \frac 1{\sqrt 2}\right) \quad\text{and}\quad \left(\frac 12, -\frac 1{\sqrt 2}\right)
are strict local minima. They are also global minima because, on the feasible set x=y^2,
f(y^2,y)=\mathrm{e}^{y^4-y^2} =\mathrm{e}^{(y^2-1/2)^2-1/4} \ge \mathrm{e}^{-1/4},
with equality exactly when y^2=1/2. Thus
f\left(\frac{1}{2}, \frac 1{\sqrt{2}}\right) = f\left(\frac{1}{2}, -\frac 1{\sqrt{2}}\right) =\mathrm{e}^{-1/4}.
Example 2.2 (determination of the nonlinear system) Given the problem
\begin{aligned} \text{minimize:} \qquad & f(x,y,z) = x - y + z^2 \\ \text{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 first forming 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 nonlinear equation:
\begin{cases} 1 - 2\lambda_1 x - \lambda_2 = 0 & : \frac{\partial}{\partial x}\mathcal{L} \\[0.5em] -1 - 2\lambda_1 y = 0 & : \frac{\partial}{\partial y} \mathcal{L} \\[0.5em] 2z - \lambda_2 = 0 & : \frac{\partial}{\partial z} \mathcal{L} \\[0.5em] x^2 + y^2 = 2 & : -\frac{\partial}{\partial \lambda_1} \mathcal{L} =h_1 \\[0.5em] x + z = 1 & : -\frac{\partial}{\partial \lambda_2}\mathcal{L} = h_2 \end{cases}
2.1 Summary of constrained minimization with proofs
Consider the equality-constrained optimization problem
\begin{aligned} \text{minimize:}\qquad & f(\bm{x}) \\ \text{subject to:}\qquad & h_i(\bm{x}) = 0, \quad i=1,2,\ldots,m, \end{aligned} \tag{2.1}
where f\in C^2(\mathbb{R}^n,\mathbb{R}) and \bm{h}=(h_1,\ldots,h_m)^T\in C^2(\mathbb{R}^n,\mathbb{R}^m). We use the Jacobian convention
\bm{J}(\bm{x}) := D\bm{h}(\bm{x}) = \begin{bmatrix} \nabla h_1(\bm{x})\\ \vdots\\ \nabla h_m(\bm{x}) \end{bmatrix} \in\mathbb{R}^{m\times n},
and all gradients of scalar functions are row vectors. The Lagrangian is
\mathcal{L}(\bm{x},\bm{\lambda}) = f(\bm{x})-\bm{\lambda}^T\bm{h}(\bm{x}) = f(\bm{x})-\sum_{i=1}^m\lambda_i h_i(\bm{x}).
Theorem 2.1 (Lagrange multipliers and second-order conditions) Let f\in C^2(\mathbb{R}^n,\mathbb{R}) and \bm{h}\in C^2(\mathbb{R}^n,\mathbb{R}^m), with m\le n. Let \bm{x}^\star be feasible,
\bm{h}(\bm{x}^\star)=\bm{0},
and assume the regularity condition
\operatorname{rank}\bm{J}(\bm{x}^\star)=m.
Then the following statements hold.
First-order necessary condition.
If \bm{x}^\star is a local minimum of Equation 2.1, then there exists a unique \bm{\lambda}^\star\in\mathbb{R}^m such that \nabla_{\bm{x}}\mathcal{L}(\bm{x}^\star,\bm{\lambda}^\star) = \nabla f(\bm{x}^\star) -\bm{J}(\bm{x}^\star)^T\bm{\lambda}^\star =\bm{0}.Second-order necessary condition.
If \bm{x}^\star is a local minimum and \bm{\lambda}^\star is the multiplier above, then \bm{z}^T \nabla_{\bm{x}\bm{x}}^2\mathcal{L}(\bm{x}^\star,\bm{\lambda}^\star) \bm{z} \ge 0 \qquad \forall\,\bm{z}\in\ker\bm{J}(\bm{x}^\star).Second-order sufficient condition.
Conversely, suppose that \bm{x}^\star is feasible and that there exists \bm{\lambda}^\star satisfying \nabla_{\bm{x}}\mathcal{L}(\bm{x}^\star,\bm{\lambda}^\star)=\bm{0}. If there exists \gamma>0 such that \bm{z}^T \nabla_{\bm{x}\bm{x}}^2\mathcal{L}(\bm{x}^\star,\bm{\lambda}^\star) \bm{z} \ge \gamma\|\bm{z}\|^2 \qquad \forall\,\bm{z}\in\ker\bm{J}(\bm{x}^\star), then \bm{x}^\star is a strict local minimum of Equation 2.1.
Because the tangent space is finite dimensional, the last condition is equivalent to strict positivity
\bm{z}^T \nabla_{\bm{x}\bm{x}}^2\mathcal{L}(\bm{x}^\star,\bm{\lambda}^\star) \bm{z}>0 \qquad \forall\,\bm{z}\in\ker\bm{J}(\bm{x}^\star)\setminus\{\bm{0}\}.