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.^[1] 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:

${\displaystyle {\begin{aligned}{\text{minimize }}&f(x)\,\\{\text{subject to: }}&g_{i}(x)\leq 0,\ i\in \left\{1,\dots ,m\right\}\\&h_{j}(x)=0,\ j\in \left\{m+1,\dots ,n\right\}\end{aligned}}}$

where ƒ is the function to be minimized, ${\displaystyle g_{i}}$ the inequality constraints and ${\displaystyle h_{j}}$ the equality constraints, and where, respectively, ${\displaystyle {\mathcal {I}}}$, ${\displaystyle {\mathcal {A}}}$ and ${\displaystyle {\mathcal {E}}}$ are the indices sets of inactive, active and equality constraints and ${\displaystyle x^{*}}$ is an optimal solution of ${\displaystyle f}$, then there exists a non-zero vector ${\displaystyle \lambda =[\lambda _{0},\lambda _{1},\lambda _{2},\dots ,\lambda _{n}]}$ such that:

${\displaystyle {\begin{cases}\lambda _{0}\nabla f(x^{*})+\sum \limits _{i\in {\mathcal {A}}}\lambda _{i}\nabla g_{i}(x^{*})+\sum \limits _{i\in {\mathcal {E}}}\lambda _{i}\nabla h_{i}(x^{*})=0\\[10pt]\lambda _{i}\geq 0,\ i\in {\mathcal {A}}\cup \{0\}\\[10pt]\exists i\in \left(\{0,1,\ldots ,n\}\backslash {\mathcal {I}}\right)\left(\lambda _{i}\neq 0\right)\end{cases}}}$

${\displaystyle \lambda _{0}>0}$ if the ${\displaystyle \nabla g_{i}(i\in {\mathcal {A}})}$ and ${\displaystyle \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 ${\displaystyle \lambda _{0}>0}$. When ${\displaystyle \lambda _{0}=0}$, the condition is equivalent to the violation of Mangasarian–Fromovitz constraint qualification (MFCQ). In other words, the Fritz John condition is equivalent to the optimality condition KKT or not-MFCQ.^{[citation needed]}

References

Further reading

• Rau, Nicholas (1981). "Lagrange Multipliers". Matrices and Mathematical Programming. London: Macmillan. pp. 156–174. ISBN 0-333-27768-6.

This page was last edited on 5 December 2022, at 22:47