Optimizing Costly Functions with Simple Constraints: A Limited-Memory Projected Quasi-Newton Algorithm

An optimization algorithm for minimizing a smooth function over a convex set is de-scribed. Each iteration of the method com-putes a descent direction by minimizing, over the original constraints, a diagonal plus low-rank quadratic approximation to the function. The quadratic approximation is constructed using a limited-memory quasi-Newton update. The method is suitable for large-scale prob-lems where evaluation of the function is sub-stantially more expensive than projection onto the constraint set. Numerical experiments on one-norm regularized test problems indi-cate that the proposed method is competitive with state-of-the-art methods such as bound-constrained L-BFGS and orthant-wise descent. We further show that the method generalizes to a wide class of problems, and substantially improves on state-of-the-art methods for prob-lems such as learning the structure of Gaus-sian graphical models and Markov random fields. 1