Accelerated Uzawa methods for convex optimization

Min Tao, Xiaoming YUAN

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

We focus on a linearly constrained strongly convex minimization model and discuss the application of the classical Uzawa method. Our principal goal is to show that some existing acceleration schemes can be used to accelerate the Uzawa method in the sense that the worst-case convergence rate (measured by the iteration complexity) of the resulting accelerated Uzawa schemes is O(1/k2) where k represents the iteration counter. Our discussion assumes that the objective function is given by a black-box oracle; thus an inexact version of the Uzawa method with a sequence of dynamically-chosen step sizes is implemented. A worst-case convergence rate of O(1/k) is also shown for this inexact version. Some preliminary numerical results are reported to verify the acceleration effectiveness of the accelerated Uzawa schemes and their superiority over some existing methods.

Original languageEnglish
Pages (from-to)1821-1845
Number of pages25
JournalMathematics of Computation
Volume86
Issue number306
DOIs
Publication statusPublished - 2017

Scopus Subject Areas

  • Algebra and Number Theory
  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Acceleration
  • Black-box oracle
  • Convergence rate
  • Convex optimization
  • Uzawa method

Fingerprint

Dive into the research topics of 'Accelerated Uzawa methods for convex optimization'. Together they form a unique fingerprint.

Cite this