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 (only showing first 100 items - show all)
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
This page was built for publication: Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
