﻿A Weaker Constraint Qualification of Globally Convergent Homotopy Method for a Multiobjective Programming Problem

Applied Mathematics
Vol.4 No.2(2013), Article ID:28209,5 pages DOI:10.4236/am.2013.42052

A Weaker Constraint Qualification of Globally Convergent Homotopy Method for a Multiobjective Programming Problem

Guangming Yao1, Wen Song2

1Department of Mathematics, Clarkson University, Potsdam, USA

2Department of Mathematics, Harbin Normal University, Harbin, China

Email: gyao@clarkson.edu, wsong218@yahoo.com.cn

Received September 29, 2012; revised January 9, 2013; accepted January 16, 2013

Keywords: Multiobjective Programming Problem; Homotopy Method; KKT Condition; Efficient Solution; MFCQ

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

If, (9) becomes

By (A2′), there exists a nonzero vector such that

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

1. W. Song and G. M. Yao, “Homotopy Method for General Multiobjective Programming Problems,” Journal of Optimization Theory and Applications, Vol. 138, No. 1, 2008, pp. 139-153. doi:10.1007/s10957-008-9366-6
2. H. W. Kuhn and A. W. Tucker, “Nonlinear Programming,” Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, Berkeley, 1951.
3. T. Maeda, “Second-Order Conditions for Efficiency in Nonsmmoth Multiobjective Optimization Problems,” Journal of Optimization Theory and Applications, Vol. 122, No. 3, 2004, pp. 521-538. doi:10.1023/B:JOTA.0000042594.46637.b4
4. C. Y. Lin and J. L. Dong, “Methods and Theories in Multiobjective Optimization,” Jinlin Education Press, Changchun, 1992.
5. M. Abadie, “Generalized Kuhn-Tucker Conditions for Mathematical Programming,” SIAM Journal on Control, Vol. 7, No. 2, 1969, pp. 232-241. doi:10.1137/0307016
6. R. B. Kellogg, T. Y. Li and J. A. Yorke, “A Constructive Proof of the Brouwer Fixed-Point Theorem and Computational Results,” SIAM Journal on Numerical Analysis, Vol. 13, No. 4, 1976, pp. 473-483. doi:10.1137/0713041
7. S. N. Chow, J. Mallet-Paret and J. A. Yorke, “Finding Zeros of Maps: Homotopy Methods That are Constructive with Probability One,” Mathematical Computation, Vol. 32, 1978, pp. 887-899. doi:10.1090/S0025-5718-1978-0492046-9
8. N. Megiddo, “Pathways to the Optimal Set in Linear Programming, in Progress in Mathematical Programming, Interior Point and Related Methods,” Springer, New York, 1988, pp. 131-158.
9. M. Kojima, S. Mizuno and A. Yoshise, “A Primal-Dual Interior Point Algorithm for Linear Programming,” In: N. Megiddo, Ed., Progress in Mathematical Programming, Interior Point and Related Methods, Springer, New York, 1988, pp. 29-47.
10. E. L. Allgower and K. Georg, “Numerical Continuation Methods: An Introduction,” Springer Verlag, Berlin, 1990. doi:10.1007/978-3-642-61257-2
11. Z. H. Lin, B. Yu and G. C. Feng, “A Combined Homotopy Interior Method for Convex Nonlinear Programming,” Applied Mathematics and Computation, Vol. 84, No. 2-3, 1997, pp. 193-211. doi:10.1016/S0096-3003(96)00086-0
12. Z. H. Lin, Y. Li and B. Yu, “A Combined Homotopy Interior Point Method for General Nonlinear Programming Problems,” Applied Mathematics and Computation, Vol. 80, No. 2-3, 1996, pp. 209-224. doi:10.1016/0096-3003(95)00295-2
13. Z. H. Lin, D. L. Zhu and Z. P. Sheng, “Finding a Minimal Efficient Solution of a Convex Multiobjective Program,” Journal of Optimization Theory and Applications, Vol. 118, No. 1, 2003, pp. 587-600. doi:10.1023/A:1024739508603
14. Y. F. Shang and B. Yu, “A Constraint Shifting Homotopy Method for Convex Multi-Objective Programming,” Journal of Computational and Applied Mathematics, Vol. 236, No. 5, 2011, pp. 640-646.
15. X. Zhao, S. G. Zhang and Q. H. Liu, “Homotopy InteriorPoint Method for a General Multiobjective Programming Problem,” Journal of Applied Mathematics, Vol. 2012, 2012, Article ID: 497345.
16. N. Kim and L. Thuy, “An Algorithm for Generating Efficient Outcome Points for Convex Multiobjective Programming Problem,” Intelligent Information and Database Systems Lecture Notes in Computer Science, Vol. 5991, No. 2010, 2010, pp. 390-399.
17. Z. Chen, “Multiobjective Optimization Problems, Vector Variational Inequalities and Proximal-Type Methods,” Dissertations, Hong Kong Polytechnic University, Kowloon, 2010.