A First-Order Smoothing Technique for a Class of Large-Scale Linear Programs

TitleA First-Order Smoothing Technique for a Class of Large-Scale Linear Programs
Publication TypeJournal Article
Year of Publication2011
AuthorsChen, J, Burer, S
Date Published11/2011
Other NumbersANL/MCS-P1971-1111
Abstract

We study a class of linear programming (LP) problems motivated by large-scale machine learning applications. After reformulating the LP as a convex nonsmooth problem, we apply Nesterov's primal-dual smoothing technique. It turns out that the iteration complexity of the smoothing technique depends on a parameter O that arises because we need to bound the originally unbounded primal feasible set. We design a strategy that dynamically updates O to speed up the convergence. The application of our algorithm to two machine learning problems demonstrates several advantages of the smoothing technique over existing methods.

PDFhttp://www.mcs.anl.gov/papers/1971-1111.pdf