Optimizing costly functions with simple constraints: a limited-memory projected Quasi-Newton algorithm

TitleOptimizing costly functions with simple constraints: a limited-memory projected {Quasi-Newton} algorithm
Publication TypeConference
Year of Publication2009
AuthorsEwout van den Berg, Mark Schmidt, Michael P. Friedlander, Kevin Murphy
Conference NameSLIM
Volume12
Month04
KeywordsSLIM
Abstract

An optimization algorithm for minimizing a smooth function over a convex set is described. Each iteration of the method computes 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 problems where evaluation of the function is substan- tially more expensive than projection onto the constraint set. Numerical experiments on one-norm regularized test problems indicate that the proposed method is competitve 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 problems such as learning the structure of Gaussian graphi- cal models (involving positive-definite matrix constraints) and Markov random fields (involving second-order cone constraints).

URLhttp://www.cs.ubc.ca/ mpf/papers/SchmidtBergFriedMurph09.pdf
Citation Keyvandenberg2009SLIMocf