Kuhn-Tucker Conditions :: SAS/IML(R) 12.3 User's Guide

Kuhn-Tucker Conditions

The nonlinear programming (NLP) problem with one objective function and constraint functions , which are continuously differentiable, is defined as follows:

$\displaystyle \mbox{minimize} f(x),$	$\displaystyle$	$\displaystyle x \in \mathcal{R}^ n, \; \mbox{subject to}$
$\displaystyle c_ i(x) = 0 ,$	$\displaystyle$	$\displaystyle i = 1,\ldots ,m_ e$
$\displaystyle c_ i(x) \ge 0 ,$	$\displaystyle$	$\displaystyle i = m_ e+1,\ldots ,m$

In the preceding notation, is the dimension of the function , and is the number of equality constraints. The linear combination of objective and constraint functions

$L(x,\lambda ) = f(x) - \sum _{i=1}^ m \lambda _ i c_ i(x)$

is the Lagrange function, and the coefficients $\lambda _ i$ are the Lagrange multipliers.

If the functions and are twice differentiable, the point is an isolated local minimizer of the NLP problem, if there exists a vector $\lambda ^*=(\lambda _1^*, \ldots ,\lambda _ m^*)$ that meets the following conditions:

Kuhn-Tucker conditions

$\begin{array}{ll} c_ i(x^*) = 0 , & i = 1, \ldots ,m_ e \\ c_ i(x^*) \ge 0 , ~ ~ \lambda _ i^* \ge 0, ~ ~ \lambda _ i^* c_ i(x^*) = 0 , & i = m_ e+1, \ldots ,m \\ \nabla _ x L(x^*,\lambda ^*) = 0 \end{array}$
second-order condition

Each nonzero vector $y \in \mathcal{R}^ n$ with

$y^ T \nabla _ x c_ i(x^*) = 0 i = 1,\ldots ,m_ e ,\; \mbox{ and } \forall i\in {m_ e+1,\ldots ,m}; \lambda _ i^* > 0$

satisfies

$y^ T \nabla _ x^2 L(x^*,\lambda ^*) y > 0$

In practice, you cannot expect the constraint functions to vanish within machine precision, and determining the set of active constraints at the solution might not be simple.