On the conditions for the finite termination of ADMM and its applications to SOS polynomials feasibility problems

Hikaru Komeiji, Sunyoung Kim, Makoto Yamashita

Research output: Contribution to journalArticlepeer-review


We study finite termination properties of the alternating direction method of multipliers (ADMM) method applied to semidefinite programs (SDPs) generated from sums of squares (SOS) feasibility problems. Expressing a polynomial as SOS of lower degree by formulating the problem as SDPs is a key problem in many fields, and ADMM is frequently used to efficiently solve the SDPs whose size grows very rapidly with the degree and number of variables of the polynomial. We present conditions for the ADMM method to converges to an optimal solution in finite iterations and prove its finite termination under the conditions. In addition, for the problem of representing a univariate trigonometric polynomial as an SOS, we also provide similar conditions for the finite termination of the ADMM at an optimal solution. Numerical results demonstrate the finite termination if the conditions are satisfied and the size of the strictly feasible region is not too small. The size is determined by solving an SDP whose optimal value indicates how much the variable matrix of the original SDP can be diagonally increased, without violating the constraints of the original SDP. The finite termination discussed in this paper is a distinctive property of ADMM, and cannot be observed when implementing the interior-point methods.

Original languageEnglish
Pages (from-to)317-344
Number of pages28
JournalComputational Optimization and Applications
Issue number2
StatePublished - 1 Nov 2019

Bibliographical note

Publisher Copyright:
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.


  • Alternating direction method of multipliers
  • Conditions for finite termination
  • Semidefinite programs
  • Sums of squares of polynomials
  • Sums of squares of univariate trigonometric polynomials


Dive into the research topics of 'On the conditions for the finite termination of ADMM and its applications to SOS polynomials feasibility problems'. Together they form a unique fingerprint.

Cite this