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

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

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

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

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

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