ВЫ́ПУКЛОЕ ПРОГРАММИ́РОВАНИЕ
-
Рубрика: Математика
-
-
Скопировать библиографическую ссылку:
ВЫ́ПУКЛОЕ ПРОГРАММИ́РОВАНИЕ, раздел математич. программирования, в котором исследуется задача максимизации вогнутой целевой функции $f(x)$ векторного аргумента $x=(x_1, …, x_n)$, удовлетворяющего ограничениям $g_i(x)⩾0, x∈X, i=1, ..., m,$ где $g_i$ – вогнутые функции, $X$ – выпуклое множество. Точка $x$, удовлетворяющая этим ограничениям, называется допустимой. Осн. результатом теории В. п. является теорема о седловой точке: для того чтобы допустимая точка $x$* задачи В. п. была оптимальной, необходимо (при довольно широких условиях) и достаточно существование вектора $y^*=(y^*1, …, y^*_m)$ с неотрицательными компонентами такого $y^*_1$, что точка ($x^*, y^*$) является седловой для функции Лагранжа$$L(x,y)=f(x)+\sum_{i=1}^my_ig_i(x)$$ задачи В. п., т. е. для любых $x∈X$ и $y$ с неотрицательными компонентами выполняются неравенства $L(x, y^*)⩽L(x^*, y^*)⩽L(x^*, y)$.
На теорему о седловой точке опирается ряд методов В. п., в которых либо минимизируется функция $φ(y_1, …, y_m)=\text {max}_{x∈X}L(x, y)$ при $y_i⩾ 0, i= 1, …, m$, либо непосредственно отыскивается седловая точка, причём вместо функции Лагранжа иногда используются некоторые её модификации. Другой подход к решению задачи В. п. связан с поиском возможных направлений движения допустимой точки $x$, которые не выводят из множества допустимых точек и при движении вдоль которых целевая функция возрастает. Этот подход реализуется с помощью последовательности итераций. На каждой итерации вычисляется возможное направление, исходящее из очередной точки, после чего производится сдвиг по этому направлению на некоторое расстояние до следующей точки. Существуют методы решения задач В. п., специально приспособленные к тому случаю, когда целевая функция нелинейна, а ограничения линейны. Как правило, методы В. п. требуют для точного определения оптимальной точки бесконечного числа итераций. Исключением являются задачи квадратичного программирования (целевая функция – сумма вогнутой квадратичной и линейной функций, ограничения линейны) и линейного программирования (целевая функция и ограничения линейны), для которых в осн. используются конечные методы. Многие вычислительные методы В. п. реализованы в виде программ для ЭВМ; существуют также пакеты программ, охватывающие задачи линейного программирования и В. п. См. также Исследование операций.