Метод множителей Лагранжа

[Nogin Anton]

Не судите строго, я только начинаю в этой теме разбираться.)

Цитата:

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

Это значит, что вместо последних трёх уравнений из поста #1 нужно использовать следующие?

$(x_1^2 +x_2^2 -10)\cdot \lambda_1=0$
$(x_1-1)\cdot \lambda_2 =0$
$(x_2-2)\cdot \lambda_3 =0$

Мат-ламер, ограничения в виде неравенств?

[мат-ламер]

Nogin Anton в сообщении #522689 писал(а):

Мат-ламер, ограничения в виде неравенств?

Да.

[Nimza]

Nogin Anton в сообщении #522689 писал(а):

Это значит, что вместо последних трёх уравнений из поста #1 нужно использовать следующие?

Откуда Вы их взяли? У вас же другие ограничения.

$(x_1 - x_2) \lambda_1 = 0$
$(x_1^2 + 4x_2 - 4) \lambda_2 = 0$
$(x_1^2+x_2^2 - 5) \lambda_3 = 0$

Плюс ко всему есть ещё ограничения на знак лямбд: $\lambda_1 \geqslant 0$, $\lambda_2 \leqslant 0$, $\lambda_3 \leqslant 0$ (для вашей функции Лагранжа).

Ну и практически дело сделано.

[Nogin Anton]

Nimza, пытался решать аналогичную задачу.. от туда и ограничения.)) Прошу прощения, перепутал.

-- Вт янв 03, 2012 22:16:43 --

Nimza, а можно $\lambda_1, \lambda_2, \lambda_3$ выразить через иксы? То есть все лямбды получатся равными нулю.

Исправил \lmbda на \lambda. /AKM

[Nimza]

Nogin Anton в сообщении #522706 писал(а):

а можно выразить через иксы? То есть все лямбды получатся равными нулю.

Как Вы из неравенств собираетесь выражать?

Ну смотрите, как можно начать и как вообще решаются такие задачки, если не прибегать к геометрии. У Вас есть 5 уравнений, первые два из которых Вы написали в первом сообщении:
$2 ( 1 + \lambda_2 - \lambda_3) x_1 = - \lambda_1 (*)$
$2 ( 1 + \lambda_3) x_2 = -\lambda_1 + 4\lambda_2 - 6 (**)$

Допустим сперва, что $\lambda_1 \neq 0$, тогда $x_1 = x_2$ из первого условия доп. нежесткости. Если при этом $\lambda_3 \neq 0$, то $x_1 = x_2 = \pm \sqrt{ \frac{5}{2} }$. С минусом нам не подходит по второму ограничению задачи. Если взять с плюсом, то второе ограничение задачи выполняется нестрого, значит, $\lambda_2 = 0$ из доп. нежесткости. Тогда смотрим на формулу $(*)$ и видим, что это невозможно. Слева положительное число, справа отрицательное. Пусть теперь $\lambda_3 = 0$. Тогда из $(**)$ имеем $x_1 = x_2 < 0$. Опять два подслучая: $\lambda_2 = 0$ ведёт к противоречию в $(*)$, $\lambda_2 < 0$ по условию доп. нежёсткости явно выдает нам значения $x_1 = x_2 = - 2 - 2 \sqrt{2}$, которые не подходят по третьему условию задачи. Таким образом, $\lambda_1 = 0$.

Осталось рассмотреть случай с $\lambda_1 = 0$

P.S. Решайте для себя, что Вам легче. Анализировать формулы или рисовать картинки. В данном случае с картинками, судя по всему, получается быстрее.

[bot]

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

(Оффтоп)

И то и другое достигается в некоторой точке. Если эта точка внутренняя, то срабатывает необходимое условия равенства
нулю тех частных производных, которые существуют. А если она на границе, то это точка условного экстремума. В такой точке (явно или чисто теоретически по теореме о неявной функции)
можно часть переменных выразить через остальные. Точки нарушения условий существования неявной функции включаем в число проверяемых. Если явное выражение не получается
или неудобно или на то есть запрет от постановщика задачи, составляем функцию Лагранжа и ищем её критические точки. Граница может быть задана кусочно и в случае неплоской
задачи может возникнуть необходимость рассмотрения совместного выполнения нескольких уравнений связи. Вот только здесь и могут сказаться некоторые вычислительные преимущества
Куна-Такера перед Лагранжем.

В нашем случае целевая функция $f(x,y)=x^2-(y+3)^2 $, а ограничения даются неравенствами $x\leqslant y, \ x^2+4y\geqslant 4, \ x^2+y^2\leqslant 5. $ Эти ограничения задают
"серпик", который впрочем рисовать не обязательно - так как всё лежит в круге, то область ограничена и замкнута, так как неравенства у нас нестрогие.
Тупо приравниваем к нулю частные производные целевой функции и получаем точку $(0; -3)$, которая лежит вне области, следовательно искомая точка (минимума или максимума) лежит на границе.

