A Matrix-free Algorithm for Equality Constrained Optimization Problems with Rank-deficient Jacobians

Frank E. Curtis (fecurtgmail.com)
Jorge Nocedal (nocedaleecs.northwestern.edu)
Andreas Wächter (andreaswwatson.ibm.com)

Abstract: We present a line search algorithm for large-scale constrained optimization that is robust and efficient even for problems with (nearly) rank-deficient Jacobian matrices. The method is matrix-free (i.e., it does not require explicit storage or factorizations of derivative matrices), allows for inexact step computations, and is applicable for nonconvex problems. The main components of the approach are a trust region subproblem for handling ill-conditioned or inconsistent linear models of the constraints and a process for attaining a sufficient reduction in a local model of a penalty function. We show that the algorithm is globally convergent to first-order optimal points or to stationary points of an infeasibility measure. Numerical results are presented.

Keywords: large-scale optimization, constrained optimization, nonconvex programming, trust regions, inexact linear system solvers, Krylov subspace methods

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Infinite Dimensional Optimization (Other )

Citation: F. E. Curtis, J. Nocedal, and A. Wächter, “A Matrix-free Algorithm for Equality Constrained Optimization Problems with Rank-Deficient Jacobians,” SIAM Journal on Optimization, 20(3): 1224–1249, 2009.

Download:

Entry Submitted: 05/20/2008
Entry Accepted: 05/20/2008
Entry Last Modified: 05/31/2014

Modify/Update this entry