Optimization Online


Fast Projection onto the Simplex and the l1 Ball

Laurent Condat(laurent.condat***at***gipsa-lab.grenoble-inp.fr)

Abstract: A new algorithm is proposed to project, exactly and in finite time, a vector of arbitrary size onto a simplex or a l1-norm ball. The algorithm is demonstrated to be faster than existing methods. In addition, a wrong statement in a paper by Duchi et al. is corrected and an adversary sequence for Michelot’s algorithm is exhibited, showing that it has quadratic complexity in the worst case.

Keywords: Simplex, l1-norm ball, large-scale optimization

Category 1: Convex and Nonsmooth Optimization

Category 2: Applications -- OR and Management Sciences

Citation: Preprint Hal-01056171, v1, Aug. 2014

Download: [PDF]

Entry Submitted: 08/17/2014
Entry Accepted: 08/17/2014
Entry Last Modified: 08/17/2014

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