Об одном алгоритме линеаризации выпуклых экстремальных задач

Предложен метод приближенного решения задач минимизации выпуклых функций многих переменных при выпуклых ограничениях. Основная идея этого метода состоит в аппроксимации выпуклой функции кусочно линейной функцией, в результате чего задача выпуклого программирования сводится к задаче линейного программирования. Для осуществления подобной аппроксимации надграфик выпуклой функции приближается проекцией многогранника большей размерности. В первой части статьи эта задача рассматривается для функций одной переменной. Для этого случая представлен алгоритм аппроксимации надграфика выпуклой функции многоугольником, доказана его оптимальность по числу вершин многоугольника и получены точные оценки для этого числа. Затем с помощью индуктивной процедуры алгоритм обобщен на определенные классы функций многих переменных. На основе предложенного метода получены полиномиальные алгоритмы приближенного вычисления $L_p$-нормы матрицы и минимума функции энтропии на многограннике.
Библиография: 19 названий.