Тема 2. Задача нелинейного программирования (продолжение) (стр. 2 )

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

Пусть . Тогда . Рассмотрим

.

В силу выпуклости f(x) имеем

.

Отсюда . Утверждение доказано.

Рис 3.8. Пример выпуклой функции с разрывами на границе выпуклого множества [A,B].

Рис 3.9. Отрезок [A’, B’] является примером множества .

Имеют место и более сложные свойства выпуклых функций.

Определение. Надграфиком (эпиграфом) выпуклой функции f(x), определенной на выпуклом множестве XEn, называется n+1-мерное множество epi f, определяемое так:

.

Понятие надграфика проиллюстрировано на рис. 3.10.

Свойство надграфика. Выпуклость надграфика функции f(x), определенной на выпуклом множестве X, эквивалентна выпуклости функции.

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

Рис. 3.10. Заштрихованное множество – надграфик выпуклой функции f(x).

Следующее свойство выпуклых функций выполняется для непрерывно дифференцируемых функций.

Теорема 3.2. Для выпуклости непрерывно дифференцируемой функции f(x), определенной на выпуклом множестве в X, необходимо и достаточно, чтобы

(3.2)

для любых .

Доказательство этой теоремы здесь приводиться не будет[2]. Дадим соответствующую иллюстрацию для случая n=1 (см. рис. 3.11). Штриховая линия на рисунке является опорной плоскостью к надграфику функции f(x) в точке . Поэтому, например, D = f(B) > C = f(x0)+tg β (B–x0). Замечая, что при n = 1 имеет место tg β = f(x0), получаем

f(B) – f(x0) > f(x0) (B–x0),

то есть выполняется соотношение (3.2).

Определение. Функция

,

график которой является опорной гиперплоскостью к надграфику функции f(x) в точке , называется опорной к функции f(x) в точке .

Рис. 3.11. Надграфик выпуклой функции f(x), заданной на отрезке [A,B], и опорная гиперплоскость к нему в точке (x0, f(x0)), изображенная штриховой линией.

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

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

Рис 3.12. Опорные функции для выпуклой не дифференцируемой функции f(x) в точке

Рассмотрим рис. 3.12, на котором выпуклая функция f(x) имеет излом в точке . В связи с этим имеется целый пучок гиперплоскостей, опорных к надграфику функции f(x) в точке . Эти гиперплоскости являются графиками опорных функций к функции f(x) в точке , задаваемых соотношениями

. (3.3)

Ясно, что для того, чтобы функция (3.3) была опорной в точке , от вектора требуется, чтобы в точке выполнялся аналог условия (3.2), который должен иметь вид

(3.4)

для любых .

Определение. Субградиентом функции f(x) в точке называется такой вектор , для которого при любых выполняется соотношение (3.4), а субдифференциалом функции f(x) в точке – совокупность всех субградиентов в этой точке.

Итак, в содержательном плане, субдифференциал – это множество “угловых коэффициентов” a функций (3.3), опорных к f(x) в точке . Субдифференциал функции f(x) в точке , который обозначается через , является выпуклым (возможно, пустым) множеством пространства . В точках непрерывности выпуклых функции их дифференциал непуст, а для непрерывно дифференцируемых функции содержит лишь градиент функции[3].

2.2.3. Признаки выпуклости и вогнутости функций

Можно сформулировать различные достаточные условия выпуклости функции f(x), определенной на выпуклом множестве в XEn. Например, необходимым и достаточным условием выпуклости функции является выпуклость ее надграфика. Во многих случаях выпуклость доказывается непосредственной проверкой условия (3.1). Для доказательства выпуклости функции могут быть использованы и свойства выпуклых функций. Так, например, из легко проверяемой выпуклости функций f(x) = x2 и f(x) = x следует выпуклость функции f(x) = a x2+b x+c при a, b, c ≥ 0.

Условия выпуклости для гладких функций

Обратимся к методу, позволяющему проверить выпуклость дважды непрерывно дифференцируемой функции f(x) на некотором выпуклом множестве SEn. Для этого используем матрицу Гессе функции f(x) в точках , которую обозначим через . Напомним, что эта матрица является симметричной.

Теорема 3.3. Пусть множество SEn выпукло. Пусть функция f(x) дважды непрерывно дифференцируема на S. Тогда для выпуклости функции f(x) на множестве S достаточно выполнение условия

(ξ) ξ ≥ 0 (3.5)

для всех при всех . При Ø условие (3.5) также является необходимым.

Доказательство теоремы приводиться не будет[4]. Заметим, что условие (3.5) зачастую пишут в эквивалентном виде

ξТ ξ ≥ 0. (3.6)

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