2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Геометрическая интерпретация Условия Каруша — Куна — Таккера
Сообщение09.09.2017, 14:42 


23/12/07
1763
для задачи оптимизации с ограничениями в виде системы равенств есть классная наглядная интерпретация для необходимого условия точки экстремума (как сонаправленность градиентов целевой функции и функций ораничений). но почему-то найти аналогичное для задачи с ограничениями в виде неравенств у меня не получается.
в частности, без этого непонятно
1) почему в первой задаче множители лагранжа могут быть любого знака, а во второй - специального
2) почему вид функции лагранжа такой же, а не наподобие того, что должен был выйти, когда ограничения в виде неравенств заменяют за счет введения фиктивных переменных на уловия в виде равенств. то есть, почему функция лагранжа не имеет вид, наподобие: $L(x, \Tilde{x}, \lambda, \mu) = f(x) + \lambda g(x) + \mu (g(x) + \Tilde{x})$, где $\Tilde{x}$ - фиктивная переменная?

 Профиль  
                  
 
 Re: Геометрическая интерпретация Условия Каруша — Куна — Таккера
Сообщение09.09.2017, 16:55 
Заслуженный участник
Аватара пользователя


11/04/08
2752
Физтех
_hum_ в сообщении #1246421 писал(а):
но почему-то найти аналогичное для задачи с ограничениями в виде неравенств у меня не получается.
Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации: Учеб. пособие. -- 2 изд. -- М.: ФИЗМАТЛИТ, 2005. -- 368 с.

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

 Профиль  
                  
 
 Re: Геометрическая интерпретация Условия Каруша — Куна — Таккера
Сообщение09.09.2017, 20:41 


23/12/07
1763
ShMaxG

спасибо, только в электронном доступе в нете ее не нашел. впрочем, я как бы уже нашел в англоязычной литературе нужный ответ.
но еще остался такой вопрос: почему нельзя свести задачу оптимизации с ограничения в виде неравенств к задаче в виде равенств, наподобие:
$$\min_x f(x), \, g(x) \leq 0\quad \rightarrow \quad \min_{x,u} f(x), \, g(x) + u^2 = 0$$
и решить ее с помощью метода лагранжа?

 Профиль  
                  
 
 Re: Геометрическая интерпретация Условия Каруша — Куна — Таккера
Сообщение09.09.2017, 21:31 
Заслуженный участник
Аватара пользователя


11/04/08
2752
Физтех
_hum_ в сообщении #1246504 писал(а):
почему нельзя свести задачу оптимизации с ограничения в виде неравенств к задаче в виде равенств
Почему же нельзя? Можно, так и делают. Я вот, кстати, не помню всех этих условий Каруша--Куна--Таккера и когда имею оптимизационную задачу с неравенствами, превращаю их в равенства и решаю полученную задачу уже привычным методом. Получается, я перевывожу известные вещи, ну и ладно, они благо не сложные.

Вам возможно кажется не совсем понятным появление условия неотрицательности множителей Лагранжа для условий-неравенств. В этом нет ничего сложного. Смотрите. Рассмотрим оптимизационную задачу $$f(x)\to\min, \ g(x) \le 0$$ Введем фиктивные переменные $u$ и рассмотрим равносильную задачу $$f(x)\to\min, \ g(x)+u^2=0$$ Для простоты будем считать, что тут все скалярно и функции хорошие. Введем функцию Лагранжа $$L(x,u,\lambda)=f(x)+\lambda(g(x)+u^2)$$ Тогда оптимальное решение этой задачи условной оптимизации удовлетворяет следующим необходимым условиям оптимальности первого порядка (это известный факт, принцип Лагранжа, мы им можем пользоваться): $$\frac{\partial L}{\partial x}=\frac{\partial f}{\partial x}+\lambda\frac{\partial g}{\partial x}=0, \ \frac{\partial L}{\partial u}=\lambda u=0, \ \frac{\partial L}{\partial \lambda} = g(x)+u^2=0$$
Теперь покажем, что $\lambda < 0$ не может быть решением этой задачи. Действительно, если $\lambda < 0$, то необходимо $u=0$, значит $g(x)=0$. Получается, что оптимальное решение тогда обязано лежать на границе множества $g(x)\le 0$. Но конкретно в данном случае эта точка не может быть оптимальной, потому что давайте рассмотрим точку $x(\alpha)=x+\alpha s$, где $s=-\partial f / \partial x$, $\alpha \ge 0$. Из необходимых условий оптимальности мы видим, что $-\partial f/\partial x = \lambda \partial g/\partial x$ -- эта штука направлена внутрь множества $g(x)\le 0$. Значит, при достаточно малом $\alpha$ мы найдем точку $x(\alpha)$ получше, чем $x$ для которой $\lambda < 0$. Значит, эта точка не может быть оптимальной, ибо мы знаем, что принцип Лагранжа устанавливает равносильность оптимальных точек исходной задачи условной оптимизации и безусловной оптимизации. Значит, как минимум $\lambda \ge 0$. Ну а там уже более конкретно и не скажешь, можно привести примеры, когда в оптимальной точке $\lambda = 0$, и когда $\lambda > 0$.

 Профиль  
                  
 
 Re: Геометрическая интерпретация Условия Каруша — Куна — Таккера
