Solving Equality-Constrained Quadratic Estimation

From a Quadratic Objective to a Joint System

A quadratic estimation problem often chooses a vector of estimates by balancing a quadratic fit criterion against exact linear restrictions. The restrictions might encode a known sum, a calibration identity, or another requirement the estimate must satisfy exactly. The useful calculation is not merely to write down a multiplier condition: it is to turn the estimate and the multipliers into one linear system and identify when that system has a unique solution.

Let $x\in\mathbb{R}^p$ be the vector to be estimated. Consider minimizing a quadratic objective subject to $m$ linear equalities. We use the convention that the quadratic term has a factor of one half, which makes its gradient especially simple.

Definition: An equality-constrained quadratic estimation problem has objective $q(x)=\frac{1}{2}x^\mathsf{T}Hx-b^\mathsf{T}x$ and restrictions $Ax=c$, where $H$ is a symmetric $p\times p$ matrix, $b\in\mathbb{R}^p$, $A$ is an $m\times p$ matrix, and $c\in\mathbb{R}^m$. The estimate is a minimizer of $q(x)$ among vectors satisfying all the restrictions.

The term “estimate” here names the vector being chosen; no probability model is needed for the optimization calculation. If $H$ is positive definite, meaning $u^\mathsf{T}Hu>0$ for every nonzero $u$, then the objective is strictly convex. We will assume this curvature condition for the main result. When $A$ has full row rank, its rows are linearly independent, and every right-hand side $c\in\mathbb{R}^m$ is feasible.

Form the Lagrangian using a multiplier vector $\lambda\in\mathbb{R}^m$: $ \mathcal{L}(x,\lambda)=q(x)+\lambda^\mathsf{T}(Ax-c) $. The sign in this definition fixes the signs in the equations below. Since $H$ is symmetric, the gradient of $q$ is $Hx-b$. Setting the gradient of the Lagrangian with respect to $x$ to zero, and imposing the original restriction, gives the joint equations.

Hx-b+A^\mathsf{T}\lambda=0,\qquad Ax=c, \qquad \begin{pmatrix}H&A^\mathsf{T}\\ A&0\end{pmatrix} \begin{pmatrix}x\\ \lambda\end{pmatrix} = \begin{pmatrix}b\\ c\end{pmatrix}.

The block matrix is often called the saddle-point or KKT matrix for the equality-constrained problem. Its lower block row enforces feasibility, while its upper block row balances the objective gradient against the constraint gradients. The multipliers are part of the solution of the equations, but the quantity of direct interest is usually $x$.

The Closed-Form Solution and Its Conditions

Theorem: Suppose $H$ is symmetric positive definite and $A$ has full row rank. Then the problem has a unique minimizer. Its estimate and multiplier are $$ \lambda=(AH^{-1}A^\mathsf{T})^{-1}(AH^{-1}b-c), \qquad x=H^{-1}b-H^{-1}A^\mathsf{T}(AH^{-1}A^\mathsf{T})^{-1}(AH^{-1}b-c). $$ They are the unique solution of the joint block system.

Derivation of the formulas. Positive definiteness makes $H$ invertible. The stationarity equation gives $x=H^{-1}(b-A^\mathsf{T}\lambda)$. Substitute this expression into $Ax=c$:

AH^{-1}b-AH^{-1}A^\mathsf{T}\lambda=c.

The matrix $AH^{-1}A^\mathsf{T}$ is invertible. To check this, take any nonzero $v\in\mathbb{R}^m$. Full row rank of $A$ implies $A^\mathsf{T}v\ne0$, so $v^\mathsf{T}AH^{-1}A^\mathsf{T}v=(A^\mathsf{T}v)^\mathsf{T}H^{-1}(A^\mathsf{T}v)>0$. Here $H^{-1}$ is positive definite because $H$ is. Thus the displayed equation has the stated unique solution for $\lambda$, and substitution gives the stated $x$.

