Материал: ОиММПР. Практические работы 2019

Выпуклые и вогнутые функции

В одномерном случае выпуклость проявляется в том, что функция всегда лежит п о д х о р д о й, соединяющей любые две точки на ее графике. Непосредственно из определения также следует, что линейная функция является выпуклой, хотя и не строго выпуклой.

Замечание. Если знак неравенства в определении выпуклой функции поменять на обратный, получится определение вогнутой функции. Специально рассматривать этот класс функций не имеет смысла, так как вогнутую функцию легко превратить в выпуклую, умножив ее на 1.

Выпуклые функции обладают рядом полезных для применения свойств. Рассмотрим их.

Свойство 1 (неравенство Иенсена). Заданная выпуклая комбинация,

состоящая из выпуклых функций, так же выпукла. То есть, если (~ ) — вы- f X

m

пуклая функция и å ai = 1; ai > 0, то

i=1

Свойство 5 (свойство экстремума). Любой локальный минимум задан-

ной выпуклой функции (~ ) на выпуклом множестве является глобальным. f X Q

Замечания

Приведенное свойство имеет высокую значимость для выпуклой оптимизации, поскольку позволяет заменить глобальные условия минимума ло-

81

кальными, основанными на дифференциальных свойствах функций в предположении, что все частные производные существуют и непрерывны.

Для приведенного свойства имеем в виду задачу минимизации, поскольку максимизация достигается сменой знака у целевой функции.

Вектор частных производных функции многих переменных (~ ) в точке f X

~ называется градиентом, обозначается как

X

Противоположный ему по направлению вектор Ñ f (X) называется антигра-

диентом и определяет направление скорейшего убывания. Скорость изме-

нения функции (~ ) по направлению, задаваемому произвольным вектором f X

~q, называется производной по направлению и может быть выражена как проекция градиента на выбранное направление:

пукла и дифференцируема на выпуклом множестве, то для любых двух точек

Матрица вторых частных производных (при условии их существования),

вычисленных в точке ~ , называется матрицей Гессе. Запишем ее как

X

мая заданная функция f (X) выпукла (строго выпукла) в окрестности точки X

только тогда, когда ее матрица Гессе (~ ) неотрицательно (положительно)

H X

определена в этой точке.

Критерий Сильвестра: матрица является положительно (неотрицательно) определенной, если все ее угловые миноры положительны (неотрицательны).

82

9.2.1. Оптимизация функций

Задача минимизации функции многих переменных в неограниченной области

Необходимым условием локального минимума является равенство нулю всех частных производных (теорема Ферма):

(~ )

d f X = 0; j = 1; :::; n: dxj

Это условие первого порядка можно записать в компактной векторной форме

~~

Ñf (X) = 0:

Точки X , удовлетворяющие условию первого порядка, называются стационарными. В общем случае стационарность не обязательно связана с минимумом, стационарными являются точки как минимума, так и максимума, а также точки перегиба одномерных функций или седловые точки в многомерном случае. Достаточным условием локального минимума является поло-

жительная определенность матрицы Гессе (~ ) в стационарной точке.

H X

Для выпуклых функций условие первого порядка является необходимым и достаточным условием локального минимума.

Метод множителей Лагранжа

Если ограничения задаются совокупностью уравнений, то условная экстремальная задача оптимизации приобретает вид

(~ ) = ( ; :::; ) ! ; f X f x1 xn min

(~ ) = ( ; :::; ) = 0; gi X gi x1 xn

i = 1; :::; m; j = 1; :::; n:

и подход к решению этой задачи (9.1) основан на использовании функции Лагранжа

телей Лагранжа, число которых равно количеству ограничений.

83

Необходимые (и достаточные в случае выпуклости всех участвующих функций) условия минимума имеют вид

Получаем систему, состоящую из (n + m) уравнений с тем же количеством переменных (x1; :::; xn; l1; :::; lm).

Всякое ее решение определяет точку X = (x10; x20; :::; xn0), в которой может быть экстремум функции f (x1; x2; :::; xn). Следовательно, решая систему уравнений, получаем все точки, в которых функция цели (а более точно — линия пересечения двух поверхностей) может иметь экстремальное значение. Далее, применяя классические подходы математического анализа, исследуем эти точки на тип экстремума.

Подытожим, что определение экстремальных точек в задаче нелинейного программирования методом множителей Лагранжа включает следующие этапы:

составляем функцию Лагранжа;

находим частные производные от функции Лагранжа по переменным xj и li и приравниваем их нулю;

решаем систему (n + m) уравнений частных производных, находим точки, в которых целевая функция может иметь экстремум;

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

Теорема Куна–Таккера

Условие Слейтера: условие регулярности, которое заключается в том, что допустимая область функции имеет хотя бы одну внутреннюю точку, т. е.

9~ (~ ) < 0; = 1; :::; :

X gi X i m

Теорема (Куна–Таккера): при соблюдении условия Слейтера для существования оптимального плана в общей задаче (9.1) с регулярным множеством планов:

84

где riQ — относительная внутренность множества Q, необходимо и достаточно существование такого вектора

l 0 2 R; li 0; i = 1; k; li0 — произвольные; i = k + 1; m;

Для ограничений, выраженных в виде линейных функций gi(x); i = 1; k, теорема Куна–Таккера верна без условия Слейтера (9.3).

Схема решения.

1.Убеждаемся в том, что данная задача является задачей выпуклого программирования, используя свойства и критерии выпуклых функций, выпуклых множеств.

2.Сформулируем и запишем задачу в виде (9.1). Множество Q стро-

им по функциям ограничений исходной задачи так, чтобы легко можно бы-

ло проверить принадлежность ему вектора x 2 Rn. Обычно Q = fx : xj 0; 8j 2 I I = fi = 1; ngg; I — является подмножеством I.

3.Определяем, является ли множество планов регулярным.

4.Находим стационарные точки функции Лагранжа. Решаем систему

уравнений:

>

>

>

:

5.Для каждой найденой стационарной точки проверяем условие (9.4).

6.Если среди полученных стационарных точек отыщется седловая точка функции Лагранжа fx ; l g, значит x — решение исходной задачи x0 = x . Если седловой точки нет, то есть x0 2 intQ, то переходим к следующему

пункту.

7.Выполняем поиск решения задачи на границе множества Q. Если Q состоит из внутренних точек, то задача решения не имеет. Пусть L — граница множества Q, L 2 Q и множества Li; i = 1; s — элементы L (например, грани, ребра, угловые точки). Для продолжения поиска решения имеем совокупность следующих задач:

85