Fritz John conditions

The Fritz John conditions (abbr. FJ conditions), in mathematics, are a necessary condition for a solution in nonlinear programming to be optimal. They are used as lemma in the proof of the Karush–Kuhn–Tucker conditions, but they are relevant on their own.

We consider the following optimization problem:

$\begin{align} \text{minimize } & f(x) \, \\ \text{subject to: } & g_i(x) \ge 0,\ i \in \left \{1,\dots,m \right \}\\ & h_j(x) = 0, \ j \in \left \{m+1,\dots,n \right \} \end{align}$

where ƒ is the function to be minimized, $g_i$ the inequality constraints and $h_j$ the equality constraints, and where, respectively, $\mathcal{I}$, $\mathcal{I'}$ and $\mathcal{E}$ are the indices set of inactive, active and equality constraints and $x^*$ is an optimal solution of $f$, then there exists a non-zero vector $\lambda=[\lambda_0, \lambda _1, \lambda _2,\dots,\lambda _n]$ such that:

$\begin{cases} \lambda_0 \nabla f(x^*) = \sum\limits_{i\in \mathcal{I}'} \lambda_i \nabla g_i(x^*) + \sum\limits_{i\in \mathcal{E}} \lambda_i \nabla h_i (x^*) \\[10pt] \lambda_i \ge 0,\ i\in \mathcal{I}'\cup\{0\} \\[10pt] \exists i\in \left( \{0,1,\ldots ,n\} \backslash \mathcal{I} \right) \left( \lambda_i \ne 0 \right) \end{cases}$

$\lambda_0>0$ if the $\nabla g_i (i\in\mathcal{I}')$ and $\nabla h_i (i\in\mathcal{E})$ are linearly independent or, more generally, when a constraint qualification holds.

Named after Fritz John, these conditions are equivalent to the Karush–Kuhn–Tucker conditions in the case $\lambda_0 > 0$.

References

• WANG Yiju, XIU Naihua. 非线性规划的理论和方法 (The theory and methods of the Non-linear programming) (in Chinese). p. 4. ISBN 978-7-5369-3825-0.