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

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

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

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

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

(ξ) ξ 0 (≤ 0) (3.8)

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

2.2.4. Алгоритм проверки выпуклости функции на заданном множестве

Пусть задана функция f(x), дважды непрерывно дифференцируемая на множестве XEn. Рассмотрим алгоритм проверки выпуклости этой функции на заданном выпуклом множестве SX с непустой внутренностью. Процедура действий такова:

1)  на множестве X находим матрицу Гессе как функцию x;

2)  рассчитываем все главные миноры , k=1,2,…,n; пусть X+ –совокупность тех точек множества X, в которых ≥ 0 одновременно для всех миноров,

3)  если SX+, то функция f(x) выпукла на S; в противном случае предположение о выпуклости f(x) на S надо отвергнуть.

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

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

ξ ξ > 0

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

Пример

Определить, будет ли выпукла (вогнута) на множестве функция .

Решение

1. Проверим выпуклость множества . Функция выпукла на , так как . По свойству выпуклых функций множество выпукло. Значит множество выпукло.

2. Составим матрицу Гессе функции и вычислим главные миноры:

3. Функция выпукла в любой выпуклой области, где матрица Гессе неотрицательно определена, т. е.

и вогнута в любой выпуклой области, где матрица Гессе неположительно определена, т. е.

.

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

4. Изобразим на координатной плоскости области выпуклости и вогнутости функции.

 

5. Изобразим дополнительно на координатной плоскости множество

 

Поскольку множество не входит целиком ни в область выпуклости, ни в область вогнутости функции , то функция на нем ни выпукла, ни вогнута.

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

Пример

Рассмотрим функцию на множестве . Очевидно, множество выпукло, и рассматриваемая функция на нем выпукла: . Однако критерий выпуклости на нем не выполняется:

т. е. всюду на матрица Гессе не определена ( знакопеременный). В данном случае, как нетрудно видеть, ).

2.3.Понятие задачи выпуклого программирования

Определение. Под задачей выпуклого программирования будем понимать задачу

F(х)→ max при хÎX={хÎ Еп: gj(x)≤bj, j=1,2,…,m, x ≥0}, (3.9)

где функция F(х) – вогнута, а функции gj(x), j=1,2,…,m – выпуклы. Напомним, что последнее условие приводит к выпуклости множества X (см. свойство 4 выпуклых функций).

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

Теорема 3.5. Множество точек X*X, на которых достигается глобальный максимум F(х) в задаче выпуклого программирования, является выпуклым.

Замечание. Множество X* в теореме 3.5 может быть и пусто.

Доказательство теоремы сразу следует из выпуклости множества X и определения вогнутости функции F(х).

Теорема 3.6 («локально-глобальная»). Пусть функция (х) вогнута на выпуклом множестве X. Тогда любой локальный максимум является глобальным.

Доказательство. Если множество X пусто, то справедливость утверждения очевидна.

Пусть теперь и - точка локального максимума. Предположим, что утверждение теоремы не верно, т. е. существует точка такая, что . Рассмотрим отрезок