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

с ограничениями
.
Функция
линейна по
.Это означает, что она может рассматриваться как выпуклая по
.Функция Лагранжа
как функция от х является положительной линейной комбинацией функций
и
.Функция
,конечно, будет вогнутой по х,если определяющие ее функции вогнуты. Однако
вогнута, если
выпукла. Следовательно,
вогнута по х,если
вогнутая, а все
выпуклые функции.
Рассмотрим теперь множества, которым принадлежат х и
. Единственное ограничение на
– требование неотрицательности. Следовательно, вектор
определен на выпуклом множестве (неотрицательный ортант). Если
– выпуклая функция, то множество
выпукло. Допустимое множество является пересечением выпуклых множеств и поэтому выпукло.
Таким образом, мы показали, что векторы х и
определены на выпуклых множествах. Необходимо, чтобы эти множества были компактами. Вид ограничений гарантирует, что множества замкнуты. Остается показать их ограниченность. Поскольку мы ищем минимум
, а
ограничены снизу требованием неотрицательности
, можно выбрать произвольную верхнюю грань, достаточно большую, чтобы не повлиять при этом на оптимальное решение. Труднее обстоит дело с требованиями к допустимому множеству для х. Нельзя избежать добавления специального предположения о том, что допустимое множество ограничено.
Таким образом, если
вогнутая функция, каждая
– выпуклая функция, а допустимое множество ограничено (и не пусто), то функция Лагранжа удовлетворяет условиям теоремы II предыдущего пункта. Следовательно, функция Лагранжа обладает седловой точкой, а общая задача оптимизации имеет решение. Более того, условия глобального оптимума удовлетворяются при тех же условиях выпуклости – вогнутости.
Теорема существования: общая задача максимизации
всегда имеет решение, если f (x) – вогнутая, все
– выпуклые функции и допустимое множество
– ограничено и не пусто.
При выполнении этих условий функция Лагранжа
обладает седловой точкой
, где х* – оптимальная точка задачи максимизации, а
. Кроме того, значения
удовлетворяют условиям Куна-Таккера, достаточным для глобального оптимума. Если
строго вогнута, точка х* – единственна.
Для того чтобы охватить случай, когда
и
– положительные монотонные преобразования вогнутой и выпуклых функций соответственно, теорема может быть обобщена.
Заметим, что задача линейного программирования удовлетворяет этим условиям выпуклости – вогнутости. Если прямая задача имеет оптимальное решение, ее допустимое множество должно быть не пустым и может рассматриваться как ограниченное. Поскольку в этом случае функция Лагранжа должна иметь седловую точку, а
в функции Лагранжа совпадать с оптимальным решением у* двойственной задачи, можно закончить доказательство теоремы существования решения задачи линейного программирования, утверждая, что если прямая задача имеет решение, то и двойственная также имеет решение.
Обычно условия теоремы существования требуют, чтобы функции
были вогнуты, потому что ограничения имеют вид
, а в функции Лагранжа они умножаются на
и прибавляются к целевой функции
.Эти условия эквивалентны приведенным выше.
Условия теоремы являются довольно жесткими, требуя выпуклости каждой функции ограничений и вогнутости целевой функции. Условия второго порядка оперировали вогнуто-выпуклыми функциями. Однако классические условия не гарантируют глобальный оптимум.
Часто можно выбрать в некотором смысле лучший из двух методов. Если число ограничений меньше числа переменных, и ограничения на неотрицательность х неэффективны в оптимуме, можно ожидать, что все функциональные ограничения будут эффективными. Таким образом, можно ввести неравенства в функциональные ограничения и использовать условия глобального оптимума для общего случая, а условия Куна-Таккера сведутся к обычным условиям первого порядка классической задачи. Таким образом, можно показать, например, что решение классической задачи на потребление
при условии, что
,дает глобальный оптимум, если
.
ГЛАВА 18
Воспользуйтесь поиском по сайту: