A Projected-Search Interior Method for Nonlinear Optimization
by Philip E. Gill, Minxin Zhang
This paper concerns the formulation and analysis of a new interior method for general nonlinearly constrained optimization that combines a shifted primal-dual interior method with a projected-search method for bound-constrained optimization. The method involves the computation of an approximate Newton direction for a primal-dual penalty-barrier function that incorporates shifts on both the primal and dual variables. Shifts on the dual variables allow the method to be safely ``warm started'' from a good approximate solution and eliminates the ill-conditioning of the associated linear equations that may occur when the dual variables are close to zero. The approximate Newton direction is used in conjunction with a new projected-search line-search algorithm that employs a flexible non-monotone quasi-Armijo line search for the minimization of each penalty-barrier function. Numerical results show that the proposed method requires fewer iterations than a conventional interior method, thereby reducing the number of times that a search direction must be computed. In particular, results from a set of quadratic programming test problems indicate that the method is particularly well-suited to solving the quadratic programming subproblem in a sequential quadratic programming method for nonlinear optimization.