TY - JOUR

T1 - A primal-dual algorithm with line search for general convex-concave saddle point problems

AU - Hamedani, Erfan Yazdandoost

AU - Aybat, Necdet Serhat

N1 - Funding Information:
\ast Received by the editors September 12, 2018; accepted for publication (in revised form) December 13, 2020; published electronically May 11, 2021. https://doi.org/10.1137/18M1213488 Funding: This research was partially supported by NSF grants CMMI-1400217 and CMMI-1635106, and by ARO grant W911NF-17-1-0298. \dagger Industrial \& Manufacturing Engineering Department, The Pennsylvania State University, University Park, PA 16802 USA (evy5047@psu.edu, nsa10@psu.edu).
Publisher Copyright:
© 2021 Society for Industrial and Applied Mathematics

PY - 2021

Y1 - 2021

N2 - 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 L (x, y) = f(x) + Φ (x, y) - h(y) with a general coupling term Φ (x, y) that is not assumed to be bilinear. Assuming ▽ xΦ (·, y) is Lipschitz for any fixed y, and ▽yΦ (·, ·) 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 L (xk, y) - L (x, yk) for the ergodic sequence {xk, yk}. In particular, we show O (1/k) rate when the problem is merely convex in x. Furthermore, assuming Φ (x, ·) is linear for each fixed x and f is strongly convex, we obtain the ergodic convergence rate of O (1/k2)-we are not aware of another single-loop method in the related literature achieving the same rate when Φ 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.

AB - 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 L (x, y) = f(x) + Φ (x, y) - h(y) with a general coupling term Φ (x, y) that is not assumed to be bilinear. Assuming ▽ xΦ (·, y) is Lipschitz for any fixed y, and ▽yΦ (·, ·) 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 L (xk, y) - L (x, yk) for the ergodic sequence {xk, yk}. In particular, we show O (1/k) rate when the problem is merely convex in x. Furthermore, assuming Φ (x, ·) is linear for each fixed x and f is strongly convex, we obtain the ergodic convergence rate of O (1/k2)-we are not aware of another single-loop method in the related literature achieving the same rate when Φ 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.

KW - Convergence rate

KW - Convex programming

KW - First-order method

KW - Line search

KW - Primal-dual method

KW - Saddle point problem

UR - http://www.scopus.com/inward/record.url?scp=85106549637&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85106549637&partnerID=8YFLogxK

U2 - 10.1137/18M1213488

DO - 10.1137/18M1213488

M3 - Article

AN - SCOPUS:85106549637

SN - 1052-6234

VL - 31

SP - 1299

EP - 1329

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 2

ER -