Lagrange Multipliers for Linear Equality Constraints

Why Equality Constraints Change the First-Order Condition

For an unconstrained differentiable objective, a local minimum in the interior of its domain must have zero gradient. A linear equality constraint changes which directions are available: from a feasible point, only directions that preserve the constraint can be followed. The gradient need not vanish in every direction; it must have zero component along every feasible direction.

This observation leads to the Lagrange multiplier equations. For linear equalities, the derivation is direct: identify the feasible directions, require the objective’s directional derivative to vanish along them, and express the resulting orthogonality condition using the constraint matrix. Feasibility comes first. If the equalities have no common solution, there is no constrained minimizer to characterize.

Feasibility and the Constraint Set

Definition: Let $A\in\mathbb{R}^{m\times p}$ and $b\in\mathbb{R}^m$. The linear equality constraints $Ax=b$ are feasible if there is at least one $x\in\mathbb{R}^p$ satisfying them. Their feasible set is $\{x\in\mathbb{R}^p:Ax=b\}$.

The constraints are feasible exactly when $b$ belongs to the column space of $A$. Equivalently,

Ax=b\text{ is feasible} \quad\Longleftrightarrow\quad \operatorname{rank}(A)=\operatorname{rank}([A\mid b]).

Here $[A\mid b]$ is the matrix formed by adjoining $b$ as a final column. This rank test follows from the definition of column space: adding $b$ leaves the column-space dimension unchanged precisely when $b$ is already in that space. If feasible, the set is an affine space. For any feasible $x_0$, every other feasible point has the form $x_0+v$, where $Av=0$.

Worked Example: Checking Whether the Constraints Are Feasible

Consider the two equations $x_1+x_2=1$ and $x_1+x_2=2$. Write them as $Ax=b$, where $A=\begin{pmatrix}1&1\\1&1\end{pmatrix}$ and $b=\begin{pmatrix}1\\2\end{pmatrix}$.

The two rows of $A$ are identical, so $\operatorname{rank}(A)=1$. In the augmented matrix, the rows $(1,1,1)$ and $(1,1,2)$ are not multiples of one another, so $\operatorname{rank}([A\mid b])=2$. The ranks differ, and the system is infeasible. Directly, the equations require the same sum $x_1+x_2$ to equal both 1 and 2, which is impossible. No choice of objective or multiplier can create a feasible point.

Deriving the Stationarity Equations

Let $f:\mathbb{R}^p\to\mathbb{R}$ be differentiable on an open set containing a feasible point $x^*$. Suppose $x^*$ is a local minimum of $f$ among points satisfying $Ax=b$. The feasible directions are exactly the vectors $v$ in the null space of $A$, since $A(x^*+tv)=b$ for every real $t$ whenever $Av=0$.

Theorem: If $Ax=b$ is feasible and $f$ is differentiable on an open set containing a local minimizer $x^*$ subject to $Ax=b$, then there is a vector $\lambda\in\mathbb{R}^m$ such that $$ Ax^*=b, \qquad \nabla f(x^*)+A^{\mathsf T}\lambda=0. $$ The multiplier $\lambda$ is unique if $A$ has full row rank. If the rows of $A$ are linearly dependent, a multiplier still exists, but it need not be unique.

The sign in this equation corresponds to defining the Lagrangian as $L(x,\lambda)=f(x)+\lambda^{\mathsf T}(Ax-b)$. Using a minus sign in the definition would change the sign of the multiplier, not the underlying condition.

Restrict to feasible directions.
If $Av=0$, then $x^*+tv$ is feasible for every real $t$.

Set the directional derivative to zero.
A differentiable function of $t$, $f(x^*+tv)$, has a local minimum at the interior point $t=0$. Its derivative there is $\nabla f(x^*)^{\mathsf T}v=0$.

Express orthogonality with a multiplier.
A vector orthogonal to every $v$ satisfying $Av=0$ lies in the range of $A^{\mathsf T}$, so $\nabla f(x^*)=-A^{\mathsf T}\lambda$ for some $\lambda$.

For completeness, the linear-algebra identity used in the final step is $\operatorname{null}(A)^\perp=\operatorname{range}(A^{\mathsf T})$. Every vector of the form $A^{\mathsf T}u$ is orthogonal to $\operatorname{null}(A)$, since $(A^{\mathsf T}u)^{\mathsf T}v=u^{\mathsf T}Av=0$. Both spaces have dimension $\operatorname{rank}(A)$: the range of $A^{\mathsf T}$ has that dimension, and rank-nullity gives $\dim(\operatorname{null}(A)^\perp)=p-\dim(\operatorname{null}(A))=\operatorname{rank}(A)$. The inclusion and equal dimensions give the identity.

If $A$ has full row rank, then $A^{\mathsf T}\lambda=0$ implies $\lambda=0$, so the multiplier solving the stationarity equation is unique. If the rows are dependent, there is a nonzero $u$ with $A^{\mathsf T}u=0$; whenever $\lambda$ solves the equation, so does $\lambda+u$. This proves the theorem’s existence and uniqueness claims. $\square$

Worked Example: Minimizing a Squared Distance Under One Equality

Minimize $f(x)=\tfrac12\|x-c\|^2$ over $x\in\mathbb{R}^3$, subject to $x_1+x_2+x_3=1$, where $c=(2,-1,3)^{\mathsf T}$. Here $A=(1,1,1)$, $b=1$, and $\nabla f(x)=x-c$.

The Lagrangian is $L(x,\lambda)=\tfrac12\|x-c\|^2+\lambda(x_1+x_2+x_3-1)$. Stationarity and feasibility require

x-c+\lambda\begin{pmatrix}1\\1\\1\end{pmatrix}=0, \qquad x_1+x_2+x_3=1.

