Optimization Online


An inexact proximal path-following algorithm for constrained convex minimization

Quoc Tran Dinh(quoc.trandinh***at***epfl.ch)
Anastasios Kyrillidis(anastasios.kyrillidis***at***epfl.ch)
Volkan Cevher(volkan.cevher***at***epfl.ch)

Abstract: Many scientific and engineering applications feature large-scale non-smooth convex minimization problems over convex sets. In this paper, we address an important instance of this broad class where we assume that the non-smooth objective is equipped with a tractable proximity operator and that the convex constraints afford a self-concordant barrier. We provide a new joint treatment of proximal and self-concordant barrier concepts and illustrate that such problems can be efficiently solved without lifting problem dimensions. We propose an inexact path-following algorithmic framework and theoretically characterize the worst case convergence as well as computational complexity of this framework, and also analyze its behavior when the proximal subproblems are solved inexactly. To illustrate our framework, we apply its instances to both synthetic and real-world applications and illustrate their accuracy and scalability in large-scale settings. As an added bonus, we describe how our framework can obtain points on the Pareto frontier of regularized problems with self-concordant objectives in a tuning free fashion.

Keywords: Inexact path-following algorithm, self-concordant barrier, tractable proximity, proximal-Newton method, constrained convex optimization

Category 1: Convex and Nonsmooth Optimization

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 11/07/2013
Entry Accepted: 11/07/2013
Entry Last Modified: 11/07/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society