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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f11a326f63b1d80ae5dd2239a83397523210f657)
where ƒ is the function to be minimized,
the inequality constraints and
the equality constraints, and where, respectively,
,
and
are the indices sets of inactive, active and equality constraints and
is an optimal solution of
, then there exists a non-zero vector
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b50d43581b08b65ec6bdbc60618b51b75a1b5bba)
if the
and
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
. When
, 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
- ^ Takayama, Akira (1985). Mathematical Economics. New York: Cambridge University Press. pp. 90–112. ISBN 0-521-31498-4.
Further reading
- Rau, Nicholas (1981). "Lagrange Multipliers". Matrices and Mathematical Programming. London: Macmillan. pp. 156–174. ISBN 0-333-27768-6.