Motivation
A constrained minimizer may have a nonzero objective gradient because motion in the direction of steepest decrease is forbidden. Conversely, solving a multiplier equation does not by itself prove that a candidate is a minimum. The missing information is geometric: which directions can be followed by feasible curves, and how does the objective change to second order along them? This section develops those questions in finite dimensions. It distinguishes a condition that every local minimizer must satisfy from a condition sufficient for a strict local minimum.
Constraint qualifications matter because the algebraic gradients of constraints need not describe the feasible set faithfully. For example, the inequality has the same feasible set as , but its gradient vanishes at zero. A theorem that relies on independent gradients cannot silently treat these descriptions as interchangeable. All functions below are defined on an open neighborhood of the point being studied; inequalities are written .
Definitions
Consider minimizing subject to and , where . At a feasible point , the active set is .
Definition 4.1.1
(Linearized cone, tangent directions and LICQ)
The linearized cone at is
A tangent direction is a limit of feasible secants: there are feasible and such that . The linear independence constraint qualification (LICQ) holds at if the equality gradients and the gradients of all active inequalities are linearly independent.
Differentiability implies every tangent direction belongs to , but the reverse inclusion needs a qualification.
For multipliers and unrestricted , write
Definition 4.1.2
(KKT point and critical cone)
A feasible point is a KKT point if there are multipliers and with and for every . Its critical cone is .
Directions with a strictly positive first-order objective change are already unfavorable for sufficiently small steps; second-order analysis is needed in the critical directions. At a KKT point, complementarity and the signs imply that every critical direction also satisfies whenever .
Theorem/Proposition
Theorem 4.1.3
(Unconstrained first- and second-order tests)
Let be twice continuously differentiable near . If is an unconstrained local minimum, then and for every . Conversely, if the gradient vanishes and the Hessian is positive definite, then is a strict local minimum.
Theorem 4.1.4
(KKT and second-order conditions under LICQ)
Suppose are near a feasible local minimizer and LICQ holds there. Unique multipliers satisfy KKT, and for every ,
Conversely, at any feasible KKT point, if this quadratic form is positive for every nonzero , then is a strict local minimum with quadratic growth: for some , every feasible with satisfies .
The sufficient statement does not require LICQ once KKT multipliers and the stated positivity are supplied. Positive semidefiniteness in the necessary condition is not sufficient: has zero gradient and Hessian at zero but has a strict local maximum there. Likewise, the sufficient condition can fail at a genuine strict minimum, as shows.
When no qualification is available, a weaker necessary condition survives.
Theorem 4.1.5
(Fritz John conditions)
Suppose are continuously differentiable near a feasible local minimizer . Then there are , and , not all zero, with
If LICQ holds at , every such relation has .
Proof sketch or proof idea
Unconstrained directions
Proof
(Restrict to lines, then use Taylor's formula)
Restrict to . A local minimum of this one-variable function has derivative zero and nonnegative second derivative at zero. Since this holds for every , the gradient vanishes and the Hessian quadratic form is nonnegative. Conversely, positive definiteness on the compact unit sphere gives a uniform lower bound for some . Taylor's formula, with a remainder , then yields for sufficiently small nonzero .
Why LICQ produces KKT multipliers
Proof
(Feasible curves, then the Farkas alternative)
For each , LICQ permits a vector with and for every active . Thus strictly decreases every active constraint to first order. The implicit function theorem corrects the equality residual by along a curve starting at with this velocity. Small positive keeps the active inequalities strict and the inactive ones feasible. Local optimality therefore gives ; letting gives for all .
The finite-dimensional Farkas alternative now gives with . One way to see the alternative is to separate from the closed polyhedral cone generated by active gradients plus the equality-gradient subspace: a separating vector would belong to and have negative product with , contrary to the preceding inequality. Set inactive multipliers to zero. LICQ makes the representation, and hence the multipliers, unique.
Second-order necessity
Proof
(A feasible curve that keeps the weighted constraints active)
Fix . Let contain active inequalities whose directional derivative along is zero. Equality gradients together with gradients in are independent. The implicit function theorem constructs a curve with , , and with and for . Every other active inequality has negative derivative and is strict for small positive ; inactive inequalities stay strict. Thus the curve is feasible on the positive side.
By complementarity and criticality, every active constraint with positive multiplier is in . Along the curve, . Its first derivative at zero is zero. Local minimality gives a nonnegative right second derivative; stationarity removes the term involving , leaving precisely .
This explains why the Hessian of the Lagrangian, rather than the objective Hessian alone, governs curved constraints.
Second-order sufficiency
Proof
(Contradiction along normalized directions)
Suppose quadratic growth failed. There would be feasible with and . A subsequence of converges to a unit vector . First-order feasibility and stationarity give , while the objective inequality gives the reverse, so is critical. For feasible , nonnegative multipliers give and equality at . Taylor expansion and stationarity therefore imply
Passing to the limit contradicts strict positivity on nonzero critical directions.
Proof X-ray
Where each hypothesis enters the sufficiency proof
The proof never builds a feasible curve; it argues by contradiction from a hypothetical bad sequence. Compactness of the unit sphere is the first move, extracting a limiting direction , and it is what turns pointwise positivity into a uniform local conclusion. Feasibility of the sequence puts in the linearized cone; stationarity with gives , while the assumed slow growth gives the reverse inequality, so lands in the critical cone, the only set where positivity is assumed. The key move is replacing by the Lagrangian: nonnegative multipliers and feasibility give , complementarity gives , and stationarity kills the first-order Taylor term, so the second-order term of alone must be small. No constraint qualification appears, because multipliers are supplied rather than derived.
Fritz John when a qualification fails
Without LICQ, the Fritz John theorem allows a nonnegative objective multiplier alongside . The possibility is called abnormal and may contain no information about the objective. The general Fritz John theorem requires continuously differentiable data near a local minimizer for the proof given below. Under LICQ, the gradients in an abnormal stationarity relation are independent, forcing all multipliers to zero, so and normalization recovers KKT. This is a statement of necessity, not a converse.
Counterexample mode
A minimizer that is not a KKT point
A tempting claim is that every local minimizer is a KKT point. Minimize subject to and . Feasibility forces , hence , so the origin is the global minimizer. Both constraints are active there, with dependent gradients and , so LICQ fails. KKT stationarity would read , whose first component says . The linearized cone contains , which is not a tangent direction because every feasible point has . Fritz John holds with the abnormal choice , . KKT necessity needs a constraint qualification.
Proof
(A penalty problem on a small ball)
The Fritz John assertion has a direct finite-dimensional penalty proof. Choose a closed ball around on which is best among feasible points. For minimize on this ball
where . A minimizer exists by continuity and compactness, and . Consequently , so it is interior for small . The square-root term cannot be zero there: that would make feasible with , contradicting local minimality.
At the positive-part squares are differentiable. Divide their residuals by the positive square-root term and call the resulting coefficients , and . They satisfy and
with derivatives evaluated at . Take a convergent subsequence of the normalized coefficients. Its limit is nonzero, satisfies stationarity and nonnegativity, and has whenever . This proves Fritz John complementarity. In the unconstrained case the same argument uses only the first square; no artificial equality or inequality is needed.
The penalty construction is local: choosing the ball inside the neighborhood where the functions are continuously differentiable makes the first-order calculation legitimate. Its compactness supplies minimizers; it does not assert that the original constrained problem has a global solution.
A qualification weaker than LICQ
LICQ is convenient, but it excludes duplicated constraints even when they create no difficulty. A weaker sufficient condition for KKT necessity is the following.
Definition 4.1.6
(Mangasarian–Fromovitz constraint qualification)
The Mangasarian–Fromovitz constraint qualification (MFCQ) holds at if the equality gradients are independent and there is a direction with and for every active inequality.
The same feasible-curve argument used above applies to for each in the linearized cone. The Farkas alternative then yields multipliers. Unlike LICQ, this condition does not imply uniqueness of multipliers.
For example, minimize subject to and . Both constraints are active at zero, and their gradients are dependent. The direction decreases both strictly, so the weaker qualification holds. KKT stationarity is . Every nonnegative pair with is a valid multiplier pair. The minimizer is unambiguous but its allocation of shadow prices between redundant descriptions is not.
A boundary curve and second-order compensation
A direction satisfying the linearized constraints need not make the straight line feasible. On the unit circle at , the tangent direction gives , which lies outside the circle for every nonzero . The feasible curve has the same first derivative at zero, but its second coordinate changes by order . This correction is precisely the order at which the objective can distinguish candidates. It explains why the second derivative of a constraint contributes through its multiplier to the Lagrangian Hessian.
For this circle example the curve gives . The Lagrangian quadratic form on is , yielding the same coefficient in Taylor's formula. A straight-line calculation using only the objective Hessian would incorrectly report no second-order change, because that line is not feasible.
Worked examples
Worked example 4.1.7
(A saddle passes the first-order test)
For , the origin is stationary but the Hessian has values of both signs. Moving along raises the objective and moving along lowers it. The necessary Hessian test fails, so stationarity is not sufficient.
Worked example 4.1.8
(A curved equality and its Lagrangian Hessian)
Minimize subject to . At , stationarity of gives . LICQ holds because . Tangent directions have form and the Lagrangian Hessian is , positive on all nonzero tangent directions. The sufficient theorem gives a strict local minimum; the circle also shows it is global. The objective Hessian itself is zero and would miss the curvature of the constraint.
Worked example 4.1.9
(An active zero multiplier)
Minimize subject to . At zero, , LICQ holds, and the critical cone is . The Lagrangian Hessian is , strictly positive on every nonzero critical direction. Thus zero has quadratic growth even though the active multiplier is not positive. Replacing the critical cone by the nullspace of all active gradients can make the sufficient test invalid. For example, minimize subject to at zero. The KKT multiplier is zero and the active-gradient nullspace is , so positivity on its nonzero vectors is vacuous; nevertheless zero is a local maximum, not a minimum. Its actual critical cone is , and the Lagrangian Hessian is negative there.
Common mistakes
Common mistake
(Treating LICQ as necessary for multipliers)
LICQ is sufficient for KKT necessity, not necessary for a particular KKT certificate to exist. The redundant pair , violates LICQ at zero, yet the problem of minimizing has a whole segment of multipliers there.
Common mistake
(Testing curvature on the wrong set of directions)
Active constraints can have zero multipliers. A nonnegative Hessian on all of is more than constrained necessity requires; positivity only on equality tangent directions can also miss weakly active inequality directions, and positivity on the null space of all active gradients can be vacuous, as on shows.
Common mistake
(Normalizing an abnormal Fritz John multiplier)
Fritz John allows an abnormal multiplier and cannot be normalized unless has been established, for instance by LICQ.
Summary
Local minima first restrict feasible directional changes. LICQ connects the linearized cone to actual feasible curves and yields KKT multipliers. The Lagrangian Hessian on critical directions supplies a necessary second-order test; strict positivity supplies quadratic growth. The tests are local and do not establish global optimality without additional structure.
Exercises
Quick check
(Classify the origin for and for .)
Solution
The first Hessian is , positive definite, so the stationary origin is a strict minimum. The second Hessian is indefinite; values of both signs occur arbitrarily close to the origin, so it is a saddle.
Quick check
(Minimize subject to . Find the multiplier and verify the second-order condition.)
Solution
With , stationarity gives ; feasibility yields and . The tangent directions satisfy and the Lagrangian Hessian is , positive on every nonzero direction. The point is a strict local and, by convexity, global minimum.
Quick check
(At zero minimize subject to . Explain why KKT fails and exhibit Fritz John multipliers.)
Solution
The only feasible point is zero. Stationarity would require , impossible at zero. Fritz John holds with and : the constraint gradient vanishes. LICQ fails and the multiplier is abnormal.
Quick check
(For subject to , calculate the KKT multiplier and critical cone at zero. Is zero a strict local minimum?)
Solution
Write . Stationarity at zero gives , so . The linearized cone is , while criticality requires ; its only element is zero. The positivity condition is vacuous and the theorem applies. Directly, for every sufficiently small feasible .