Algebraic Relaxations and Hardness Results in Polynomial Optimization and Lyapunov Analysis

Abstract

This thesis settles a number of questions related to computational complexity and algebraic, semidefinite programming based relaxations in optimization and control.

PhD Thesis, MIT, September, 2011

References in corpus (11)

• Symmetry groups, semidefinite programs, and sums of squares
• Stability and Robustness Analysis of Nonlinear Systems via Contraction Metrics and SOS Programming
• Approximation of the joint spectral radius using sum of squares
• NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems
• On Hilbert's construction of positive polynomials
• Convex Forms that are not Sums of Squares
• A geometric inequality for circle packings
• Dimensional Differences between Nonnegative Polynomials and Sums of Squares
• Nonnegative Polynomials and Sums of Squares
• A Positivstellensatz for projective real varieties
• An elementary proof of Hilbert's theorem on ternary quartics

Cited by in corpus (11)

• NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems
• Joint Spectral Radius and Path-Complete Graph Lyapunov Functions
• Optimization over Nonnegative and Convex Polynomials With and Without Semidefinite Programming
• Learning Contracting Vector Fields For Stable Imitation Learning
• Stability of Polynomial Differential Equations: Complexity and Converse Lyapunov Questions
• The Maximal Positively Invariant Set: Polynomial Setting
• Complexity of Ten Decision Problems in Continuous Time Dynamical Systems
• Converse Lyapunov theorems for discrete-time linear switching systems with regular switching sequences
• Control Design along Trajectories with Sums of Squares Programming
• Stability of discrete-time switching systems with constrained switching sequences
• Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making