Home

Семинар 24 июня 2002 года

Понедельник, 24 июня, комната 203. Начало в 14:00.

Докладчик: Д. В. Пасечник (Франкфурт).

FINDING OPTIMUM SUBJECT TO FEW QUADRATIC CONSTRAINTS IN POLYNOMIAL TIME (joint work with D.Grigoriev i E. de Klerk)
It is shown that quadratic programming in $ n $ variables subject to $ k $ quadratic constraints has time complexity $ n^{O(k^2)} $, while feasibility can be tested in $ n^{O(k)} $ operations. The described procedure outputs the optimal value, as well as an optimal point, if they exist. Otherwise, it reports the range of the objective function on the feasible region. Optimal points and values are given exactly, via algebraic numbers. For this purpose the tools of quantifier elimination over the real closed fields with infinitesimals are involved.
In contrast, the best previously known procedure needs $ n^{O(k^2)} $ operations just for answering feasibility in the homogeneous case due to A.Barvinok, and no polynomial-time procedure previously known is able to find a feasible point with prescribed precision.