Matching Items (2)
Filtering by
- All Subjects: Mathematics
- Genre: Doctoral Dissertation
Description
In this thesis, we focus on some of the NP-hard problems in control theory. Thanks to the converse Lyapunov theory, these problems can often be modeled as optimization over polynomials. To avoid the problem of intractability, we establish a trade off between accuracy and complexity. In particular, we develop a sequence of tractable optimization problems - in the form of Linear Programs (LPs) and/or Semi-Definite Programs (SDPs) - whose solutions converge to the exact solution of the NP-hard problem. However, the computational and memory complexity of these LPs and SDPs grow exponentially with the progress of the sequence - meaning that improving the accuracy of the solutions requires solving SDPs with tens of thousands of decision variables and constraints. Setting up and solving such problems is a significant challenge. The existing optimization algorithms and software are only designed to use desktop computers or small cluster computers - machines which do not have sufficient memory for solving such large SDPs. Moreover, the speed-up of these algorithms does not scale beyond dozens of processors. This in fact is the reason we seek parallel algorithms for setting-up and solving large SDPs on large cluster- and/or super-computers.
We propose parallel algorithms for stability analysis of two classes of systems: 1) Linear systems with a large number of uncertain parameters; 2) Nonlinear systems defined by polynomial vector fields. First, we develop a distributed parallel algorithm which applies Polya's and/or Handelman's theorems to some variants of parameter-dependent Lyapunov inequalities with parameters defined over the standard simplex. The result is a sequence of SDPs which possess a block-diagonal structure. We then develop a parallel SDP solver which exploits this structure in order to map the computation, memory and communication to a distributed parallel environment. Numerical tests on a supercomputer demonstrate the ability of the algorithm to efficiently utilize hundreds and potentially thousands of processors, and analyze systems with 100+ dimensional state-space. Furthermore, we extend our algorithms to analyze robust stability over more complicated geometries such as hypercubes and arbitrary convex polytopes. Our algorithms can be readily extended to address a wide variety of problems in control such as Hinfinity synthesis for systems with parametric uncertainty and computing control Lyapunov functions.
We propose parallel algorithms for stability analysis of two classes of systems: 1) Linear systems with a large number of uncertain parameters; 2) Nonlinear systems defined by polynomial vector fields. First, we develop a distributed parallel algorithm which applies Polya's and/or Handelman's theorems to some variants of parameter-dependent Lyapunov inequalities with parameters defined over the standard simplex. The result is a sequence of SDPs which possess a block-diagonal structure. We then develop a parallel SDP solver which exploits this structure in order to map the computation, memory and communication to a distributed parallel environment. Numerical tests on a supercomputer demonstrate the ability of the algorithm to efficiently utilize hundreds and potentially thousands of processors, and analyze systems with 100+ dimensional state-space. Furthermore, we extend our algorithms to analyze robust stability over more complicated geometries such as hypercubes and arbitrary convex polytopes. Our algorithms can be readily extended to address a wide variety of problems in control such as Hinfinity synthesis for systems with parametric uncertainty and computing control Lyapunov functions.
ContributorsKamyar, Reza (Author) / Peet, Matthew (Thesis advisor) / Berman, Spring (Committee member) / Rivera, Daniel (Committee member) / Artemiadis, Panagiotis (Committee member) / Fainekos, Georgios (Committee member) / Arizona State University (Publisher)
Created2016
Description
For the last 50 years, oscillator modeling in ranging systems has received considerable
attention. Many components in a navigation system, such as the master oscillator
driving the receiver system, as well the master oscillator in the transmitting system
contribute significantly to timing errors. Algorithms in the navigation processor must
be able to predict and compensate such errors to achieve a specified accuracy. While
much work has been done on the fundamentals of these problems, the thinking on said
problems has not progressed. On the hardware end, the designers of local oscillators
focus on synthesized frequency and loop noise bandwidth. This does nothing to
mitigate, or reduce frequency stability degradation in band. Similarly, there are not
systematic methods to accommodate phase and frequency anomalies such as clock
jumps. Phase locked loops are fundamentally control systems, and while control
theory has had significant advancement over the last 30 years, the design of timekeeping
sources has not advanced beyond classical control. On the software end,
single or two state oscillator models are typically embedded in a Kalman Filter to
alleviate time errors between the transmitter and receiver clock. Such models are
appropriate for short term time accuracy, but insufficient for long term time accuracy.
Additionally, flicker frequency noise may be present in oscillators, and it presents
mathematical modeling complications. This work proposes novel H∞ control methods
to address the shortcomings in the standard design of time-keeping phase locked loops.
Such methods allow the designer to address frequency stability degradation as well
as high phase/frequency dynamics. Additionally, finite-dimensional approximants of
flicker frequency noise that are more representative of the truth system than the
tradition Gauss Markov approach are derived. Last, to maintain timing accuracy in
a wide variety of operating environments, novel Banks of Adaptive Extended Kalman
Filters are used to address both stochastic and dynamic uncertainty.
attention. Many components in a navigation system, such as the master oscillator
driving the receiver system, as well the master oscillator in the transmitting system
contribute significantly to timing errors. Algorithms in the navigation processor must
be able to predict and compensate such errors to achieve a specified accuracy. While
much work has been done on the fundamentals of these problems, the thinking on said
problems has not progressed. On the hardware end, the designers of local oscillators
focus on synthesized frequency and loop noise bandwidth. This does nothing to
mitigate, or reduce frequency stability degradation in band. Similarly, there are not
systematic methods to accommodate phase and frequency anomalies such as clock
jumps. Phase locked loops are fundamentally control systems, and while control
theory has had significant advancement over the last 30 years, the design of timekeeping
sources has not advanced beyond classical control. On the software end,
single or two state oscillator models are typically embedded in a Kalman Filter to
alleviate time errors between the transmitter and receiver clock. Such models are
appropriate for short term time accuracy, but insufficient for long term time accuracy.
Additionally, flicker frequency noise may be present in oscillators, and it presents
mathematical modeling complications. This work proposes novel H∞ control methods
to address the shortcomings in the standard design of time-keeping phase locked loops.
Such methods allow the designer to address frequency stability degradation as well
as high phase/frequency dynamics. Additionally, finite-dimensional approximants of
flicker frequency noise that are more representative of the truth system than the
tradition Gauss Markov approach are derived. Last, to maintain timing accuracy in
a wide variety of operating environments, novel Banks of Adaptive Extended Kalman
Filters are used to address both stochastic and dynamic uncertainty.
ContributorsEchols, Justin A (Author) / Bliss, Daniel W (Thesis advisor) / Tsakalis, Konstantinos S (Committee member) / Berman, Spring (Committee member) / Mittelmann, Hans (Committee member) / Arizona State University (Publisher)
Created2020