Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 

 

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
DOI: https://doi.org/10.1090/mcom/3145
Published electronically: October 20, 2016
Full-text PDF

Abstract | References | 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.


References [Enhancements On Off] (What's this?)


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
Email: taom@nju.edu.cn

Xiaoming Yuan
Affiliation: Department of Mathematics, Hong Kong Baptist University, Hong Kong, People’s Republic of China
Email: xmyuan@hkbu.edu.hk

DOI: https://doi.org/10.1090/mcom/3145
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