Text

A primal-Dual Algorithm With Line Search for General Convex-Concave Saddle Point Problems

In this paper, we propose a primal-dual algorithm with a novel momentum term using the partial gradients of the coupling function that can be viewed as a generalization of the method proposed by Chambolle and Pock in [Math. Program., 159 (2016), pp. 253--287] for solving saddle point problems defined by a convex-concave function $\mathcal{L}(x,y)=f(x)+\Phi(x,y)-h(y)$ with a general coupling term $\Phi(x,y)$ that is not assumed to be bilinear. Assuming $\nabla_x\Phi(\cdot,y)$ is Lipschitz for any fixed $y$, and $\nabla_y\Phi(\cdot,\cdot)$ is Lipschitz, we show that the iterate sequence converges to a saddle point, and for any $(x,y)$, we derive error bounds in terms of $\mathcal{L}(\bar{x}_k,y)-\mathcal{L}(x,\bar{y}_k)$ for the ergodic sequence $\{\bar{x}_k,\bar{y}_k\}$. In particular, we show $\mathcal{O}(1/k)$ rate when the problem is merely convex in $x$. Furthermore, assuming $\Phi(x,\cdot)$ is linear for each fixed $x$ and $f$ is strongly convex, we obtain the ergodic convergence rate of $\mathcal{O}(1/k^2)$---we are not aware of another single-loop method in the related literature achieving the same rate when $\Phi$ is not bilinear. Finally, we propose a backtracking technique which does not require knowledge of Lipschitz constants yet ensures the same convergence results. We also consider convex optimization problems with nonlinear functional constraints, and we show that by using the backtracking scheme, the optimal convergence rate can be achieved even when the dual domain is unbounded. We tested our method against other state-of-the-art first-order algorithms for solving quadratically constrained quadratic programming (QCQP): in the first set of experiments, we considered QCQPs with synthetic data, and in the second set, we focused on QCQPs with real data originating from a variant of the linear regression problem with fairness constraints arising in machine learning.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON OPTIMIZATION; Vol.31 No.2 April-June 2021

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1299-1329

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

CONVEX PROGRAMMING
SADDLE POINT PROBLEM
CONVERGENCE RATE
LINE SEARCH
FIRST-ORDER METHOD
PRIMAL-DUAL METHOD

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Erfan Yazdandoost Hamedani, Necdet Serhat Aybat

Versi lain/terkait

Lampiran Berkas

Komentar