学术活动

Approximate first-order primal-dual algorithms for the saddle point problems

2020-11-07 14:19

报告人: 韩德仁

报告人单位: 北京航空航天大学

时间: 2020.11.8 15:50-16:30

地点: 天津大学卫津路校区14楼214

开始时间: 2020

报告人简介: 教授

年:

日月:

We propose two approximate versions of the first-order primal-dual algorithm (PDA) for solving a class of convex-concave saddle point problems. The introduced approximate criteria are easy to implement in the sense that they only involve the subgradient of a certain function at the current iterate. The first approximate PDA solves both subproblems inexactly and adopts absolute error criteria, which are based on nonnegative summable sequences. The second approximate PDA, assuming that one of the PDA subproblems can be solved exactly, solves the other subproblem approximately and adopts a relative error criterion. The relative error criterion only involves a single parameter ranging in [0; 1), which makes the method more applicable. For both versions, we establish the global convergence and O(1=N) rate of convergence measured by the iteration complexity, where N counts the number of iteration. Under further assumptions that partial of the underlying functions and the whole underlying functions are strongly convex, we show the accelerated O(1=N 2) and linear rate of convergence, respectively, for the inexact PDA with absolute error criteria. We then prove that these inexact criteria can also be extended to solve a class of more general problems. Finally, we perform some numerical experiments on sparse recovery and image processing problems, and the results demonstrate the feasibility and superiority of the proposed methods.


Contact us

Add:Building 32, The School of Mathematics, Tianjin University Beiyangyuan Campus,

        No. 135, Ya Guan Road, Jinnan District, Tianjin, PRC 

Tel:022-27402850   Mail:math@tju.edu.cn