Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Accelerated Uzawa methods for convex optimization

Authors: Min Tao and Xiaoming Yuan
Journal: Math. Comp. 86 (2017), 1821-1845
MSC (2010): Primary 90C25; Secondary 94A08
Published electronically: October 20, 2016
MathSciNet review: 3626538
Full-text PDF

Abstract | Similar Articles | Additional Information

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/k^2)$ 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.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 90C25, 94A08

Retrieve articles in all journals with MSC (2010): 90C25, 94A08

Additional Information

Min Tao
Affiliation: Department of Mathematics, Nanjing University, Nanjing, 210093, People’s Republic of China
MR Author ID: 987506

Xiaoming Yuan
Affiliation: Department of Mathematics, Hong Kong Baptist University, Hong Kong, People’s Republic of China
MR Author ID: 729439

Keywords: Convex optimization, Uzawa method, acceleration, convergence rate, black-box oracle
Received by editor(s): March 31, 2015
Received by editor(s) in revised form: January 28, 2016
Published electronically: October 20, 2016
Additional Notes: The first author was supported by the Natural Science Foundation of China grant NSFC-11301280, and the Fundamental Research Funds for the Central Universities, 020314330019
The second author was supported in part by the General Research Fund from Hong Kong Research Grants Council, HKBU 12300515
Article copyright: © Copyright 2016 American Mathematical Society