Fritz John Conditions

The Fritz-John conditions (abbreviated to FJ conditions ) are a necessary first-order optimality criterion in mathematics in non-linear optimization . They are a generalization of the Karush-Kuhn-Tucker conditions and, in contrast to these, do not have any regularity conditions. They are named after the American mathematician of German descent, Fritz John .

Framework

The Fritz-John-Conditions allow statements about an optimization problem of the form

${\displaystyle \min _{x\in D}f(x)}$

under the constraints

${\displaystyle g_{i}(x)\leq 0~,1\leq i\leq m}$

${\displaystyle h_{j}(x)=0~,1\leq j\leq l}$.

All functions considered are continuously differentiable and is a non-empty subset of the . ${\displaystyle f(x),g_{i}(x),h_{j}(x)\colon D\to \mathbb {R} }$ ${\displaystyle D}$ ${\displaystyle \mathbb {R} ^{n}}$

statement

A point is called the Fritz-John point or FJ point for short in the above optimization problem if it meets the following conditions: ${\displaystyle (z^{*},x^{*},\mu ^{*},\lambda ^{*})\in \mathbb {R} ^{1+n+m+l}}$

${\displaystyle z^{*}\nabla f(x^{*})+\sum _{i=1}^{m}\mu _{i}^{*}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\lambda _{j}^{*}\nabla h_{j}(x^{*})=0}$

${\displaystyle g_{i}(x^{*})\leq 0,{\mbox{ für }}i=1,\ldots ,m}$

${\displaystyle h_{j}(x^{*})=0,{\mbox{ für }}j=1,\ldots ,l\,\!}$

${\displaystyle \mu _{i}^{*}\geq 0,{\mbox{ für }}i=1,\ldots ,m}$

${\displaystyle \mu _{i}^{*}g_{i}(x^{*})=0,{\mbox{für }}\;i=1,\ldots ,m.}$

${\displaystyle z^{*}\geq 0}$

These conditions are called the Fritz-John-Conditions or FJ-Conditions for short .

If the point is the local minimum of the optimization problem, then there is such that is an FJ point and is not equal to the zero vector. ${\displaystyle x^{*}}$ ${\displaystyle \mu ^{*},\lambda ^{*},z^{*}}$ ${\displaystyle (z^{*},x^{*},\mu ^{*},\lambda ^{*})}$ ${\displaystyle (z^{*},\mu ^{*},\lambda ^{*})}$

Thus the FJ conditions are a necessary first order optimality criterion .

Relationship to the Karush-Kuhn-Tucker Terms

For the FJ conditions correspond exactly to the Karush-Kuhn-Tucker conditions . Is a FJ-point, so also with a FJ-point. It can therefore be assumed that if is, a KKT point is already present; this is also generated by rescaling . Then the KKT point belonging to an FJ point is. Conversely, the constraint qualifications of the KKT conditions can now be interpreted in such a way that they guarantee the FJ conditions . ${\displaystyle z^{*}=1}$ ${\displaystyle (z^{*},x^{*},\mu ^{*},\lambda ^{*})}$ ${\displaystyle (sz^{*},x^{*},s\mu ^{*},s\lambda ^{*})}$ ${\displaystyle s>0}$ ${\displaystyle z^{*}>0}$ ${\displaystyle z^{*}}$ ${\displaystyle (x^{*},\mu ^{*}/z^{*},\lambda ^{*}/z^{*})}$ ${\displaystyle z^{*}>0}$

Examples

FJ without KKT

As an example, consider the optimization problem

${\displaystyle \min _{x\in X}-x_{1}}$

with restriction amount

${\displaystyle X=\{x\in \mathbb {R} ^{2}\,|\,g_{1}(x)=-x_{2}\leq 0,\,g_{2}(x)=x_{2}+x_{1}^{5}\leq 0\}}$.

The minimum of the problem is the point . Hence there is an FJ point such that ${\displaystyle x^{*}=(0,0)}$ ${\displaystyle (z^{*},0,0,\mu _{1}^{*},\mu _{2}^{*})}$

${\displaystyle z^{*}(-1,0)^{T}+\mu _{1}^{*}(0,-1)^{T}+\mu _{2}^{*}(0,1)^{T}=(0,0)^{T}}$.

It follows directly that for an FJ point. ${\displaystyle z^{*}=0,\,\mu _{1}^{*}=\mu _{2}^{*}>0}$

In particular, there is no associated KKT point. If one sets , the system of equations for the gradients cannot be solved. In fact, no regularity condition is fulfilled in the point , especially not the most general one, the Abadie CQ . ${\displaystyle z^{*}=1}$ ${\displaystyle x^{*}}$

FJ and KKT

As an example, consider the optimization problem

${\displaystyle \min _{x\in X}-x_{2}+x_{1}^{2}}$

with restriction amount

${\displaystyle X=\{x\in \mathbb {R} ^{2}\,|\,g_{1}(x)=x_{1}+x_{2}-1\leq 0,\,g_{2}(x)=x_{1}^{2}+x_{2}^{2}-1\leq 0\}}$.

The restriction set is the unit circle with the curvature of the circle removed from the first quadrant. The minimum of the problem is the point . Hence there is an FJ point so that ${\displaystyle x^{*}=(0,1)}$ ${\displaystyle (z^{*},0,1,\mu _{1}^{*},\mu _{2}^{*})}$

${\displaystyle z^{*}(0,-1)^{T}+\mu _{1}^{*}(1,1)^{T}+\mu _{2}^{*}(0,2)^{T}=(0,0)^{T}}$

applies. One solution would be what leads to the FJ point . Rescaling with leads to the KKT point . In fact, the LICQ is also fulfilled in this point , which is why the KKT conditions also apply here. ${\displaystyle z^{*}=2,\,\mu _{1}^{*}=0,\,\mu _{2}^{*}=1}$ ${\displaystyle (2,0,1,0,1)}$ ${\displaystyle z^{*}}$ ${\displaystyle (x^{*},\mu _{1}^{*}/z^{*},\mu _{2}^{*}/z^{*})=(0,1,0,1/2)}$ ${\displaystyle x^{*}}$

Related concepts

For convex optimization problems, in which the functions are not continuously differentiable, there are the saddle point criteria of the Lagrange function . If all the functions involved are continuously differentiable, then they are structurally similar to the Fritz-John conditions and equivalent to the KKT conditions.

literature

• Florian Jarre, Josef Stoer: Optimization. Springer, Berlin 2004, ISBN 3-540-43575-1 .
• C. Geiger, C. Kanzow: Theory and numerics of restricted optimization tasks . Springer, 2002, ISBN 3-540-42790-2 , books.google.de

Web links

• Stephen Boyd, Lieven Vandenberghe: Convex Optimization . (PDF; English)

Individual evidence

1. ↑ F. John: Extremum problems with inequalities as subsidiary conditions . In: Kurt Friedrichs, Otto Neugebauer, JJ Stoker (Ed.): Studies and Essays . Courant Anniversary Volume, Wiley, 1948, pp. 187-204, reprinted in: Fritz John: Collected Papers . Birkhäuser 1985, pp. 543-560