Седловые точки и двойственность
Рассмотренные выше оптимальные условия для общей задачи максимизации обычно называются условиями Куна-Таккера. Обычно они выражаются в терминах функции Лагранжа: изаписываются в векторной форме при помощи введенных ранее обозначений. В этих обозначениях условия оптимальности имеют вид: В первоначальной формулировке Куна и Таккера и в большинстве изложений теории Куна-Таккера ограничения приводятся в форме Мы уже заметили, что Поэтому решение общей задачи оптимизации может рассматриваться как нахождение седловой точки функции Лагранжа или точки, максиминимизирующейили минимаксимизирующейфункцию Лагранжа. Последняя терминология следует из того, что мы находим максимум по х и минимум по Теперь мы можем строго установить связь между множителями Лагранжа и двойственными переменными задачи линейного программирования. Рассмотрим стандартную задачу линейного программирования и двойственную к ней Функция Лагранжа для прямой задачи имеет вид Имеем Пусть
Таким образом, множители Лагранжа в общей задаче оптимизации играют роль двойственных переменных в линейном программировании и сводятся к ним, если общая задача оптимизации линейна. Поэтому в экономических задачах множители Лагранжа можно интерпретировать так же, как и двойственные переменные (обычно как неявные или условные оценки). Очевидно, что условия Куна-Таккера являются обобщением условий оптимальности каждого частного типа задач оптимизации. Теоретически, можно было бы исходить из этих более общих условий при рассмотрении частных случаев – линейного программирования и строгих классических задач на условный оптимум.
Двойственные переменные Рассмотрим общую задачу максимизации, для которой известно решение х*. Необходимо найти оптимальные значения двойственных переменных Поскольку оптимальное значение х* задано, величины Если рассматривается задача в строго классической форме, где все ограничения – равенства и отсутствуют требования неотрицательности х (но не
Приведенное соотношение представляет собой систему уравнений относительно В общей задаче максимизации условия оптимальности представляют собой неравенства. Взяв необходимую для определения Приведенные неравенства похожи на ограничения в задаче линейного программирования. Подберем подходящую целевую функцию. В нашем случае Таким образом, мы установили, что в общей задаче максимизации оптимальные значения где Ранее было показано, что в строгом классическом случае множители Лагранжа удовлетворяют соотношениям
где Можно ли в общем случае дать множителям ту же интерпретацию? Оказывается, можно, но с большими изменениями. Если, как и в классическом случае, положить При малых вариациях в окрестности оптимума неэффективные ограничения остаются неэффективными и могут быть отброшены. Следовательно, можно рассматривать задачу только с ограничениями-равенствами. Если же все прямые ограничения на х неэффективны, то анализ проводится точно так же, как в классическом случае.
Именно требование неотрицательности х,а не неравенства в функциональных ограничениях, заставляет беспокоиться. Игнорируя неэффективные функциональные ограничения и проводя анализ, аналогичный анализу в классическом случае, получаем соотношение где S – множество индексов эффективных ограничений, а все производные взяты в оптимальной точке. В классическом случае из-за условий оптимальности выражение в скобках обращается в нуль, и равенство Если же Следовательно, Поэтому в общем случае имеем
для некоторого j;
Экономическая интерпретация совершенно ясна. Множитель Требование неотрицательности Теорема о минимаксе В задаче, имеющей локальный условный максимум, функция Лагранжа удовлетворяет условию
где В этом пункте будет показано, что minimax Рассмотрим непрерывную функцию Теорема I: Прежде всего, заметим, что по определению
для всех х. Таким образом, первая часть теоремы доказана. Это предложение (minimax F Предположим, что (х*, у*) – седловая точка функции и
Аналогично, исходя из неравенства
Отсюда Сравнивая полученное соотношение с неравенством, составляющим содержание основной леммы, получаем Следовательно, существования седловой точки достаточно для выполнения утверждения теоремы. Докажем необходимость. Выберем х* таким образом, что а у* – так,что Поскольку Следовательно, Теперь можно доказать следующую теорему существования.
Теорема II: пусть множества X и Y выпуклы. Кроме того, пусть функция
Определим следующие множества: Поскольку Что и требовалось доказать.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|