Nonlinear Optimization Examples

Kuhn-Tucker Conditions

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

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

In the preceding notation, n is the dimension of the function $f(x)$, and $m_ e$ 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 f and $c_ i$ are twice differentiable, the point $x^*$ 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 $c_ i(x^*)$ to vanish within machine precision, and determining the set of active constraints at the solution $x^*$ might not be simple.