EncycloReader

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:

[math]\displaystyle{ \begin{align} \text{minimize } & f(x) \, \\ \text{subject to: } & g_i(x) \le 0,\ i \in \left \{1,\dots,m \right \}\\ & h_j(x) = 0, \ j \in \left \{m+1,\dots,n \right \} \end{align} }[/math]

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

[math]\displaystyle{ \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^*) =0\\[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} }[/math]

[math]\displaystyle{ \lambda_0\gt 0 }[/math] if the [math]\displaystyle{ \nabla g_i (i\in\mathcal{I}') }[/math] and [math]\displaystyle{ \nabla h_i (i\in\mathcal{E}) }[/math] 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 [math]\displaystyle{ \lambda_0 \gt 0 }[/math]. When [math]\displaystyle{ \lambda_0=0 }[/math], 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.

References

↑ Takayama, Akira (1985). Mathematical Economics. New York: Cambridge University Press. pp. 90–112. ISBN 0-521-31498-4. https://archive.org/details/mathematicalecon00taka.

References

Further reading