Глава 7 Выпуклые функции и теорема Куна-Таккера

В этой главе изучаются экстремумы выпуклых функций на вы-

пуклых множествах в пространстве Rn . Причем если выпуклое множество задано системой ограничений типа равенств, то решение задачи сводится к поиску критических точек функции Лагранжа. Если же выпуклое множество определено системой неравенств, то оптимальное значение целевой функции находится с помощью решения системы Куна-Таккера, которая и является основной темой данной главы.

7.1. Выпуклые функции

Напомним, что множество M Rn называется выпуклым, если для любых двух точек A M и B M отрезок AB целиком принад-

(1−t)A +tB M . Если же найдется пара точек множества M , для ко-

торых это условие не выполняется, то множество выпуклым не является.

Пусть теперь точка X = (x1, x2 , , xn ) принадлежит выпуклому

92

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

ства – строго вогнутой).

Предположим теперь, что функция y = f (X ) имеет непрерывные частные производные 2-ого порядка на выпуклом множестве

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

Определитель матрицы Гессе называется гессианом.

Замечание 7.1. Отметим, что в силу условия непрерывности частных производных 2-ого порядка матрица H является симметричной. Поэтому элементы матрицы Гессе, зависящие от точки X M , можно рассматривать как коэффициенты квадратичной

i, j=1

y = f (X ).

Теорема 7.1 (достаточное условие выпуклости). Пусть M Rn

– выпуклое открытое множество, y = f (X ) – функция, имеющая в

Mнепрерывные частные производные 2-го порядка. Тогда

1.Функция y = f (X ) является строго выпуклой (строго во-

гнутой) на M , если квадратичная форма d 2 f (X ) положительно (отрицательно) определена.

2.Функция y = f (X ) является выпуклой (вогнутой) на M ,

если квадратичная форма d 2 f (X ) неотрицательно (неположи-

тельно) определена.

Обозначим

93

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

Теорема 7.2. При выполнении условий теоремы 7.1 функция y = f (X ) является строго выпуклой в M , если в каждой точке об-

ласти

∆i > 0, i =1,2, n.

Функция y = f (X ) является строго вогнутой в M , если в к а-

ждой точке области

∆1 < 0 , ∆2 > 0 , ∆3 < 0, …, (−1)n ∆n > 0 ,

т.е.

(−1)i ∆i > 0, i =1,2, n.

Для функции двух переменных z = f (x, y) следствие можно

сформулировать в следующей форме.

Следствие 7.1. Пусть M – выпуклое открытое множество на плоскости (x, y) и z = f (x, y) имеет в M непрерывные частные

производные 2-го порядка. Тогда функция z = f (x, y) является строго выпуклой (вогнутой) на множестве M , если в каждой точке

(x, y) M выполняются условия

1.fxx′′ (x, y)> 0 (fxx′′ (x, y)< 0).

Пример 7.1. Рассмотрим функцию

f (x, y, z)= 2x2 −4xz + 4y2 −8yz +9z2 + 4x +8y −2 z .

Эта функция дважды дифференцируема и ее частные производные fx′ = 4x −4z +4 = 0, fy′ =8y −8z +8, fz′= −4x −8y +18z −20, fxx′′ = 4 ,

94

не дает ответа на вопрос о выпуклости исходной функции. С другой

стороны, второй дифференциал d 2Q = QKK′′ d 2 K +2QKL′′ dKdL +QLL′′ d 2 L легко преобразуется к виду

d 2Q = −aβ (1−β)K β−2 L−β−1 (L2d 2 K −2KLdKdL + K 2d 2 L)=

= −aβ (1−β)K β−2 L−β−1 (LdK − KdL)2 ,

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

Пусть функция y = f (X ) определена на некотором множестве

M Rn . Тогда точка X0 называется точкой локального условного максимума (минимума) функции y = f (X ), если f (X )≤ f (X0 ) (или f (X )≥ f (X0 )) для всех точек X M , достаточно близких к X0 .

95