UC San Diego

Projected-search methods for bound-constrained optimization are based on searching along a continuous path obtained by projecting a search direction onto the feasible region. These methods have the potential to change the direction of the search path multiple times along the boundary of the feasible region at the cost of computing a single direction. However, as the objective function is only piecewise differentiable along the path, conventional projected-search methods are limited at using a simple backtracking procedure to obtain a step that satisfies an “Armijo-like” sufficient decrease condition. To extend the benefits of Wolfe line search for unconstrained optimization to projected-search methods, a new quasi-Wolfe step is introduced. Two general classes of projected-search methods that use the new quasi-Wolfe search are then formulated and analyzed. These methods may be broadly categorized as either active-set methods or interior methods. Additionally, a new quasi-Newton projected-search method UBOPT is proposed for unconstrained and bound-constrained optimization. The method computes quasi-Newton directions in a sequence of subspaces, and employs the framework of the class of projected-search active-set methods.

Furthermore, a new interior method is proposed for general nonlinearly constrained optimization, combining 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. The shifts allow the method to be safely “warm started” from a good approximate solution and eliminate the ill-conditioning of the associated linear equations that may occur when the variables are close to zero. The approximate Newton direction is used in conjunction with a new projected-search algorithm that employs a flexible non-monotone quasi-Armijo line search for the minimization of each penalty-barrier function. Numerical results demonstrate that the new method requires significantly fewer iterations than a conventional interior method, thereby reducing the number of times that the search direction need be computed.