Глава 10. Модели выпуклого программирования

Рассмотрим задачу нелинейного программирования (9.1) и (9.2) при условии, что функции ∕ и являются выпуклыми. Введем необходимые понятия.

10.1. Производная по направлению и градиент. Выпуклые функции

Производной функции по направлению I в точке X называется предел

Направление ∕ обычно задается вектором

Если функция Fдифференцируема в точке X, то она имеет в этой точке производную по любому направлению /, которая выражается через частные производные по формуле

(10.1)

где– длина вектора /, т.е.

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

Градиентом VF функцииназывается вектор, проекциями которого на координатные оси служат соответствующие частные производные, т.е.

Можно показать, чтодостигается тогда, когда на

правление I совпадает с направлением VF. По формуле (10.1) производная функции F по направлению градиента W равна

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

10.1. Найти наибольшую скорость возрастания функциив точке Л (0; 1; 2) и определить характер изменения этой функции в точке А в направлении ∕ =

= (1; -2; 2).

Решение. Так как тои. Таким образом, наибольшая скорость возрастания функции в точке А равна. Далееи

Так как, функция F в точке А в направлении ∕ возрастает. ►

Напомним (см. параграф 2.2), что множество точек называется выпуклым, если оно вместе с любыми своими двумя точками содержит и весь отрезок, соединяющий эти точки. Если а,Ь] – отрезок на числовой прямой и, то, как показано в параграфе 3.1,или

(10.2)

Нетрудно видеть и обратное: если выполняется (10.2), то . Таким образом, отрезокможно определить как множество всех точек х, удовлетворяющих условию (10.2). Тогда выпуклое множество – это множество, которое вместе с любой парой своих точек а, b содержит и все точки X, для которых выполняется (10.2). Эти определения отрезка и выпуклого множества сохраняются для случая, когда а, Ь,х – точки "-мерного пространства (где операции в равенстве (10.2) выполняются покоординатно).

Исходя из равенства (10.2) по индукции можно показать, что если М – выпуклое пространство, то для любых точеки любых действительных

чисел tj > 0, удовлетворяющих условию

Функция, определенная на выпуклом множестве М п-мерного пространства, называется выпуклой на этом множестве, если

(10.3)

для любых точеки любого числа

Если в условии (10.2) изменить знак неравенства < на >, то получим определение вогнутой функции. Если же в условии (10.3) неравенство выполняется как строгое, то функция называется строго выпуклой (или строго вогнутой).

На рис. 10.1 изображен график функции одной переменной, выпуклой на всей числовой прямой.

Рис. 10.1

Для любой пары Xv Х2 значений аргумента произвольную точку(см. (10.2)) можно задать в виде

. Как видно из рис. 10.1, неравенство (10.3) означает, что отрезок, соединяющий точкии

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

10.2. Установить выпуклость (вогнутость) функций, приведенных на рис. 10.2.

Решение. Функцииявляются всюду строго выпуклыми, астрого вогнута на интервале (0, ∞).

Рис. 10.2

Функцияне является ни выпуклой, ни вогнутой на всей числовой прямой, но точка х = 2 разбивает ее на два участка: слева от этой точки она вогнута, справа – выпукла (см. рис. 10.2). ►

Рассмотрим свойства выпуклых функций. Все рассматриваемые функции предполагаются определенными на некотором выпуклом множестве М. Свойства приводятся без доказательств, но многие из них легко проверяются по определению (10.3) и для функций одной переменной иллюстрируются графиками.

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

• 1. Если функция Г(Х) выпукла, то функция -F(X) вогнута.
• 2. Функция F(X) = C и линейная функция FyX) = aX + b являются всюду выпуклымии всюду вогнутыми.
• 3. Если функциивыпуклы, то при любых действительных числахфункция так

же является выпуклой.

4. Если функция F(X) выпукла, то для любого числа а область решений неравенства F[X)< а является либо выпуклым множеством, либо пустым.

Отметим следствия свойства 4 и теоремы о пересечении выпуклых множеств.

5. Если функциивыпуклые при всех неотрица

тельных значениях переменных, то область решений системы неравенствявляется выпуклым множеством (если она не пуста).

• 6. Выпуклая (вогнутая) функция, определенная на выпуклом множестве М, непрерывна в каждой внутренней точке этого множества.
• 7. Всякая дифференцируемая строго выпуклая (вогнутая) функция имеет не более одной стационарной точки (т.е. точки, в которой равны нулю все частные производные).

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

8. Дважды дифференцируемая функция

является выпуклой в том и только в том случае, когда

(10.4)

для любыхне обращающихся в нуль од

новременно.

Чтобы использовать это условие для определения выпуклости конкретной функции, часто бывает полезен критерий Сильвестра^[1]: условие (10.4) выполняется тогда и только тогда, когда неотрицательны все главные миноры Δ⅛ матрицы вторых частных производных, т.е. определители

(10.5)

Если все, то неравенство (10.4) выполняется как строгое, и тогда функция F будет строго выпуклой.

10.3. Показать, что следующие функции являются выпуклыми:

Решение, а) Находим частные производные:

Матрица вторых частных производных имеет вид Ее главные миноры Δ, = |4| = 4 > О, Δ2 = | ∏| = 7 > 0.

Значит, на основании свойства 8 функция F является строго выпуклой при всех X.

б) Здесь

Матрица вторых частных производных имеет вид

Таким образом, G является выпуклой, но не строго выпуклой функцией при►

• [1] Дж. Сильвестр (1814–1897) – английский математик.