Misplaced Pages

Fritz John conditions

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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:

minimize  f ( x ) subject to:  g i ( x ) ≤ 0 ,   i ∈ { 1 , … , m } h j ( x ) = 0 ,   j ∈ { m + 1 , … , n } {\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, g i {\displaystyle g_{i}} the inequality constraints and h j {\displaystyle h_{j}} the equality constraints, and where, respectively, I {\displaystyle {\mathcal {I}}} , A {\displaystyle {\mathcal {A}}} and E {\displaystyle {\mathcal {E}}} are the indices sets of inactive, active and equality constraints and x ∗ {\displaystyle x^{*}} is an optimal solution of f {\displaystyle f} , then there exists a non-zero vector λ = [ λ 0 , λ 1 , λ 2 , … , λ n ] {\displaystyle \lambda =} such that:

{ λ 0 ∇ f ( x ∗ ) + ∑ i ∈ A λ i ∇ g i ( x ∗ ) + ∑ i ∈ E λ i ∇ h i ( x ∗ ) = 0 λ i ≥ 0 ,   i ∈ A ∪ { 0 } ∃ i ∈ ( { 0 , 1 , … , n } ∖ I ) ( λ i ≠ 0 ) {\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\\\lambda _{i}\geq 0,\ i\in {\mathcal {A}}\cup \{0\}\\\exists i\in \left(\{0,1,\ldots ,n\}\backslash {\mathcal {I}}\right)\left(\lambda _{i}\neq 0\right)\end{cases}}}

λ 0 > 0 {\displaystyle \lambda _{0}>0} if the ∇ g i ( i ∈ A ) {\displaystyle \nabla g_{i}(i\in {\mathcal {A}})} and ∇ h i ( i ∈ E ) {\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 λ 0 > 0 {\displaystyle \lambda _{0}>0} . When λ 0 = 0 {\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.

References

  1. 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.
Category: