Homotopy Continuous Method for Weak Efficient Solution of Multiobjective Optimization Problem with Feasible Set Unbounded Condition ()
1. Introduction
Mathematical modeling of real-life, economics and engineering problems usually results in optimization and decision systems, such as multiobjective optimization systems, linear and nonlinear optimization systems, global optimization systems and others. Many mathematical formulation of economics and decisions contain multiobjective optimization problems, which arise in use of choosing projects in Bid Decision, developing production plan by Enterprise and requiring human resource in Management; for more details see ([1,2]) and the reference cited therein. Therefore, it is very actually meaning subject how we find the KKT points of multiobjective optimization problem. Hence we consider the following multiobjective programming problem with inequality constraints:
(MOP) ![](https://www.scirp.org/html/14-7400844\46170db3-883b-4682-8aaf-9c552d50d0b9.jpg)
where
![](https://www.scirp.org/html/14-7400844\e4b22d5f-ea78-489d-a92a-39369443aa65.jpg)
and
![](https://www.scirp.org/html/14-7400844\af4243b2-9283-4994-95df-03f5fa6cc622.jpg)
are twice times continuously differentiable functions.
Since 1981, Garcia and Zangwill [3] firstly used homotopy method to study convex programming problem, which makes the method become a powerful tool in dealing with various programming problems. In 1988, Megiddo [4] and Kojima [5] et al. discovered that the Karmakar interior point method was a kind of path following method for solving linear programming. Since then the interior path-following method has been extensively used for solving mathematical programming problems. In 1994, Lin, Yu and Feng [6] constructed a new interior point method—combined homotopy interior point method (CHIP method), formed by Newton homotopy and linearly homotopy—for solving the KKT point of convex nonlinear programming. Subsequently, Lin, Li and Yu [7], without strictly convexity of the logarithmic barrier function, showed that the iteration points generated by CHIP, also converged to the KKT points of optimization problem. In 2003, CHIP method was generalized to convex multiobjective optimization problem by Lin, Zhu and Sheng [8]. They constructively proved the existence of KKT system solution for corresponding purification problem.
In 2008, Song and Yao [9] further generalized the results of [8,10]. They constructed a new combined homotopy mapping. A smooth bounded homotopy path was obtained under the normal cone condition and weaker Mangasarian-Fromovitz constraint qualification. However, up till now the convergence of homotopy path in literature related above is obtained under the condition that the feasible set is nonempty and bounded. Recently by adapting the combined homotopy method developed in [11,12], a homotopy method was proposed in [13,14] for variational inequalities on unbounded sets.
In this paper, we will discuss about homotopy methods for MOP on unbounded set. Under conditions which are commonly used in the literature, a smooth path from a given interior point set to a solution of MOP will be proven exist. The paper is organized as follows. In Section 2, we recall some preliminaries results, formulate an equivalent form of KKT system for MOP and list some lemmas from differential topology which will be used in this paper. In Section 3, we proved in detail existence and convergence of the smooth path under a weak condition.
Throughout the paper, let
be the feasible set of MOP, and
be the strictly feasible set of MOP. In addition, we denote the index set of
at x by
.
![](https://www.scirp.org/html/14-7400844\9ffc85b6-f942-433c-8b5e-fcc1abea9317.jpg)
and
![](https://www.scirp.org/html/14-7400844\4daf5261-8020-4ef7-b599-8c83b913d9f8.jpg)
represent the nonnegative and positive orthant of
, respectively.
2. Preliminaries
As we know, the solutions for a multiobjective programming problem are referred to variously as efficient, Pareto-optimal and nondominated solution [15]. In this paper, we will refer to a solution of a multiobjective programming problem as an efficient solution.
Definition 2.1 [15]
is an efficient solution of multiobjective programming problem, if there is no
such that
holds.
In [9], a homotopy method for MOP with bounded
was given. In this paper, we will discuss MOP with
which is not necessarily bounded. It is well known that, if x is an efficient solution of MOP, under some constraint qualifications (e.g. Kuhn and Tucker constraint qualification [16]), MOP satisfies KKT constraint condition at x (see [10,15]):
(1)
where
,
,
,
,
![](https://www.scirp.org/html/14-7400844\48480c5b-f456-4f0e-968a-9b8d966542f7.jpg)
and
.
We call that a point x satisfying the KKT condition (1) is a Karush-Kuhn-Tucker point of MOP, and
are the corresponding Lagrangian multipliers of MOP at x. Because
, let
For solving the KKT system, we search a vector
![](https://www.scirp.org/html/14-7400844\012500f6-da2c-4e92-bc3a-91d2e260e058.jpg)
such that
(2)
is called a Kuhn-Tucker vector of MOP. Usually, we will solve its KKT system of MOP instead of solving MOP directly.
The following lemmas from differential topogy will be used in the next section.
Definition 2.2 [17] Let X and Y be topological space,
be continuous mapping and
be real interval. H is called a homotopy mapping
such that
![](https://www.scirp.org/html/14-7400844\9603ff2c-afa9-4d46-9dd2-af543ab7aca9.jpg)
To solve (2), the homotopy mapping H is given by [7] as follow:
(3)
where
![](https://www.scirp.org/html/14-7400844\5d8e975b-5f6d-4fe7-af83-0e3a727057c2.jpg)
![](https://www.scirp.org/html/14-7400844\88a472bc-56df-4606-939b-8ce44c476ab1.jpg)
![](https://www.scirp.org/html/14-7400844\b4086722-4119-4e55-8aed-2cad3e60a25d.jpg)
and
Sometimes, we rewrite
as
for convenience. Because f and g are continuous mappings, H is also continuous mapping. When
, the homotopy Equation (3) becomes
(4)
(5)
(6)
Hence, it is easily obtained
,
and
. Thus
. That is, the equation
with respect to
has only one solution.
As
, the solution of the Equation (3) is just that of KKT system (2).
Thus, for a given
, the zero-point of the mapping
constructed above is the homotopy mapping between the trivial mapping of
and KKT system (2) of MOP. To develop our main result, we need the following basic definitions and lemmas in topology. By the definition of Cr differential manifold [17], we know
is a n-dimensional differential manifold. For the definition of product manifold [17],
is a manifold with boundary
.
Definition 2.3 [17] Let U, V be differential manifold with
, and
be a differential mapping. We say that
is a regular value of H and
is a regular point, if
(7)
holds. Given a curve
, if every
is a regular point, then
is a regular path.
Lemma 2.1 [17] Let
and
be two open sets, and
be a
differentiable mapping with
. If
is a regular value of
, then for almost all
, 0 is a regular value of
.
Lemma 2.2 [17] If 0 is a regular value of the mapping
, then
consists of some smooth manifolds.
Lemma 2.3 (Classification Theorem of One-Dimensional Manifold with Boundary [17]) Each connected part of a one-dimensional manifold with boundary is homeomorphic either to a unit circle or to a unit interval.
3. Main Results
According to [15], as the objective function of optimization problem is convex, there exists a
and
, satisfying
for any weak efficient solution x of MOP. Thus, we introduce the definition of a weak solution at infinity for MOP.
Definition 3.1 MOP has a weak solution at infinity, denoted by a sequence
, if
, ![](https://www.scirp.org/html/14-7400844\a4abb57b-bf8d-4072-805d-64da4d036426.jpg)
as
, and for any given
, there exist
and
such that
as
, where
.
The following example illustrates the meaning of Definition 3.1.
Example 3.1 Consider MOP with ![](https://www.scirp.org/html/14-7400844\0472283b-8f09-4c62-8448-09d384ef2726.jpg)
and
. Take
and
. Let
,
. Then
is a weak solution at infinity for MOP as
. For any given
, there exist
and
, when
satisfying
![](https://www.scirp.org/html/14-7400844\015d74ad-c872-4bbb-9bb2-d4fb1d1e7d3e.jpg)
Theorem 3.1 Consider the homotopy mapping H of MOP constructed as (3). Suppose the following four conditions are satisfied:
(A)
is nonempty (Slater condition);
(B) For any
,
are nonnegatively independent, i.e.
and ![](https://www.scirp.org/html/14-7400844\b2241056-6ca5-4f93-81a9-002020d965cd.jpg)
for any
imply that
for any
;
(C)
and
are twice continuously differentiable functions. All of
are convex;
(D) There exist
, such that
and MOP has weak solution at infinity.
Then, for almost all
, the zero-point set
of the homotopy map (3) contains a smooth curve
, which starts from
. As
, the limit set
of
is nonempty and every point
in
is a solution of KKT system (2).
To prove Theorem 3.1, we need to prove the following three results. For a given
, we set
![](https://www.scirp.org/html/14-7400844\32f0de9a-bb58-47eb-961e-d7b11c6f4b3c.jpg)
Lemma 3.1 If the conditions (A) and (B) of Theorem 3.1 holds, then for almost all
0 is a regular value of
and
consists of some smooth curves. Among them, a smooth curve
starts from
.
Proof: For any
,
![](https://www.scirp.org/html/14-7400844\483c22cd-03d9-444c-a8ad-624b2557a905.jpg)
where I is an identical matrix. By a simple computation, we have
.
For
, we have
, and hence
. Thus, 0 is the regular value of H. By Lemma 2.1, for almost all
, 0 is a regular value of
. By Lemma 2.2,
consists of some smooth curves. Since
there must be a smooth curves, denoted by
, which starts from ![](https://www.scirp.org/html/14-7400844\8479cc42-f178-47ea-b749-89a37932bc05.jpg)
Lemma 3.1 guarantees that the zero-point set of H has a good geometric structure. The following theorem is the key of boundedness for the homotopy path generated by (3), which is the main result of this paper.
Theorem 3.2 Suppose that the condition (C) of Theorem 3.1 holds. There exists
, such that
. Then, either the x-component of the smooth curve
is bounded or (2) has a weak solution at infinity.
Proof: For any
, we construct two set as follows:
![](https://www.scirp.org/html/14-7400844\4e6733d3-dd29-4fea-b9f5-fdf9235aedcb.jpg)
![](https://www.scirp.org/html/14-7400844\59d2fd35-017d-4aae-a15c-54f3b3893eb7.jpg)
Thus, we have
.
The properties of norm imply the following equality holds, that is, given a start point
, for any
, we have
.
Indeed
![](https://www.scirp.org/html/14-7400844\33ded162-a339-4c7b-ad19-59185995ac04.jpg)
Take any
. From the first Equation (3) multiplied by
, we obtained that
(8)
By the convexity of
and
, we know:
(9)
From the (7), (8) and the second equation in (3), we simplify the Equation (8), that is
![](https://www.scirp.org/html/14-7400844\29fc8c67-3636-4daa-83fc-4ee10347375c.jpg)
Taking
and
, we have
![](https://www.scirp.org/html/14-7400844\f7517ee9-a300-47ab-bd08-88baa1b25378.jpg)
Hence,
is bounded.
Suppose that x-component of
is unbounded, there exists
such that
(10)
and
as
. Without loss of generality, suppose that
by boundedness of
, from the equality (7), (10),
and
, we obtained that for any
,
![](https://www.scirp.org/html/14-7400844\ebb2ebb3-1545-4c27-854a-b120063b4d33.jpg)
As
and
as
, hence, for any sufficient large k, there exists
such that
![](https://www.scirp.org/html/14-7400844\1b0dac48-22b9-4de2-a1c4-7cfef871242f.jpg)
Therefore,
is a weak solution at infinity to MOP by Definition 3.1.
If MOP has no weak solution at infinity, the x-component of
is a bounded curve from Theorem 3.2. Refer to [8], we know that
-component in
is also bounded curve. Thus, we only need to prove that u-component in
is bounded, in order to obtain that
is a bounded curve.
Theorem 3.3 (Boundedness) Suppose that the condition (A)-(D) of Theorem 3.1 hold. For a given
, if 0 is a regular value of
, then
is a bounded curve in
.
Proof: We use proof by contradiction. Suppose that
is bounded. Then, by Theorem 3.2 there exists a sequence
such that
and
as ![](https://www.scirp.org/html/14-7400844\186022dd-014a-4ccb-a079-3ca2fd6aae41.jpg)
From the second equality of (10), we obtain that there exists some index i such that
(11)
Since
, let
where
denotes the ith component of
. Hence,
is nonempty. It follows from (11) that
, that is
From the first equality of (10),
(12)
The following is divided two parts:
1) When
, rewrite (12) as
![](https://www.scirp.org/html/14-7400844\4ba966ef-ccc5-4bbe-a0fd-5ca4bd0242d3.jpg)
Let
; Since
,
and
,
are all bounded, the above equality becomes
(13)
From the condition (C),
implies
. Hence (13) becomes
. (14)
It is obviously that the coefficient in left-hand side
![](https://www.scirp.org/html/14-7400844\8f2f1156-8272-416d-b840-af11c87c2726.jpg)
of equality (14) must be positive finite quantities as value. Otherwise, the condition (B) of Theorem 3.1 implies
is nonnegatively independent, i.e.
and
for any
imply that
for any
. So, if we take
as infinite value,
holds. Therefore, if we get
,
, the lefthand side of equality (14) is infinite. This is contradiction with the finite value of the right-hand for the equality
(14). Let
,
, where
. Hence we have
(15)
Since
and
, the equality (15) multiplied by
implies:
(16)
However, the convexity of
implies
![](https://www.scirp.org/html/14-7400844\42ca68e7-b3fa-45cb-8c6a-8311c0744356.jpg)
Thus, we obtain
. This contradicts
. So
as
.
2) When
, we rewrite (12) as
(17)
From
and the condition (B), it follows that the last term in the (17) tends to infinity, whereas the first and second terms are bounded. This is impossible.
As stated previously,
is a smooth bounded curve.
Proof of Theorem 3.1: By Lemma 2.3,
must be diffeomorphic to a unit circle or a unit interval
.
Since the matrix
![](https://www.scirp.org/html/14-7400844\cfc3e624-cfdf-4808-afce-80d3558c3630.jpg)
Is nonsingular,
is not tangent to the plane
at
. Because
has only one solution
, we know
must have limit point. We assume that
is limit point, then
.
In fact, if
since 0 is a regular value of
and
, the Jacobian matrix of H at ![](https://www.scirp.org/html/14-7400844\fa01b617-2ad4-4afe-8e1d-bca09f00be9d.jpg)
is full row rank. By implicit function theorem,
must be extended at
. This contradicts the fact that
is a limit point of
. Hence only the following three cases are possible:
1)
;
2)
;
3) ![](https://www.scirp.org/html/14-7400844\d7b283ec-bdbc-4e81-9af8-15e0cef3994d.jpg)
Case 1) is impossible because
has only one solution
in
.
Case 2) holds, which implies that there must be a sequence
as
in
and
. However, in fact, the component
and
in
satisfying
and
.
Indeed, if
, then there must be some
satisfying
. So there exists a sequence
such that
as
. Since
is bounded, we have
.
From the second equality of homotopy Equation (10), we can see
.
This is a contradiction.
Second, we assume that
. There also exists a sequence
such that ![](https://www.scirp.org/html/14-7400844\ba9870de-ece5-4ebf-9293-ec0040b4eea8.jpg)
as
for some
. Noticing that
and from the third equality in (10), we have
.
As
, since
, we obtain
from the above equation. Take the
th equality of the third equation in (10),
.
Let
, we can see
. Thus
This contradicts
. Hence case 2) does not hold.
Therefore case 3) is the only possible case. From Theorem 3.3 and condition (D),
is a solution of the KKT system. ![](https://www.scirp.org/html/14-7400844\43dcc76a-245b-4058-8633-a60b83e8f3a7.jpg)
Remark 3.1 If
is a bounded set, the condition (D) of Theorem 3.1 holds obviously. Hence, the result of Theorem 3.1 implies the one in [9].
Above all, we do not only prove the existence of solution for KKT equation, but also give a kind of numerical algorithm, that is, the solution can be obtained by tracing numerically the homotopy path
, starting from
. If we denote s as arc length parameter of curve
, then the differential homotopy Equation (1) with respect to s implies the theorem as follow:
Theorem 3.4 Assume that the conditions (A)-(D) in Theorem 3.1 hold. We denote
as parametrized curve of
, where s represents arc length parameter of
. Then
is determined by the following initial value problem to the ordinary differential equation:
(18)
If there exists
such that
, then
,
and
are the solution of KKT equation.
4. Conclusion
In summary, the HCM is employed to find weak efficient of MOP with inequality constraints. The method needs much less restrictive condition and computational work compared with traditional method. It is shown that the HCM is globally convergent and computational tractability for solving MOP on unbounded set.
5. Acknowledgements
The authors are grateful to Professor W. Song and the referee for valuable comments and suggestions. We also thank editors and reviewers for their valued comments, which helped in improving the quality of the paper.