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