Why a qualification is needed
At a constrained minimum, the negative objective gradient may be balanced by constraint gradients. But a constraint can describe a perfectly ordinary set with a useless gradient: describes the singleton , while its gradient is zero there. Minimizing on this set has a minimum at zero, yet the stationarity equation cannot hold there for any multiplier. We need a condition on the representation, not merely on the feasible set, before asserting that multipliers exist.
Let and be continuously differentiable near a feasible point . Write inequalities as and equalities as . Set , and let . Inactive inequalities are already strict and stay strict near .
Definition 4.2.1
(Mangasarian–Fromovitz constraint qualification)
The Mangasarian–Fromovitz constraint qualification (MFCQ) holds at if
- the rows of are linearly independent; and
- there is a vector with and for every .
When is empty, the second requirement is vacuous: suffices. When there are no equalities, the first is vacuous. MFCQ asks for a first-order escape into the strict side of every active inequality while respecting the equalities to first order. It is weaker than requiring linear independence of all equality and active inequality gradients (LICQ).
Proposition 4.2.2
(LICQ implies MFCQ)
If the gradients and , , are linearly independent, then MFCQ holds at .
Proof
(Prescribe the directional derivatives)
The rows of are among the independent gradients, so they are independent. Stack all the listed gradients as the rows of a matrix . Independence of the rows means has full row rank, so is solvable for every right-hand side . Choose with zero entries for the equality rows and for each active inequality row. The solution satisfies and for .
The converse can fail, as duplicated inequalities show below.
From linearized directions to multipliers
Define the linearized cone
Theorem 4.2.3
(MFCQ and the KKT conditions)
If is a local minimizer and MFCQ holds, there are and such that
Moreover, the set of such multiplier pairs is bounded and closed, hence compact. It need not contain only one pair.
Proof
(Perturb into the strict side, then normalize)
Fix and choose an MFCQ direction . For every , satisfies and strictly decreases each active inequality to first order. Since has full row rank, the implicit function theorem supplies an equality-feasible curve for small positive . Every active then has for small ; inactive inequalities remain strict. Local optimality gives . Letting yields for every .
The finite-dimensional Farkas alternative now represents as with . Set all inactive multipliers to zero. This gives stationarity and complementarity.
To prove boundedness, suppose instead that multiplier pairs have norms tending to infinity. Divide their stationarity equations by those norms and take a convergent subsequence of the normalized pairs. Its limit has norm one, for active indices, and
Take the inner product with : the equality term vanishes and every coefficient is strictly negative. Hence every is zero. Full row rank then implies , contradicting norm one. The multiplier set is closed because its defining equations and inequalities are closed.
Proof X-ray
One direction does two jobs
The MFCQ direction is used twice, for different purposes. In the existence part it tilts an arbitrary linearized direction into , which points strictly into every active inequality; only then does the implicit-function curve stay feasible, and full row rank of is what makes that theorem applicable to the equalities. Closedness of the inequality lets . In the boundedness part the key move is normalization: dividing by diverging norms removes and leaves the homogeneous equation of a nonzero abnormal multiplier. Pairing that equation with is a certificate that no such multiplier exists, because each surviving coefficient has a strict sign. Full row rank is spent a second time to kill . Without MFCQ the homogeneous equation can have nonzero solutions, and the counterexample below shows the multiplier set then becoming unbounded.
The key is the exclusion of a nonzero abnormal multiplier satisfying the homogeneous equation above. Boundedness concerns multipliers at this fixed point and for this fixed representation. It does not by itself say that a numerical algorithm converges, or that multipliers for nearby problems vary continuously.
Concept lensAlgebraic
MFCQ as the absence of abnormal multipliers
MFCQ has an equivalent dual form: it holds exactly when the only solution of
is , . The boundedness proof used one direction: pairing with forces , and full row rank forces . The converse follows from a theorem of the alternative of Farkas type. The primal form is confirmed by exhibiting ; the dual form is refuted by exhibiting one abnormal multiplier, as in the counterexample below.
Worked example: duplicated constraints
Worked example 4.2.4
(A segment of multipliers)
Minimize subject to and . The unique minimizer is . LICQ fails because the two active gradients, and , are dependent. MFCQ holds with : their products with are and . Stationarity requires
Every pair with is a multiplier pair. The interval is bounded but nonunique: the same supporting force can be distributed between redundant descriptions.
Common mistake
(Reading a multiplier as a property of the feasible set)
Rescaling a constraint changes its numerical multiplier, even though the feasible set is unchanged: in the example above, replacing by would turn the coefficient into . A multiplier belongs to a representation of the constraints, and only under a qualification such as LICQ is it unique.
When the constraints are independent, the multiplier is pinned down.
Worked example 4.2.5
(An equality and an active inequality)
Minimize subject to and . Feasible points are with , and , so is the minimizer. Here and . MFCQ holds with : and . Stationarity reads
so and . Hence and . The two gradients are independent, so LICQ holds as well and the multiplier pair is unique.
The edge case of the definition is a point with nothing active.
Worked example 4.2.6
(No active inequality)
Minimize subject to . The minimizer has , so is empty and there are no equalities; MFCQ holds with . Complementarity forces , and stationarity is then the unconstrained condition. The multiplier set is the single point , compact as the theorem asserts.
When the qualification fails
For the singleton problem subject to , the active gradient is zero, so no direction can decrease it strictly to first order. MFCQ fails and, as seen above, no KKT multiplier exists.
Counterexample mode
Without MFCQ the multiplier set can be unbounded
Keep the constraint but change the objective to . The minimizer is still , and MFCQ still fails there. Stationarity reads , which holds at for every . So a KKT multiplier exists, but the multiplier set is the whole ray , which is not bounded. Indeed solves the homogeneous equation : it is an abnormal multiplier, exactly what MFCQ excludes. The boundedness conclusion of the theorem needs the qualification.
Failure of MFCQ does not imply that KKT must fail, as this example shows. Thus a qualification guarantees useful conclusions; it is not a necessary condition for every individual problem to possess a certificate.
Practice with solutions
Quick check
(Minimize subject to , . Verify MFCQ at the origin and calculate its multipliers using the convention .)
Solution · Answer
Write , . The direction gives both products , so MFCQ holds. Stationarity gives . All feasible points have , so the origin is indeed a global minimizer.
Quick check
(Minimize subject to and . At , verify MFCQ and find the multipliers. Is LICQ true?)
Solution · Answer
Here and the active inequality gradient is . Take : and . Stationarity is , giving , . The two gradients are independent, so LICQ also holds. The equality reduces the feasible set to , making a global minimum.
Quick check
(At a feasible point with no equalities, the active inequality gradients are , . Can MFCQ hold? Explain without assuming an objective.)
Solution · Answer
No: strict decrease would require both and . This is a property of the chosen constraint representation at the point, independent of the objective. It does not rule out the existence of a KKT pair for a particular objective.