A PRIMAL-DUAL ALGORITHM WITH LINE SEARCH FOR GENERAL CONVEX-CONCAVE SADDLE POINT PROBLEMS
A PRIMAL-DUAL ALGORITHM WITH LINE SEARCH FOR GENERAL CONVEX-CONCAVE SADDLE POINT PROBLEMS
复制标题
DOI：
10.1137/18m1213488
复制
发表时间：
2021-01-01
影响因子：
3.1
通讯作者：
Aybat, Necdet Serhat
中科院分区：
文献类型：
--
作者：
Hamedani, Erfan Yazdandoost;Aybat, Necdet Serhat
在本文中，我们提出了一个原始-对偶算法，该算法使用耦合函数的部分梯度，并带有一个新的动量项，可以看作是Chambolle和Pock在[Math. Program.，159（2016），pp. 253-287]求解由凹凸函数L（x，y）= f（x）+ Phi（x，y）- h（y）定义的鞍点问题，其中一般耦合项Phi（x，y）不假定是双线性的。假设del（x）Phi（.，y）对于任何固定的y都是Lipschitz，并且del（y）Phi（.，.)是Lipschitz，我们证明了该序列收敛于鞍点，并且对于任意（x，y），我们得到了遍历序列{（x）over bar（k），（y）over bar（k）}的误差界L（（x）over bar（k），y）- L（x，（y）over bar（k））.特别是，我们显示O（1/k）率时，问题只是凸的x。此外，假设Phi（x，.）是线性的，并且f是强凸的，我们得到了O（1/k（2））的遍历收敛速度-我们不知道在相关文献中的另一个单循环方法在Phi不是双线性的情况下达到了相同的速度。最后，我们提出了一个回溯技术，不需要知识的Lipschitz常数，但确保相同的收敛结果。我们还考虑了非线性函数约束的凸优化问题，我们表明，通过使用回溯计划，即使当对偶域是无界的，也可以达到最佳的收敛速度。我们测试了我们的方法对其他国家的最先进的一阶算法求解二次约束二次规划（QCQP）：在第一组实验中，我们认为QCQP与合成数据，并在第二组中，我们专注于QCQP与真实的数据源于一个变种的线性回归问题与公平性约束中产生的机器学习。
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) + Phi (x, y) - h(y) with a general coupling term Phi (x, y) that is not assumed to be bilinear. Assuming del(x)Phi(., y) is Lipschitz for any fixed y, and del(y)Phi(., .) 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 ((x) over bar (k), y) - L (x, (y) over bar (k)) for the ergodic sequence {(x) over bar (k), (y) over bar (k)}. In particular, we show O (1/k) rate when the problem is merely convex in x. Furthermore, assuming Phi (x, .) is linear for each fixed x and f is strongly convex, we obtain the ergodic convergence rate of 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.