Optimization Online


A Primal-Dual Trust Region Algorithm for Nonlinear Optimization

E. Michael Gertz (gertz***at***mcs.anl.gov)
Philip E. Gill (peg***at***optimal.ucsd.edu)

Abstract: This paper concerns general (nonconvex) nonlinear optimization when first and second derivatives of the objective and constraint functions are available. The proposed method is based on finding an approximate solution of a sequence of unconstrained subproblems parameterized by a scalar parameter. The objective function of each unconstrained subproblem is an augmented penalty-barrier function that involves both primal and dual variables. Each subproblem is solved using a second-derivative Newton-type method that employs a combined trust-region and line search strategy to ensure global convergence. It is shown that the trust-region step can be computed by factorizing a sequence of systems with diagonally-modified primal-dual structure, where the inertia of these systems can be determined without recourse to a special factorization method. This has the benefit that off-the-shelf linear system software can be used at all times, allowing the straightforward extension to large-scale problems.

Keywords: nonlinear optimization -- constrained minimization -- primal-dual

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Optimization Technical Report 02-09, University of Wisconsin, Madison Computer Sciences Department, October 2002. Departement of Mathematics Report NA 02-1, University of California, San Diego, October 2002

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 11/04/2002
Entry Accepted: 11/04/2002
Entry Last Modified: 11/04/2002

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society