  


An acceleration procedure for optimal firstorder methods
Michel Baes(michel.baesifor.math.ethz) Abstract: We introduce in this paper an optimal firstorder method that allows an easy and cheap evaluation of the local Lipschitz constant of the objective's gradient. This constant must ideally be chosen at every iteration as small as possible, while serving in an indispensable upper bound for the value of the objective function. In the previously existing variants of optimal firstorder methods, this upper bound inequality was constructed from points computed during the current iteration. It was thus not possible to select the optimal value for this Lipschitz constant at the beginning of the iteration. In our variant, the upper bound inequality is constructed from points available before the current iteration, offering us the possibility to set the Lipschitz constant to its optimal value at once. This procedure, even if efficient in practice, presents a higher worsecase complexity than standard optimal firstorder methods. We propose an alternative strategy that retains the practical efficiency of this procedure, while having an optimal worsecase complexity. We show how our generic scheme can be adapted for smoothing techniques, and perform numerical experiments on large scale eigenvalue minimization problems. As compared with standard optimal firstorder methods, our schemes allows us to divide computation times by two to three orders of magnitude for the largest problems we considered. Keywords: Convex Optimization, FirstOrder Methods, Eigenvalue Optimization Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Category 2: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Download: [PDF] Entry Submitted: 07/17/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  