现在位置:首页 > 学术报告
 

 

Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:

Prof. Yangyang Xu, Department of Mathematical Sciences, Rensselaer Polytechnic Institute, U.S.

Inviter:  
Title:
Optimal first-order method for constrained convex programs
Time & Venue:
2018.6.26 15:30-16:30 Z311
Abstract:
First-order methods have recently been very popular for solving large-scale optimization problems, partly due to its low per-iteration complexity. It has been well known that for smooth convex problems without constraint or with simple-to-project constraint, the best convergence rate of first-order methods is O(1/k^2), where k is the number of gradient evaluations. In this talk, I will first present a linearized augmented Lagrangian method for affinely constrained convex problems. Each iteration, it performs linearization to the smooth part of the objective function but not to the augmented term. It enjoys O(1/k^2) ergodic convergence rate in terms of both objective and feasibility error. Then I will show that if the augmented term is also linearized, O(1/k) is a lower complexity bound, and thus O(1/k^2) convergence rate is generally impossible to achieve. Finally, I will present an optimal first-order method for solving smooth convex programs with both affine and nonlinear functional constraints. Its complexity matches with the lower bound. Comparison to existing works will be discussed.
 

 

附件下载:
 
 
【打印本页】【关闭本页】
电子政务平台   |   科技网邮箱   |   ARP系统   |   会议服务平台   |   联系我们   |   友情链接