Fritz John Duality in the Presence of Equality and Inequality Constraints ()
1. Introduction
Consider the following mathematical programming problems.
(NP): Minimize ![](https://www.scirp.org/html/10-7400898\f7ae8268-afc1-4b39-a369-8dc745379323.jpg)
Subject to
![](https://www.scirp.org/html/10-7400898\88338f6f-bdfe-47ce-98d3-0932008c2d32.jpg)
(NEP): Minimize ![](https://www.scirp.org/html/10-7400898\e7d42576-3b6e-4ad5-b7db-f116e2826a29.jpg)
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
![](https://www.scirp.org/html/10-7400898\7ef65ea6-c77b-4c0f-a2aa-026c30b36bc4.jpg)
![](https://www.scirp.org/html/10-7400898\b4c91ae8-c7ab-43dd-824b-154dc434959f.jpg)
![](https://www.scirp.org/html/10-7400898\6ba42d5d-da23-4b15-84bc-eea27c840c26.jpg)
![](https://www.scirp.org/html/10-7400898\dd08d8da-8df2-4f3c-a92c-af7777598a9d.jpg)
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 ![](https://www.scirp.org/html/10-7400898\36bd376f-8dd6-4e61-9cd6-66ad31ca27de.jpg)
Subject to
![](https://www.scirp.org/html/10-7400898\263a9fe8-506d-4a12-b9c8-7e7befde051c.jpg)
![](https://www.scirp.org/html/10-7400898\ca7ac46f-7a16-40d5-9ded-e06fb726f050.jpg)
![](https://www.scirp.org/html/10-7400898\5541a802-1d70-43e0-9696-a4c52f24ba4f.jpg)
.
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 ![](https://www.scirp.org/html/10-7400898\9967a534-d207-4d36-abc4-883bf609c943.jpg)
![](https://www.scirp.org/html/10-7400898\d9856a3b-f2a0-4c86-a6c9-fa00a2dfe82e.jpg)
Equivalently
![](https://www.scirp.org/html/10-7400898\b8c50095-905b-49e5-9b6e-3f00d033f46e.jpg)
2) For
and
is said to be semi-strictly pseudoconvex if
is strictly pseudoconvex for all ![](https://www.scirp.org/html/10-7400898\fc1874d2-d641-41c0-85f2-d8b4f92e468c.jpg)
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
![](https://www.scirp.org/html/10-7400898\30b7837a-3c91-4038-8f54-4d6d180cde53.jpg)
Since
is pseudoconvex, this implies
![](https://www.scirp.org/html/10-7400898\1c99a29d-42e0-4db2-a2ad-f7b6a367a14d.jpg)
and
(7)
with strict-inequality in the above if ![](https://www.scirp.org/html/10-7400898\37c3ca01-584d-4212-ab3d-502af29c7e0a.jpg)
Since
is feasible for (NEP) we have
![](https://www.scirp.org/html/10-7400898\982f96c7-bb34-4d13-9cef-ca59a3597c6c.jpg)
Because of semi strict pseudoconvexity of
, This implies
(8)
With strict inequality with
,
.
Also ![](https://www.scirp.org/html/10-7400898\54c5b39c-50e9-4709-acfe-4cbdc14dd381.jpg)
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 ![](https://www.scirp.org/html/10-7400898\b6b87b87-c2e6-4fd8-87c2-69834af4739b.jpg)
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
![](https://www.scirp.org/html/10-7400898\07051cb9-1d67-415b-82b9-e8b5cf6df9ef.jpg)
Proof: Suppose
this, because of pseudoconvexity of
yields
, Multiplying this, by
We have
(15)
With strict inequality in (15) if ![](https://www.scirp.org/html/10-7400898\c10929f4-3906-4740-bf81-21cd65170ad4.jpg)
From the Constraints of
and
, we have
![](https://www.scirp.org/html/10-7400898\3e891fd0-5d53-492f-aa91-09051400bdef.jpg)
which by semi-strictly pseudoconvexity of
implies
(16)
with strict inequality in (16) if ![](https://www.scirp.org/html/10-7400898\2837a2b5-479d-4d92-b0da-e5d87ff6f53a.jpg)
As earlier ![](https://www.scirp.org/html/10-7400898\e0aa1080-2bdf-4127-81a1-b79f0332a662.jpg)
This along with quasiconvexity of
implies
(17)
Combining (15), (16), (17), we have
![](https://www.scirp.org/html/10-7400898\ae120194-de82-4e7f-9387-d5ca2010a69b.jpg)
Contradicting
![](https://www.scirp.org/html/10-7400898\dd3cbfdc-b350-4aeb-9824-31c6feb39294.jpg)
Hence ![](https://www.scirp.org/html/10-7400898\e17debf5-1772-45fb-a9ca-646ef7c12ee6.jpg)
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
![](https://www.scirp.org/html/10-7400898\1197a292-fa19-4490-b7a9-1158cf2e6289.jpg)
![](https://www.scirp.org/html/10-7400898\49f07609-a410-43d4-b023-0d510a834f32.jpg)
![](https://www.scirp.org/html/10-7400898\d2100b2a-032d-4c8d-812a-0057053ca287.jpg)
![](https://www.scirp.org/html/10-7400898\060ba029-d47a-484f-9876-083e6348ad97.jpg)
![](https://www.scirp.org/html/10-7400898\9f491e41-87cf-4cf4-85f3-3d407630139e.jpg)
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
![](https://www.scirp.org/html/10-7400898\6dcc9993-56cf-41a3-8516-9b016d0044b4.jpg)
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 ![](https://www.scirp.org/html/10-7400898\146b45c3-351d-4767-aa3c-9c6fe9efa748.jpg)
Also
which by quasi-convexity of
at
, implies
(20)
Combining (18), (19), and (20), we have
![](https://www.scirp.org/html/10-7400898\07b04b23-eae2-4c02-bba7-28f6474cb113.jpg)
which contradicts
![](https://www.scirp.org/html/10-7400898\dbd0da7b-4502-47e0-92c8-b1a80b785ed9.jpg)
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
, ![](https://www.scirp.org/html/10-7400898\18e4b0fb-fbc4-452b-9719-01709c2d4339.jpg)
,
,
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 ![](https://www.scirp.org/html/10-7400898\3bebab94-e1f7-4531-ba05-be3fffac9af2.jpg)
Multiplying (21) by
and using (31) and (32), we have
![](https://www.scirp.org/html/10-7400898\85fc0c4a-6618-49f5-8005-91ca1f572c95.jpg)
Multiplying the above equation by r and using (33), we have
![](https://www.scirp.org/html/10-7400898\34e3f12f-662f-49c9-8d18-5bee0824b82d.jpg)
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
![](https://www.scirp.org/html/10-7400898\6fbb27f9-93ac-454b-bd69-b274c2dd3173.jpg)
Using the equality constraint (10) in the above, we have
![](https://www.scirp.org/html/10-7400898\f34e889a-4d59-4950-a37e-fed1f38b105b.jpg)
This reduces to
![](https://www.scirp.org/html/10-7400898\d799d1a0-8802-4a9a-96a6-94d13150e1fa.jpg)
By the linear independence hypothesis (A3). this implies
and ![](https://www.scirp.org/html/10-7400898\78259b23-ad46-4e87-a17e-ae7761c07a29.jpg)
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
, ![](https://www.scirp.org/html/10-7400898\9acc58c6-f46b-420f-95a8-77abeb31d223.jpg)
This implies
and ![](https://www.scirp.org/html/10-7400898\392d5d4c-da9e-4fc6-9d4f-b7403d594df4.jpg)
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 ![](https://www.scirp.org/html/10-7400898\1f46cad7-ef09-46d0-90f9-38d5c927b209.jpg)
Subject to
![](https://www.scirp.org/html/10-7400898\e2a76691-fde1-478f-b19f-5f155bf6d775.jpg)
![](https://www.scirp.org/html/10-7400898\85a154b2-6ba4-4f58-97cb-695597319457.jpg)
![](https://www.scirp.org/html/10-7400898\32471c4b-8137-45de-95b5-38f9e2f996c5.jpg)
![](https://www.scirp.org/html/10-7400898\1b2d58d9-cb06-4a44-81f3-79c437fabc61.jpg)
![](https://www.scirp.org/html/10-7400898\215e987a-6999-45f6-b50f-8a153fd5f889.jpg)
Theorem 6: If
is pseudoconvex, ![](https://www.scirp.org/html/10-7400898\341607d5-5cbb-44b2-8875-3e8462a62c72.jpg)
is semi-strictly pseudoconvex,
and
is quasiconvexThen ![](https://www.scirp.org/html/10-7400898\a903fbe2-b915-4882-8af6-43aa0606f677.jpg)
Proof: Let
be feasible for
and
feasible for
. Suppose
This by pseudoconvexity of
yields
(34)
with strict inequality in (34) if ![](https://www.scirp.org/html/10-7400898\e6f7c726-6cea-41f5-9e4b-0a2bc5aa1bd5.jpg)
From the constraint of
and
, we have
(35)
Which because of semistrictly pseudoconvexity of
implies
(36)
with strict inequality in (36) if some ![](https://www.scirp.org/html/10-7400898\f35f41ed-8ce9-458c-b983-303831843f64.jpg)
Also
![](https://www.scirp.org/html/10-7400898\0a3b9ec4-cfab-45cc-811a-390857769d76.jpg)
And
![](https://www.scirp.org/html/10-7400898\1c988775-6cb7-4053-9282-0e43fd8c5215.jpg)
Which by quasiconvex of
and
![](https://www.scirp.org/html/10-7400898\cc19fb61-170b-4473-8beb-28fb61ad3cf0.jpg)
respectively imply
![](https://www.scirp.org/html/10-7400898\d52599bd-d5f2-4caa-a974-0123130f854f.jpg)
and
![](https://www.scirp.org/html/10-7400898\84987746-e245-44c1-937e-5bff582fcff7.jpg)
combining (34), (35), (36) and above equation we have
![](https://www.scirp.org/html/10-7400898\8a84f300-4b98-4886-8ee3-b47c8cde5bb4.jpg)
contradicting the equality constraint of
. Hence ![](https://www.scirp.org/html/10-7400898\5daaa14c-4fc0-48c8-94ba-713500476c1f.jpg)
Implying ![](https://www.scirp.org/html/10-7400898\ef5e1600-db05-45da-954b-53669a3c0561.jpg)
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
![](https://www.scirp.org/html/10-7400898\42e67038-105a-4e31-a891-2ea24ade0c6a.jpg)
![](https://www.scirp.org/html/10-7400898\d2e45e4e-7a11-4407-96d0-9655467045ac.jpg)
![](https://www.scirp.org/html/10-7400898\18963e7a-4eb5-4daa-be66-12b65175c45e.jpg)
![](https://www.scirp.org/html/10-7400898\0411d897-c3da-44ab-a98c-946d3715bb41.jpg)
Since
,
and
feasibility of
for
is obvious. Optimality follows, give the pseudoconvexity of ![](https://www.scirp.org/html/10-7400898\c237f2fc-7e82-4fae-bd24-c7459febb2fb.jpg)
and semi-strict pseudoconvexity of
quasiconvexity of
and quasiconvexity of
from Theorem 1.
Theorem 8: (Mangasarian [4] Type Strict Converse Duality): Assume that
![](https://www.scirp.org/html/10-7400898\e9ac5a64-0c46-41c3-9b25-a62ea36bce45.jpg)
is strictly pseudoconvex,
![](https://www.scirp.org/html/10-7400898\3de7dbfd-03da-417a-9619-a872b461d54d.jpg)
is semi-strictly pseudoconvex and
![](https://www.scirp.org/html/10-7400898\833c4152-eb89-4c19-aed4-2b5dc85e2f38.jpg)
and
are quasiconvex.
![](https://www.scirp.org/html/10-7400898\665dce6d-5bb9-483b-b382-b2989efe2174.jpg)
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 ![](https://www.scirp.org/html/10-7400898\b24ab08e-8038-4917-8ca6-965d30dd5207.jpg)
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
![](https://www.scirp.org/html/10-7400898\0c0debc0-26aa-42f3-9cee-d3b7f83eaa4b.jpg)
which contradicts the feasibility of
for
. Hence ![](https://www.scirp.org/html/10-7400898\dd685db0-4b6a-4db7-9ef1-c7aba311118d.jpg)
Theorem 9 (Converse Duality): Let
![](https://www.scirp.org/html/10-7400898\9f9071fb-97cd-4443-9a21-8dce856ff323.jpg)
be an optimal solution of
.
![](https://www.scirp.org/html/10-7400898\5f958449-69b3-475b-9e00-a625a463fdf7.jpg)
be pseudoconvex,
semistrictly pseudoconvex,
quasiconvex.
The Hessian matrix
![](https://www.scirp.org/html/10-7400898\88d3534a-f1b1-49d5-bc32-811b3d24cf74.jpg)
is positive or negative definite, and
The set
![](https://www.scirp.org/html/10-7400898\edc86cdf-b8b3-40e2-8207-81de7b58e926.jpg)
is linearly independent. Then
is feasible for
.
Proof: By Proposition 2, there exist
, ![](https://www.scirp.org/html/10-7400898\ef240219-94bf-4e3b-a022-95eb6d6b361d.jpg)
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
![](https://www.scirp.org/html/10-7400898\5f1ad06f-4d85-469f-899f-d955a4f2cd2f.jpg)
By positive or negative definite and by hypothesis
, we have ![](https://www.scirp.org/html/10-7400898\11be901d-16a8-4952-964d-4663fa8403fd.jpg)
In view of
, equality constraint of
implies that
Hence
using
we have
![](https://www.scirp.org/html/10-7400898\94ebb04b-b625-453d-b229-69d28a3f26f3.jpg)
which in view of the hypothesis
gives
,
. From (44) and (45), we have
and
consequently we have
![](https://www.scirp.org/html/10-7400898\2314b3f9-f4ea-4f49-b60e-dd128664fbbb.jpg)
Contradicting Fritz John Condition (51). Hence
since
The Equations (45) and (46), implies ![](https://www.scirp.org/html/10-7400898\09ddec69-eaa3-481d-a453-e8e796e5200a.jpg)
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.