2.3.1. Некоторые важные следствия вогнутости в нелинейном программировании

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

Утверждение 2.6. Пусть — дифференцируемая вогнутая функция в . В таком случае тогда и только тогда, когда х максимизирует на

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

Таким образом, х максимизирует на Необходимость следует из следствия 2.1.1.

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

Лемма 2.7. Пусть — вогнутая функция. Тогда для любой фиксированной скалярной величины у множество содержащееся в выпукло.

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

Значит, следовательно, выпукло.

Утверждение 2.8. Пусть — ограничения задачи НЛП. Предположим, что для каждого I множество выпукло для любой скалярной величины Тогда допустимая область выпукла.

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

Лемма 2.7 и утверждение 2.8 устанавливают, что если ограничения — вогнутые функции, то допустимая область выпукла.

Дополнительные свойства. Перечислим некоторые дополнительные свойства вогнутых функций и выпуклых множеств (упр. 5):

а) вогнута в тогда и только тогда, когда множество выпукло, где у — переменный скаляр;

б) полупространство является выпуклым множеством для любого вектора и скаляра

в) линейная функция является как вогнутой, так и выпуклой:

г) пусть А — матрица размеров -мерный вектор. Тогда множество всех х, удовлетворяющих условиям выпукло;

д) пусть вогнутые функции. Тогда функция

также вогнута;

е) пусть принадлежит выпуклому множеству С. Положим

где у — фиксированные скалярные величины, Тогда

ж) предположим, что — вогнутая функция. Пусть

Где — фиксированные скалярные величины,

Тогда

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

Как было отмечено выше, два свойства вогнутых функций особенно ценны в НЛП: первое — из следует, что х — глобальный максимум; второе — множество выпукло для любого скаляра у. Первое свойство обеспечивает то, что условие является одновременно необходимым и достаточным для того, чтобы х максимизировал на Если каждое из ограничений обладает вторым свойством, то множество, определяемое системой ограничений, является выпуклым по утверждению 2.8. Оба свойства очень полезны при установлении достаточных условий оптимальности. Функция, обладающая обоими этими свойствами, является псевдовогнутой, а квазивошутая функция обладает лишь вторым свойством. Сначала рассмотрим псевдовогнутую функцию.

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

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

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

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

Квазивогнутая функция. Определим квазивогнутую функцию. Функция называется квазивогнутой, если для данных и любого

Мы назовем функцию квазивыпуклой, если квазивогнута. Следующая лемма устанавливает, что обладает упомянутым ранее вторым свойством и одновременно дает другое эквивалентное определение квазивогнутости.

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

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

Таким образом, и множество выпукло.

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

Положим

Тогда по определению где и так как выпукло, то для

Отсюда, принимая во внимание выражения (2.11) и (2.12), получаем

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

Рис. 2.2. Функции: а — псевдовогнутые функции; — квазивогнутые функции.

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