В чём заключается метод эллипсоидов для решения задач линейного программирования?

Метод эллипсоидов — алгоритм нахождения точки, лежащей в пересечении выпуклых множеств. 12 Разработан А. С. Немировским и доведён до алгоритмической реализации Л. Г. Хачияном в ВЦ АН СССР. 12

Суть метода для решения задач линейного программирования заключается в следующем: 1

1. Вначале находят точку внутри шара, содержащего искомое решение, которая удовлетворяет ограничениям задачи. 12
2. Через неё проводят гиперплоскость (где f — целевая функция) и находят точку в пересечении исходных и новой гиперплоскостей (начиная с текущего эллипсоида). 12
3. С новой найденной точкой проделывают то же самое. 12

Процесс сходится к оптимальному решению с экспоненциальной скоростью (поскольку с этой скоростью убывает объём эллипсоида). 12

Метод эллипсоидов используется в задачах малой размерности, но в задачах со многими переменными он неэффективен. 3