Двойственность. Метод множителей Лагранжа.

[jury.k]

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

min(c,x)
||x|| \leqslant 1

Необходимо построить задачу, двойственную заданной.

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

[Imperator]

Какая здесь норма берется?

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

[jury.k]

Imperator писал(а):

Какая здесь норма берется?

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

В задании, к сожалению, ничего не сказано, но я думаю вряд ли нам стали бы давать экзотические случаи - скорей всего евклидова =)

[Imperator]

Есть предложение сделать так.

Пусть $x$ -- $n-$мерный вектор. По условию его евклидова норма не превосходит 1 $\Rightarrow x_{1}^{2}+x_{2}^{2}+...+x_{n}^{2}\leqslant 1$. Из последнего можно заключить, что для всех $i=1,...,n$ выполнены двойные неравенства $-1\leqslant x_{i} \leqslant 1$. Сделаем замену переменных в исходной задаче: $z_{i}=x_{i}+1$ ($i=1,...,n$). Тогда $z_{i}\geqslant 0$ и в то же время $z_{i}\leqslant 2$ для $i=1,...,n$.

Итак, имеем следующую прямую задачу, для которой требуется построить двойственную:
$max[-c_{1}\cdot (z_{1}-1)-c_{2}\cdot (z_{2}-1)-...-c_{n}\cdot (z_{n}-1)]$
при ограничениях:
$z_{1}\leqslant2,$
...
$z_{n}\leqslant2,$
$z_{i}\geqslant 0$ $(i=1..n)$.


А к такой задаче (см. выше), думаю, Вы построите двойственную без проблем. Только обратите внимание на вид целевой функции.

[мат-ламер]

Вообще, действовать можно по-разному. Можно схитрить, прикинуться чайником и возвести ограничение в квадрат. Получим задачу эквивалентную данной (хотя уже где-то и другую). В этом случае минимум функции Лагранжа найдётся легко, посколько она будет дифференцируемая. Но, возможно, это не совсем то, что Вам нужно. Если работать с задачей в исходной постановке, то функция Лагранжа будет не дифференцируемая в обычном смысле. Чтобы найти её минимум, надо найти ёё субдифференциал. Условие минимума - нуль принадлежит субдифференциалу Субдифференциал от нормы в нуле - это единичный шар, а не в нуле норма дифференцируема в обычном смысле. Надо рассмотреть отдельно случаи когда минимум достигается в нуле и когда не достигается вообще ( в зависимости от нормы вектора c). В итоге получим ответ, отличный от ответа при первом подходе. Т.е. две эквивалетные постановки одной задачи имеют разные двойственные. Популярно вопрос рассмотрен у Сухарева-Тимохова-Фёдорова в главе 4.

Добавлено спустя 2 часа 22 минуты 29 секунд:

Сейчас прочёл сообщение от Imperator. По-моему, переход от сферической нормы к кубической не вполне правомерен, хотя-бы потому, что минимум линейной функции на шаре и на кубе достигается в разных точках (это разные задачи).

[jury.k]

мат-ламер писал(а):

Вообще, действовать можно по-разному. Можно схитрить, прикинуться чайником и возвести ограничение в квадрат. Получим задачу эквивалентную данной (хотя уже где-то и другую). В этом случае минимум функции Лагранжа найдётся легко, посколько она будет дифференцируемая. Но, возможно, это не совсем то, что Вам нужно. Если работать с задачей в исходной постановке, то функция Лагранжа будет не дифференцируемая в обычном смысле. Чтобы найти её минимум, надо найти ёё субдифференциал. Условие минимума - нуль принадлежит субдифференциалу Субдифференциал от нормы в нуле - это единичный шар, а не в нуле норма дифференцируема в обычном смысле. Надо рассмотреть отдельно случаи когда минимум достигается в нуле и когда не достигается вообще ( в зависимости от нормы вектора c). В итоге получим ответ, отличный от ответа при первом подходе. Т.е. две эквивалетные постановки одной задачи имеют разные двойственные. Популярно вопрос рассмотрен у Сухарева-Тимохова-Фёдорова в главе 4.

Благодарю за развернутый ответ со ссылками на литературу.

Вы не могли бы прокомментировать следующий способ? Имеет ли он право на жизнь?

Если записать функцию Лагранжа как
L(x,u)=(c,x)-(u,||x||-1)
а затем найти частную производную
dL/dx=c+u x/||x||
то возможно ли перегруппировкой слагаемых (как обычно делается в задачах линейного программирования, например как показано http://www.ccas.ru/mmes/educat/lab01/7/dwoystv.html ) добиться требуемой цели?

[мат-ламер]

Извините, насчёт группировки я не понял. У Вас цель - найти минимум функции Лагранжа. В нашем случае она не дифференцируема в нуле. То что Вы на нашли производную (+ замените на -) помогает только отчасти. Можно показать с её помощью, что при значении u равном норме вектора с (извините, что словами - TEX только начал осваивать) мимимум функции Лагранжа будет достигаться на луче, выходящем из нуля. Если u меньше этой границы, то функция Лагранжа неограничена снизу и значение двойственной функции равно минус бесконечности. Если u больше этой границы, то минимум функции Лагранжа достигается в нуле, что можно установить, выписав субдифференциал этой функции в нуле, или рассматривая значение функции Лагранжа на произвольном луче, выходящем из нуля. Отсюда следует, что если u больше нормы вектора c, то значение двойственной функции равно -u. По поводу этого примера смотрите также Поляк Б.Т. Введение в оптимизацию.стр. 238, упр. 11.