Curvature along feasible directions
Consider the problem
where , has full row rank, and . These assumptions make every feasible, but do not require to be positive definite. The constraint may remove directions in which has negative curvature. Conversely, positive curvature in directions that violate the constraint does not help minimize over the feasible set.
Choose any feasible and let the columns of form a basis of . Every feasible point has a unique representation . Substitution gives
Definition 4.3.1
(Null-space basis and reduced Hessian)
A matrix whose columns form a basis of is a null-space basis for the constraint. The symmetric matrix is the reduced Hessian, and is the reduced gradient at the feasible point .
The entries of depend on the chosen basis, but whether it is positive definite or semidefinite does not: measures curvature of the original quadratic along a feasible direction.
Theorem 4.3.2
(Complete classification)
For (1), a minimizer exists precisely when is positive semidefinite and . When it exists, all minimizers are with . The minimizer is unique precisely when is positive definite. In every other case the objective is unbounded below on the feasible set.
Proof
(Separate curved and flat directions)
By (2) it suffices to study on . If has a vector with , then as . Now suppose . Since is symmetric, . If is not in the range, some has ; choosing the sign of makes .
If is in the range, choose with . Completing the square yields
Thus minimizes. The other minimizers differ from it by vectors in : for a positive semidefinite matrix, zero quadratic form is equivalent to membership in the kernel. These are exactly the solutions of . The minimizer is unique exactly when that kernel is zero, equivalently .
Proof X-ray
Where the two failure modes come from
Substitution (2) is the only place the constraint enters; afterwards the problem is an unconstrained quadratic in , and full row rank of is never used again except to guarantee a feasible . The proof then separates two different ways to fail. Negative curvature is detected by one direction with , and the linear term cannot rescue it because the quadratic term grows faster. Flat directions are subtler: symmetry of is spent on , which turns the algebraic condition into a geometric one, a flat direction along which the reduced gradient has a nonzero component. The key move in the remaining case is completing the square around a solution of , which writes the gap to every competitor as a quadratic form in . Positive semidefiniteness is used a second time in the uniqueness step: for an indefinite matrix a zero quadratic form does not force a vector into the kernel.
Common mistake
(Testing the full Hessian instead of the reduced one)
Indefiniteness of does not rule out a unique constrained minimizer, and the constraint may remove every direction of negative curvature: for with , the reduced Hessian is . Only , the curvature along feasible directions, decides the classification. A positive definite does give , but that is a sufficient condition, not the test.
Multipliers and a concrete calculation
At a feasible point, stationarity in every feasible direction means . Because , this holds exactly when a multiplier exists with
Full row rank makes the multiplier unique for a given stationary . The system detects stationary points, not automatically minima. Whether it determines them uniquely is again a question about .
Proposition 4.3.3
(Nonsingularity of the KKT matrix)
Under the assumptions of (1), the coefficient matrix of (3) is nonsingular if and only if the reduced Hessian is nonsingular.
Proof
(Solve the homogeneous system in null-space coordinates)
Consider the homogeneous system , . The second equation gives ; multiplying the first equation by gives , since . If is nonsingular then , so , and with injective gives . Conversely, if for nonzero , then is orthogonal to every column of , so it lies in : write . Then is a nonzero homogeneous solution, because has independent columns.
Worked example 4.3.4
(A constraint removes the unconstrained answer)
Minimize subject to . Set and . Here and , so , and . Hence and . The gradient there is , so (3) holds with . Since , this is the unique global constrained minimizer, with value . The unconstrained minimizer is infeasible.
The numbers and are tied to the basis, while the minimizer is not.
Worked example 4.3.5
(A different null-space basis)
Repeat the calculation with . Then and , so and , the same point. Rescaling the basis by multiplies by and by , but leaves the sign of and the solution set unchanged.
The edge case of the classification is a reduced Hessian that is singular but still allows a minimizer.
Worked example 4.3.6
(A singular reduced Hessian with a line of minimizers)
Minimize subject to . Here
Take and with columns . Then is singular, and . The solutions of are , so the minimizers are for every real , all with value . At each of them and (3) holds with . The KKT matrix is singular, as the proposition predicts, but the system is consistent.
Counterexample mode
An invertible KKT system can describe a maximum
Minimize subject to . Here , , and , so is nonsingular. The KKT system has the unique solution , but . Nonsingularity gives a unique stationary point, not a minimum; the classification also needs .
Practice with solutions
Quick check
(Minimize subject to . Describe all minimizers.)
Solution · Answer
Every is a minimizer. With , and , so the reduced problem is constant.
Quick check
(Minimize subject to . Does a minimizer exist?)
Solution · Answer
No. but is not in its range ; the feasible values at tend to .
Quick check
(For and constraint , is the constrained minimizer of unique?)
Solution · Answer
Yes. The reduced Hessian is , so uniquely minimizes, even though is indefinite on the whole space.
The full-row-rank assumption simplifies the multiplier discussion. Redundant equations can describe the same feasible set, but then multipliers may not be unique; remove redundancies or state a separate result before using (3).