ABSTRACT

In this paper, we prove that the combined homotopy interior point method for a multiobjective programming problem introduced in Ref. [1] remains valid under a weaker constrained qualification—the Mangasarian-Fromovitz constrained qualification, instead of linear independence constraint qualification. The algorithm generated by this method associated to the Karush-Kuhn-Tucker points of the multiobjective programming problem is proved to be globally convergent.

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.

REFERENCES