DSOS and SDSOS optimization: LP and SOCP-based alternatives to sum of squares optimization

Amir Ali Ahmadi; Anirudha Majumdar

doi:10.1109/CISS.2014.6814141

DSOS and SDSOS optimization: LP and SOCP-based alternatives to sum of squares optimization

Amir Ali Ahmadi, Anirudha Majumdar

Research output: Contribution to conference › Paper › peer-review

67 Scopus citations

Abstract

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.

Original language	English (US)
DOIs	https://doi.org/10.1109/CISS.2014.6814141
State	Published - 2014
Externally published	Yes
Event	2014 48th Annual Conference on Information Sciences and Systems, CISS 2014 - Princeton, NJ, United States Duration: Mar 19 2014 → Mar 21 2014

Other

Other	2014 48th Annual Conference on Information Sciences and Systems, CISS 2014
Country/Territory	United States
City	Princeton, NJ
Period	3/19/14 → 3/21/14

All Science Journal Classification (ASJC) codes

Information Systems

Access to Document

10.1109/CISS.2014.6814141

Cite this

@conference{9a8882650e7e43169dd22e264fea5b8b,

title = "DSOS and SDSOS optimization: LP and SOCP-based alternatives to sum of squares optimization",

abstract = "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.",

author = "Ahmadi, {Amir Ali} and Anirudha Majumdar",

year = "2014",

doi = "10.1109/CISS.2014.6814141",

language = "English (US)",

note = "2014 48th Annual Conference on Information Sciences and Systems, CISS 2014 ; Conference date: 19-03-2014 Through 21-03-2014",

}

TY - CONF

T1 - DSOS and SDSOS optimization

T2 - 2014 48th Annual Conference on Information Sciences and Systems, CISS 2014

AU - Ahmadi, Amir Ali

AU - Majumdar, Anirudha

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84901465557&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84901465557&partnerID=8YFLogxK

U2 - 10.1109/CISS.2014.6814141

DO - 10.1109/CISS.2014.6814141

M3 - Paper

AN - SCOPUS:84901465557

Y2 - 19 March 2014 through 21 March 2014

ER -

DSOS and SDSOS optimization: LP and SOCP-based alternatives to sum of squares optimization

Abstract

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this