Text

Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems

We consider the convex-concave saddle point problem
, where the decision variables and/or are subject to certain multi-block structure and affine coupling constraints, and possesses certain separable structure. Although the minimization counterpart of this problem has been widely studied under the topics of ADMM, this minimax problem is rarely investigated. In this paper, a convenient notion of -saddle point is proposed, under which the convergence rate of several proposed algorithms are analyzed. When only one of and has multiple blocks and affine constraint, several natural extensions of ADMM are proposed to solve the problem. Depending on the number of blocks and the level of smoothness, or convergence rates are derived for our algorithms. When both and have multiple blocks and affine constraints, a new algorithm called xtra- radient Method of ultipliers (EGMM) is proposed. Under desirable smoothness conditions, an rate of convergence can be guaranteed regardless of the number of blocks in and . An in-depth comparison between EGMM (fully primal-dual method) and ADMM (approximate dual method) is made over the multi-block optimization problems to illustrate the advantage of the EGMM.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON OPTIMIZATION; Vol.33 No.2 April-June 2023

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1035-1060

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

SADDLE POINT PROBLEM
FIRST-ORDER METHOD
PRIMAL-DUAL METHOD
MULTI-BLOCK PROBLEM
AFFINE CONSTRAINTS

Info Detail Spesifik

https://doi.org/10.1137/21M1451944

Pernyataan Tanggungjawab

Junyu Zhang, Mengdi Wang, Mingyi Hong, Shuzhong Zhang

Versi lain/terkait

Lampiran Berkas

Komentar