Algebraic Relaxations and Hardness Results in Polynomial Optimization and Lyapunov Analysis

2012/01/13 by Amir Ali Ahmadi, Ahmadi, Amir Ali · 3 citations
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Formal Methods in Verification #Numerical Methods and Algorithms #Optimization and Control (math.OC) #cs.CC #cs.DS #math.OC

paper · pdf · doi:10.48550/arxiv.1201.2892

PhD Thesis, MIT, September, 2011

arxiv created 2012/01/13 · openalex publication_date 2012/01/13 · arxiv updated 2012/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Citations

• Convex Forms that are not Sums of Squares
• The general problem of the stability of motion
• Semidefinite programming relaxations for semialgebraic problems
• Sums of squares on real algebraic surfaces
• Uniform stabilization of discrete-time switched and Markovian jump linear systems
• Lagrange Multipliers and Optimality
• Distinguishing Separable and Entangled States
• Symmetry groups, semidefinite programs, and sums of squares
• Multiple Lyapunov functions and other analysis tools for switched and hybrid systems
• Semidefinite Programming

Cited by

• Learning Contracting Vector Fields For Stable Imitation Learning
• Optimization over Nonnegative and Convex Polynomials With and Without Semidefinite Programming
• Stability of Polynomial Differential Equations: Complexity and Converse\n Lyapunov Questions

Related

• Minimizing Polynomial Functions
• Tight Relaxations for Polynomial Optimization and Lagrange Multiplier Expressions
• A Lagrangian relaxation view of linear and semidefinite hierarchies
• Polynomial Optimization with Applications to Stability Analysis and Control - Alternatives to Sum of Squares
• Polynomial mathematical programs with equilibrium constraints and semidefinite programming relaxations