Inexact Sequential Quadratic Programming Methods for Large-Scale Nonlinear Optimization

Frank Edward Curtis

doi:https://doi.org/10.21985/N2R99V

Work

Inexact Sequential Quadratic Programming Methods for Large-Scale Nonlinear Optimization

Public Deposited

Download PDF

Download All Files (.zip)

This thesis concerns the development of robust algorithms for large-scale nonlinear programming. Despite recent advancements in high-performance computing power, classes of problems exist that continue to challenge the practical limits of contemporary optimization methods. The focus of this dissertation is the design and analysis of algorithms intended to achieve economy of computation for the solution of such problems, where, for ease of presentation, the discussion is framed in the context of equality constrained optimization. The first part of this thesis concerns the development of a globally convergent inexact Sequential Quadratic Programming (SQP) framework. The novelty of the approach is that it is matrix-free (i.e., only mechanisms for computing products of vectors with Jacobian and Hessian matrices are required), thereby avoiding a need for the explicit formation of the arising iteration matrices. Iterative linear algebra techniques, for example, can then be used in place of factorization methods, allowing the introduction of inexactness into the step computation process to achieve further savings in computation. The algorithm automatically determines when a given inexact SQP step makes sufficient progress toward a solution of the nonlinear program, as measured by an exact penalty function, in order to ensure global convergence to a first order optimal point. An analysis of the global behavior of the algorithm is presented under common conditions, and numerical results are presented for a large collection of test problems and two realistic applications. Finally, algorithmic enhancements are provided for cases where certain convexity assumptions about the problem formulation may fail to hold. In the latter part of this thesis, a new globalization mechanism is proposed. The method expands the definition of a standard penalty function so that during each iteration the penalty parameter can be chosen as any number within a prescribed interval, rather than a fixed value. This increased flexibility in the step acceptance procedure is designed to promote long productive steps and fast convergence. An analysis of the global convergence properties of the mechanism in the context of a line search SQP method and numerical results for the <em>KNITRO</em> software package are presented.

Last modified