﻿Homotopy Continuous Method for Weak Efficient Solution of Multiobjective Optimization Problem with Feasible Set Unbounded Condition

Applied Mathematics
Vol. 3  No. 7 (2012) , Article ID: 20011 , 7 pages DOI:10.4236/am.2012.37114

Homotopy Continuous Method for Weak Efficient Solution of Multiobjective Optimization Problem with Feasible Set Unbounded Condition

Wei Xing, Boying Wu

Department of Mathematics, Harbin Institute of Technology, Harbin, China

Email: xingmeiwei@163.com, mathwby@hit.edu.cn

Received May 9, 2012; revised June 9, 2012; accepted June 16, 2012

Keywords: Multiobjective Optimization Problem; Feasible Set Unbounded; Homotopy Continuous Method; Global Convergence

ABSTRACT

In this paper, we propose a homotopy continuous method (HCM) for solving a weak efficient solution of multiobjective optimization problem (MOP) with feasible set unbounded condition, which is arising in Economical Distributions, Engineering Decisions, Resource Allocations and other field of mathematical economics and engineering problems. Under the suitable assumption, it is proved to globally converge to a weak efficient solution of (MOP), if its x-branch has no weak infinite solution.

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)

where

and

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

.

and

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, , ,

,

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

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

To solve (2), the homotopy mapping H is given by [7] as follow:

(3)

where

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 , 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

and. Take and

. Let,. Then is a weak solution at infinity for MOP as. For any given, there exist and, when satisfying

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

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

Lemma 3.1 If the conditions (A) and (B) of Theorem 3.1 holds, then for almost all0 is a regular value of and consists of some smooth curves. Among them, a smooth curve starts from.

Proof: For any,

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

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:

Thus, we have.

The properties of norm imply the following equality holds, that is, given a start point, for any, we have

.

Indeed

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

Taking and, we have

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,

As and as, hence, for any sufficient large k, there exists such that

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

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

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

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

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

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

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)

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

.

Second, we assume that. There also exists a sequence such that

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.

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.

REFERENCES

1. A. Charne and W. W. Cooper, “Management Models and Industrial Application of Linear Programming,” Wiley Press, New York, 1961.
2. G. Fandel and T. Gal, “Multiple Criteria Decision Making: Theory and Applications,” Springer-Verlag Press, New York, 1980. doi:10.1007/978-3-642-48782-8
3. C. B. Garcia and W. I. Zangwill, “Pathways to Solutions, Fixed Points and Equilibria,” Prentice-Hall, Englewood Cliffs, 1981, pp. 475-495.
4. N. Megiddo, “Pathways to the Optimal Set in Linear Programming,” In: N. Megiddo, Ed., Progress in Mathematical Programming Interior Point and Related Methods, Springer, New York, 1988, pp. 131-158.
5. 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.
6. Z. H. Lin, B. Yu and G. C. Feng, “A Combined Homotopy Interior Point Method for Convex Nonlinear Programming Problems,” Applied Mathematics and Computation, Vol. 84, No. 2-3, 1994, pp. 193-211. doi:10.1016/S0096-3003(96)00086-0
7. 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, 1997, pp. 209-224. doi:10.1016/0096-3003(95)00295-2
8. Z. H. Lin, D. L. Zhu and Z. D. Sheng, “Finding a Minimal Efficient Solution of a Convex Multiobjective Program,” Journal of Optimization Theory and Applications, Vol. 118, No. 3, 2003, pp. 587-600. doi:10.1023/B:JOTA.0000004872.93803.09
9. W. Song and G. M. Yao, “Homotopy Method for a General Multiobjective Programming Problem,” Journal of Optimization Theory and Applications, Vol. 138, No. 1, 2008, pp. 139-153. doi:10.1007/s10957-008-9366-6
10. T. Maeda, “Second-Order Conditions for Efficiency Nonsmooth 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
11. L. T. Watson, “Globally Convergent Homotopy Algorithms for Nonlinear Systems of Equations,” Nonlinear Dynamics, Vol. 1, No. 2, 1990, pp.143-191. doi:10.1007/BF01857785
12. G. C. Feng, Z. L. Lin and B. Yu, “Existence of an Interior Pathway to a Karush-Kuhn-Tucker Point of a Nonlinear Programming Problem,” Nonlinear Analysis, Vol. 32, No. 6, 1998, pp. 761-768. doi:10.1016/S0362-546X(97)00516-6
13. Q. Xu, B. Yu and G. C. Feng, “Homotopy Methods for Solving Variational Inequalities in Unbounded Sets,” Journal of Global Optimization, Vol. 31, No. 1, 2005, pp. 121-131. doi:10.1007/s10898-004-4272-4
14. Q. Xu, B. Yu, G. C. Feng and C. Y. Dan, “Condition for Global Convergence of a Homotopy Method for Variational Inequality Problems on Unbounded Sets,” Optimization Methods and Software, Vol. 22, No. 4, 2007, pp. 587-599. doi:10.1080/10556780600887883
15. C. Y. Lin and J. L. Dong, “Methods and Theories in Multiobjective Optimization,” Jilin Education Press, Changchun, 1992.
16. 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.
17. G. L. Naber, “Topological Methods in Euclidean Space,” Cambridge University Press, London, 1980.