Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane

Alberto Del Pia, Robert Hildebrand, Robert Weismantel, Kevin ZemmerMath. Oper. Res 2016 · OpenReview

TL;DR

This paper tackles the computational complexity of finding the minimum value of a polynomial over integer points within a polyhedron. The authors demonstrate that minimizing cubic polynomials (degree 3) over integer points in a 2D polyhedron can be done efficiently, closing a gap in understanding the complexity landscape for polynomial optimization. This has implications for various fields relying on integer optimization.

What Problem Does This Paper Address?

The core problem is finding the minimum value of a polynomial $f(x)$ where $x$ must be an integer point within a given polyhedron $P$. This is known as integer polynomial optimization. The complexity of this problem varies significantly with the degree of the polynomial and the dimension of the space. For instance, linear polynomials (degree 1) are efficiently solvable (integer linear programming), and quadratic polynomials (degree 2) in 2D are also efficiently solvable. However, it was known that for degree 4 polynomials in 2D, the problem becomes NP-hard. This paper addresses the "gap" for cubic polynomials (degree 3) in 2D, proving that they can be minimized efficiently, thus completing the complexity classification for fixed dimension $n=2$ and varying polynomial degrees. They also extend this to homogeneous polynomials of any fixed degree.

Methods

The authors employ a sophisticated approach that combines several key techniques:

  • Feasibility to Optimization Reduction: They show that solving the optimization problem is equivalent to solving a series of feasibility problems (determining if a solution exists below a certain value). This is a standard technique in optimization.
  • Operator on Convex Sets and Polyhedra: A crucial tool is an "operator" that can efficiently determine if a given convex set (or a semi-algebraic set) contains any integer points. This operator is applied to subregions of the feasible domain.
  • Division of the Feasible Domain: The core algorithmic idea is to divide the feasible region (the polyhedron $P$) into smaller, manageable pieces. These pieces are designed such that within each piece, the polynomial exhibits certain desirable properties, like being quasiconvex or quasiconcave. This division is achieved by analyzing the roots and critical points of the polynomial and its derivatives.
  • Numerical Approximations: To handle irrational roots and critical points, the authors use numerical approximations with guaranteed error bounds. This allows them to construct "thin boxes" or intervals that contain these critical values.
  • Homogenization and Translatability: For homogeneous polynomials, they leverage properties of the bordered Hessian. For general polynomials, they introduce the concept of "homogeneous translatable" polynomials, which can be transformed into homogeneous polynomials via a translation. They also show that checking for this property and finding the translation can be done efficiently.
  • Rational Polyhedra and Hyperplanes: The division of the domain results in a set of rational polyhedra and lines, which can be processed efficiently.

Datasets

Not discussed in the paper. The problem is theoretical and deals with arbitrary polyhedra and polynomials defined by their coefficients.

Key Insights and Ideas

  • Cubic Polynomials are Tractable: The most significant insight is that minimizing cubic polynomials over integer points in a 2D polyhedron is computationally tractable (solvable in polynomial time), despite degree 4 being NP-hard. This suggests that the complexity doesn't always increase monotonically with degree.
  • Homogeneous Polynomials are Key: The paper heavily relies on the properties of homogeneous polynomials and their "homogeneous translatable" counterparts. Understanding the structure of their level sets and regions of quasiconvexity/quasiconcavity is central to the algorithm.
  • The Power of Division: The strategy of dividing the feasible region into smaller pieces where the polynomial behaves predictably (e.g., quasiconvex/quasiconcave) is a powerful algorithmic paradigm. This allows for the application of specialized tools on each piece.
  • Numerical Approximations are Sufficient: The authors demonstrate that precise analytical solutions for irrational roots are not always necessary. Well-controlled numerical approximations are sufficient to construct the necessary algorithmic components.
  • Unbounded Solutions Can Be Exponentially Large: For homogeneous polynomials, they show that even if the problem is solvable in polynomial time, the size of the optimal integer solution can be exponentially large in the input size, highlighting the need for careful representation of solutions.

Key Results

  • Polynomial-Time Solvability for Cubic Polynomials: The paper proves that minimizing a cubic polynomial ($d=3$) over integer points in a 2D polyhedron ($n=2$) is solvable in polynomial time, even for unbounded polyhedra.
  • Polynomial-Time Solvability for Homogeneous Translatable Polynomials: They show that minimizing homogeneous translatable polynomials of any fixed degree $d$ over integer points in a bounded 2D polyhedron is solvable in polynomial time.
  • Complexity Classification for $n=2$: This work completes the complexity classification for minimizing polynomials of fixed degree $d$ over integer points in a 2D polyhedron: polynomial time for $d \le 3$, and NP-hard for $d \ge 4$.
  • Exponential Solution Size: For certain homogeneous minimization problems, the minimal integer solution can have an exponential size, even when the problem is polynomially solvable.

Limitations and Future Work

  • Fixed Dimension: The results are primarily for dimension $n=2$. The complexity for $n \ge 3$ and degrees $d \in \{2, 3\}$ remains an open question.
  • Homogeneous Translatable Assumption: While they show how to check for homogeneous translatability efficiently, the core algorithms rely on this property or on the polynomial being homogeneous. Extending to more general polynomials might require further work.
  • Unbounded Case for Homogeneous Polynomials: While they show that minimizing homogeneous polynomials is polynomial time solvable, they highlight that the size of the optimal solution can be exponential. This necessitates careful handling of solution representation.
  • Future Work: The paper explicitly mentions the open question of complexity for $n \ge 3$ and $d \in \{2,3\}$. Further research could explore these higher dimensions and degrees. Additionally, investigating the practical performance of the proposed algorithms would be valuable.

Summary updated

Abstract

We complete the complexity classification by degree of minimizing a polynomial over the integer points in a polyhedron in a real vector space of dimension two. Previous work shows that optimizing a...
BibTeX
@inproceedings{pia2016minimizing,
  author = {Alberto Del Pia and Robert Hildebrand and Robert Weismantel and Kevin Zemmer},
  title = {{Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane}},
  booktitle = {Math. Oper. Res},
  year = {2016},
  url = {https://openreview.net/forum?id=o0jDsUWnxG2},
}
Figure