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

Hikaru Komeiji (), Sunyoung Kim () and Makoto Yamashita ()
Additional contact information
Hikaru Komeiji: Tokyo Institute of Technology
Sunyoung Kim: Ewha W. University
Makoto Yamashita: Tokyo Institute of Technology

Computational Optimization and Applications, 2019, vol. 74, issue 2, No 1, 317-344

Abstract: Abstract 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.

Keywords: Sums of squares of polynomials; Sums of squares of univariate trigonometric polynomials; Semidefinite programs; Alternating direction method of multipliers; Conditions for finite termination; 90C22; 90C25; 90C26 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-019-00118-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:74:y:2019:i:2:d:10.1007_s10589-019-00118-5

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-019-00118-5

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().