Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
From MaRDI portal
Publication:5470252
DOI10.1137/050623802zbMath1109.65058OpenAlexW2166798101MaRDI QIDQ5470252
Masakazu Muramatsu, Sunyoung Kim, Hayato Waki, Kojima, Masakazu
Publication date: 30 May 2006
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/0076a9c9f46c0595ddfc2b233132467e5a8976d4
global optimizationnumerical resultsLagrangian relaxationpolynomial optimization problemLagrangian dualsums of squares optimization
Related Items
LP relaxations for a class of linear semi-infinite programming problems, Algebraic Perspectives on Signomial Optimization, Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields, Nonnegative Polynomials and Circuit Polynomials, Symmetry Reduction in AM/GM-Based Optimization, Optimization on the Euclidean Unit Sphere, Exact Recovery with Symmetries for Procrustes Matching, Partial Lasserre relaxation for sparse Max-Cut, A hierarchy of spectral relaxations for polynomial optimization, Minimal energy configurations of bilayer plates as a polynomial optimization problem, A new global algorithm for max-cut problem with chordal sparsity, A new scheme for approximating the weakly efficient solution set of vector rational optimization problems, Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks, A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization, A Geometrical Analysis on Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems, An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization, Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022, Bounding extrema over global attractors using polynomial optimisation, TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity, Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension, Minimizing Rational Functions: A Hierarchy of Approximations via Pushforward Measures, On the estimation of the equilibrium points of uncertain nonlinear systems, Bounding the parameters of block‐structured nonlinear feedback systems, Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems, Convergence analysis of a block improvement method for polynomial optimization over unit spheres, Preprocessing and Regularization for Degenerate Semidefinite Programs, Algorithm 996, Formal Proofs for Nonlinear Optimization, Minimizing the sum of many rational functions, Mathematical programming methods for microgrid design and operations: a survey on deterministic and stochastic approaches, Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and unbounded semialgebraic feasible sets, Positive polynomials on fibre products, A convex relaxation approach to set-membership identification of LPV systems, Global optimization with spline constraints: a new branch-and-bound method based on B-splines, Sum of squares method for sensor network localization, Semidefinite Approximations of Projections and Polynomial Images of SemiAlgebraic Sets, Moments and sums of squares for polynomial optimization and related problems, Approximate gcds of polynomials and sparse SOS relaxations, Computing sum of squares decompositions with rational coefficients, Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints, Sparse noncommutative polynomial optimization, 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, Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity, Globally optimal estimates for geometric reconstruction problems, A conversion of an SDP having free variables into the standard form SDP, RLT-POS: reformulation-linearization technique-based optimization software for solving polynomial programming problems, 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, Canonical primal-dual algorithm for solving fourth-order polynomial minimization problems, A bounded degree SOS hierarchy for polynomial optimization, Solving polynomial least squares problems via semidefinite programming relaxations, Bounded error identification of Hammerstein systems through sparse polynomial optimization, Welfare-maximizing correlated equilibria using Kantorovich polynomials with sparsity, A sums-of-squares extension of policy iterations, Exploiting sparsity for the min \(k\)-partition problem, Partitioning procedure for polynomial optimization, Solving stress constrained problems in topology and material optimization, Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global optimality, Global optimization of polynomial-expressed nonlinear optimal control problems with semidefinite programming relaxation, Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures, Strong duality and minimal representations for cone optimization, A facial reduction algorithm for finding sparse SOS representations, SONC optimization and exact nonnegativity certificates via second-order cone programming, Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization, An algorithm for semi-infinite polynomial optimization, Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones, Polynomial sum of squares in fluid dynamics: a review with a look ahead, Discussion on: ``A decomposition algorithm for KYP-SDPs, A Multigrid Approach to SDP Relaxations of Sparse Polynomial Optimization Problems, Sum-of-squares chordal decomposition of polynomial matrix inequalities, Chordal graphs in triangular decomposition in top-down style, Enclosing ellipsoids and elliptic cylinders of semialgebraic sets and their application to error bounds in polynomial optimization, Exploiting sparsity for semi-algebraic set volume computation, Convex underestimators of polynomials, Revisiting several problems and algorithms in continuous location with \(\ell _\tau \) norms, Lower bounds on the global minimum of a polynomial, Min-max and robust polynomial optimization, Distributionally robust polynomial chance-constraints under mixture ambiguity sets, Sum-of-Squares Optimization without Semidefinite Programming, Bounds on mean energy in the Kuramoto–Sivashinsky equation computed using semidefinite programming, Semidefinite programming for min-max problems and games, Exploiting term sparsity in noncommutative polynomial optimization, A multilevel analysis of the Lasserre hierarchy, Lasserre Hierarchy for Large Scale Polynomial Optimization in Real and Complex Variables, LP Formulations for Polynomial Optimization Problems, Global optimality conditions and optimization methods for polynomial programming problems, Improved parameter bounds for set-membership EIV problems, An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming, SDP RELAXATIONS FOR QUADRATIC OPTIMIZATION PROBLEMS DERIVED FROM POLYNOMIAL OPTIMIZATION PROBLEMS, On minimizing difference of a SOS-convex polynomial and a support function over a SOS-concave matrix polynomial constraint, Binary quadratic optimization problems that are difficult to solve by conic relaxations, Global minimization of rational functions and the nearest GCDs, A polynomial optimization approach to constant rebalanced portfolio selection, A parallel interior point decomposition algorithm for block angular semidefinite programs, 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, Canonical dual least square method for solving general nonlinear systems of quadratic equations, Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion, A survey on conic relaxations of optimal power flow problem, Decomposition-based method for sparse semidefinite relaxations of polynomial optimization problems, Approximating Pareto curves using semidefinite relaxations, A semidefinite programming approach to the generalized problem of moments, Positive polynomials on projective limits of real algebraic varieties, A moment and sum-of-squares extension of dual dynamic programming with application to nonlinear energy storage problems, Alternative SDP and SOCP approximations for polynomial optimization, A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones, Introduction to Semidefinite, Conic and Polynomial Optimization, Positivity and Optimization: Beyond Polynomials, Exploiting Sparsity in SDP Relaxation of Polynomial Optimization Problems, Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy, Perturbed sums-of-squares theorem for polynomial optimization and its applications, Recognizing underlying sparsity in optimization, Smaller SDP for SOS decomposition, GpoSolver: a Matlab/C++ toolbox for global polynomial optimization, Correlative sparsity in primal-dual interior-point methods for LP, SDP, and SOCP, Immediate schedule adjustment and semidefinite relaxation, Newton polytopes and relative entropy optimization, A sublevel moment-SOS hierarchy for polynomial optimization, Decomposed structured subsets for semidefinite and sum-of-squares optimization, Exploiting sparsity in complex polynomial optimization, Finding unstable periodic orbits: a hybrid approach with polynomial optimization, Choosing better variable orderings for cylindrical algebraic decomposition via exploiting chordal structure, Certification of real inequalities: templates and sums of squares, A convex optimization approach to synthesizing state feedback data-driven controllers for switched linear systems, Univariate parameterization for global optimization of mixed-integer polynomial problems, New limits of treewidth-based tractability in optimization
Uses Software
