Dependent Constraints and Nonunique Multipliers

Why Constraint Redundancy Matters

In constrained optimization, the equations used to describe a feasible set matter as well as the set itself. Two lists of equalities can specify exactly the same points, yet produce different multiplier equations. If some constraint gradients are linearly dependent, a multiplier may not be uniquely determined. In more severe cases, the regular gradient-span condition may not apply at all.

This distinction matters when solving a problem: a feasible point is a point satisfying every constraint, while a Lagrange multiplier is a coefficient in a representation of the objective gradient using constraint gradients. Redundant equations can change those coefficients without changing the feasible points or the optimization problem.

The Regular Multiple-Constraint Condition

Let \(f:\mathbb{R}^n\to\mathbb{R}\) be the objective, and let the equality constraints be \(g_i(\mathbf{x})=c_i\), for \(i=1,\dots,m\). A feasible point \(\mathbf{p}\) satisfies all \(m\) equalities. The constraint gradients at \(\mathbf{p}\) are \(\nabla g_1(\mathbf{p}),\dots,\nabla g_m(\mathbf{p})\).

Definition: The constraints are regular at a feasible point \(\mathbf{p}\) if their gradients \(\nabla g_1(\mathbf{p}),\dots,\nabla g_m(\mathbf{p})\) are linearly independent. Equivalently, the only coefficients \(\mu_1,\dots,\mu_m\) satisfying \(\sum_{i=1}^m\mu_i\nabla g_i(\mathbf{p})=\mathbf{0}\) are \(\mu_1=\cdots=\mu_m=0\).

For continuously differentiable constraints that are regular at \(\mathbf{p}\), the multiple-constraint Lagrange theorem says that if \(\mathbf{p}\) is a local constrained extremum of \(f\), then there are multipliers \(\lambda_1,\dots,\lambda_m\) such that

\nabla f(\mathbf{p}) = \sum_{i=1}^m\lambda_i\nabla g_i(\mathbf{p}).

The independence condition is a hypothesis of this result, not a technical detail that can be ignored. When the gradients are dependent, the regular theorem does not establish that the displayed equation must hold. If the equation does have solutions, those solutions might not be unique.

How Dependence Produces Nonunique Multipliers

Collect the constraint gradients as the columns of a matrix \(\mathbf{A}\). The multiplier equation is then \(\mathbf{A}\boldsymbol{\lambda}=\nabla f(\mathbf{p})\), where \(\boldsymbol{\lambda}\) is the vector of multipliers. Suppose the constraint gradients are dependent. Then there is a nonzero vector \(\boldsymbol{\mu}\) such that \(\mathbf{A}\boldsymbol{\mu}=\mathbf{0}\). If \(\boldsymbol{\lambda}_0\) solves the multiplier equation, then for every real number \(t\),

\mathbf{A}(\boldsymbol{\lambda}_0+t\boldsymbol{\mu}) = \mathbf{A}\boldsymbol{\lambda}_0+t\mathbf{A}\boldsymbol{\mu} = \nabla f(\mathbf{p})+t\mathbf{0} = \nabla f(\mathbf{p}).

Thus each \(\boldsymbol{\lambda}_0+t\boldsymbol{\mu}\) is also a solution. The calculation proves a useful rule: if the multiplier equation has one solution and the constraint gradients are dependent, then it has more than one solution. In fact, all solutions are obtained by adding vectors in the nullspace of \(\mathbf{A}\) to a particular solution.

Key takeaway: Dependent constraint gradients do not by themselves tell us whether the multiplier equation has a solution. But when it does have a solution, dependence guarantees that its multipliers are nonunique.

Worked Examples

Worked Example: A Circle Described by a Redundant Equality

Maximize \(f(x,y)=x\) subject to \(g_1(x,y)=x^2+y^2=1\) and \(g_2(x,y)=2x^2+2y^2=2\). The second equality is twice the first, so both describe the unit circle.

On the unit circle, \(x\leq 1\), with equality at \((1,0)\). Therefore \((1,0)\) is a global maximum. It is feasible because \(1^2+0^2=1\) and \(2(1^2+0^2)=2\).

Now calculate the gradients:

\nabla f=(1,0),\qquad \nabla g_1=(2x,2y),\qquad \nabla g_2=(4x,4y).

At \((1,0)\), these constraint gradients are \((2,0)\) and \((4,0)\), so \(\nabla g_2=2\nabla g_1\). The multiplier equation becomes

(1,0)=\lambda_1(2,0)+\lambda_2(4,0), \qquad 2\lambda_1+4\lambda_2=1.

For any real \(t\), setting \(\lambda_2=t\) gives \(\lambda_1=\frac12-2t\). Substitution checks the equation: \(2(\frac12-2t)+4t=1-4t+4t=1\). Thus infinitely many multiplier pairs represent the same objective gradient at the same maximum. The point and the maximum value are unambiguous; the multipliers are not.

Worked Example: Redundancy on a Line

