Fritz John Duality in the Presence of Equality and Inequality Constraints ()
1. Introduction
Consider the following mathematical programming problems.
(NP): Minimize 
Subject to
(NEP): Minimize 
Subject to
(1)
(2)
where
, 
and 
are differentiable functions. The best-known necessary optimality conditions for the mathematical programming problem (NP) and (NEP) are Fritz John necessary optimality conditions and Karush-Kuhn-Tucker type optimality conditions. The Fritz John type [1] optimality condition which predates the Karush-Kuhn-Tucker type optimality conditions by a few years are more general in a sense. In order for Karush-Kuhn-Tucker type optimality conditions to hold, a constraint qualification or regularity condition on the constraint is required. On the other hand, no such constraint qualification is needed for Fritz John optimality conditions to hold.
Fritz John [2] established the following optimality conditions for (NP):
Proposition 1. (Fritz John type necessary conditions). If 
is an optimal solution of (NP), then there exist 
and a vector 
such that
Using these optimality conditions, Weir and Mond [3] formulated the for Fritz John type dual 
to (NP) and established usual duality theorems, this eliminating the requirement of a constraint qualification:
: Maximize 
Subject to
.
Originally, Fritz John derived his optimality condition for the case of inequality constraint alone. If equality constraint are present in a mathematical programming problem and they are converted into two inequality constraints, then the Fritz John optimality conditions become useless because every feasible point satisfying them. Later Mangasarian and Fromovitz [4] derived necessary optimality condition for (NEP) without replacing an equality constraint by two inequalities and hence making it possible to handle equalities and inequalities together as many realistic problems contain both equality and inequality constraint. Mangasarian and Fromovitz [4] established the following Fritz John type optimality condition given in the following propositions:
Proposition 2.(Generalized Fritz John necessary optimality Conditions [4]):
If 
is an optimal solution of (NEP), then there exist
, 
and 
such that
(3)
(4)
(5)
(6)
2. Sufficiency of Fritz John Optimality Conditions
Before proceeding to the main results of our analysis we give the following definitions which are required for their validation.
1) The function
is strictly pseudoconvex on 
for all 
Equivalently
2) For 
and 
is said to be semi-strictly pseudoconvex if 
is strictly pseudoconvex for all 
Theorem 1. (Sufficient Optimality Conditions):
Assume that
1) 
is pseudoconvex2) 
is semi strictly pseudoconvex and 3) 
is quasiconvexIf there exist
, 
, 
and 
such that (3)-(8) are satisfied, then 
is an optimal solution of (NEP).
Proof: Suppose 
is not optimal, i.e., and then there exists 
Such that
Since 
is pseudoconvex, this implies
and
(7)
with strict-inequality in the above if 
Since 
is feasible for (NEP) we have
Because of semi strict pseudoconvexity of
, This implies
(8)
With strict inequality with
,
.
Also 
Because of quasi-convexity of 
at
,
(9)
Combining (7), (8) and (9), we have
Contradicting (3). Hence 
is an optimal solution of (NEP).
3. Fritz John Type Duality
We propose the following dual (FrED) to (NEP), using Fritz John optimality conditions stated in the preceding section instead of Karush-Kuhn-Tucker conditions [5,6] and established duality results, thus the requirement of a constraint qualification [4] is eliminated:
Dual Problem:
(FrED): Maximize 
Subject to
(10)
(11)
(12)
(13)
(14)
Theorem 2. (Weak Duality):Assume that
: x is feasible for (NEP) and 
is feasible for
.
: For all feasible
, 
is pseudoconvex, 
is semi-strictly pseudoconvex and 
is quasiconvex.
Then
Proof: Suppose 
this, because of pseudoconvexity of 
yields
, Multiplying this, by 
We have
(15)
With strict inequality in (15) if 
From the Constraints of 
and
, we have
which by semi-strictly pseudoconvexity of 
implies
(16)
with strict inequality in (16) if 
As earlier 
This along with quasiconvexity of 
implies
(17)
Combining (15), (16), (17), we have
Contradicting
Hence 
This implies
.
Theorem 3. (Strong Duality):
If 
is an optimal solution of 
then there exist
, 
and 
such that 
is feasible for 
and the corresponding values of 
and 
are equal. If, also f is pseudoconvex, 
is semi-strictly pseudoconvex and 
is quasi-convex, then 
is an optimal solution of
.
Proof: Since 
is an optimal solution of
, by Proposition 2. There exist
, 
and 
such that
This implies 
is feasible for
. Equality of objective function of 
and 
is abovious optimality follows, in view of the hypothesis of the theorem1.
Theorem 4. (Strict Converse Duality): Assume that
1) 
is strictly pseudoconvex, 
is semistrictly pseudoconvex and as 
is quasiconvex and 2) The problem 
has an optimal solution
.
If 
is an optimal solution of
, Then 
i.e. 
is an optimal solution of
.
Proof: We assume that 
and exhibit a contradiction, it follows from Proposition 2 that there exist
, 
and 
such that 
is optimal solution of
, since 
is also an optimal solution for
, It follows that
by strict pseudoconvexity of 
we have
(18)
Also from the constraints of 
and 
we have
.
By the semi strictly convexity of
, this implies
(19)
with strict inequality in the above, if 
Also 
which by quasi-convexity of 
at
, implies
(20)
Combining (18), (19), and (20), we have
which contradicts
Hence 
is an optimal solution.
Theorem 5. (Converse Duality): If 
is an optimal solution of
. Assume that
: 
is pseudoconvex, 
is semi strictlypseudoconvex and 
is quasiconvex.
: Hessian matrix 
is positive or negative definite, and
: the set 
is linearly independent, and Then 
is an optimal solution of
.
Proof: By Preposition 2, there exist
, 
, 
, 
and 
such that
(21)
(22)
(23)
(24)
(25)
(26)
(27)
(28)
(29)
(30)
Multiplying (23) by y ≥ 0 and using (25) and (28), we obtain
(31)
Multiplying (24) by 
and 
we have
(32)
Multiplying equality constraint of 
by 
and using (31) and (32) We have 
Multiplying (21) by 
and using (31) and (32), we have
Multiplying the above equation by r and using (33), we have
This because of hypothesis (A2) implies rθ = 0. In view of (A3) the equality constraint of 
implies r ≠ 0, i.e., r > 0.consequently θ = 0.
Multiplying (21) by r and using θ = 0, we have
Using the equality constraint (10) in the above, we have
This reduces to
By the linear independence hypothesis (A3). this implies
and 
Now if τ = 0, then from above, we have ϕ = 0, ψ = 0 and from (22) and (23), We have ξ = 0, η = 0, consequently we have 
contradicting to (30).
Hence t > 0, ϕ > 0, and ψ > 0.
Using 
in (23) and (24), we have
, 
This implies 
and 
Thus 
is feasible for 
and the objective functions of 
and 
are equal in their formulations. Under, the state generalized Convexity, Theorem 1 implies that, 
is an optimal solution of
.
4. Generalized Fritz John Duality
Let 
and 
with 
and
. and
with
, 
and
. Let 
and 
The following is the generalized Fritz John type dual to
.
Maximize 
Subject to
Theorem 6: If 
is pseudoconvex, 
is semi-strictly pseudoconvex, 
and 
is quasiconvexThen 
Proof: Let 
be feasible for 
and 
feasible for
. Suppose 
This by pseudoconvexity of 
yields
(34)
with strict inequality in (34) if 
From the constraint of 
and
, we have
(35)
Which because of semistrictly pseudoconvexity of 
implies
(36)
with strict inequality in (36) if some 
Also
And
Which by quasiconvex of 
and
respectively imply
and
combining (34), (35), (36) and above equation we have
contradicting the equality constraint of
. Hence 
Implying 
Theorem 7. (Strong Duality):
If 
is an optimal solution of 
and there exist
, 
and 
such that 
is feasible for 
and the corresponding value of 
and 
are equal. If, the hypotheses of Theorem 1 hold, then 
is an optimal solution of
.
Proof: By Proposition 2, there exist
, 
and 
such that
Since
, 
and 
feasibility of 
for 
is obvious. Optimality follows, give the pseudoconvexity of 
and semi-strict pseudoconvexity of 
quasiconvexity of 
and quasiconvexity of 
from Theorem 1.
Theorem 8: (Mangasarian [4] Type Strict Converse Duality): Assume that
is strictly pseudoconvex,
is semi-strictly pseudoconvex and
and 
are quasiconvex.
is an optimal solution of
.
If 
is an optimal solution of 
then 
i.e. 
is an optimal solution of
.
Proof: Assume that 
and exhibit a contradiction. Since 
is an optimal solution of
, by Proposition 2, it implies that there exist
, 
and 
such that 
is an optimal solution of
.
Since 
is an optimal solution for
, it follows that 
This, in view of strict pseudoconvexity of 
implies
(37)
From the constraint of 
and
, we have
(38)
and
(39)
The inequality (38), in view of semi-strict pseudo convexity of 
implies
(40)
with strict inequality in (40) if
.
By quasiconvexity of 
(38) implies
(41)
The inequality (39), because of quasiconvexity of 
yields,
(42)
Combining (37), (40), (41) and (42), we have
which contradicts the feasibility of 
for 
. Hence 
Theorem 9 (Converse Duality): Let
be an optimal solution of
.
be pseudoconvex, 
semistrictly pseudoconvex, 
quasiconvex.
The Hessian matrix
is positive or negative definite, and
The set
is linearly independent. Then 
is feasible for
.
Proof: By Proposition 2, there exist 
, 
and 
such that
(43)
(44)
(45)
(46)
(47)
(48)
(49)
(50)
(51)
(52)
Multiplying (45) and (46) by 
and 
respectively and using (47) and (48), we have
(53)
(54)
Multiplying (44) by r, we have
(55)
Multiplying (43) by 
and using (53), (54) and (53), we have
By positive or negative definite and by hypothesis
, we have 
In view of
, equality constraint of 
implies that 
Hence 
using 
we have
which in view of the hypothesis 
gives 
,
. From (44) and (45), we have 
and 
consequently we have
Contradicting Fritz John Condition (51). Hence 
since 
The Equations (45) and (46), implies 
Thus 
is feasible for 
and optimality follows as earlier.
5. Conclusion
In this exposition, we have formulated a dual and generalized dual by Fritz John optimality conditions instead of the Karush-Kuhn-Tucker optimality conditions. Consequently no constraint qualification is required and hence such formulations enjoy computational advantage over those formulated by using Karush-Kuhn-Tucker. The problems of these results can be revisited in multiobjective and dynamic setting.