Numerical Investigation of the Powell-Yuan Method for Equality-Constrained Optimization Problems

Details

Supervisors

Nunes Grapiglia, Geovani

Faculty

Ecole polytechnique de Louvain

Degree label

Master [60] en sciences informatiques

Abstract

enThe Powell-Yuan algorithm is a trust-region method for equality-constrained nonlinear optimization with strong global and superlinear local convergence guarantees. Despite its publication in 1991, no open-source implementation has been made available, leaving its practical performance systematically uncharacterized for over three decades. This thesis presents the first open-source implementation of the Powell-Yuan method in Python, built directly from the original paper and including a complete solver for the Celis-Dennis-Tapia (CDT) subproblem based on the Lagrangian dual algorithm of Yuan. The implementation is benchmarked against SciPy's trust-constr (Byrd-Omojokun), SLSQP, and ALGENCAN on 149 equality-constrained problems from the CUTEst library, evaluated using Dolan-More performance profiles. Powell-Yuan achieves a 69.3% solution rate on the restricted problem set. Of the 70 nearly-feasible points it finds, 69 have objective values within 10^-4 of the best objective found by any solver on the same problem, giving a 98.6% near-optimal rate. Here, near-optimal means the returned point is competitive in objective value with the best-known nearly-feasible point across all four methods benchmarked. The central empirical finding is that the CDT subproblem is the main computational bottleneck. Yuan's dual solver requires an O(n^3) Cholesky factorization of an n by n matrix at every inner iteration, and this cost grows prohibitively with problem dimension regardless of implementation language or quality. The median per-iteration cost of Powell-Yuan is 4.7x that of Byrd-Omojokun, rising to 230x on the most CDT-intensive problems. This is an algorithmic bottleneck, not a Python artifact, and serves as the primary obstacle to a practically competitive implementation. A case study analysis identifies a niche subclass of problems, primarily pure nonlinear equation systems where Byrd-Omojokun's stopping criterion fires just above the feasibility threshold, where Powell-Yuan's unified CDT step continues making progress. The thesis concludes that the method's long absence from the optimization ecosystem was not fully justified as the outer algorithm is sound, solution quality is strong, and a subspace or compiled reimplementation that addresses the CDT bottleneck would improve the algorithm to a practically relevant and competitive solver.