kReese.net

The Karush-Kuhn-Tucker (KKT) conditions, sometimes referred to as the Kuhn-Tucker conditions, are the conditions that a Nonlinear Programming problem need to meet in order to be optimal. The KKT conditions extends the method of Lagrangian multipliers by allowing for inequality constraints, as opposed to the Lagrange Multipliers which only allow equality constraints.

Let us consider a nonlinear optimization problem:

Minimize $f(x)$
subject to: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

We will let $x^{*}$ represent a relative minimum point for our problem, which also satisfies some constraint qualification. With this, then we can assume that for every element there exists a vector $\lambda_j \left ( j = 1, \ldots, l \right )$ , where l represents the number of equality constraints, and $\mu_i\left ( i = 1, \ldots, m \right )$ , where m represents the number of inequality constraints. These constants, $\lambda_j$ and $\mu_i$ , are called KKT multipliers.

In order for the KKT conditions to be held in a nonlinear programming problem (NLP), then each of three conditions must be met [1-4]. The Primal Feasibility restates what the problem states, that the inequality and equality constraints on $x^*$ must be met in order for the problem to be optimal:

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

The second condition is known as the dual feasibility condition. In this condition states, rather verbosely, that every element in $\mu_i$ must be greater than zero, and that the stationarity of the problem must be equal to 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)}$

The stationarity of the problem is:

$\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$

While the other two are simply conditions that λ and μ must meet in order for $x^*$ to be optimal.

The third condition that must be met is known as complementary slackness. This condition simply states that for each mu and its respective inequality constraint, the product of the two should result in zero:

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

When these three conditions are met, we have met the KKT conditions and our solution, $x^*$ , is an optimal solution for the NLP problem. There maybe more than one x in the space which meet the conditions. Any point in the problem space where every element of λ and μ, such that the tuple (x, λ, μ) satisfy the KKT conditions are called KKT points. Derivation of these constraints can be found in [1,2]

Constraint Qualifications

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^*)$ and $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^*) =$ and $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, pp. 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, E. and Ribeiro, A. 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. pp 95-110.

A Computer Science and Teaching Journal

Recent Posts

Karush-Kuhn-Tucker Conditions

Constraint Qualifications