A Primal-Dual Trust Region Algorithm for Nonlinear Optimization
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.