On the Goldstein-Levitin-Polyak gradient projection method

TLDR

The paper examines aspects of the gradient projection method introduced by Goldstein, Levitin and Polyak, and later adapted by McCormick. The authors aim to propose and analyze convergent step‑size rules for use with the gradient projection method. The proposed step‑size rules, inspired by the Armijo rule, identify active inequality constraints in finite iterations and include quadratically convergent combinations with Newton’s method. These rules enable conversion of the method to conjugate‑direction, quasi‑Newton, or Newton’s methods, yielding superlinear convergence and high efficiency on large‑scale problems with many simple constraints, such as those in optimal control.

Abstract

This paper considers some aspects of a gradient projection method proposed by Goldstein [1], Levitin and Polyak [3], and more recently, in a less general context, by McCormick [10]. We propose and analyze some convergent step-size rules to be used in conjunction with the method. These rules are similar in spirit to the efficient Armijo rule for the method of steepest descent and under mild assumptions they have the desirable property that they identify the set of active inequality constraints in a finite number of iterations. As a result the method may be converted towards the end of the process to a conjugate direction, quasi-Newton or Newton's method, and achieve the attendant superlinear convergence rate. As an example we propose some quadratically convergent combinations of the method with Newton's method. Such combined methods appear to be very efficient for large-scale problems with many simple constraints such as those often appearing in optimal control.