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 ([email protected], [email protected]).
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 -