Fritz John conditions explained
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:
\begin{align}
minimize&f(x)\\
subjectto:&gi(x)\le0, i\in\left\{1,...,m\right\}\\
&hj(x)=0, j\in\left\{m+1,...,n\right\}
\end{align}
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:
\begin{cases}
λ0\nablaf(x*)+\sum\limitsi\in
} \lambda_i \nabla g_i(x^*) + \sum\limits_ \lambda_i \nabla h_i (x^*) =0\\[10pt] \lambda_i \ge 0,\ i\in \mathcal\cup\ \\[10pt] \exists i\in \left(\ \backslash \mathcal \right) \left(\lambda_i \ne 0 \right)\end
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.
Further reading
- Book: Rau, Nicholas . Lagrange Multipliers . Matrices and Mathematical Programming . London . Macmillan . 1981 . 0-333-27768-6 . 156–174 .
Notes and References
- Book: Takayama, Akira . Akira Takayama
. Akira Takayama . Mathematical Economics . registration . New York . Cambridge University Press . 1985 . 90–112 . 0-521-31498-4 .
