Novel results on computational methods for polynomial optimization

Abstract

The thesis consists of four chapters discussing theory, methodology and results followed by a chapter of sample code. The work is connected by the common theme of computational methodology for polynomial optimization. The first two chapters tackle the problem of certifying Lyapunov stability of dynamical systems. The first chapter is the most theoretical: we demonstrate how a globally asymptotically stable polynomial vector field can fail to have a rational Lyapunov certificate. In the second chapter, we expand the usual search class of Lyapunov certificates from polynomials to logarithmic functions, which is accomplished by an alternating optimization approach to exploit bilinear structure of the search problem. The procedure is successful on the motivating example and some other systems with similar properties. The later two chapters discuss methodology and present results on lower bounds of polynomial optimization problems (POPs). The third chapter implements the generic optimization-free hierar- chy of algebraic certificates that can be use to find lower bounds on the optimal value of any POP. The last chapter looks at the kissing number, which can be formulated as a POP, and provides lower bounds through a relaxation of Sum-of-Squares programming called Diagonally-Dominant-Sum-of- Squares programming. The kissing number is not resolved by this approach but early results are promising.