- AN OPTIMAL ALGORITHM FOR CONSTRAINED DIFFERENTIABLE CONVEX OPTIMIZATION Clóvis C. Gonzaga(clovismtm.ufsc.br) Elizabeth W. Karas(ewkarasgmail.com) Diane R. Rossetto(dianerrime.usp.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 well-known 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 box-constrained 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/2011Entry Accepted: 06/06/2011Entry Last Modified: 06/06/2011Modify/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 Optimization Online is supported by the Mathematical Optmization Society.