Метод внутренних точек: история и перспективы

Рассмотрены два взаимно двойственных семейства алгоритмов внутренних точек. Представлена история создания алгоритмов, основные теоретические результаты по их обоснованию, опыт практического использования, возможные направления развития, способы противодействия погрешностям вычислений. Выделены подмножества алгоритмов, обладающих различными особыми свойствами, в том числе гарантированно приводящие к относительно внутренним точкам оптимальных решений. Представлен алгоритм поиска чебышёвской проекции на линейное многообразие, в котором эффективно используется свойство относительно внутренних точек оптимальных решений. Данный алгоритм всегда вырабатывает единственную проекцию и позволяет обходиться без трудно проверяемого и иногда нарушающегося условия Хаара. Библ. 30. Табл. 1.