Projected-search methods for bound-constrained minimization are based on performing a line search along a continuous piecewise-linear path obtained by projecting a search direction onto the feasible region. A potential benefit of a projected-search method is that many changes to the active set can be made at the cost of computing a single search direction. As the objective function is not differentiable along the piecewise-linear path, it is not possible to use a line-search based on satisfying the Wolfe conditions, which involve the derivatives at two points on the search path. This means that the step must be computed using a simpler backtracking method. Methods for conventional unconstrained minimization that use the Wolfe conditions are more reliable and efficient than methods based on simple backtracking. For example, if the search direction is generated using a quasi-Newton method, the Wolfe conditions impose a restriction on the directional derivative that guarantees the satisfaction of a necessary condition for the quasi-Newton update to give a positive-definite approximate Hessian. This paper concerns projected-search methods based on a new quasi-Wolfe line search that is appropriate for piecewise differentiable functions. The behavior of the line search is similar to that of a conventional Wolfe line search, except that a step is accepted under a wider range of conditions. These conditions take into consideration steps at which the restriction of the objective function on the search path is not differentiable. Standard existence and convergence results associated with a conventional Wolfe line search are extended to the quasi-Wolfe case. The quasi-Wolfe line search is considered in conjunction with two projected search methods: a limited-memory quasi-Newton method and a new method that combines a primal-dual interior method with a projected search. Computational results show that in these contexts, a quasi-Wolfe line search is substantially more efficient and reliable than an Armijo line search.
Citation
UC San Diego Center for Computational Mathematics, Technical Report CCoM-1-20, March 25, 2020
Article
View Projected-Search Methods for Bound-Constrained Optimization