Projected Newton methods for optimization problems with simple constraints
Dimitri P. Bertsekas · 1981
We consider the problem min {f(x)|x ≥ 0} and algorithms of the form xk+1 = [xk - ·k Dk▽f(xk)]+ where [·]+ denotes projection on the positive orthant, αk is a stepsize chosen by an Armijolike 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 of f 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.