UC San Diego

The main goal of this dissertation is to study the formulation and analysis of primal-dual path-following methods for nonlinear programming (NLP), which involves the minimization or maximization of a nonlinear objective function subject to constraints on the variables. Two important types of nonlinear program are problems with nonlinear equality constraints and problems with nonlinear inequality constraints. In this dissertation, two new methods are proposed for nonlinear programming. The first is a new primal-dual path-following augmented Lagrangian method (PDAL) for solving a nonlinear program with equality constraints only. The second is a new primal-dual path-following shifted penalty-barrier method (PDPB) for solving a nonlinear program with a mixture of equality and inequality constraints. The method of PDPB may be regarded as an extension of PDAL to handle nonlinear inequality constraints.

Algorithms PDAL and PDPB are iterative methods that share the same "two-level" structure involving outer and inner iterations. In the outer iteration of PDAL, the optimality conditions are perturbed to define a "path-following trajectory'' parameterized by a set of Lagrange multiplier estimates and a penalty parameter. The iterates are constructed to closely follow the trajectory towards a constrained local minimizer of the nonlinear program. If an outer iterate deviates significantly from the trajectory, then an inner iteration is invoked in which a primal-dual augmented Lagrangian merit function is minimized to force the iterates back to a neighborhood of the trajectory.

A similar approach is used to handle the inequality constraints in PDPB. In this case, the trajectory is followed towards a local solution of the mixed-constraint nonlinear program. This trajectory is parameterized by a set of Lagrange multiplier estimates and penalty and barrier parameters associated with the equality and inequality constraints. If an iterate moves away from the trajectory, a primal-dual shifted penalty-barrier merit function is minimized using a trust-region method. By introducing slack variables, global convergence can be achieved from any starting point without the need for an initial strictly feasible point. Furthermore, numerical experiments indicate that when minimizing the shifted barrier function, the trust-region method requires fewer matrix factorizations and iterations than a comparable line-search method.