Optimization Online


A golden ratio primal-dual algorithm

Chang Xiaokai (15293183303***at***163.com)

Abstract: This paper presents a golden ratio primal-dual algorithm (GRPDA) for solving convex optimization problems with known bilinear saddle-point structure, using a convex combination of all previous iterates rather than classic inertial technique. Both fixed and adaptive step sizes gained by linesearch are involved, and each iteration of the linesearch requires to update only the dual variable. The convergence and ergodic O(1/N) convergence rate for the primal-dual gap are established under two types of step sizes. In case when one of the prox-functions is strongly convex, we modify our basic method to get a better convergence rate O(1/N^2). Moreover, we observe that GRPDA with fixed step sizes is an inexact Alternating Direction Method of Multipliers (ADMM) with linearization and indefinite proximal regularization. The numerical experiments illustrate the proposed PDA is efficient.

Keywords: Saddle-point problem first order algorithm primal-dual algorithm linesearch convergence rate

Category 1: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 04/07/2020
Entry Accepted: 04/08/2020
Entry Last Modified: 05/28/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society