# 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.