Projected Newton Methods for Optimization Problems with Simple Constraints

Abstract

Abstract. We consider the problem min {f(x)\\x 201, and propose algorithms of the form xk+, = [xt-akDkvf(xk)]+, where [.I+ denotes projection on the positive orthant, ak is a stepsize chosen by an Armijo-like rule and Dk is a positive definite symmetric matrix which is partly diagonal. We show that Dk can be calculated simply on the basis of second derivatives off so that the resulting Newton-like algorithm has a typically superlinear rate of convergence. With other choices of Dk convergence at a typically linear rate is obtained. The algorithms are almost as simple as their unconstrained counterparts. They are well suited for problems of large dimension such as those arising in optimal control while being competitive with existing methods for low-dimensional problems. The effectiveness of the Newton-like algorithm is demonstrated via computational examples involving as many as 10,000 variables. Extensions to general linearly constrained problems are also provided. These extensions utilize a notion of an active generalized rectangle patterned after the notion of an active manifold used in manifold suboptimization methods. By contrast with these methods, many constraints can be added or subtracted from the binding set at each iteration without the need to solve a quadratic programming problem. 1. Introduction. We