Сообщение09.09.2017, 21:51 


23/12/07
1763
ShMaxG
ясно. спасибо.

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

(Оффтоп)

Изображение
Изображение


и если да, насколько такой подход лучше/хуже других? (или они по сложности равносильны?)

 Профиль  
                  
 
 Re: Геометрическая интерпретация Условия Каруша — Куна — Таккера
Сообщение10.09.2017, 00:39 
Заслуженный участник
Аватара пользователя


11/04/08
2752
Физтех
_hum_ в сообщении #1246527 писал(а):
можно просто перебрать все возможные варианты с выбрасыванием неактивных ограничений, и для каждого варианта решить уже задачу лагранжа или вообще задачу без ограничений?
Я не специалист в этом вопросе, но кое что могу сказать. Перебирать что-то придется в любом случае. Причина этого -- в наличии условий нежесткости, приходится учитывать кучу вариантов, когда одни переменные равны нулю, а другие нет. И это повезет, если ограничения-неравенства имеют какой-нибудь удобоваримый вид.

Мне приходится сталкиваться с такими вещами, которые даже и формулой явной толком не выразить. Целевая функция и ограничения как черные ящики. Мои задачи (из астродинамики) хорошо решаются методом последовательного квадратичного программирования. Здесь на каждой итерации целевая функция аппроксимируется квадратичной функцией, а ограничения-равенства и неравенства -- линейными функциями. Далее решается задача квадратичного программирования. Так вот здесь равенства и неравенства имеют тот самый удобоваримый вид и что-то определенное про активные ограничения уже можно сказать. Разумеется, эффективные методы решения задач квадратичного программирования были реализованы (они тоже могут быть итерационными в свою очередь). Решение такой квадратичной подзадачи может вывести за исходные нелинейные ограничения, поэтому полученное решение надо насильно в ограничения вернуть. Затем ставится новая квадратичная подзадача, она решается, потом решение корректируется. И так далее.

 Профиль  
                  
 
 Re: Геометрическая интерпретация Условия Каруша — Куна — Таккера
Сообщение10.09.2017, 13:17 


23/12/07
1763
ShMaxG в сообщении #1246580 писал(а):
Перебирать что-то придется в любом случае. Причина этого -- в наличии условий нежесткости, приходится учитывать кучу вариантов, когда одни переменные равны нулю, а другие нет. И это повезет, если ограничения-неравенства имеют какой-нибудь удобоваримый вид.

меня больше интересует - насколько число переборов зависит от подхода :) то есть, имеет ли смысл выписывать все в виде условия кунна-такерра и потом решать эту систему, или это то же самое, что изначально просто все возможные варианты поразбирать, и для каждого составить и решить задачу условной оптимизации с ограничениями в виде равенств?

(а еще интересно, как на практике такие задачи решают, когда ограничений больше десятка. ведь количество вариантов пропорционально 2^(число ограничений в виде неравенств), - используют пакеты символьных вычислений?)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Alex Krylov, B@R5uk


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group