2006/10/19 by Elad Hazan, Hazan, Elad
Computer Science · Decision Sciences · Engineering · Mathematics · #Advanced Bandit Algorithms Research #Advanced Optimization Algorithms Research #Advanced Wireless Network Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0610119
arxiv created 2006/10/19 · openalex publication_date 2006/10/19 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Lagrangian relaxation and approximate optimization algorithms have received much attention in the last two decades. Typically, the running time of these methods to obtain a ε approximate solution is proportional to (1)/(ε2). Recently, Bienstock and Iyengar, following Nesterov, gave an algorithm for fractional packing linear programs which runs in \frac1ε iterations. The latter algorithm requires to solve a convex quadratic program every iteration - an optimization subroutine which dominates the theoretical running time. We give an algorithm for convex programs with strictly convex constraints which runs in time proportional to \frac1ε. The algorithm does NOT require to solve any quadratic program, but uses gradient steps and elementary operations only. Problems which have strictly convex constraints include maximum entropy frequency estimation, portfolio optimization with loss risk constraints, and various computational problems in signal processing. As a side product, we also obtain a simpler version of Bienstock and Iyengar's result for general linear programming, with similar running time. We derive these algorithms using a new framework for deriving convex optimization algorithms from online game playing algorithms, which may be of independent interest.