Геометрическая интерпретация Условия Каруша — Куна — Таккера

[_hum_]

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

[ShMaxG]

_hum_ в сообщении #1246421 писал(а):

но почему-то найти аналогичное для задачи с ограничениями в виде неравенств у меня не получается.

Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации: Учеб. пособие. -- 2 изд. -- М.: ФИЗМАТЛИТ, 2005. -- 368 с.

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

[_hum_]

ShMaxG

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

$$\min_x f(x), \, g(x) \leq 0\quad \rightarrow \quad \min_{x,u} f(x), \, g(x) + u^2 = 0$$

и решить ее с помощью метода лагранжа?

[ShMaxG]

_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$.

[_hum_]

ShMaxG
ясно. спасибо.

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

(Оффтоп)

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

[ShMaxG]

_hum_ в сообщении #1246527 писал(а):

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

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

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

[_hum_]

ShMaxG в сообщении #1246580 писал(а):

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

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

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