Projected Lagrangian Methods Based on the Trajectories of Penalty and Barrier Functions.

摘要

This report contains a complete derivation and description of two algorithms for nonlinearly constrained optimization which are based on properties of the solution trajectory of the quadratic penalty function and the logarithmic barrier function. The methods utilize the penalty and barrier functions only as merit functions, and do not generate iterates by solving a sequence of ill-conditioned problems. The search direction is the solution of a simple, well-posed quadratic program (QP), where the quadratic objective function is an approximation to the Lagrangian function; the steplength is based on a sufficient decrease in a penalty or barrier function, to ensure progress toward the solution. The penalty trajectory algorithm was first proposed by Murray in 1969; the barrier trajectory algorithm, which retains feasibility throughout, was given by Wright in 1976. Here we give a unified presentation of both algorithms, and indicate their relationship to other QP-based methods. Full details of implementation are included, as well as numerical results that display the success of the methods on non-trivial problems. (Author)