Существование рационально --- лагранжева двойственность

Это требует небольшого понимания метода множителей Лагранжа. Вы, наверное, знакомы с этим известным методом. Но все еще есть много новичков, которые забывают конкретный процесс, поэтому я надеюсь, что вы сможете взглянуть на это, чтобы систематически понять этот метод.«Множители Лагранжа».

$\bf \color{red}{前方多公式预警,非战斗人员撤离}$

Бойцам рекомендуется жевать его несколько раз, и лучше всего уметь проталкивать формулу руками.

проблема с исходной функцией

Вернемся к проблеме ограничений в общем случае:

s.t. \quad c_{i}(x)\leq0 \ ,\quad i=1,2,...,k

\quad \qquad h_{j}(x)=0 \ ,\quad j=1,2,...,l

Его лагранжева функция:

L(x,\alpha, \beta) = f(x) + \sum _{i=1}^k \alpha_{i} c_{i}(x)+ \sum_{j=1}^l \beta_{j} h_{j} (x)

Мы заказываем:

\theta_P(x) = \max_{\alpha,\beta: \alpha_i \geq0}L(x,\alpha,\beta)

Зависит от«Множители Лагранжа».Вывод в случае ограничений неравенства, описанных выше, можно увидеть следующим образом:

\theta_P(x) = \begin{cases} f(x), \quad x \text{满足原始问题约束} \\ +\infty, \quad others \\ \end{cases}

Итак, рассмотрим задачу минимизации:

\min_x \theta_P(x) = \min_x \max_{\alpha,\beta: \alpha_i \geq0}L(x,\alpha,\beta)

Это эквивалентно решению исходной задачи. потому что минимизация будет $+\infty$ удалять. Эта последняя задача минимизации называетсяМинимаксная задача обобщенных функций Лагранжа.. Мы определяем:

двойная проблема

Мы переопределяем:

\theta_D(\alpha,\beta) = \min_xL(x, \alpha,\beta)

но:

\max_{\alpha,\beta}\theta_D(\alpha,\beta) = \max_{ \alpha,\beta} \ \min_xL(x,\alpha,\beta)

s.t. \qquad \alpha_i \geq 0, \quad i =1,2,...,k

называется двойственной задачей исходной задачи. Точно так же мы также определяем:

d^* = \max_{\alpha,\beta:\alpha_i \geq0}\theta_D( \alpha,\beta)

значение называется двойственной проблемой.

Связь между исходной проблемой и двойной проблемой

Если и основная задача, и двойственная задача имеют оптимальные значения, то:

d^* = \max_{\alpha,\beta:\alpha_i \geq 0} \min_x L(x, \alpha,\beta) \leq \min_x \max_{\alpha,\beta:\alpha_i\geq0}L(x,\alpha,\beta) = p^*

доказывать:

для любого $\alpha,\beta$ и,имеют

\theta_D(\alpha,\beta)=\min_x L(x, \alpha,\beta)\leq L(x,\alpha,\beta)

\qquad \qquad \leq \max_{ \alpha,\beta:\alpha_i \geq0}L(x,\alpha,\beta)= \theta_P(x)

который

Поскольку и основная задача, и двойственная задача имеют оптимальные значения,

\max_{\alpha,\beta:\alpha_i\geq0}\theta_D(\alpha,\beta)\leq \min_x \theta_P(x)

который:

Отсюда мы можем сделать вывод, что если d^*=p^* , то если $x^*, \alpha^*,\beta^*$ Для допустимого решения исходной задачи и двойственной задачи это оптимальное решение.

При условии ККТ оптимальные решения прямой задачи и двойственной задачи равны, т. е. d^*=p^* . В это время мы решаем двойственную задачу, чтобы получить решение исходной задачи. Если друзья не понимают условия ККТ, вы можете прочитать эту статью«Множители Лагранжа»..

Конечные титры - условие ручного толчка KKT и двойные отношения.

Для нашей задачи оптимизации:

\min_xf(x) \qquad \qquad s.t. \; g_i(x) \leq0 \quad i=1,2,...,l

Существуют следующие функции Лагранжа:

Отметим, что здесь мы делаем $\mu_i \geq0$ , по тем же причинам, что и выше. но $\mu g(x)\leq0$ ,Так:

\max_{\mu}L(x,\mu)=\max_{\mu}f(x)+\max_{\mu} \sum_{i=1}^l \mu_i g_i(x)=\max_{\mu}f(x)

Затем мы получаем:

Давайте остановимся здесь и изменим основную строку: У нас двойная проблема $\max_{\mu} \min_xL(x,\mu)$ Расширять:

\max_{\mu} \min_xL(x,\mu)=\max_{\mu}[\min_xf(x)+\min_x \mu g(x)]

\qquad\qquad \qquad \quad =\min_xf(x)+\max_{\mu}\min_x \mu g(x)

Мы должны обратить внимание здесь $\mu$ и g(x) все векторы, поэтому я удалил индексы,так как f(x) и $\mu$ не имеет значения, поэтому вышеприведенная формула верна. Это также легко узнать:

\min_x \mu g(x)= \begin{cases} 0 \qquad if\ \mu=0 \; or \; g(x)=0 \\ -\infty \quad if \ \mu >0\ and \ g(x)<0\\ \end{cases}

Тогда у нас также есть

Таким образом, в этом случае в сочетании с формулой, которую мы остановили ранее, мы имеем:

\max_{\mu} \min_xL(x,\mu)=\min_x \max_{\mu}L(x,\mu)

Это двойственная задача, равная основной задаче. И на каких условиях это все основано? Резюмируем доступные условия ККТ:

\begin{cases} L(x,\mu)=f(x)+ \sum_{i=1}^l \mu_ig_i(x)\\ \mu_i \geq0\\ g_i(x)\leq0 \end{cases}

При этом условии первичная и двойственная задачи совпадают и те же, что и $\min_xf(x)$ такой же. В начале оптимального решения $\mu=0$ или g(x)=0 , это оптимальное значение также $L(x,\mu)$ точка экстремума. Конечно, все это предлагается на основе выпуклых функций. Если это невыпуклая функция, то условие ККТ можно рассматривать только как необходимое условие, и нет других достаточных и необходимых условий, которые легче использовать.

Отсюда получаем условие ККТ. Из вышеизложенного введены полные условия ККТ.