Skip to yearly menu bar Skip to main content


Unified Methods for Exploiting Piecewise Linear Structure in Convex Optimization

Tyler Johnson · Carlos Guestrin

Area 5+6+7+8 #174

Keywords: [ Convex Optimization ]


We develop methods for rapidly identifying important components of a convex optimization problem for the purpose of achieving fast convergence times. By considering a novel problem formulation—the minimization of a sum of piecewise functions—we describe a principled and general mechanism for exploiting piecewise linear structure in convex optimization. This result leads to a theoretically justified working set algorithm and a novel screening test, which generalize and improve upon many prior results on exploiting structure in convex optimization. In empirical comparisons, we study the scalability of our methods. We find that screening scales surprisingly poorly with the size of the problem, while our working set algorithm convincingly outperforms alternative approaches.

Live content is unavailable. Log in and register to view live content