Why this solution is the unique minimizer. The formulas satisfy both $Ax=c$ and $Hx-b+A^\mathsf{T}\lambda=0$. Take any other feasible vector $x+d$, so $Ad=0$. Expanding the quadratic exactly gives

q(x+d)-q(x) =(Hx-b)^\mathsf{T}d+\frac{1}{2}d^\mathsf{T}Hd =-\lambda^\mathsf{T}Ad+\frac{1}{2}d^\mathsf{T}Hd =\frac{1}{2}d^\mathsf{T}Hd.

This difference is positive for every nonzero $d$, by positive definiteness of $H$. Therefore $x$ is the unique feasible minimizer. Finally, any solution of the joint equations must obey the same substitution steps, which uniquely determine $\lambda$ and $x$; hence the block system also has a unique solution. $\square$

The rank and curvature conditions have distinct roles. Positive definiteness ensures strict curvature in every direction and makes $H$ invertible. Full row rank ensures that the restrictions are independent and the multipliers are uniquely determined. If constraints are redundant, an estimate can still be unique while the multiplier vector is not.

Worked Solutions

Worked Example: Two Estimates With a Fixed Sum

Minimize $q(x)=\frac{1}{2}(2x_1^2+4x_2^2)-2x_1-4x_2$ subject to $x_1+x_2=1$. Find the estimate using the joint system and verify it.

Here $H=\begin{pmatrix}2&0\\0&4\end{pmatrix}$, $b=(2,4)^\mathsf{T}$, $A=(1,1)$, and $c=1$. The matrix $H$ is positive definite, and $A$ has full row rank. We have $H^{-1}=\begin{pmatrix}1/2&0\\0&1/4\end{pmatrix}$, so $AH^{-1}A^\mathsf{T}=3/4$ and $AH^{-1}b=2$. The multiplier is therefore

\lambda=(3/4)^{-1}(2-1)=4/3.

The estimate is $x=H^{-1}b-H^{-1}A^\mathsf{T}\lambda =(1,1)^\mathsf{T}-(1/2,1/4)^\mathsf{T}(4/3) =(1/3,2/3)^\mathsf{T}$. It satisfies the restriction because $1/3+2/3=1$. In the stationarity equation, $Hx-b=(-4/3,-4/3)^\mathsf{T}$, while $A^\mathsf{T}\lambda=(4/3,4/3)^\mathsf{T}$, so their sum is zero. The objective value is $q(x)=\frac12(2/9+16/9)-2/3-8/3=1-10/3=-7/3$. Strict positive definiteness ensures this feasible point is the unique minimizer.

Worked Example: Two Restrictions on Three Components

Let $q(x)=\frac12 x^\mathsf{T}x-b^\mathsf{T}x$, where $b=(3,0,1)^\mathsf{T}$. Minimize subject to $x_1+x_2=2$ and $x_2+x_3=1$.

Here $H=I_3$, $A=\begin{pmatrix}1&1&0\\0&1&1\end{pmatrix}$, and $c=(2,1)^\mathsf{T}$. The two rows of $A$ are independent. The multiplier equations use $AH^{-1}A^\mathsf{T}=AA^\mathsf{T}=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ and $AH^{-1}b=(3,1)^\mathsf{T}$. Thus

\begin{pmatrix}2&1\\1&2\end{pmatrix}\lambda = \begin{pmatrix}1\\0\end{pmatrix}, \qquad \lambda=\frac13\begin{pmatrix}2&-1\\-1&2\end{pmatrix} \begin{pmatrix}1\\0\end{pmatrix} = \begin{pmatrix}2/3\\-1/3\end{pmatrix}.

