Abstract
A Newton-type active set algorithm for large-scale minimization subject to polyhedral constraints is proposed. The algorithm consists of a gradient projection step, a second-order Newton-type step in the null space of the constraint matrix, and a set of rules for branching between the two steps. We show that the proposed method asymptotically takes the Newton step when the active constraints are linearly independent and a strong second-order sufficient optimality condition holds. We also show that the method has a quadratic rate of convergence under standard conditions. Numerical experiments are presented illustrating the performance of the algorithm on the CUTEst and on a specific class of problems for which finding second-order stationary points is critical.
Introduction
In the field of mathematical optimization, many real-world applications—ranging from neural network training to financial portfolio management—require minimizing a function subject to polyhedral constraints, typically expressed as a set of linear inequalities $Ax \le b$. As the scale of these problems grows to include thousands or millions of variables, traditional active set methods often encounter a computational bottleneck. These methods generally require solving a general Quadratic Programming (QP) subproblem at every iteration to identify which constraints are "active" (exactly equal to zero) at the solution. The Newton-type Polyhedral Active Set Algorithm (NPASA) is designed to overcome this limitation by providing high-speed convergence while maintaining a low cost per iteration.
The NPASA Framework
NPASA operates by intelligently alternating between two distinct phases to navigate the feasible region and reach an optimal solution efficiently.
Phase 1: Gradient Projection (GP)
The first-order phase utilizes gradient projection to explore the feasible region. By using the gradient of the function to project the current iterate onto the constraints, this phase is highly effective at rapidly identifying the set of active constraints likely to define the final solution. This avoids the need for expensive subproblem solves during the initial exploration phase.
Phase 2: Newton-type Linearly Constrained Optimizer (NLCO)
Once the algorithm identifies a stable set of active constraints, it switches to the NLCO phase. Unlike traditional methods that solve a general QP, NLCO solves a simplified equality-constrained problem within the "null space" of the currently active constraints. This allows the algorithm to take a precise Newton step, which is the primary driver of rapid convergence near the solution.
The Switching Rule and Negative Curvature
The transition between these phases is governed by a sophisticated switching rule. The algorithm monitors two measures of stationarity—indicators of how close the current point is to an optimum—and uses a parameter $\theta$ to decide whether to continue exploring (GP) or begin exploiting the local curvature (NLCO). Furthermore, NPASA explicitly accounts for negative curvature. By identifying directions where the function curves downward, the algorithm can effectively escape saddle points, a feature often missing in standard solvers like IPOPT.
Theoretical Properties
The authors provide a rigorous mathematical foundation for NPASA, proving that the method achieves a quadratic rate of convergence under standard conditions. This implies that as the algorithm approaches the solution, the precision of the result (the number of correct digits) roughly doubles with each iteration. This asymptotic behavior is guaranteed when the active constraints are linearly independent and a strong second-order sufficient optimality condition is met.
Numerical Results
The performance of NPASA was evaluated against established solvers using two primary datasets: the CUTEst benchmark suite and Hamiltonian Cycle Problem (HCP) instances.
CUTEst Benchmarks
On a set of 55 nonlinear problems from the CUTEst suite, featuring up to 7,564 variables, NPASA demonstrated superior efficiency. Performance profiles indicated that NPASA solved approximately 70% of the problems using the fewest function evaluations compared to other tested algorithms.
Hamiltonian Cycle Problem (HCP)
The HCP, a classic graph theory problem, was reformulated as a continuous optimization problem to test the algorithm's ability to find global minimizers in complex landscapes. In tests involving 571 cubic graphs, NPASA found a Hamiltonian Cycle in 81.9% of cases, significantly outperforming PASA (71.2%) and IPOPT (70.9%). Additionally, NPASA was notably more efficient; for 14-node graphs, it averaged approximately 15 function evaluations per run, compared to over 35 for IPOPT.
Conclusion and Future Work
NPASA offers a robust and efficient approach for large-scale nonlinear optimization with polyhedral constraints by avoiding the traditional QP bottleneck and leveraging second-order information. While the current iteration requires the availability of the Hessian matrix, future research may explore "quasi-Newton" variants for applications where second derivatives are unavailable. Additionally, for extremely large-scale problems, the authors suggest an inexact version (NPASA-CG) utilizing the Conjugate Gradient method to further reduce the computational cost of the null-space linear systems.
Summary updated