Convex Optimization 2026, 40 - Equality Constrained Minimization

Given a function f that is convex and twice continuously differentiable, subject to Ax = b with A ∈ ℝ^p×n, rank A = p < n, and assuming that an optimal solution to minimize f exists, then Ax^* = b, ∇f(x^*) + A^Tv^* = 0 (Eq. 10.1 - 2). This resolves to solving the KKT equations. The first set of equations are dual feasibility equations, which are generally nonlinear. Equality constrained minimization problems can be reduced to an equivalent unconstrained problem through elimination of constraints. Alternatively, one could solve the dual problem through unconstrained minimization, then recover the solution of the equality constrained problem (p. 521). If f is of the form f(x) = (1/2)x^TPx + q^Tx + r with optimality conditions Ax^* = b, Px^* + q + A^Tv^* = 0. This is the KKT system for the equality constrained quadratic optimization problem. The emerging coefficient matrix is the KKT matrix (Eq. 10.4). If it's singular, but the system is solveable, the quadratic optimization problem is unbounded below, or infeasible. Nonsingularity of the KKT matrix is equivalent to N(P) ∩ N(A) = {0}, P being positive definite on the nullspace of A, or F^TPF ⪯ 0 (10.1.1).

Generally, the equality constrained problem can be approached by eliminating the equality constraints, then solving the unconstrainted problem as for unconstrained minimization. For this, find a matrix F ∈ ℝ^{n×(n - p)} and vector x' ∈ ℝⁿ so that { x | Ax = b} = {Fz + x' | z ∈ ℝ^{n - p}} with x' a particular solution for Ax = b, and F a matrix whose range is the nullspace of A. Then, minimize g(z) = f(Fz + x'). An optimal dual variable v* = -(AA^T)^-1A∇f(x'). F is not generally unique. For T ∈ ℝ^{(n - p)×(n - p)} nonsingular, then F' = FT is also a suitable elimination matrix. In that case, minimize f(F'z' + x') = f(F(Tz') + x') for the same result by change of coordinates (p. 524) (10.1.2). Alternatively, the dual can be solved, and then the optimal primal variable recovered afterward. The dual problem is maximizing g(v) = -b^Tv + inf(f(x) + v^TAx) = ... = -b^Tv - f*(-A^Tv). If an optimal point is assumed, this problem is strictly feasible. (10.1.3)

The newton step for an equality constrained problem at a feasible point x can be derived by replacing the objective with its second order Taylor approximation, f(x) + ∇f(x)^Tv + (1/2)v^T∇²f(x)v. From this, the Newton step can be found from the matrix equation

(Eq. 10.11). The Newton step and associated vector w can be read as the solution of linearized approximation of the optimality conditions. The Newton decrementfor the equality constrained problem is determined the same way as in the unconstrained case. The affine invariance of this case can be checked by performing a change of coordinates on the matrix equation and recovering the original Newton step upon back-transformation (10.2.1). Overall, the application of Newton's method doesn't differ whether the problem is constrained or not (10.2.2).