Since $x=b-A^\mathsf{T}\lambda$, we obtain $A^\mathsf{T}\lambda=(2/3,1/3,-1/3)^\mathsf{T}$ and $x=(7/3,-1/3,4/3)^\mathsf{T}$. The restrictions check directly: $7/3-1/3=2$ and $-1/3+4/3=1$. Stationarity also holds, since $x-b=(-2/3,-1/3,1/3)^\mathsf{T}$ and $A^\mathsf{T}\lambda=(2/3,1/3,-1/3)^\mathsf{T}$. This is the unique minimizer because $H=I_3$ is positive definite.

Worked Example: Redundant Restrictions and Nonunique Multipliers

Minimize $q(x)=\frac12[(x_1-2)^2+x_2^2]$ subject to both $x_1+x_2=1$ and $2x_1+2x_2=2$. The second restriction repeats the first, so $A$ does not have full row rank.

The objective has $H=I_2$ and $b=(2,0)^\mathsf{T}$. Write the two rows of $A$ as $(1,1)$ and $(2,2)$. The stationarity equation is $x-b+A^\mathsf{T}\lambda=0$. Because $A^\mathsf{T}\lambda=(\lambda_1+2\lambda_2,\lambda_1+2\lambda_2)^\mathsf{T}$, write $s=\lambda_1+2\lambda_2$. Stationarity gives $x=(2-s,-s)^\mathsf{T}$. The restriction $x_1+x_2=1$ requires $2-2s=1$, so $s=1/2$ and $x=(3/2,-1/2)^\mathsf{T}$. The repeated restriction is also satisfied.

Every pair of multipliers satisfying $\lambda_1+2\lambda_2=1/2$ works; for instance, $(\lambda_1,\lambda_2)=(1/2,0)$ and $(-3/2,1)$ both work. The estimate is nevertheless unique: $H=I_2$ is positive definite, and the feasible set is the same single line whether it is written once or twice. This example shows why full row rank is needed for the theorem’s unique-multiplier formula, not for uniqueness of the estimate in every possible problem.

Common Mistakes and Practical Checks

The block equations are compact, but a sign error or a dimension mismatch can produce a plausible-looking answer that is not feasible or optimal. The following checks catch the most common problems.

Changing the multiplier sign halfway through. With $\mathcal{L}=q(x)+\lambda^\mathsf{T}(Ax-c)$, stationarity is $Hx-b+A^\mathsf{T}\lambda=0$. Choosing a minus sign in the Lagrangian is also valid, but it changes the sign of the multiplier; the estimate remains the same if the convention is used consistently.
Solving stationarity but not enforcing feasibility. A solution of $Hx-b+A^\mathsf{T}\lambda=0$ alone need not satisfy $Ax=c$. Both block rows are essential.
Assuming every constraint matrix gives unique multipliers. If rows are redundant, $AH^{-1}A^\mathsf{T}$ is singular. Check the row rank before using its inverse; do not interpret a singular multiplier system as proof that the estimate itself is nonunique.
Using positive semidefiniteness as if it implied a unique estimate. If $H$ has zero-curvature directions, the objective need not be strictly convex. The uniqueness proof above specifically uses positive definiteness.

In applications, it is often useful to solve the joint block system directly rather than explicitly compute matrix inverses. The formulas explain the solution and its conditions; a numerical linear-system solver can be more stable than forming inverses. In either approach, verify the residuals $Hx-b+A^\mathsf{T}\lambda$ and $Ax-c$, and confirm that the stated assumptions justify the claimed uniqueness.

Check Your Understanding

Use the definitions and derivations above to answer these questions.

For the stated sign convention in the Lagrangian, what are the two block equations for the estimate and multiplier?
Why does full row rank of $A$ make $AH^{-1}A^\mathsf{T}$ positive definite when $H$ is positive definite?
In the first worked example, verify the constraint and stationarity equation using the reported estimate and multiplier.
What part of the uniqueness argument fails if $H$ is only positive semidefinite?
Can the estimate be unique if the constraints are redundant? Explain what the third example shows about the multipliers.

Solving Equality-Constrained Quadratic Estimation

What You'll Learn