[Home]
[
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
A Projected-Search Interior Method for Nonlinear Optimization
by Philip E. Gill, Minxin Zhang
Abstract:
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.
UCSD-CCoM-22-01.pdf February 2022
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
Directors:
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
by Philip E. Gill, Minxin Zhang
Abstract:
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.
UCSD-CCoM-22-01.pdf February 2022