Sum of squares (SOS) optimization has been a powerful and influential addition to the theory of optimization in the past decade. Its reliance on relatively large-scale semidefinite programming, however, has seriously challenged its ability to scale in many practical applications. In this paper, we introduce DSOS and SDSOS optimization1 as more tractable alternatives to sum of squares optimization that rely instead on linear programming and second order cone programming. These are optimization problems over certain subsets of sum of squares polynomials and positive semidefinite matrices and can be of potential interest in general applications of semidefinite programming where scalability is a limitation.
Note: This is an invited paper for the session on “Optimization in the Information Sciences” of the 48th Annual Conference on Information Sciences and Systems (CISS 2014). It is meant to serve as an extended abstract for a longer upcoming paper [1] by the authors on the same topic. Most details are omitted.
By: Amir Ali Ahmadi, Anirudha Majumdar
Published in: Proceedings of 2014 48th Annual Conference on Information Sciences and Systems (CISS),Piscataway, NJ, , IEEE. , p.10.1109/CISS.2014.6814141 in 2014
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .