Symmetry groups, semidefinite programs, and sums of squares

DOI10.1016/j.jpaa.2003.12.011zbMath1108.13021arXivmath/0211450OpenAlexW2055993677MaRDI QIDQ1878418

Pablo A. Parrilo, Karin Gatermann

Publication date: 19 August 2004

Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0211450

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Semidefinite programming (90C22) Real algebra (13J30)

Related Items

A survey of nonlinear robust optimization, Automorphisms of Rank-One Generated Hyperbolicity Cones and Their Derivative Relaxations, Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs, Convex computation of maximal Lyapunov exponents, Handling symmetries in mixed-integer semidefinite programs, Faster real root decision algorithm for symmetric polynomials, Reflection groups and cones of sums of squares, Construction of Multivariate Polynomial Approximation Kernels via Semidefinite Programming, Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022, Finding Symmetry Groups of Some Quadratic Programming Problems, DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization, Preface, Semidefinite Descriptions of the Convex Hull of Rotation Matrices, High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts, Symmetry Reduction to Optimize a Graph-based Polynomial From Queueing Theory, On the tightness of SDP relaxations of QCQPs, Symmetry in Mathematical Programming, Sum of squares method for sensor network localization, Quantum hedging in two-round prover-verifier interactions, Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank, On Flattenability of Graphs, Symmetry in Turán sums of squares polynomials from flag algebras, Bounding the separable rank via polynomial optimization, Quantum entanglement, symmetric nonnegative quadratic polynomials and moment problems, Copositive programming motivated bounds on the stability and the chromatic numbers, Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, Certifying the global optimality of quartic minimization over the sphere, Nonnegative Polynomials and Circuit Polynomials, Semidefinite programming relaxations for graph coloring and maximal clique problems, Strengthened semidefinite programming bounds for codes, Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation, Symmetry Reduction in AM/GM-Based Optimization, On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs, The Maximum k-Colorable Subgraph Problem and Related Problems, Semidefinite relaxations of dynamical programs under discrete constraints, Symmetric non-negative forms and sums of squares, New upper bounds for the density of translative packings of three-dimensional convex bodies with tetrahedral symmetry, On semidefinite programming relaxations of maximum \(k\)-section, Algorithms for fundamental invariants and equivariants of finite groups, Symmetry in multivariate ideal interpolation, Sums of Hermitian squares decomposition of non-commutative polynomials in non-symmetric variables using NCSOStools, Dimension reduction for semidefinite programs via Jordan algebras, CLASSICAL AND QUANTUM CONTROL OF A SIMPLE QUANTUM SYSTEM, Controlled invariant hypersurfaces of polynomial control systems, A numerical algorithm for block-diagonal decomposition of matrix \(*\)-algebras with application to semidefinite programming, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, An Algebraic Approach to Nonorthogonal General Joint Block Diagonalization, Breaking symmetries to rescue sum of squares in the case of makespan scheduling, Algorithms for highly symmetric linear and integer programs, Sum-of-squares chordal decomposition of polynomial matrix inequalities, Characterizing the universal rigidity of generic tensegrities, Simultaneous singular value decomposition, Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry, Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting), Symmetric sums of squares over \(k\)-subset hypercubes, Review on contraction analysis and computation of contraction metrics, Group symmetry and covariance regularization, Stability and robustness analysis of nonlinear systems via contraction metrics and SOS programming, Polynomial Norms, Exploiting symmetry in integer convex optimization using core points, Sum-of-Squares Optimization without Semidefinite Programming, On Sum of Squares Representation of Convex Forms and Generalized Cauchy--Schwarz Inequalities, Bounds on mean energy in the Kuramoto–Sivashinsky equation computed using semidefinite programming, Using symmetry to optimize over the Sherali-Adams relaxation, Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017, An alternative approach for nonlinear optimal control problems based on the method of moments, Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization, Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra, A computational comparison of symmetry handling methods for mixed integer programs, Optimizing Hypergraph-Based Polynomials Modeling Job-Occupancy in Queuing with Redundancy Scheduling, An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming, Bounding averages rigorously using semidefinite programming: mean moments of the Lorenz system, Symmetry in semidefinite programs, A polynomial optimization approach to constant rebalanced portfolio selection, Coarse-Convex-Compactification Approach to Numerical Solution of Nonconvex Variational Problems, A convex polynomial that is not sos-convex, A method for computing lowest eigenvalues of symmetric polynomial differential operators by semidefinite programming, Perturbation analysis for matrix joint block diagonalization, Reduction of truss topology optimization, An SOS counterexample to an inequality of symmetric functions, Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming, Unnamed Item, Robust static output feedback design for polynomial nonlinear systems, A Comprehensive Analysis of Polyhedral Lift-and-Project Methods, Multivariate interpolation: preserving and exploiting symmetry, Sums of squares and moment problems in equivariant situations, Orbital shrinking: theory and applications, Improving the Semidefinite Programming Bound for the Kissing Number by Exploiting Polynomial Symmetry, Exactness of sums of squares relaxations involving \(3\times 3\) matrices and Lorentz cones, LMI relaxations in robust control, Alternative SDP and SOCP approximations for polynomial optimization, Introduction to Semidefinite, Conic and Polynomial Optimization, Invariant Semidefinite Programs, Sums of squares over totally real fields are rational sums of squares, Equilibrium problems involving the Lorentz cone, Preprocessing sparse semidefinite programs via matrix completion, Lower bounds on nonnegative rank via nonnegative nuclear norms, New bounds for truthful scheduling on two unrelated selfish machines, Moment methods in energy minimization: New bounds for Riesz minimal energy problems, An LMI description for the cone of Lorentz-positive maps II, On the Lovász \(\vartheta\)-number of almost regular graphs with application to Erdős-Rényi graphs, Numerical approaches for collaborative data processing, Symmetry Adapted Gram Spectrahedra, Exact Semidefinite Programming Bounds for Packing Problems, Noncoercive sums of squares in \(\mathbb R[x_1,\ldots ,x_n\)], Exploiting group symmetry in truss topology optimization, Exploiting special structure in semidefinite programming: a survey of theory and applications, Modified orbital branching for structured symmetry with an application to unit commitment, RepLAB: A Computational/Numerical Approach to Representation Theory, Sparse interpolation in terms of multivariate Chebyshev polynomials, Semidefinite programming and eigenvalue bounds for the graph partition problem, Modelling and control of flexible joint robot based on Takagi–Sugeno fuzzy approach and its stability analysis via sum of squares, On matrix algebras associated to sum-of-squares semidefinite programs, Heat transport bounds for a truncated model of Rayleigh-Bénard convection via polynomial optimization, A dynamic inequality generation scheme for polynomial programming

Uses Software

• GAP
• Macaulay2
• Sostools
• INVAR
• symmetry

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Real zeros for positive semidefinite forms. I
• Even symmetric sextics
• Singularities and groups in bifurcation theory. Volume II
• Positive semidefinite biquadratic forms
• Extremal positive semidefinite forms
• Positive symmetric functions
• The representation theory of the symmetric groups
• An algorithm for sums of squares of real polynomials
• Zeros of equivariant vector fields: Algorithms for an invariant approach
• Semidefinite programming relaxations for semialgebraic problems
• Computational invariant theory
• Group symmetry in interior-point methods for semidefinite program
• Semi-invariants, equivariants and algorithms
• Computer algebra methods for equivariant dynamical systems
• Global Optimization with Polynomials and the Problem of Moments
• Real Schubert Calculus: Polynomial Systems and a Conjecture of Shapiro and Shapiro
• Class of global minimum bounds of polynomial functions
• Invariants of finite groups and their applications to combinatorics
• Handbook of semidefinite programming. Theory, algorithms, and applications