Complexity, Exactness, and Rationality in Polynomial Optimization

Daniel Bienstock, Alberto Del Pia, Robert HildebrandMath. Program 2021 · OpenReview

TL;DR

This paper investigates the existence and complexity of rational solutions (solutions expressible as fractions) for polynomial optimization problems. The authors demonstrate that while some polynomial systems admit rational solutions, determining their existence or size can be NP-hard. They also introduce a simple certificate for feasibility in polynomial time for fixed dimensions.

What Problem Does This Paper Address?

Polynomial optimization problems, where we seek to minimize or maximize a polynomial subject to polynomial constraints, are fundamental in many scientific and engineering fields. A key challenge arises when dealing with the exactness and certification of solutions. Solvers often produce approximate solutions, and rigorously verifying their quality can be difficult. This paper delves into the question of whether rational solutions, which are inherently exact and easier to represent, exist for these problems, and if so, how hard it is to find them or even determine their existence. Specifically, it addresses the complexity of finding rational feasible solutions, the relationship between infeasibility and "superoptimality" (where a slightly infeasible point is much better than any feasible point), and the existence of rational unbounded rays for cubic objectives.

Methods

The paper employs a combination of theoretical tools from computational complexity and optimization theory. Key methods include:

  • Reductions from 3-SAT: The authors use the well-known NP-complete problem 3-SAT to establish NP-hardness results. They construct specific systems of polynomial inequalities whose satisfiability or the size of whose solutions is directly linked to the satisfiability of a 3-SAT instance.
  • Certificate Construction: For the feasibility problem in fixed dimensions, they provide a simple certificate that can be verified in polynomial time. This certificate is a rational, "near-feasible" vector.
  • Analysis of Polynomial Properties: The paper leverages properties of polynomials, such as their behavior on rays, Lipschitz continuity, and the nature of local minima, to prove existence and complexity results.
  • Construction of Specific Examples: Novel examples of polynomial systems are constructed to demonstrate specific phenomena, such as systems with no rational feasible solutions or systems where solutions require exponential size.

Datasets

Not discussed in the paper. The paper focuses on theoretical results and constructions rather than empirical evaluation on existing datasets.

Key Insights and Ideas

  • Rationality is Not Guaranteed: While some polynomial systems admit rational solutions, it's not a universal property. The paper shows cases where feasible solutions exist but are provably irrational or require exponential bit-encoding length.
  • NP-Hardness of Rationality Detection: It's strongly NP-hard to determine if a system of quadratic inequalities has a rational feasible solution of polynomial size, or even if a feasible system of linear and cubic inequalities has any rational solution. This highlights a significant computational barrier.
  • Infeasibility Can Lead to Superoptimality: A slightly infeasible point can sometimes yield a much better objective value than any truly feasible point. The paper shows this phenomenon can be constructed and that distinguishing between near-optimality and large superoptimality can be NP-hard.
  • Simple Certificates for Fixed Dimensions: For polynomial inequality systems in a fixed number of variables, the feasibility problem is in NP. The authors provide a constructive proof by exhibiting a simple, polynomial-size rational "near-feasible" certificate.
  • Unbounded Rays and Rationality: For cubic objectives, while unbounded rays exist, they are not always rational. The paper shows that if a cubic function is unbounded on an irrational ray, it's not necessarily unbounded on a rational ray.

Key Results

  • NP-Hardness: It is strongly NP-hard to test for the existence of rational feasible solutions of polynomial size in certain quadratic and cubic systems.
  • Feasibility in NP (Fixed Dimension): For polynomial inequalities in a fixed dimension, the feasibility problem is in NP, with a simple, polynomial-size rational certificate.
  • Superoptimality: The paper constructs examples where a slightly infeasible point can be "superoptimal," and distinguishing this from near-optimality is NP-hard.
  • Unbounded Rays: For cubic objectives, the existence of rational unbounded rays is not guaranteed, even if the function is unbounded on irrational rays.

Limitations and Future Work

  • Fixed Dimension Assumption: The result showing feasibility is in NP relies on the dimension being fixed. Generalizing this to arbitrary dimensions remains an open challenge.
  • Separability Conditions: Some positive results regarding rational solutions are contingent on separability conditions, suggesting that more general cases might be harder.
  • Generalization of Certificates: While a simple certificate is provided for feasibility, extending this to optimality certificates for general polynomial optimization problems is a complex area.
  • Practical Implications: The theoretical hardness results suggest that finding exact rational solutions for complex polynomial optimization problems might be computationally intractable in many cases, motivating the use of approximation algorithms and heuristics.

The authors' work opens avenues for further research into the precise computational complexity of various aspects of polynomial optimization, particularly concerning the nature and tractability of rational solutions and certificates.

Summary updated

Abstract

We focus on rational solutions or nearly-feasible rational solutions that serve as certificates of feasibility for polynomial optimization problems. We show that, under some separability conditions, certain cubic polynomially constrained sets admit rational solutions. However, we show in other cases that it is NP Hard to detect if rational solutions exist or if they exist of any reasonable size. Lastly, we show that in fixed dimension, the feasibility problem over a set defined by polynomial inequalities is in NP.
BibTeX
@inproceedings{bienstock2021complexity,
  author = {Daniel Bienstock and Alberto Del Pia and Robert Hildebrand},
  title = {{Complexity, Exactness, and Rationality in Polynomial Optimization}},
  booktitle = {Math. Program},
  year = {2021},
  url = {https://openreview.net/forum?id=dGmTGYMAxo2},
}
Figure