TY - GEN
T1 - Control and verification of high-dimensional systems with DSOS and SDSOS programming
AU - Majumdar, Anirudha
AU - Ahmadi, Amir Ali
AU - Tedrake, Russ
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84987962935&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84987962935&partnerID=8YFLogxK
U2 - 10.1109/CDC.2014.7039413
DO - 10.1109/CDC.2014.7039413
M3 - Conference contribution
AN - SCOPUS:84987962935
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 394
EP - 401
BT - 53rd IEEE Conference on Decision and Control,CDC 2014
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014
Y2 - 15 December 2014 through 17 December 2014
ER -