Convergence Analysis of Approximate Primal Solutions in Dual First-Order Methods

• Published in: SIAM journal on optimization 2016-01, Vol.26 (4), p.2430-2467
• Main Authors: Lu, Jie, Johansson, Mikael
• Format: Article
• Language: English
• Subjects: Convergence analysis; Convergence properties; Convex optimization; Dual optimization; Dual optimizations; Error analysis; Fast gradient methods; First order method; First-order methods; Gradient methods; Iterative methods; Large-scale convex optimization; Numerical analysis; Primal convergence; Projected gradient methods
• ISSN: 1052-6234; 1095-7189; 1095-7189
• DOI: 10.1137/15M1008956

Dual first-order methods are powerful techniques for large-scale convex optimization. Although an extensive research effort has been devoted to studying their convergence properties, explicit convergence rates for the primal iterates have essentially only been established under global Lipschitz continuity of the dual gradient. This is a rather restrictive assumption that does not hold for several important classes of problems. In this paper, we demonstrate that primal convergence rate guarantees can also be obtained when the dual gradient is only locally Lipschitz. The class of problems that we analyze admits general convex constraints including nonlinear inequality, linear equality, and set constraints. As an approximate primal solution, we take the minimizer of the Lagrangian computed when evaluating the dual gradient. We first derive error bounds for this approximate primal solution in terms of the errors of the dual variables. Then we establish convergence rates of the dual variables when dual problems with locally Lipschitz gradient are solved using a projected gradient method and when dual problems with Lipschitz gradient over the dual feasible set are solved using fast gradient methods. By combining these results, we show that the suboptimality and infeasibility of the approximate primal solution at iteration k are no worse than O(1/ √ k) when the projected dual gradient method is used and O(1/k) when a fast dual gradient method is used.