Integer Polynomial Optimization in Fixed Dimension
Kevin Zemmer · Repository for Publications and Research Data (ETH Zurich) · 2017
The third result deals with minimizing quadratic polynomials over the mixed-integer points of polyhedra in fixed dimension.We show that this problem is solvable in time that is polynomial in the size of the input and the maximum absolute values of the matrices defining the constraints and the objective function.We also combine this with previous results to derive a similar result for quadratic functions defined by a low-rank matrix in variable dimension.The fourth result also deals with minimizing quadratic polynomials over the integer points of a polyhedron in fixed dimension.We present a fully polynomial-time approximation scheme (FPTAS) for this problem when the objective function is homogeneous and the matrix defining it has at most one positive or at most one negative eigenvalue. Zusammenfassung Das Problem derOptimierung multivariater skalarer Polynomfunktionen über gemischt-ganzzahligen Punkten in Polyedern ist eine Verallgemeinerung des bekannten Problems der linearen Programmierung (engl.Linear Programming, LP).Während bekannt ist, dass LP-Probleme polynomiell lösbar sind, ist ihre Erweiterung auf gemischt-ganzzahlige Punkte (engl.Mixed-Integer Linear Programming, MILP) N P-schwer.Ist die Anzahl der ganzzahligen Variablen hingegen fix, so ist MILP polynomiell lösbar.Wir entwickeln Algorithmen für (gemischt-)ganzzahlige Optimierungsprobleme mit einer fixen Anzahl von Variablen und unterschiedlichen Klassen von Zielfunktionen mit fixem Grad von mindestens Zwei, unter zusätzlichen Annahmen.Dies erlaubt uns neue Komplexitätsresultate für die gegebenen Problemklassen abzuleiten.Das erste Resultat befasst sich mit der Minimierung kubischer Polynomfunktionen über ganzzahligen Punkten in Polyedern in Dimension Zwei.Wir zeigen durch die Konstruktion von einem expliziten Algorithmus, dass dieses Problem in der Eingabegrösse polynomiell lösbar ist und erweitern damit ein bestehendes Resultat für quadratische Polynomfunktionen.Wir zeigen dies für beschränkte und unbeschränkte Polyeder.Das zweite Resultat befasst sich mit der Minimierung homogener Polynomfunktionen über ganzzahligen Punkten in Polyedern in Dimension Zwei.Wir entwickeln einen Algorithmus, der dieses Problem in polynomieller Zeit in der Eingabegrösse löst, wenn der Grad der Polynomfunktion fix und das Polyeder beschränkt ist.Das Resultat gilt zudem für Translationen homogener Funktionen, auch wenn die resultierende Funktion nicht homogen und der Translationsvektor nicht bekannt ist.Wir zeigen ausserdem, dass im Falle eines unbeschränkten Polyeders eine Lösung mit