Timezone: »

 
Poster
Unified Methods for Exploiting Piecewise Linear Structure in Convex Optimization
Tyler Johnson · Carlos Guestrin

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #174 #None
in Tuesday Posters »

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.

Keywords: Convex Optimization
[ PDF] 

Author Information

Tyler Johnson (University of Washington)
Carlos Guestrin (University of Washington)

More from the Same Authors