A Weaker Constraint Qualification of Globally Convergent Homotopy Method for a Multiobjective Programming Problem ()
1. Introduction
Let be the -dimensional Euclidean space, and let and denote the nonnegative and positive, respectively. For any two vectors and in, we use the following conventions:. Similarly, we can define, and.
Consider the following multiobjective programming problem (MOP)
where
We assume that all and are twice continuously differentiable functions, where
Let
It is well known that if is an efficient solution of (MOP), under some constraint qualifications, such as the Kuhn and Tucker constraint qualification (see Ref. [2]) or the Abadie constraint qualification (see Ref. [3]), then the following Karush-Kuhn-Tucker (KKT) condition at for (MOP) holds (see Refs. [4,5]):
(1)
where and
We say that is a KKT point of (MOP) if it satisfies the KKT condition.
Since the remarkable papers of Kellogg et al. (Ref. [6]) and Chow et al.(Ref. [7]) have been published, more and more attention has been paid to the homotopy method. As a globally convergent method, the homotopy method (or path-following method) now becomes an important tool for numerically solving nonlinear problems includeing nonlinear mathematical programming and complementarily problems (see Refs. [3,4]).
In 1988, Megiddo (see Ref. [8]) and Kojima et al. (see Ref. [9]) 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 generalized to convex programming, and becomes one of the main methods for solving mathematical programming problems. Among most interior methods, one of the main ideas is numerically tracing the center path generated by the optimal solution set of the so-called logarithmic barrier function. Usually, the strict convexity of the logarithmic barrier function or nonemptiness and boundedness of the feasible set (see Ref. [10]) are needed. In 1997, Lin, Yu and Feng (see Ref. [11]) presented a new interior point method—combined homotopy interior point method (CHIP method)—for convex nonlinear programming without such assumptions. Subsequently, Lin, Li and Yu (see Ref. [12]) generalized CHIP method to general nonlinear programming where, instead of convexity condition, they used a more general “normal cone condition”.
In 2003, Lin, Zhu and Sheng (see Ref. [13]) generalized CHIP method to convex multiobjective programming(CMOP) with only inequality constraints. Instead of (CMOP), they considered an associated non-convex nonlinear scalar optimization problem and constructed the homotopy mapping.
In Refs. [1,14], we considered a combined homotopy interior point method for the multiobjective programming (MOP) under the condition linearly independent constraint qualification (LICQ). To find a KKT point of (MOP), we construct a homotopy as follows
(2)
where
Let
Let be a nonempty closed set and. We recall that the Fréchet normal cone of at is defined as
We used the following basic assumptions which are commonly used in that literature:
(A1) is nonempty (Slater condition) and bounded;
(A2) (LICQ) the matrix
is a matrix of full column rank;
(A3) Normal condition:
It is well known that if condition (A2) holds, then
(3)
We have proved the following convergence result in Ref. [1].
Theorem 1.1 (Convergence of the method) Suppose and are twice continuously differentiable functions such that the conditions (A1), (A2), and (A3) hold. Then for almost all
the zero-point set of the homotopy map (2)
contains a smooth curve
which starts from As the limit set
of is nonempty, and the
component of every point in is a KKT point of (MOP).
Recently, many researchers extended and improved the results in Ref. [1] to convex multiobjective programming problem, see Ref. [14-17]. The purpose of this paper is to show that Theorem 1.1 remains true under the condition MFCQ instead of LICQ. The paper is organized as following. In Section 2, we prove the existence and convergence of a smooth homotopy path from almost any interior initial point to a solution of the KKT system of (MOP) under the condition MFCQ.
2. Main Results
We need the following elementary condition.
(A2′) (MFCQ) For every the following conditions hold:
• are linear independent;
• there exists a such that
and
Clearly, condition (A2) implies (A2′). It is also known that if (A2′) holds, then (3) remains valid.
By using an analogue argument as in Ref. [1], we can prove the following two theorems.
Theorem 2.1 Suppose that and conditions (A1), (A2′) hold. Then for almost all initial points
is a regular value of
and consists of some smooth curves. Among them, a smooth curve, say starts from
Theorem 2.2 Suppose that and conditions (A1), (A2′) hold. For a given if 0 is a regular value of, then the projection of the smooth curve on the component is bounded.
We next prove that is a bounded curve.
Theorem 2.3 (Boundedness) Suppose that the conditions (A1), (A2′), and (A3) hold. Then for a given
if 0 is a regular value of, then is a bounded curve.
Proof: By Theorem 2.2, it is sufficient to show that the component of smooth curve is bounded. Suppose that there exists a sequence
such that
and
where Since closed unit circle of is compact, without loss of generality we can assume that
Clearly, By (2), we have
(4)
(5)
Let
By (5), we know
Rewrite (4) as
(6)
Divide (6) by and let since
, (6) becomes
(7)
where
1) If then By
(A2′), This is a contradiction with.
2) If we consider the following two cases:
1. If, we know because of By (A2′), there exists a nonzero vector such that
(8)
This, together with (7), implies that which is a contradiction.
2. If, by (7) and (A2′), we know So,
since
Because of (5), Thus
Without loss of generality, we can assume that
Hence
a) If, then is bounded. We may assume Divide (6) by and let
(6) becomes
(9)
This implies that
exists. Indeed,
If
that is
By condition (A3), This is impossible since. So
By (9), we then have that exists. Assume
Then
If, (9) becomes
This contradicts to condition (A3).
If, (9) becomes
By (A2′), there exists a nonzero vector such that
Thus which contradicts
b) If, without loss of generality, we can assume that
where Since
(10)
we divide (4) by and let
we have that
(11)
If then
By condition (A2′), This is a contradiction since
If by (A2′), there is a nonzero vector such that
This, together with (11), implies This is a contradiction.
Therefore, is a bounded curve.
By an analogue argument as in Ref. [1], it is easy to show the following result.
Theorem 2.4 (Convergence of the method) Suppose that the conditions (A1), (A2′), and (A3) hold. Then for almost all the zero-point set of the homotopy map (2) contains a smooth curve
which starts from As
the limit set of
is nonempty, and every point in is a solution of (1).
Therefore, Theorem 2.4 shows that for almost all the homotopy Equation (2)
generates a smooth curve starts from
which is called the homotopy path, the limit set
of is nonempty, and the x-component of every point in is a KKT point of (MOP), the of the homotopy path is the solution of (1) as goes to 0.