Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Итеративный метод минимизации выпуклых функций
Iterative method for minimizing convex functions
В математической оптимизации эллипсоидный метод — это итеративный метод минимизации выпуклых функций на выпуклых множествах. Эллипсоидный метод генерирует последовательность эллипсоидов, объем которых равномерно уменьшается на каждом шаге, тем самым заключая минимизатор выпуклой функции. При применении к решению выполнимых задач линейного программирования с рациональными данными, эллипсоидный метод является алгоритмом, который находит оптимальное решение за полиномиальное от размера входных данных число шагов.
In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions over convex sets. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every step, thus enclosing a minimizer of a convex function. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm which finds an optimal solution in a number of steps that is polynomial in the input size.
История
Метод эллипсоидов имеет долгую историю. Как итеративный метод, его предварительная версия была предложена Наумом З. Шором. В 1972 году Аркадий Немировский и Дэвид Б. Юдин (Джудин) исследовали алгоритм аппроксимации для вещественной выпуклой минимизации. Леонид Хачиян изучал эллипсоидный алгоритм как алгоритм решения задач линейного программирования с рациональными данными; главным достижением Хачияна стало доказательство полиномиальной сложности линейных программ. Это был значительный шаг с теоретической точки зрения: стандартным алгоритмом для решения линейных задач в то время был симплекс-метод, время работы которого обычно линейно зависит от размера задачи, но существуют примеры, для которых оно становится экспоненциальным. Поэтому наличие алгоритма, гарантированно полиномиального во всех случаях, казалось теоретическим прорывом. Работа Хачияна впервые показала, что существуют алгоритмы для решения задач линейного программирования, время работы которых можно доказать как полиномиальное. Однако на практике алгоритм оказался довольно медленным и малоинтересным, хотя и послужил вдохновением для последующих работ, которые оказались гораздо более практически полезными. В частности, алгоритм Кармаркара, метод внутренней точки, на практике значительно быстрее метода эллипсоидов. Алгоритм Кармаркара также быстрее в худшем случае. Эллипсоидный алгоритм позволил теоретикам сложности получать (в худшем случае) оценки, зависящие от размерности задачи и размера данных, но не от количества строк, поэтому он оставался важным в теории комбинаторной оптимизации на протяжении многих лет. Только в XXI веке появились алгоритмы внутренней точки с сопоставимыми свойствами сложности.
The ellipsoid method has a long history. As an iterative method, a preliminary version was introduced by Naum Z. Shor. In 1972, an approximation algorithm for real convex minimization was studied by Arkadi Nemirovski and David B. Yudin (Judin). As an algorithm for solving linear programming problems with rational data, the ellipsoid algorithm was studied by Leonid Khachiyan; Khachiyan's achievement was to prove the polynomial time solvability of linear programs. This was a notable step from a theoretical perspective: The standard algorithm for solving linear problems at the time was the simplex algorithm, which has a run time that typically is linear in the size of the problem, but for which examples exist for which it is exponential in the size of the problem. As such, having an algorithm that is guaranteed to be polynomial for all cases seemed like a theoretical breakthrough. Khachiyan's work showed, for the first time, that there can be algorithms for solving linear programs whose runtime can be proven to be polynomial. In practice, however, the algorithm is fairly slow and of little practical interest, though it provided inspiration for later work that turned out to be of much greater practical use. Specifically, Karmarkar's algorithm, an interior point method, is much faster than the ellipsoid method in practice. Karmarkar's algorithm is also faster in the worst case. The ellipsoidal algorithm allows complexity theorists to achieve (worst case) bounds that depend on the dimension of the problem and on the size of the data, but not on the number of rows, so it remained important in combinatorial optimization theory for many years. Only in the 21st century have interior point algorithms with similar complexity properties appeared.