Minimizing cubic and homogeneous polynomials over integers in the plane

DOI10.1287/MOOR.2015.0738MaRDI QIDQ2806816zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Alberto Del Pia, Robert Hildebrand, Robert Weismantel, Kevin Zemmer

Publication date 19 May 2016

Published in Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

polynomial optimizationnonlinear integer programming

Mathematics Subject Classification ID

Nonlinear programming (90C30) Integer programming (90C10)

Abstract: We complete the complexity classification by degree of minimizing a polynomial over the integer points in a polyhedron in $mathbb{R}^2$. Previous work shows that optimizing a quadratic polynomial over the integer points in a polyhedral region in $mathbb{R}^2$ can be done in polynomial time, while optimizing a quartic polynomial in the same type of region is NP-hard. We close the gap by showing that this problem can be solved in polynomial time for cubic polynomials. Furthermore, we show that the problem of minimizing a homogeneous polynomial of any fixed degree over the integer points in a bounded polyhedron in $mathbb{R}^2$ is solvable in polynomial time. We show that this holds for polynomials that can be translated into homogeneous polynomials, even when the translation vector is unknown. We demonstrate that such problems in the unbounded case can have smallest optimal solutions of exponential size in the size of the input, thus requiring a compact representation of solutions for a general polynomial time algorithm for the unbounded case.

Recommendations

• Integer quadratic programming in the plane
• Integer Polynomial Optimization in Fixed Dimension
• The efficient minimization of quadratic polynomials depending on integer variables, with quadratic monomials \(b^2_{i,j}(x_i - x_j)^2\)
• The quadratic Graver cone, quadratic integer minimization, and extensions
• A PTAS for the minimization of polynomials of fixed degree over the simplex

Cites work

• scientific article; zbMATH DE number 3592969 (Why is no real title available?)
• scientific article; zbMATH DE number 1383707 (Why is no real title available?)
• Computing real roots of real polynomials
• Generalized convexity and optimization. Theory and applications
• Integer Polynomial Optimization in Fixed Dimension
• Integer optimization on convex semialgebraic sets
• Mirror-Descent Methods in Mixed-Integer Convex Optimization
• Mixed-integer quadratic programming is in NP
• On integer points in polyhedra
• On the Computational Complexity of Determining the Solvability or Unsolvability of the Equation X 2 - DY 2 = -1
• On the Diophantine Equation mX 2 - nY 2 = ± 1
• On the complexity of nonlinear mixed-integer optimization
• Production Sets with Indivisibilities, Part I: Generalities
• Production Sets with Indivisibilities, Part II: The Case of Two Activities

Cited in

(9)

• Integer Polynomial Optimization in Fixed Dimension
• The efficient minimization of quadratic polynomials depending on integer variables, with quadratic monomials \(b^2_{i,j}(x_i - x_j)^2\)
• Complexity aspects of local minima and related notions
• A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity \(2^{O(n\log n)}\)
• The quadratic Graver cone, quadratic integer minimization, and extensions
• Short Presburger Arithmetic Is Hard
• Complexity of optimizing over the integers
• Integer quadratic programming in the plane
• A Polyhedral Frobenius Theorem with Applications to Integer Optimization

This page was built for publication: Minimizing cubic and homogeneous polynomials over integers in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2806816)