kReese.net | Компьютерные науки и преподавания Journal

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

Рассмотрим нелинейную задачу оптимизации:

Минимизировать $f(x)$
при условии: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

Мы позволим $x^{*}$ представляют собой относительную точку минимума для нашей задачи, которая также удовлетворяет некоторым ограничением квалификации. С этой, то можно считать, что для каждого элемента существует вектор $\lambda_j \left ( j = 1, \ldots, l \right )$ , где л представляет собой число ограничений типа равенств, и $\mu_i\left ( i = 1, \ldots, m \right )$ , где метр представляет собой число ограничений типа неравенств. Эти константы, $\lambda_j$ и $\mu_i$ , называются мультипликаторами ККТ.

Для того, чтобы условия ККТ, которая состоится в задачи нелинейного программирования (НЛП), то каждое из трех условий должны быть выполнены [1-4]. Технико-экономическое Primal еще раз подтверждается, что проблемы государства, , что неравенство и равенство ограничения на $x^*$ должны быть выполнены для того, чтобы проблема оптимальной:

$\left.\begin{matrix} h\left ( x^* \right )=0\\ g\left ( x^* \right )\leq0 \end{matrix}\right\} \textrm{primal feasibility (PF)}$

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

$\left.\begin{matrix} \bigtriangledown f\left ( x^* \right ) + \sum_{i=1}^{m}\lambda_{i}\bigtriangledown h_{i}\left ( x^* \right ) + \sum_{j=1}^{l}\mu_{j}\bigtriangledown g_{j}\left ( x^* \right ) = 0\\ \lambda_i \in \mathbb{R}\\ \mu_i \geq 0 \end{matrix}\right\}\textrm{dual feasibility (DF)}$

Стационарности проблема:

$\bigtriangledown f\left ( x^* \right ) + \sum_{i=1}^{m}\lambda_{i}\bigtriangledown h_{i}\left ( x^* \right ) + \sum_{j=1}^{l}\mu_{j}\bigtriangledown g_{j}\left ( x^* \right ) = 0$

В то время как два других просто условия, которые л и метр должна удовлетворять для того, чтобы $x^*$ оптимальным.

Третье условие, которое должно быть выполнено известен как взаимодополняющие вялость. Это условие просто заявляет, что для каждого му и его соответствующие ограничения неравенства, произведение двух должно привести к нулю:

$\mu_i g_{i} \left ( x^* \right ) = 0$

Когда эти три условия в, у нас с ККТ условия и наше решение, $x^*$ , является оптимальным решением для проблемы НЛП. Там может быть больше одного х в пространстве, которые отвечают условиям. Любая точка в пространстве проблемы, где каждый элементлиметр, такие, что набор (х, л, метр) удовлетворить ККТ условия называются точками ККТ. Вывод из этих ограничений можно найти в [1,2]

Ограничение Квалификация

Как уже упоминалось ранее, моменты, которые мы проводим тестирование необходимо для удовлетворения некоторых квалификации для того, чтобы момент, который следует считать. Наиболее известные ограничения Квалификация Квалификация Линейные ограничения независимости (LICQ), , который просто утверждает, что $h_{j}(x^*)$ и $g_{i}(x^*)$ линейно независимы от других в точке $x^*$ . Мангасарян-Fromovitz ограничение квалификации (MFCQ) государств аналогичным LICQ с добавлением будучи положительно lineraly независимы в $x^*$ . [5]

Существуют, однако, другие ограничения, которые расслабляют отборочных LICQ. Отборочный Слейтера может быть использован в выпуклых задач. Если существует такая точка х такая, что $h_{j}(x^*) =$ и $g_{i}(x^*) < 0$ для всех я,J активность в $x^*$ , Затем шифер условие. [5,6]

Другие типы ограничений отборочных существуют, но эти три, кажется, наиболее часто используется в ККТ квалификации.

[1] Кун, H. и Такер, А., “Нелинейное программирование” Труды 2-го симпозиума Беркли 1951, п.п.. 481-492.
[2] Каруша, W., “Минимумы функций многих переменных с Неравенства как ограничений”. M. Sc. Диссертация, Univ. Чикагский, Чикаго, Il, 1939.
[3] Кун, М. “Каруша-Куна-Таккера”, Интернет: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM Королевство. Мангейм, 2006.
[4]McCarl, B. и Spreen, Т., “Нелинейные условия оптимизации”, Ч.. 12, Прикладных математических программирование с использованием алгебраических систем. Интернет: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Эустакио, R. Карась, E. Рибейро и, A. Ограничение Квалификация для нелинейного программирования, Tech Report, Univ. Параны.
[6] Прибывать, D. и Zalinescu, C. “О необходимости некоторых ограничений Квалификация Условия в выпуклого программирования”, Журнал Анализ Выпуклые, 11 (1), 2004. п.п. 95-110.

Последние сообщения

Ограничение Квалификация