kReese.net

Karush-Kuhn-Tucker (EZ) условия, понякога по-долу условия Kuhn-Tucker, са условията,, че нелинеен проблем за програмиране трябва да отговарят, за да бъде оптимална. KKT условия разширява метода на Лагранж множители, като позволява за неравенство ограничения, за разлика от множители на Лагранж, които позволяват само на половете ограничения.

Нека разгледаме нелинеен проблем за оптимизация:

Минимизиране $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 )$ , където m представлява броя на неравенството ограничения. Тези константи, $\lambda_j$ и $\mu_i$ , наричат KKT множители.

За KKT условия, която ще се проведе в нелинеен проблем за програмиране (НЛП), след това всяка от трите условия, трябва да бъдат изпълнени [1-4]. Primal Отново Предпроектни какъв е проблема-членки, че неравенството и равенство ограничения за $x^*$ трябва да бъдат изпълнени за да може проблемът да бъде оптимално:

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

Второто условие е известно като двойно условие за осъществимост. В това състояние, а verbosely, че всеки елемент в $\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$

Докато другите две са просто условия, че л и m трябва да отговарят, за $x^*$ за оптимално.

Третото условие, което трябва да бъдат изпълнени, е известен като допълват небрежно. Това състояние просто заявява, че за всеки МУ и съответното ограничение неравенство, продукт от двете трябва да доведе до нула:

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

Когато тези три условия са изпълнени, които сме срещали KKT условия и нашето решение, $x^*$ , е оптималното решение за проблема НЛП. Има може би повече от една X в пространството, които отговарят на условията. Всяка точка в проблемното пространство, където всеки елемент отлиm, по такъв начин, че ключа (X, л, m) отговарят на KKT условия са наричат KKT точки. Извеждане на тези ограничения могат да бъдат намерени в [1,2]

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

As mentioned previously, the points that we are testing need to meet some qualification in order for the point to be considered. The most well known constraint Qualification is the Linear Independence constraint Qualification (LICQ), which simply states that $h_{j}(x^*)$ и $g_{i}(x^*)$ are linearly independent from the other at point $x^*$ . The Mangasarian-Fromovitz constraint qualification (MFCQ) states similarly the LICQ with the addition of being positive-lineraly independent at $x^*$ . [5]

There are however other constraint qualifiers that relax the LICQ. The Slater constraint qualifier can be used in convex problems. If there exists a point x such that $h_{j}(x^*) =$ и $g_{i}(x^*) < 0$ for all i,j active in $x^*$ , then the slate condition holds. [5,6]

Other types of constraint qualifiers do exist, but these three seem to be the most commonly used in KKT qualification.

[1] Kuhn, H. and Tucker, A., “Nonlinear Programming” Proceedings of the 2nd Berkeley Symposium 1951, п.п.. 481-492.
[2] Karush, W., “Minima of Functions of Several Variables with Inequalities as Side Constraints”. M.Sc. Dissertation, Univ. of Chicago, Chicago, Il, 1939.
[3] Kuhn, M. “The Karush-Kuhn-Tucker Theorem”, Internet: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM Uni. Mannheim, 2006.
[4]McCarl, B. and Spreen, T., “Nonlinear Optimization Conditions”, Ch. 12, Applied Mathematical Programming Using Algebraic Systems. Internet: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, R. Karas, То. and Ribeiro, А. Constraint Qualification for Nonlinear Programming, Tech Report, Univ. of Parana.
[6] Tiba, D. and Zalinescu, C. “On the Necessity of some Constraint Qualification Conditions in Convex Programming”, Journal of Convex Analysis, 11 (1), 2004. п.п. 95-110.

Компютърни науки и преподаване вестник

Последните публикации

Karush-Kuhn-Tucker Условия

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