The first equation gives $x=c-\lambda(1,1,1)^{\mathsf T}$. Summing its coordinates gives $4-3\lambda=1$, so $\lambda=1$. Therefore $x^*=(1,-2,2)^{\mathsf T}$, whose coordinates sum to 1. Its gradient is $x^*-c=(-1,-1,-1)^{\mathsf T}$, which cancels $A^{\mathsf T}\lambda=(1,1,1)^{\mathsf T}$ as required. The squared-distance objective is strictly convex, so this feasible stationary point is the unique global minimum.

Redundant Constraints and Matrix Objectives

Redundant equalities affect the multiplier, not necessarily the constrained solution. If the same linear condition is written more than once, the row rank is deficient. The theorem still applies, but different multiplier vectors can produce the same vector $A^{\mathsf T}\lambda$ and hence the same stationarity equation.

Worked Example: A Redundant System Has Nonunique Multipliers

Minimize $f(x)=\tfrac12(x_1^2+x_2^2)$ subject to $x_1+x_2=1$ and $2x_1+2x_2=2$. The second equality repeats the first, so the system is feasible and $A=\begin{pmatrix}1&1\\2&2\end{pmatrix}$ has rank 1.

The feasible points have the form $(t,1-t)^{\mathsf T}$. Substitution gives $f(t,1-t)=\tfrac12(t^2+(1-t)^2)$. Its derivative is $2t-1$, so the minimum occurs at $t=\tfrac12$; thus $x^*=(\tfrac12,\tfrac12)^{\mathsf T}$.

The stationarity equation is $x^*+A^{\mathsf T}\lambda=0$. Since $A^{\mathsf T}\lambda=(\lambda_1+2\lambda_2)(1,1)^{\mathsf T}$, it reduces to $\lambda_1+2\lambda_2=-\tfrac12$. For example, both $(\lambda_1,\lambda_2)=(-\tfrac12,0)$ and $(0,-\tfrac14)$ satisfy it. The optimizer is unique, but the two multipliers are not.

The same reasoning applies when the decision variable is a matrix. Let $X\in\mathbb{R}^{r\times s}$, let $f(X)$ be differentiable, and impose a linear constraint $\mathcal{A}(X)=b$, where $\mathcal{A}$ maps matrices to vectors. The matrix gradient uses the Frobenius inner product $\langle U,V\rangle_F=\operatorname{tr}(U^{\mathsf T}V)$. Define the adjoint $\mathcal{A}^*$ by $\langle \mathcal{A}^*(\lambda),H\rangle_F=\lambda^{\mathsf T}\mathcal{A}(H)$ for every matrix $H$. The stationarity equations become

\mathcal{A}(X^*)=b, \qquad \nabla f(X^*)+\mathcal{A}^*(\lambda)=0.

Indeed, a feasible direction $H$ satisfies $\mathcal{A}(H)=0$, and the directional derivative is $\langle\nabla f(X^*),H\rangle_F$. Requiring it to vanish for every such $H$ gives the stated adjoint form of the same orthogonality condition.

Worked Example: A Trace Constraint on a Matrix

Minimize $f(X)=\tfrac12\|X-C\|_F^2$ over $2\times2$ matrices subject to $\operatorname{tr}(X)=1$, where $C=\begin{pmatrix}2&1\\0&0\end{pmatrix}$. The gradient is $\nabla f(X)=X-C$. The linear map is $\mathcal{A}(X)=\operatorname{tr}(X)$; its adjoint maps the scalar $\lambda$ to $\lambda I$, because $\langle\lambda I,H\rangle_F=\lambda\operatorname{tr}(H)$.

Thus stationarity gives $X-C+\lambda I=0$, or $X=C-\lambda I$. Taking traces and using $\operatorname{tr}(C)=2$ gives $2-2\lambda=1$, so $\lambda=\tfrac12$. The resulting matrix is $X^*=\begin{pmatrix}\tfrac32&1\\0&-\tfrac12\end{pmatrix}$; its trace is $1$, and $X^*-C+\tfrac12 I=0$. Since the objective is a strictly convex squared distance, this is the unique global minimizer.

What the Equations Do—and Do Not—Say

The stationarity equations are necessary conditions for a local minimum under the stated differentiability and feasibility assumptions. They are not, by themselves, proof that a feasible point is a minimum: a stationary point might instead be a maximum or a saddle point. For convex objectives, additional convexity reasoning can establish global optimality, but the multiplier equations alone encode first-order balance.

A common mistake is to solve $\nabla f(x)+A^{\mathsf T}\lambda=0$ and report the resulting point without checking $Ax=b$. The stationarity equation describes a candidate; feasibility is a separate required equation. Another mistake is to assume that every constraint system gives a unique multiplier. Uniqueness requires full row rank, while redundant constraints can yield many multipliers. Conversely, a deficient row rank does not automatically mean infeasibility: the repeated equations in the preceding example were consistent.

Key takeaway: First establish that the equalities are feasible. At a differentiable constrained local minimum, the gradient is orthogonal to every feasible direction and therefore lies in the row space of the constraint matrix. This is exactly the Lagrange stationarity equation, together with the original constraints.

Check Your Understanding

Use the definitions and derivation above to answer the following questions.

What rank condition characterizes feasibility of $Ax=b$, and what does failure of that condition imply?
Why must the gradient at a constrained local minimum be orthogonal to every vector $v$ satisfying $Av=0$?
When is the Lagrange multiplier unique? What can happen when the constraints are redundant?
For a matrix constraint $\mathcal{A}(X)=b$, what role does the adjoint $\mathcal{A}^*$ play in stationarity?
Why must a candidate satisfying stationarity still be checked against the original equality constraints?