LP Formulations for Polynomial Optimization Problems

DOI10.1137/15M1054079zbMath1395.80005OpenAlexW2801165240MaRDI QIDQ4637509

Gonzalo Muñoz, Bienstock, Daniel

Publication date: 24 April 2018

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1054079

zbMATH Keywords

linear programmingpolynomial optimizationtree-width

Mathematics Subject Classification ID

Linear programming (90C05) Optimization problems in thermodynamics and heat transfer (80M50)

Related Items (13)

Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems ⋮ A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time ⋮ Exploiting sparsity for the min \(k\)-partition problem ⋮ Principled deep neural network training through linear programming ⋮ On the impact of running intersection inequalities for globally solving polynomial optimization problems ⋮ On optimization problems in acyclic hypergraphs ⋮ On the complexity of binary polynomial optimization over acyclic hypergraphs ⋮ Penalized semidefinite programming for quadratically-constrained quadratic optimization ⋮ Extended formulations for vertex cover ⋮ The Running Intersection Relaxation of the Multilinear Polytope ⋮ Strong NP-hardness of AC power flows feasibility ⋮ A fast algorithm for the semi-definite relaxation of the state estimation problem in power grids ⋮ New limits of treewidth-based tractability in optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimality conditions and finite convergence of Lasserre's hierarchy
• Reduced RLT representations for nonconvex polynomial programming problems
• Graph minors. III. Planar tree-width
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Nonconstructive advances in polynomial-time complexity
• Tree clustering for constraint networks
• New reformulation linearization/convexification relaxations for univariate and multivariate polynomial programming problems
• Sparsity in sums of squares of polynomials
• Strong reductions for extended formulations
• An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex
• Tree-width and the Sherali-Adams operator
• Incidence matrices and interval graphs
• A bounded degree SOS hierarchy for polynomial optimization
• A note on the representation of positive polynomials with structured sparsity
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• Nonserial dynamic programming
• Solving Mixed Integer Bilinear Problems Using MILP Formulations
• Combining Exact and Heuristic Approaches for the Capacitated Fixed-Charge Network Flow Problem
• Evaluating Gas Network Capacities
• Error Bounds for Some Semidefinite Programming Approaches to Polynomial Minimization on the Hypercube
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Graphical Models, Exponential Families, and Variational Inference
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• A sufficient condition for backtrack-bounded search
• Polynomial-time self-reducibility: theoretical motivations and practical results^∗
• Improved Linear Integer Programming Formulations of Nonlinear Integer Problems
• Splitting dense columns of constraint matrix in interior point methods for large scale linear programming¹¹The results discussed in the paper have been obtained when the author was staying at LAMSADE, University of Paris Dauphine, Place du Marechal de Lattre de Tassigny, 75775 Paris Cedex 16, France$ef:²²A preliminary version of the paper has been presented at the Applied Mathematical Programming and Modelling Symposium APMOD’91 in London, January 14-…
• Linear-time computation of optimal subgraphs of decomposable graphs
• Quadratically Constrained Quadratic Programs on Acyclic Graphs With Application to Power Flow
• On Integer Programming and the Branch-Width of the Constraint Matrix
• On the MIR Closure of Polyhedra
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution
• Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity

This page was built for publication: LP Formulations for Polynomial Optimization Problems