# 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 {for}} i = 1, \ ldots, m}$
${\ displaystyle h_ {j} (x ^ {*}) = 0, {\ mbox {for}} j = 1, \ ldots, l \, \!}$
${\ displaystyle \ mu _ {i} ^ {*} \ geq 0, {\ mbox {for}} i = 1, \ ldots, m}$
${\ displaystyle \ mu _ {i} ^ {*} g_ {i} (x ^ {*}) = 0, {\ mbox {for}} \; 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.