Projected Newton Methods for Optimization Problems with Simple Constraints

Abstract

We consider the problem $\min \{ f(x)|x \geqq 0\} $, and propose algorithms of the form $x_{k + 1} = [x_k - \alpha _k D_k \nabla f(x_k )]^ + $, where $[ \cdot ]^ + $ denotes projection on the positive orthant, $\alpha _k $ is a stepsize chosen by an Armijo-like rule and $D_k $ is a positive definite symmetric matrix which is partly diagonal. We show that $D_k $ can be calculated simply on the basis of second derivatives of f so that the resulting Newton-like algorithm has a typically superlinear rate of convergence. With other choices of $D_k $ 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.