  


AN OPTIMAL ALGORITHM FOR CONSTRAINED DIFFERENTIABLE CONVEX OPTIMIZATION
Clóvis C. Gonzaga(clovismtm.ufsc.br) Abstract: We describe three algorithms for solving differentiable convex optimization problems constrained to simple sets in $ \R^n $, i.e., sets on which it is easy to project an arbitrary point. The first two algorithms are optimal in the sense that they achieve an absolute precision of $ \varepsilon $ in relation to the optimal value in $ O(1/\sqrt\varepsilon) $ iterations using only first order information. This complexity depends on a Lipschitz constant $ L $ for the function derivatives and on a strong convexity constant $ \mu\geq 0 $. The first algorithm extends to the constrained case a wellknown method devised by Nesterov \cite{nesterov1} for unconstrained problems, and includes a procedure guessing the unknown value of $ L $. The complexity analysis follows a simpler geometric approach. The other algorithms have several enhancements, including line searches that improve the performance: the second algorithm is enhanced and optimal; the third relaxes somewhat the optimality to obtain the best practical performance. Numerical tests for boxconstrained quadratic problems are presented in the last section. Keywords: optimal algorithms, convex problems Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Technical Report, Federal University of Paraná, Dep. of Mathematics, Brazil, June, 2011. Download: [PDF] Entry Submitted: 06/06/2011 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  