Minimize \(f(x,y)=(x-y)^2\) subject to \(g_1(x,y)=x+y=1\) and \(g_2(x,y)=3x+3y=3\). The second equality is three times the first, so the feasible set is the line \(x+y=1\).

A square is nonnegative, and \(x-y=0\) is possible on this line at \((\frac12,\frac12)\). Hence the minimum is \(0\), attained at that point. Both constraints hold there: \(\frac12+\frac12=1\) and \(3(\frac12+\frac12)=3\).

The gradients are

\nabla f=(2(x-y),-2(x-y)),\qquad \nabla g_1=(1,1),\qquad \nabla g_2=(3,3).

At the minimum, \(\nabla f=(0,0)\). The multiplier equation is therefore

(0,0)=\lambda_1(1,1)+\lambda_2(3,3), \qquad \lambda_1+3\lambda_2=0.

Taking \(\lambda_2=t\) and \(\lambda_1=-3t\) satisfies the equation for every real \(t\). Indeed, \((-3t)(1,1)+t(3,3)=(0,0)\). Here even the zero objective gradient has infinitely many multiplier representations. This example also shows why nonuniqueness is about the equations’ gradients, not about whether the optimum is unique.

Worked Example: Dependent Gradients Can Prevent the Regular Condition

Consider minimizing \(f(x,y)=x\) subject to the two equalities \(g_1(x,y)=x^2=0\) and \(g_2(x,y)=2x^2=0\). Both equalities require \(x=0\), so the feasible set is the entire \(y\)-axis. On that set \(f=0\), meaning every feasible point is both a constrained minimum and a constrained maximum.

The gradients are \(\nabla f=(1,0)\), \(\nabla g_1=(2x,0)\), and \(\nabla g_2=(4x,0)\). At any feasible point \((0,y)\), both constraint gradients are \((0,0)\). Consequently the multiplier equation would require

(1,0)=\lambda_1(0,0)+\lambda_2(0,0)=(0,0),

which is impossible for every choice of \(\lambda_1,\lambda_2\). The point is a constrained extremum, but the regular gradient-span condition cannot represent its objective gradient. The reason is visible in the hypotheses: the constraint gradients are dependent, so the regular multiple-constraint theorem does not apply. The correct conclusion is not that the constrained extremum does not exist; it is that this theorem supplies no gradient-span equation here.

Why the Feasible Set and Multipliers Are Different

In the first two examples, constraints that repeated the same information left the feasible set unchanged. Yet the multiplier vectors varied. This is expected: the feasible set records which points are allowed, whereas the multipliers record how a gradient is expressed using the chosen list of constraint gradients.

Even a change of scale changes the numerical multiplier. If a constraint \(g(\mathbf{x})=c\) is replaced by \(ag(\mathbf{x})=ac\), where \(a\neq 0\), its gradient is multiplied by \(a\). To represent the same contribution to the objective gradient, its multiplier must be divided by \(a\). The feasible set has not changed, but the coefficient has.

With dependent gradients, there is a stronger ambiguity: multiple coefficients can yield exactly the same combined gradient. Therefore, a multiplier should not automatically be interpreted as a unique feature of the optimization problem. Its meaning depends on the constraint representation and on whether the gradients are independent.

A Common Mistake

A common error is to see that the multiplier equation has solutions and conclude that the constraints are regular, or that the multipliers are unique. Neither conclusion follows. For example, in the circle calculation, the choice \((\lambda_1,\lambda_2)=(\frac12,0)\) satisfies the equation. But so does \((-\frac32,1)\), since \(2(-\frac32)+4(1)=1\). The two constraint gradients are proportional, so this is a dependent system and the multipliers are not unique.

The correction is to check the constraint gradients separately from solving the multiplier equation. At a point, test whether the only linear combination of those gradients equal to zero has all coefficients zero. If not, the regularity hypothesis fails. A solution to the gradient equation may still exist, as in the circle example, but its existence does not restore the missing hypothesis or guarantee uniqueness.

Practical Checks

Check feasibility.
Substitute the candidate point into every equality; redundant equations still have to be satisfied.

Compute every constraint gradient.
Evaluate the gradients at the candidate point, not just at a general point.

Test independence.
If a nontrivial linear combination of the gradients is zero, the constraints are not regular there.

Interpret the multiplier equation carefully.
If it has solutions under dependence, expect a family of solutions; if it has none, the regular theorem does not justify rejecting the constrained extremum.

These checks separate three questions that are easy to conflate: whether a point is feasible, whether it is an extremum on the feasible set, and whether its objective gradient can be represented by the constraint gradients. Regularity is what links the last question to constrained extrema in the Lagrange theorem.

Check Your Understanding

Answer each question using the definitions and calculations above.

What does it mean for the constraint gradients to be linearly independent at a feasible point?
If a dependent-gradient multiplier equation has one solution, why must it have more than one?
In the circle example, verify that \((\lambda_1,\lambda_2)=(-\frac32,1)\) satisfies the multiplier equation.
Why do duplicate equality constraints leave the feasible set unchanged but affect the multiplier values?
What should you conclude when the regularity hypothesis fails and the multiplier equation has no solution?