Semidefinite programming relaxations for semialgebraic problems

2003/05/01 by Pablo A. Parrilo · 78 citations
Mathematics · Computer Science · #Advanced Optimization Algorithms Research #Polynomial and algebraic computation #Formal Methods in Verification

paper · doi:10.1007/s10107-003-0387-5

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Symmetry groups, semidefinite programs, and sums of squares

Cited by

• Beyond Ellipsoids: Semi-Algebraic Tightening for Chance Constraints Under Actuator Saturation
• Is Your Safe Controller Actually Safe? A Critical Review of CBF Tautologies and Hidden Assumptions
• Tight Conic Relaxations for Rank-one Doubly Nonnegative Matrix Completion
• Robust Optimal Control of Arbitrarily Switched Systems: A Path-Complete Framework
• First Order Conditions for Semidefinite Representations of Convex Sets Defined by Rational or Singular Polynomials
• Application of Polynomial Optimization to Electricity Transmission\n Networks
• Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden\n Submatrix Problems
• Relative Entropy Relaxations for Signomial Optimization
• Positivity and optimization for semi-algebraic functions
• Real ideal and the duality of semidefinite programming for polynomial optimization
• Bounding Multivariate Trigonometric Polynomials with Applications to Filter Bank Design
• Stabilizing Dynamical Systems via Policy Gradient Methods
• Control Contraction Metrics, Robust Control and Observer Duality
• Efficiently Maximizing a Homogeneous Polynomial over Unit Sphere without\n Convex Relaxation
• On symmetry adapted bases in trigonometric optimization
• Positive polynomials on unbounded domains
• Sum-of-Squares Stability Verification on Manifolds with Applications in Spacecraft Attitude Control
• Barrier Certificates Revisited
• Algorithms in Real Algebraic Geometry: A Survey
• A Counter-Example Guided Framework for Robust Synthesis of Switched\n Systems Using Control Certificates
• Linear Relaxations of Polynomial Positivity for Polynomial Lyapunov\n Function Synthesis
• SOSTOOLS Version 4.00 Sum of Squares Optimization Toolbox for MATLAB
• Computational Complexity and the Nature of Quantum Mechanics
• Real-time Funnel Generation for Restricted Motion Planning
• Practicality of Nested Risk Measures for Dynamic Electric Vehicle Charging
• Refined Asymptotics for Multigraded Sums of Squares
• Convexity in semi-algebraic geometry and polynomial optimization
• NIL: Learning Nonlinear Interpolants
• Minimum Ellipsoid Bounds for Solutions of Polynomial Systems via Sum of Squares
• Recognizing Graph Theoretic Properties with Polynomial Ideals
• Nonlinear Stabilization via Control Contraction Metrics: a Pseudospectral Approach for Computing Geodesics
• Review on Set-Theoretic Methods for Safety Verification and Control of Power System
• An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization
• Contributions to Semialgebraic-Set-Based Stability Verification of Dynamical Systems with Neural-Network-Based Controllers
• Stability and Performance Verification of Optimization-based Controllers
• A Unified and Scalable Method for Optimization over Graphs of Convex Sets
• The Kinematics of Tracked Vehicles via the Power Dissipation Method
• A refined error analysis for fixed-degree polynomial optimization over the simplex
• Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers
• Unbounded-Time Safety Verification of Stochastic Differential Dynamics
• The Interplay between Quantum Contextuality and Wigner Negativity
• Automatically Discovering Relaxed Lyapunov Functions for Polynomial Dynamical Systems
• Symmetry in Turán Sums of Squares Polynomials from Flag Algebras
• Semidefinite Programming and Nash Equilibria in Bimatrix Games
• A Novel Algorithm for Representing Positive Semi-Definite Polynomials as Sums of Squares with Rational Coefficients
• The NPA hierarchy does not always attain the commuting operator value
• Robust Data-Driven Control for Nonlinear Systems Using their Digital Twins and Quadratic Funnels
• Learning Hybrid Dynamics via Convex Optimizations
• Bernstein Polynomial Relaxations for Polynomial Optimization Problems
• The determinant of the second additive compound of a square matrix: a formula and applications
• Safe-by-Design: Approximate Nonlinear Model Predictive Control with Real Time Feasibility
• Input-to-state Stable Approximate Nonlinear Model Predictive Control with Realtime Feasibility
• T-positive semidefiniteness of third-order symmetric tensors and T-semidefinite programming
• The weighted difference substitutions and Nonnegativity Decision of Forms
• Counterexample Guided Synthesis of Switched Controllers for\n Reach-While-Stay Properties
• Distributed Nonlinear Control Design using Separable Control Contraction\n Metrics
• Improving Efficiency and Scalability of Sum of Squares Optimization: Recent Advances and Limitations
• Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and the Nullstellensatz
• Solving ill-conditioned polynomial equations using score-based priors with application to multi-target detection
• Stable Nonlinear Identification From Noisy Repeated Experiments via\n Convex Optimization
• On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
• Generating Non-Linear Interpolants by Semidefinite Programming
• Controller Synthesis for Robust Invariance of Polynomial Dynamical Systems using Linear Programming
• The Hierarchy of Local Minimums in Polynomial Optimization
• Computation of the maximal invariant set of discrete-time linear systems subject to a class of non-convex constraints
• A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
• Synthesis and SOS-based Stability Verification of a Neural-Network-Based Controller for a Two-wheeled Inverted Pendulum
• The Saddle Point Problem of Polynomials
• S.o.s. approximation of polynomials nonnegative on a real algebraic set
• Decomposition Algorithm for Distributionally Robust Optimization using Wasserstein Metric
• Detection of Planted Solutions for Flat Satisfiability Problems
• First-order and interior-point methods for entanglement detection
• Control Closure Certificates
• Enumerative Aspects of Nullstellensatz Certificates
• Unitary Gate Synthesis via Polynomial Optimization
• On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization
• SOS Tensor Decomposition: Theory and Applications
• A proof of Hilbert's theorem on ternary quartic forms with the ladder technique