(Оффтоп)

Если не тупо, то ещё очевиднее - во внутренней точке можно сдвинуться по вертикали вниз/вверх и получить большее/меньшее значение

Граница состоит из трёх кусков - кругового, параболического и прямолинейного. Для примера рассмотрим случай когда искомая точка лежит на окружности.

(Оффтоп)

Я бы просто заменил в целевой функции $x^2$ на $5-y^2$ и рассмотрел функцию одной переменной на понятно каком отрезке, но нам это запретили.

Функция Лагранжа для этого случая $L=x^2-(y+3)^2+\lambda (x^2+y^2)$. Приравниваем частные производные к нулю:

$\begin{cases} x(1+\lambda)=0 \\ (\lambda-1)y-3=0\end{cases}$

Если $\lambda=-1$, то $y=-3/2, x=\pm ... $ - обе точки лежат ниже серпика. Если $\lambda\ne -1$, то $x=0, y=+\sqrt 5$. Эта точка очевидного минимума. Остались ещё граничные точки дуги - это
точки пересечения окружности с параболой и прямой

$A(-2\sqrt{\sqrt5-1};2-\sqrt5)$ и $B(\sqrt{5/2}; \sqrt{5/2})$

[Nogin Anton]

bot,пытаюсь разобраться.

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

Вы рассмотрели пример для окружности. И нужно теперь аналогично составить функции лагранжа для параболы и прямой?

[Nogin Anton]

Цитата:

Приравниваем частные производные к нулю:

$\begin{cases} x(1+\lambda)=0 \\ (\lambda-1)y-3=0\end{cases}$

Скажите, а почему не нужно брать частную производную по лямбде?

[bot]

Всё бы Вам в буковки играть. Уравнение кривой $x^2+y^2=5$, на которой сидим, без всякого дифференцирования по лямбде знаем. Кстати сказать, поскольку я константу -5 из скобки убрал, то дифференцированием по лямбде этого уравнения и не получить.

-- Ср янв 04, 2012 19:50:11 --

Nogin Anton в сообщении #522822 писал(а):

Вы рассмотрели пример для окружности. И нужно теперь аналогично составить функции лагранжа для параболы и прямой?

Да, поскольку явное сведение к одной переменной Вам запретили.

[Nogin Anton]

Скажите, я верно сделал для остальных двух ограничений:

1. Для прямой: $L=x_1^2-(x_2+3)^2+\lambda (x_1-x_2)$
$L'_{x_1}=2x_1+\lambda$
$L'_{x_2}=-2x_2-6-\lambda$
$L'_{\lambda}=x_1-x_2$

В ходе решения системы выявил противоречие ($3 \noteq 0$). Решений нет.

2. Для параболы: $L=x_1^2-(x_2+3)^2+\lambda (x_1^2+4x_2-4)$
$L'_{x_1}=(2x_1+2\lambda x_1)$
$L'_{x_2}=(-2x_2-6+4\lambda )$
$L'_{\lambda}=x_1^2+4x_2-4$

Тут получил две точки - (4.9; -5) и (-4.9; -5), которые не удовлетворяют ограничениям.

[bot]

1) Условного экстремума на прямой нет - это верно. А максимум минимум на отрезке быть обязан, следовательно они в крайних точках.
2) Аналогично, критические точки оказались вне зоны наших интересов, а вот крайние остались. Одна из них уже есть - это точка B и надо ещё добавить C - точку C пересечения параболы с прямой. Итого, имеем три точки A,B,C, в которых только и осталось быть максимуму - теперь просто сравнить значения и всё.

[Nogin Anton]

Ещё вопрос по условиям: а нужно все условия приводить к виду $g(x_i)\ge 0$, то есть условие для окружности должно ли быть таким: $5-x_1^2-x_2^2 \ge 0$?

[bot]

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

[Nogin Anton]

Нашёл точки пересечения прямой и окружности: $A_1 (\sqrt{2.5}; \sqrt{2.5})$ и $A_2 (-\sqrt{2.5}; -\sqrt{2.5})$

Точки пересечения прямой и параболы: $B(2(-1-\sqrt{2}); 2(-1-\sqrt{2}))$ и $C(2(\sqrt{2}-1); \sqrt{2}-1)$

Значения функции для точек $A_1,A_2,B,C$ соответственно: $-18.48$, $0.48$, $19.8$ и $-13.92$. Получается, что точка B - искомая точка экстремума?

[bot]

Да Вам же уже открытым текстом три точки выдали!