arrow
Volume 11, Issue 1
Adaptive Parallel Primal-Dual Method for Saddle Point Problems

Xiayang Zhang

Numer. Math. Theor. Meth. Appl., 11 (2018), pp. 187-210.

Published online: 2018-11

Export citation
  • Abstract

The primal-dual hybrid gradient method is a classic way to tackle saddle-point problems. However, its convergence is not guaranteed in general. Some restrictions on the step size parameters, e.g., $τσ  ≤ 1/‖A^TA‖$, are imposed to guarantee the convergence. In this paper, a new convergent method with no restriction on parameters is proposed. Hence the expensive calculation of $‖A^TA‖$ is avoided. This method produces a predictor like other primal-dual methods but in a parallel fashion, which has the potential to speed up the method. This new iteration is then updated by a simple correction to guarantee the convergence. Moreover, the parameters are adjusted dynamically to enhance the efficiency as well as the robustness of the method. The generated sequence monotonically converges to the solution set. A worst-case $\mathcal{O}(1/t)$ convergence rate in ergodic sense is also established under mild assumptions. The numerical efficiency of the proposed method is verified by applications in LASSO problem and Steiner tree problem.

  • Keywords

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{NMTMA-11-187, author = {Xiayang Zhang}, title = {Adaptive Parallel Primal-Dual Method for Saddle Point Problems}, journal = {Numerical Mathematics: Theory, Methods and Applications}, year = {2018}, volume = {11}, number = {1}, pages = {187--210}, abstract = {

The primal-dual hybrid gradient method is a classic way to tackle saddle-point problems. However, its convergence is not guaranteed in general. Some restrictions on the step size parameters, e.g., $τσ  ≤ 1/‖A^TA‖$, are imposed to guarantee the convergence. In this paper, a new convergent method with no restriction on parameters is proposed. Hence the expensive calculation of $‖A^TA‖$ is avoided. This method produces a predictor like other primal-dual methods but in a parallel fashion, which has the potential to speed up the method. This new iteration is then updated by a simple correction to guarantee the convergence. Moreover, the parameters are adjusted dynamically to enhance the efficiency as well as the robustness of the method. The generated sequence monotonically converges to the solution set. A worst-case $\mathcal{O}(1/t)$ convergence rate in ergodic sense is also established under mild assumptions. The numerical efficiency of the proposed method is verified by applications in LASSO problem and Steiner tree problem.

}, issn = {2079-7338}, doi = {https://doi.org/10.4208/nmtma.2018.m1621}, url = {http://global-sci.org/intro/article_detail/nmtma/10650.html} }
TY - JOUR T1 - Adaptive Parallel Primal-Dual Method for Saddle Point Problems AU - Xiayang Zhang JO - Numerical Mathematics: Theory, Methods and Applications VL - 1 SP - 187 EP - 210 PY - 2018 DA - 2018/11 SN - 11 DO - http://doi.org/10.4208/nmtma.2018.m1621 UR - https://global-sci.org/intro/article_detail/nmtma/10650.html KW - AB -

The primal-dual hybrid gradient method is a classic way to tackle saddle-point problems. However, its convergence is not guaranteed in general. Some restrictions on the step size parameters, e.g., $τσ  ≤ 1/‖A^TA‖$, are imposed to guarantee the convergence. In this paper, a new convergent method with no restriction on parameters is proposed. Hence the expensive calculation of $‖A^TA‖$ is avoided. This method produces a predictor like other primal-dual methods but in a parallel fashion, which has the potential to speed up the method. This new iteration is then updated by a simple correction to guarantee the convergence. Moreover, the parameters are adjusted dynamically to enhance the efficiency as well as the robustness of the method. The generated sequence monotonically converges to the solution set. A worst-case $\mathcal{O}(1/t)$ convergence rate in ergodic sense is also established under mild assumptions. The numerical efficiency of the proposed method is verified by applications in LASSO problem and Steiner tree problem.

Xiayang Zhang. (2018). Adaptive Parallel Primal-Dual Method for Saddle Point Problems. Numerical Mathematics: Theory, Methods and Applications. 11 (1). 187-210. doi:10.4208/nmtma.2018.m1621
Copy to clipboard
The citation has been copied to your clipboard