Part 1 involves iterative methods for solving linear systems, least-squares problems, and least-norm problems. We show that solution error bounds at each iteration of these methods can be computed efficiently provided certain additional spectral information of the linear operators involved. Part 2 develops a smooth exact penalty method for constrained nonlinear optimization based on the work of Fletcher (1970, 1973b), where the methods of Part 1 play a central role in evaluating the penalty function and its gradients.Often the most computationally intensive operation in numerical methods is solving linear systems, least-squares, and least-norm problems. Further, these linear systems often do not need to be solved to high accuracy---many methods can accept solutions solved to a prescribed accuracy. For positive definite systems, Part 1 develops Euclidean-norm error bounds for the Krylov methods SYMMLQ and CG using Gauss-Radau quadrature, when provided an underestimate of the smallest eigenvalue. For least-squares and least-norm problems, we develop solvers LSLQ and LNLQ (equivalent to SYMMLQ applied to the associated normal equations) and extend the error-bounding procedure for SYMMLQ to LSLQ and LNLQ. Similarly, the error-bounding procedure for CG is extended to LSQR and CRAIG. We compare with existing approaches for bounding errors, using linear systems from a standard test set and from the penalty method of Part 2. Our approach is remarkably tight for the LQ methods (when good estimates of the spectrum are available), and gives reliable bounds for the CG-based methods.In Part 2, we develop a general constrained nonlinear optimization algorithm based on a smooth penalty function proposed by Fletcher (1970, 1973b). We first present the penalty function for equality-constrained problems, then provide a new smooth extension to inequality constrained problems. Although it was historically considered to be computationally prohibitive in practice, we demonstrate that the computational kernels required are no more expensive than other widely accepted methods for nonlinear optimization. The main computational kernel required to evaluate the penalty function and its derivatives is solving a structured linear system. This system can be solved efficiently by storing a single factorization per iteration. Alternatively, we can adapt the penalty function to the class of factorization-free algorithms by solving the linear system iteratively, using for example the methods described in Part 1. The penalty function shows particular promise in cases where such linear system can be solved efficiently, e.g., for PDE-constrained optimization problems where efficient preconditioners exist, and opens the door to optimization solvers that accept inexact evaluations and derivatives. We discuss extensions including handling simple constraints explicitly, regularizing the penalty function, and demonstrate the merits of this approach on nonlinear optimization problems with PDE-constraints, and those from a standard test set.
展开▼
