New algorithms for maximization of concave functions with box constraints

This paper considers the problem of maximizing a differentiable concave function subject to bound constraints and a Lipschitz condition on the gradient, using active set strategies. A general model algorithm for this probem is proposed. The algorithm includes a procedure for deciding when to leave a face of the polytope without having reached a stationary point relative to that face, guaranteeing that return to that face excludes a neighborhood of fixed size of the current point. Mild conditions are required to abandon a face, which may possibly never be visited again, and the authors show that any face may be revisited at most a finite number of times. They show a bound for this quantity. The authors prove global convergence for this algorithm and they also show that it identifies the correct optimal face in a finite number of iterations, even without any nondegeneracy condition, when the authors use the ‘chopped gradient’, as the direction on which they leave any face. The authors combine the active set strategy proposed with a gradient projection method following the approach of Morè-Toraldo, in order to accelerate the identification of the correct optimal face.