2016/01/01 by Reza Kamyar, Kamyar, Reza
Computer Science · Engineering · Mathematics · #Advanced Control Systems Optimization #Advanced Optimization Algorithms Research #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Stability and Control of Uncertain Systems
paper · pdf · doi:10.48550/arxiv.1702.05851
openalex publication_date 2016/01/01 · openalex created_date 2022/09/05 · openalex updated_date 2026/07/28
In this thesis, we focus on some of the NP-hard problems in control theory.\nThanks to the converse Lyapunov theory, these problems can often be modeled as\noptimization over polynomials. To avoid the problem of intractability, we\nestablish a trade off between accuracy and complexity. We develop a sequence of\ntractable optimization problems - in the form of LPs and SDPs - whose solutions\nconverge to the exact solution of the NP-hard problem. However, the\ncomputational and memory complexity of these LPs and SDPs grow exponentially\nwith the progress of the sequence - meaning that improving the accuracy of the\nsolutions requires solving SDPs with tens of thousands of decision variables\nand constraints. Setting up and solving such problems is a significant\nchallenge. The existing optimization algorithms and software are only designed\nto use desktop computers or small cluster computers - machines which do not\nhave sufficient memory for solving such large SDPs. This in fact is the reason\nwe seek parallel algorithms for setting-up and solving large SDPs on\nsupercomputers.\n We propose parallel algorithms for stability analysis of two classes of\nsystems: 1) Linear systems with a large number of uncertain parameters; 2)\nNonlinear systems defined by polynomial vector fields. First, we develop a\ndistributed parallel algorithm which applies Polya's and Handelman's theorems\nto some variants of parameter-dependent Lyapunov inequalities with parameters\ndefined over the simplex. The result is a sequence of SDPs which possess a\nblock-diagonal structure. We then develop a parallel SDP solver which exploits\nthis structure to map the computation, memory and communication to a\ndistributed parallel environment. Numerical tests on a supercomputer\ndemonstrate the ability of the algorithm to efficiently utilize hundreds and\npotentially thousands of processors and analyze systems with 100+ dimensional\nstate-space.\n