2.3. ВОГНУТОСТЬ, ВЫПУКЛОСТЬ, ПСЕВДОВОГНУТОСТЬ И КВАЗИВОГНУТОСТЬ

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

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

при изменении 0 от 0 до 1. Выпуклые множества обладают тем свойством, что отрезок, соединяющий любые две точки множества, также принадлежит этому множеству. Более точно, множество выпукло, если из следует, что для любого 0

Рис. 2.1. Множества и функции: а — выпуклые множества; — невыпуклые множества; в — вогнутые функции; — выпуклые функции; — функции, которые не являются ни вогнутыми, ни выпуклыми.

из отрезка Например, — выпуклое множество: другие примеры даны на рис. 2.1.

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

Лемма 2.2. Пусть — выпуклые множества. Тогда множество

также выпукло.

Доказательство. Если то, по определению пересечения Так как все выпуклы, то для любого

Опять по определению пересечения

Вогнутые и выпуклые функции. Теперь мы можем определить вогнутые и выпуклые функции. Функция является вогнутой на заданном выпуклом множестве С, если из следует, что

для любого 0 из отрезка .

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

пиала изображает вогнутую функцию. Линейная функция является одновременно и вогнутой и выпуклой. Другие примеры даны на рис. 2.1, а частный случай вогнутой функции, называемой строго вогнутой, рассмотрен в упр. 2.9. Для простоты результаты этого параграфа сформулируем в. терминах вогнутых функций. Читатель без затруднений сможет получить аналогичные результаты для выпуклых функций.

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

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

вогнута на С.

Доказательство. Благодаря вогнутости для

Так как то

Суммируя, получаем

Характеристика вогнутости. Для дифференцируемой функции имеется эквивалентное определение вогнутости.

Лемма 2.4. Пусть дифференцируема на Тогда вогнута в том и только в том случае, если

для любых х и у.

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

Отсюда для любого

Перейдя к пределу при получаем

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

Теперь допустим, что

Выбирая и последовательно получаем

Учитывая, что

и

и полагая преобразуем уравнения (2.5) и (2.6) к виду

и

Умножая (2.7) на и (2.8) на и складывая, получаем

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

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

Лемма 2.5. Пусть имеет непрерывные вторые частные производные. Тогда вогнута в том и только в том случае, если гессиан является отрицательно полуопределенным.

Доказательство. Разложение в ряд Тейлора имеет вид

где — некоторое число из отрезка [0, 1].

Ясно, что

тогда и только тогда, когда

Если гессиан отрицательно полуопределен, то выражение (2.9) справедливо. Тогда согласно (2.10) и лемме 2.4 функция вогнута.

Теперь положим, что вогнута, но гессиан не является отрицательно полуопределенным. Тогда для соответствующего у

Благодаря непрерывности гессиана мы можем выбрать у столь близким к х, что для всех , будем иметь

Но тогда, используя (2.9), получаем, что (2.10) не может иметь места. Однако лемма 2.4 требует выполнения условия Противоречие очевидно.