Semidefinite programming relaxations for semialgebraic problems
From MaRDI portal
Publication:1424271
DOI10.1007/s10107-003-0387-5zbMath1043.14018OpenAlexW1967184028WikidataQ93515461 ScholiaQ93515461MaRDI QIDQ1424271
Publication date: 11 March 2004
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-003-0387-5
Semidefinite programming (90C22) Integer programming (90C10) Semialgebraic sets and related spaces (14P10) Real algebra (13J30)
Related Items
Continuous-variable nonlocality and contextuality, Products of positive forms, linear matrix inequalities, and Hilbert 17th problem for ternary forms, Symmetry groups, semidefinite programs, and sums of squares, Inverse problems from biomedicine: inference of putative disease mechanisms and robust therapeutic strategies, Computing sum of squares decompositions with rational coefficients, Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere, Arc length based maximal Lyapunov functions and domains of attraction estimation for polynomial nonlinear systems, Semidefinite programming hierarchies for constrained bilinear optimization, An alternative Kalman-Yakubovich-Popov lemma and some extensions, Certifying the global optimality of quartic minimization over the sphere, On linear programming relaxations for solving polynomial programming problems, Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables, Discrete dynamical system approaches for Boolean polynomial optimization, The saddle point problem of polynomials, An approximate characterisation of the set of feasible trajectories for constrained flat systems, Local stability analysis for large polynomial spline systems, A sums-of-squares extension of policy iterations, Design of continuous twisting algorithm, Solving rank-constrained semidefinite programs in exact arithmetic, Chebyshev model arithmetic for factorable functions, Global optimization of polynomial-expressed nonlinear optimal control problems with semidefinite programming relaxation, The convex geometry of linear inverse problems, UTA-poly and UTA-splines: additive value functions with polynomial marginals, Sums of Hermitian squares decomposition of non-commutative polynomials in non-symmetric variables using NCSOStools, One-shot set-membership identification of generalized Hammerstein-Wiener systems, Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization, On solving biquadratic optimization via semidefinite relaxation, On robust stability of switched systems in the context of Filippov solutions, Exact SDP relaxations for classes of nonlinear semidefinite programming problems, Augmented finite transition systems as abstractions for control synthesis, Misspecified nonconvex statistical optimization for sparse phase retrieval, Outer approximation with conic certificates for mixed-integer convex problems, Breaking symmetries to rescue sum of squares in the case of makespan scheduling, The tracial moment problem and trace-optimization of polynomials, On relations between summands in the discriminant of a symmetric matrix, Automatically discovering relaxed Lyapunov functions for polynomial dynamical systems, The matricial relaxation of a linear matrix inequality, Cooperativity, absolute interaction, and algebraic optimization, On the complexity of testing attainment of the optimal value in nonlinear optimization, Optimal control for non-polynomial systems, Discovering polynomial Lyapunov functions for continuous dynamical systems, Optimal bounds and extremal trajectories for time averages in nonlinear dynamical systems, Transverse contraction criteria for existence, stability, and robustness of a limit cycle, Exact determinations of the maximal output admissible set for a class of nonlinear systems, Stability and robustness analysis of nonlinear systems via contraction metrics and SOS programming, Global optimality principles for polynomial optimization over box or bivalent constraints by separable polynomial approximations, Efficiency improvement in an \(n\)D systems approach to polynomial optimization, An alternative approach for nonlinear optimal control problems based on the method of moments, Stable rank-one matrix completion is solved by the level \(2\) Lasserre relaxation, Bounding averages rigorously using semidefinite programming: mean moments of the Lorenz system, Lift \& project systems performing on the partial-vertex-cover polytope, DC decomposition of nonconvex polynomials with algebraic techniques, Optimization over structured subsets of positive semidefinite matrices via column generation, Feedback control of quantum entanglement in a two-SPIN system, Constructing invariants for hybrid systems, Numerical multilinear algebra and its applications, The tracial moment problem on quadratic varieties, Guaranteed cost \(H_\infty \) controller synthesis for switched systems defined on semi-algebraic sets, There are significantly more nonnegative polynomials than sums of squares, Global minimization of rational functions and the nearest GCDs, Approximation of the joint spectral radius using sum of squares, Explicit hard bounding functions for boundary value problems for elliptic partial differential equations, On the conditions for the finite termination of ADMM and its applications to SOS polynomials feasibility problems, A new bounded degree hierarchy with SOCP relaxations for global polynomial optimization and conic convex semi-algebraic programs, Global optimization of rational functions: a semidefinite programming approach, Minimizing polynomials via sum of squares over the gradient ideal, Robust global optimization with polynomials, Bounds on linear PDEs via semidefinite optimization, An improved semidefinite programming relaxation for the satisfiability problem, Sparsity in sums of squares of polynomials, Inverse conic programming with applications, A survey on conic relaxations of optimal power flow problem, A PTAS for the minimization of polynomials of fixed degree over the simplex, T-positive semidefiniteness of third-order symmetric tensors and T-semidefinite programming, Incremental \(\mathcal{L}_2\)-gain stability of piecewise-affine systems with piecewise-polynomial storage functions, Region of attraction analysis with integral quadratic constraints, Lyapunov based estimation of the basin of attraction of Poincaré maps with applications to limit cycle walking, Alternative SDP and SOCP approximations for polynomial optimization, Semidefinite and linear programming integrality gaps for scheduling identical machines, Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs, An efficient global algorithm for worst-case linear optimization under uncertainties based on nonlinear semidefinite relaxation, Analysis of optimization algorithms via sum-of-squares, An arc-search infeasible interior-point method for semidefinite optimization with the negative infinity neighborhood, An augmented Lagrangian algorithm for nonlinear semidefinite programming applied to the covering problem, NIL: learning nonlinear interpolants, Saddle points of rational functions, Modeling and estimation of thermal flows based on transport and balance equations, The weirdness theorem and the origin of quantum paradoxes, Safety of stochastic systems: an analytic and computational approach, Finding unstable periodic orbits: a hybrid approach with polynomial optimization, Unconstrained minimization of block-circulant polynomials via semidefinite program in third-order tensor space, Compositional construction of control barrier functions for continuous-time stochastic hybrid systems, An approximation algorithm for the maximum spectral subgraph problem, Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs, Feedback control design using sum of squares optimisation, Automated verification and synthesis of stochastic hybrid systems: a survey, Cutting planes for RLT relaxations of mixed 0-1 polynomial programs, Formalization of Bernstein polynomials and applications to global optimization, An algorithm for decomposing a non-negative polynomial as a sum of squares of rational functions, Error bounds for polynomial optimization over the hypercube using Putinar type representations, A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation, Mathematical programming methods for microgrid design and operations: a survey on deterministic and stochastic approaches, A tensor analogy of Yuan's theorem of the alternative and polynomial optimization with sign structure, Some applications of polynomial optimization in operations research and real-time decision making, Nonlinear analysis of vehicle control actuations based on controlled invariant sets, Independent sets in semi-random hypergraphs, A probabilistic interpretation of set-membership filtering: application to polynomial systems through polytopic bounding, Sum of squares method for sensor network localization, Moments and sums of squares for polynomial optimization and related problems, Symmetry in Turán sums of squares polynomials from flag algebras, On the reduction of multivariate quadratic systems to best rank-1 approximation of three-way tensors, Set-membership errors-in-variables identification of MIMO linear systems, Semidefinite programming and sums of Hermitian squares of noncommutative polynomials, Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, Global completability with applications to self-consistent quantum tomography, Sums of squares on the hypercube, A copositive formulation for the stability number of infinite graphs, Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals, Real ideal and the duality of semidefinite programming for polynomial optimization, Algorithmic aspects of sums of Hermitian squares of noncommutative polynomials, Semidefinite representations for finite varieties, Welfare-maximizing correlated equilibria using Kantorovich polynomials with sparsity, Facial reduction algorithms for conic optimization problems, Exact asymptotic stability analysis and region-of-attraction estimation for nonlinear systems, Partitioning procedure for polynomial optimization, Finding the maximum eigenvalue of essentially nonnegative symmetric tensors via sum of squares programming, An extension of sums of squares relaxations to polynomial optimization problems over symmetric cones, On the Kalman-Yakubovich-Popov lemma and the multidimensional models, Approximation algorithms for homogeneous polynomial optimization with quadratic constraints, An approximation bound analysis for Lasserre's relaxation in multivariate polynomial optimization, SOS approximations of nonnegative polynomials via simple high degree perturbations, Linear-quadratic control and quadratic differential forms for multidimensional behaviors, A facial reduction algorithm for finding sparse SOS representations, Integral quadratic constraints for delayed nonlinear and parameter-varying systems, POS3POLY -- a MATLAB preprocessor for optimization with positive polynomials, Copositivity and constrained fractional quadratic problems, Optimal voting rules for two-member tenure committees, Border basis relaxation for polynomial optimization, Some geometric properties of successive difference substitutions, Set-membership estimation of fiber laser physical parameters from input-output power measurements, On the performance of nonlinear dynamical systems under parameter perturbation, Change-of-bases abstractions for non-linear hybrid systems, Copositive optimization -- recent developments and applications, Stability analysis of polynomial fuzzy models via polynomial fuzzy Lyapunov functions, An optimization approach to weak approximation of stochastic differential equations with jumps, Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization, Global stability analysis of fluid flows using sum-of-squares, Optimizing \(n\)-variate \((n+k)\)-nomials for small \(k\), Efficient and accurate computation of upper bounds of approximation errors, Obtaining certificates for complete synchronisation of coupled oscillators, A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs, SAT modulo linear arithmetic for solving polynomial constraints, Equilibrium-independent passivity: a new definition and numerical certification, Controller synthesis for robust invariance of polynomial dynamical systems using linear programming, Tunable halfband-pair wavelet filter banks and application to multifocus image fusion, Robust control of uncertain systems: classical results and recent developments, Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz, A Frank-Wolfe type theorem for nondegenerate polynomial programs, A computational approach to synthesizing guards for hybrid systems, A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set, Discriminants and nonnegative polynomials, Positive semidefinite diagonal minus tail forms are sums of squares, First order conditions for semidefinite representations of convex sets defined by rational or singular polynomials, Exploiting equalities in polynomial programming, Algorithms for multidimensional spectral factorization and sum of squares, Analysis of autocatalytic networks in biology, Robust stability and instability of biochemical networks with parametric uncertainty, A refined error analysis for fixed-degree polynomial optimization over the simplex, Exact relaxations of non-convex variational problems, Cross-Hill: a heuristic method for global optimization, Sums of squares based approximation algorithms for MAX-SAT, Barrier certificates revisited, Exact conic programming relaxations for a class of convex polynomial cone programs, Semidefinite approximations of conical hulls of measured sets, Optimal switching between cash-flow streams, Stability and performance verification of optimization-based controllers, Construction of parametric barrier functions for dynamical systems using interval analysis, A search-based procedure for nonlinear real arithmetic, Polynomial designs. I: Polynomial characterizations of common properties of a design, Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces, A polynomial optimization approach to constant rebalanced portfolio selection, MetiTarski: An automatic theorem prover for real-valued special functions, A revision of the proof of the Kepler conjecture, A convex polynomial that is not sos-convex, A method for computing lowest eigenvalues of symmetric polynomial differential operators by semidefinite programming, Decomposition-based method for sparse semidefinite relaxations of polynomial optimization problems, A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones, A new full-Newton step \(O(n)\) infeasible interior-point algorithm for semidefinite optimization, Local stability analysis using simulations and sum-of-squares programming, Minimizing rational functions by exact Jacobian SDP relaxation applicable to finite singularities, Linear optimization with cones of moments and nonnegative polynomials, Smaller SDP for SOS decomposition, Numerical approaches for collaborative data processing, An algorithm for the global optimization of a class of continuous minimax problems, A semi-algebraic approach for asymptotic stability analysis, Computing differential invariants of hybrid systems as fixed points, Conditions for strong ellipticity and M-eigenvalues, Advances in computational Lyapunov analysis using sum-of-squares programming, Minimum ellipsoid bounds for solutions of polynomial systems via sum of squares, A dynamic inequality generation scheme for polynomial programming, A modified infeasible interior-point algorithm with full-Newton step for semidefinite optimization, Automatic robust convex programming, Further results on sum-of-squares tensors, Nonnegative polynomials and sums of squares, Lifting for Simplicity: Concise Descriptions of Convex Sets, Discriminant of symmetric matrices as a sum of squares and the orthogonal group, Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization, Process Flexibility: A Distribution-Free Bound on the Performance of k-Chain, Sharper and Simpler Nonlinear Interpolants for Program Verification, Linearly Solvable Stochastic Control Lyapunov Functions, An accelerated first-order method for solving SOS relaxations of unconstrained polynomial optimization problems, Successive Rank-One Approximations for Nearly Orthogonally Decomposable Symmetric Tensors, Characteristic polynomial assignment for plants with semialgebraic uncertainty: A robust diophantine equation approach, On long-term boundedness of Galerkin models, Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines, Quantum Bilinear Optimization, Fiber Orientation Distribution Estimation Using a Peaceman--Rachford Splitting Method, An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs, Voronoi Diagram and Delaunay Triangulation with Independent and Dependent Geometric Uncertainties, An SOS method for the design of continuous and discontinuous differentiators, Minimizer Extraction in Polynomial Optimization Is Robust, Tractable Relaxations of Composite Functions, Iterative LMI approach to robust static output feedback control of uncertain polynomial systems with bounded actuators, Finding the extreme Z-eigenvalues of tensors via a sequential semidefinite programming method, Phase portraits, Lyapunov functions, and projective geometry. Lessons learned from a differential equations class and its aftermath, Computation of the maximal invariant set of discrete-time linear systems subject to a class of non-convex constraints, Causal gain-scheduled output feedback controllers using parameter-dependent Lyapunov functions, Viability, viscosity, and storage functions in model-predictive control with terminal constraints, Unnamed Item, Greedy Approaches to Symmetric Orthogonal Tensor Decomposition, Bounding Stationary Averages of Polynomial Diffusions via Semidefinite Programming, Polynomial sum of squares in fluid dynamics: a review with a look ahead, Sampling Algebraic Varieties for Sum of Squares Programs, Semi-Infinite Programming using High-Degree Polynomial Interpolants and Semidefinite Programming, Strong SOCP Relaxations for the Optimal Power Flow Problem, On the Construction of Converging Hierarchies for Polynomial Optimization Based on Certificates of Global Positivity, On the equivalence of two post-quantum cryptographic families, Sum-of-squares approach to feedback control of laminar wake flows, A Multigrid Approach to SDP Relaxations of Sparse Polynomial Optimization Problems, Bifurcation Analysis of a Predator–Prey System with Ratio-Dependent Functional Response, Generic Properties for Semialgebraic Programs, Finding positively invariant sets and proving exponential stability of limit cycles using sum-of-squares decompositions, Learning dynamical systems using local stability priors, SMOOTH UPPER BOUNDS FOR THE PRICE FUNCTION OF AMERICAN STYLE OPTIONS, Application of direct extended modified algebraic method of Bogoyavlenskii equation on lower and upper bounds in managing and optimizing queues, Deciding Robust Feasibility and Infeasibility Using a Set Containment Approach: An Application to Stationary Passive Gas Network Operations, Sum of squares basis pursuit with linear and second order cone programming, Distributionally Robust Optimization with Infinitely Constrained Ambiguity Sets, Polynomial Norms, DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization, Design of Lyapunov functions for a class of homogeneous systems: Generalized forms approach, A paradox in bosonic energy computations via semidefinite programming relaxations, On Sum of Squares Representation of Convex Forms and Generalized Cauchy--Schwarz Inequalities, Linear Temporal Logic Satisfaction in Adversarial Environments Using Secure Control Barrier Certificates, A guide to conic optimisation and its applications, Stability Verification for a Class of Stochastic Hybrid Systems by Semidefinite Programming, Consistency Analysis for Massively Inconsistent Datasets in Bound-to-Bound Data Collaboration, Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz, Lasserre Hierarchy for Large Scale Polynomial Optimization in Real and Complex Variables, Improved parameter bounds for set-membership EIV problems, An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming, Nonstationary LPV control for trajectory tracking: a double pendulum example, A Weak Approximation of Stochastic Differential Equations with Jumps Through Tempered Polynomial Optimization, Combining qualitative information and semi‐quantitative data for guaranteed invalidation of biochemical network models, Robust nonlinear stability and performance analysis of an F/A‐18 aircraft model using sum of squares programming, New upper bounds for kissing numbers from semidefinite programming, Computational and statistical tradeoffs via convex relaxation, Switching and stability properties of conewise linear systems, Approximation of Model Predictive Control Laws for Polynomial Systems, Coarse-Convex-Compactification Approach to Numerical Solution of Nonconvex Variational Problems, Real World Verification, Lyapunov-based exact stability analysis and synthesis for linear single-parameter dependent systems, Volterra series approximation for rational nonlinear system, Semidefinite programming relaxations and algebraic optimization in control, Introduction to Semidefinite, Conic and Polynomial Optimization, Convex Hulls of Algebraic Sets, Positivity and Optimization: Beyond Polynomials, SDP Relaxations for Non-Commutative Polynomial Optimization, Sums of squares over totally real fields are rational sums of squares, Time-Varying Semidefinite Programs, Certifying Polynomial Nonnegativity via Hyperbolic Optimization, Relative Entropy Relaxations for Signomial Optimization, Algorithm 996, Algorithm 998, Finding Extremal Periodic Orbits with Polynomial Optimization, with Application to a Nine-Mode Model of Shear Flow, Stochastic polynomial optimization, Policy iteration in finite templates domain, Decompositional Construction of Lyapunov Functions for Hybrid Systems, Preprocessing sparse semidefinite programs via matrix completion, Perturbed sums-of-squares theorem for polynomial optimization and its applications, A proof of Hilbert's theorem on ternary quartic forms, GpoSolver: a Matlab/C++ toolbox for global polynomial optimization, NCSOStools: a computer algebra system for symbolic and numerical computation with noncommutative polynomials, Bounding Extreme Events in Nonlinear Dynamics Using Convex Optimization, Semidefinite Programming and Nash Equilibria in Bimatrix Games, Approximate dynamic programming via iterated Bellman inequalities, Polyhedra related to integer-convex polynomial systems, Passivity and passivity indices of nonlinear systems under operational limitations using approximations, On matrix algebras associated to sum-of-squares semidefinite programs, On a new generalised LMI condition and randomised algorithm for robust stabilisation via static-output-feedback, Learning Dynamical Systems with Side Information, ℋ2 state-feedback control for continuous semi-Markov jump linear systems with rational transition rates, A practical approach to SOS relaxations for detecting quantum entanglement, Safety verification for regime-switching jump diffusions via barrier certificates, Analysis of pulse width modulation controlled systems based on a piecewise affine description, Auxiliary functions as Koopman observables: data-driven analysis of dynamical systems via polynomial optimization, A unified framework for the identification of a general class of multivariable nonlinear block‐structured systems, New directions in real algebraic geometry. Abstracts from the workshop held March 19--24, 2023, A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization, Nonlinear parameter‐varying state‐feedback design for a gyroscope using virtual control contraction metrics, A Sum of Squares Characterization of Perfect Graphs, Uniform exponential stability criteria with verification for nonautonomous switched nonlinear systems with uncertainty, k-Inductive Barrier Certificates for Stochastic Systems, Compositional synthesis of control barrier certificates for networks of stochastic systems against \(\omega\)-regular specifications, Analysis and verification of uniform moment exponential stability for stochastic hybrid systems with Poisson jump, Stability analysis of sampled-data control systems with input saturation: a hybrid system approach, Convex Relaxations of Integral Variational Problems: Pointwise Dual Relaxation and Sum-of-Squares Optimization, Data-driven optimal control via linear transfer operators: a convex approach, A knapsack intersection hierarchy, On the strength of recursive McCormick relaxations for binary polynomial optimization, An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization, Exponential Convergence of Sum-of-Squares Hierarchies for Trigonometric Polynomials, Invariants of SDP exactness in quadratic programming, On vanishing sums of roots of unity in polynomial calculus and sum-of-squares, The Spectrum of the Grigoriev–Laurent Pseudomoments, Shortest Paths in Graphs of Convex Sets, How Do Exponential Size Solutions Arise in Semidefinite Programming?, Harmonic Hierarchies for Polynomial Optimization, Second Order Conditions to Decompose Smooth Functions as Sums of Squares, Unnamed Item, Quantitative local L2‐gain and Reachability analysis for nonlinear systems, Convergence analysis of a block improvement method for polynomial optimization over unit spheres, Well-Posedness in Unconstrained Polynomial Optimization Problems, Validating numerical semidefinite programming solvers for polynomial invariants, Intersection cuts for nonlinear integer programming: convexification techniques for structured sets, A convex optimization model for finding non-negative polynomials, Symbolic Model Checking of Hybrid Systems Using Template Polyhedra, Radii minimal projections of polytopes and constrained optimization of symmetric polynomials, Computation of parameter stability margins using polynomial programming techniques, Inhomogeneous polynomial optimization over a convex set: An approximation approach, Positive Gorenstein ideals, Approximating amoebas and coamoebas by sums of squares, Bounds for Deterministic and Stochastic Dynamical Systems using Sum-of-Squares Optimization, High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts
