Mathematical Programming Computation, Volume 12, Issue 3, September 2020
An adaptive primal-dual framework for nonsmooth convex minimization
Quoc Tran-Dinh, Ahmet Alacaoglu, Olivier Fercoq, Volkan Cevher
We propose a new self-adaptive and double-loop smoothing algorithm to solve composite,
nonsmooth, and constrained convex optimization problems. Our algorithm is based on
Nesterov’s smoothing technique via general Bregman distance functions. It self-adaptively
selects the number of iterations in the inner loop to achieve a desired complexity bound
without requiring to set the accuracy a priori as in variants of augmented Lagrangian
methods (ALM). We prove O(1/k)-convergence rate on the last iterate of the outer sequence
for both unconstrained and constrained settings in contrast to ergodic rates which are c
ommon in ALM as well as alternating direction method-of-multipliers literature.
Compared to existing inexact ALM or quadratic penalty methods, our analysis does not rely
on the worst-case bounds of the subproblem solved by the inner loop. Therefore, our
algorithm can be viewed as a restarting technique applied to the ASGARD method in
Tran-Dinh et al. (SIAM J Optim 28(1):96–134, 2018) but with rigorous theoretical
guarantees or as an inexact ALM with explicit inner loop termination rules and
adaptive parameters. Our algorithm only requires to initialize the parameters once,
and automatically updates them during the iteration process without tuning.
We illustrate the superiority of our methods via several examples as compared
to the state-of-the-art.
Full Text: PDF
Imprint and privacy statement
For the imprint and privacy statement we refer to the Imprint of ZIB.
© 2008-2020 by Zuse Institute Berlin (ZIB).