Control and verification of high-dimensional systems with DSOS and SDSOS programming

Research output: Chapter in Book/Report/Conference proceedingConference contribution

52 Scopus citations


In this paper, we consider linear programming (LP) and second order cone programming (SOCP) based alternatives to sum of squares (SOS) programming and apply this framework to high-dimensional problems arising in control applications. Despite the wide acceptance of SOS programming in the control and optimization communities, scalability has been a key challenge due to its reliance on semidefinite programming (SDP) as its main computational engine. While SDPs have many appealing features, current SDP solvers do not approach the scalability or numerical maturity of LP and SOCP solvers. Our approach is based on the recent work of Ahmadi and Majumdar [1], which replaces the positive semidefiniteness constraint inherent in the SOS approach with stronger conditions based on diagonal dominance and scaled diagonal dominance. This leads to the DSOS and SDSOS cones of polynomials, which can be optimized over using LP and SOCP respectively. We demonstrate this approach on four high dimensional control problems that are currently well beyond the reach of SOS programming: computing a region of attraction for a 22 dimensional system, analysis of a 50 node network of oscillators, searching for degree 3 controllers and degree 8 Lyapunov functions for an Acrobot system (with the resulting controller validated on a hardware platform), and a balancing controller for a 30 state and 14 control input model of the ATLAS humanoid robot. While there is additional conservatism introduced by our approach, extensive numerical experiments on smaller instances of our problems demonstrate that this conservatism can be small compared to SOS programming.

Original languageEnglish (US)
Title of host publication53rd IEEE Conference on Decision and Control,CDC 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Electronic)9781479977468
StatePublished - 2014
Event2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 - Los Angeles, United States
Duration: Dec 15 2014Dec 17 2014

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0743-1546
ISSN (Electronic)2576-2370


Other2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014
Country/TerritoryUnited States
CityLos Angeles

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization


Dive into the research topics of 'Control and verification of high-dimensional systems with DSOS and SDSOS programming'. Together they form a unique fingerprint.

Cite this