Title :
Control and verification of high-dimensional systems with DSOS and SDSOS programming
Author :
Majumdar, Anirudha ; Ahmadi, Amir Ali ; Tedrake, Russ
Author_Institution :
Comput. Sci. & Artificial Intell. Lab., Massachusetts Inst. of Technol., Cambridge, MA, USA
Abstract :
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.
Keywords :
humanoid robots; linear programming; mechanical variables control; polynomials; ATLAS humanoid robot; Acrobot system; DSOS programming; LP; Lyapunov functions; SDP; SDSOS programming; SOCP; attraction region; balancing controller; control applications; control input model; diagonal dominance; high-dimensional system control; high-dimensional system verification; linear programming; oscillators network; polynomials; scaled diagonal dominance; second order cone programming; semidefinite programming; state input model; sum-of-squares programming; Approximation methods; Lyapunov methods; Optimization; Polynomials; Programming; Scalability; Symmetric matrices;
Conference_Titel :
Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on
Conference_Location :
Los Angeles, CA
Print_ISBN :
978-1-4799-7746-8
DOI :
10.1109/CDC.2014.7039413