The Aggregate Homotopy Method for Multi-objective Max-min Problems

Published Online March 2011 in MECS

Homotopy method(or path-following method) is a developing and important method of global convergence to resolve Multi-objective programming problem emerged at the end of 20th century. At first, homotopy method played a very important roll in algebra equations, zero and fixed points[1], and existence theorem[2]. In 1988, Megiddo[3] and Kojima et al. [4] discovered that the attractive Karmarkar interior point method for linear programming was a kind of path-following method. Since then, the homotopy method for mathematical programming has become an active research field. Reference [5-8] presented a new interior point method— combined homotopy interior point method (CHIP method)—for nonlinear programming under cone condition, quasi-normal cone condition and pseudo cone condition. In 2003, Z.H. Lin and Z. P. Sheng [9] transformed the multi-objective programming problem into single-objective programming problem through linear weighted technique, generalized the CHIP method to convex multi-objective programming (MOP) problems. In this work, we presented a new transformation method (Max-min method) which was different from that used in reference [9]. Because the obtained single-objective programming problem after this transformation was nonsmooth, we need to search for a new method (different from that of [9]) to solve this problem.

Consider the following multi-objective programming problem min f (x)

( MOP ) [            ,

[ s.t g ( x ) <  0

where x e K * , f = ⁽ f,f ,,•••, f p ) T , g = ⁽ g i, g ₂, L , g m ) T

Let Q = {x e R" | gj (x) < 0, j e M} be the feasible set, and Q0 = {x e R" | gj (x) < 0, j e M} be the strictly feasible set. dQ = Q \ Q0 is the boundary set, I(x) = {j e{1 2, L, w' gj(x) = 0} is the active index set, x o У = (x1 У1, x 2 У 2, L, x„yn ) T

,

Л⁺ = { Ae R P | A i >  0, i = 1,2, - , p , £ A i = 1 } , i = 1

Л⁺⁺ = { A e R P | A i >  0, i = 1,2, - , p , £ A i = 1 }

P = {1,2, - , p }, M = {1, 2, - , m }, e = (1, 1, ^ ,1) T e R^p .

For MOP problems, each efficient solution of Q is equivalent to the existence of a vector A e Л⁺ , such that the solution is optimal for the program

[ min A f ( x ), — , A f ( x )[

( MOP 1) [      ^{        , ’ ^{pJp }}} .

[ s.t g ( x ) <  0 x e R "

Hence, there exists a minimal efficient solution set such that each point in this set is optimal for the problem MOP1 , V A e Л⁺ ,see the definition below.

Definition 1.1[10] (x*, A) is a minimal weak efficient solution of MOP1 if (x*, A) a solutions of the problem min {A fv (x),L, Apfp (x)}

( MOP 2) <

s.t g ( x ) <  0 x e R "

£ A i = 1, A i >  0

i = 1

Let F ( x , A ) = max A i f i ( x ) , G ( x ) = max g j ( x ) and 1 < i <  p                                 1 < j <  m

MOP 2 is equivalent to

( MOP 3) <

min F ( x , A )

s.t G ( x ) <  0

p

£ A i = 1, A > 0

. i = 1

So the optimistic solutions of MOP 3 is minimal weak efficient solution of MOP 1 .

Because MOP3 is a single-objective strained optimization problem, it is more simple than that in [9]. But F (x, A) = max A f, (x) and G (x) = max g; (x) are 1

• II.    Preleliminaries

The following are four assumptions used in the literature:

(H1) f ( i e P ), g j ( j e M ) are three continuously differentiable convex functions

(H2) Q 0 is nonempty and bounded;

(H3)   Vx e дQ,   {Vgj (x) (j e I(x))}   is linearly independent.

(H4) (The weak normal cone condition) There exists a nonempty closed subset Q of Q 0 , V x e дQ the cone of Q at x that does not meet Q , i.e.

< x + ^ u j V g j ( x ), u j >  0, 1 I S = ф

I       j e I ( x )                                 J

Let

F ( x , 2 , 0 t ) = 0 t ln ^ exp

i = 1

G ( x , 0 t ) = 0 t ln £ exp j = 1

2 f ( x )

0 t

g_j ( x )

0 t

V x G ( x , 0 t ) = $>/ x , t ) V g j ( x ), j = 1

Q₀ ( t ) = { x e R"\g ( x, 0 t ) <  0 }

Q0(t) = {x e RnG(x, 0t) < 0}, д' (t) Q. (t )\ Q0( t), л             1    , x    exp( gj(x)/0t)

0e ( 0,1 ] , and y j ( x , t ) = —----------------(1.1)

Z exp( g j (^x )/ ^{0 t} ) j = 1

Lemmn2.1 For a given 0 e ( 0,1 ] , we have

• (1)    G ( x, 0 t 1 ) <  G ( x , 0 t ₂) (0 <  t 1 <  1 ₂ <  1);

F ( x , 2 , 0 t 1 ) <  F ( x , 2 , 0 t ₂) (0 <  1 1 <  1 ₂ <  1);

• (2)    G ( x ) <  G ( x , 0 t ) <  G ( x ) + 0 t ln m ;

F ( x , 2 ) <  F ( x , 2 , 0 t ) <  F ( x , 2 ) + 0 t ln p

Remark2.1. For a given 0 e ( 0,1 ] , as t ^ 0 + , G ( x , 0 t ), F ( x , 2 , 0 t ) converge uniformly as well as monotonically to G ( x ) and F ( x , 2 ), respectively.

Lemme2.2 From(1.1), y_j ( x , t ) has follow results:

(1) y j (x , t ) > 0, and ^ y ( x , t ) = 1;

j = 1

• (2)    For x e Q ⁰ , x ^ x e дQ , as t ^ 0 ⁺ , j £ I ( x ) we have y j ( x , t ) ^ 0 .

Lemmn2.3 if the assumed condition of (H1) is satisfied, then F ( x , 2 , 0 t ) and G ( x , 0 t ) should be three continuously differentiable convex functions

Lemmn2.4 if the assumption conditions of (H1) and (H2) are satisfied, then (1) any 0 e ( 0,1 ] , t e ( 0,1 ] has Q ₀ ( t ) c Q ; (2) for any closed subset Q cQ ⁰ , there exists a 0 e ( 0,1 ] , s.t Q cQ 0 (1).

Lemmn2.5 if the conditions of (H1)~(H3) are satisfied, there exists a 0 e ( 0,1 ] , s.t any t e ( 0,1 ] , дQ₀ ( t ) is the regularity, i.e., V x e дQ₀ ( t ), V _xG ( x , 0 t ) * 0.

Lemmn2.6 if the assumption conditions of (H1), (H2) and (H4) are satisfied, then for any closed subset Q c Q , there exists a 0 e ( 0,1 ] , s.t. any t e ( 0,1 ] , Q ₀ ( t ) is satisfied with the weak normal cone condition about Q .

The proof of Lemma 1.1~Lemma 1.6 are referred to [11-12].

Definition 2.1 Let M , N be differential manifolds with dim N = p and let H : M ^ N be a differentiable mapping. If rank( 5 H ( x ) / 6 x ) = p , V x e H - ( y ), we say that that y e N is a regular value of H and x e M is a regular point. Given a curve Г c H ^{- 1}( y ), if every x er is a regular point, then we say that Г is a regular path.

Lemma 2.7 (Parametric Form of the Sard Theorem on a Manifold with Boundary) Let Q and N be differential manifolds of dimension q and p , respectively. Let M be a m -dimensional differential manifold with boundary. Suppose that ф : Q x M ^ N is a C r mapping, where r >  max { 0, m - p } . If 0 e N is a regular value of ф and 5Ф , then for almost all a e Q , 0 is a regular value of ф a =ф ( a , • ) and дф a , where 5ф , дф a denote the restriction of ф and ф a to Q xd M and д M , respectively.

This lemma is a special case of the transversality theorem (Theorem 5.7 in [13]).

Lemma 2.8 (Inverse Image Theorem, See [13,14]) Suppose that M is a m - dimensional C r differential manifold with boundary, N is a p - dimensional C^r differential manifold, r >  1, and ф : M ^ N is a C r map. If a e N is a regular value of ф and дф , then either S = ф^{- 1} ( a ) is empty or a ( m - p ) dimensional submanifold, and д S = S I д M .

Lemma 2.9 (classification theorem of one-dimensional manifold with boundary, see [14] ) Each connected part of a one-dimensional manifold with boundary is homeomorphic either to a unit circle or to a unit interval.

• III.    Main Results

In order to find the solution of MOP3 , we turn it into problems as follows by means of aggregate functions： min F (X, X,et)

( MOP 4) <  s.t G ( x , G t ) <  0

p

£ X i = 1, X i >  0

. i = 1

Let x , X be a KKT point of MOP 4 , Then there exist u e R ₊ , § e R + , and h e R , such that

'v _xf ( x , x , e t ) + u v _xg ( x , e t ) = 0

V X F ( X , X , e t ) - § - h ■ e = 0

1 - £ X = 0

• •              ^{£ 1}                       (3.1)

uG ( X , e t ) = 0

§ o X = 0

_ X >  0, § >  0, u >  0, G ( X , e t ) <  0

Remark 3.1 From Lemmn1.1, we know that the KKT point of equation (3.1) is convergence to optimistic solutions of MOP 3 , so that it is a minimal weak efficient solution of MOP1 as t ^ 0 ⁺ .

Therefore, to find a minimal weak efficient solution, we have to solve problem (3.1) as t ^ 0 ⁺ .

Now we construct a homotopy mapping as follows:

H : Q ⁰ x Л⁺⁺ x R ₊₊ x R p ₊ x R x ( 0,1 ] ^ R n ⁺ 2 p ^{+ 2}

H ( w , w ⁽⁰⁾, t )

" (1 - 1 ) [ V _XF ( x , X,et ) + u V _XG ( x ,e ) ] + 1 ( x - x ⁽⁰⁾)

(1 - 1 ) [ V X F ( X , X , et ) - § ] - ( h - h ⁽⁰⁾) ■ e + 1(X - X^w )

p

1 -£ X i=1

uG ( x ,et ) - tu ⁽⁰⁾ g ( x ⁽⁰⁾, e )

§ X - t§ ^<0) o X^<0)

= 0

(3.2)

Because of x ⁰ e Q ⁰ , it must be a e , s.t. X ⁰ e Q e (1).

Let w = (x, X, u, §, h)T e Rn+2p+2

w ⁽⁰⁾ = ( x ⁽⁰⁾, X ^<0), u ⁽⁰⁾, § ^<0), h ⁽⁰⁾) T eQ e (1) xЛ⁺⁺x R ++ x R + p + x { 0 } .

When t = 1, the homotopy equation (3.2) becomes

J - ^X '"’=⁰

- ( h - h ⁽⁰⁾) ■ e + ( X - X ^<0)) = 0

p

• <         1 - £ ^x i = 0                    ^(3.3)

uG ( x , e ) - u ⁽⁰⁾ g ( x ⁽⁰⁾, e ) = 0 § o X - X^{й 0} o x ^<0) = 0

We have x = x ⁽⁰⁾ , u = u ⁽⁰⁾ , h = h ⁽⁰⁾ = 0, X = X ^<0), § = § (⁰ . Thus, the equation H ( w , w ⁽⁰⁾ ,1) = 0 has only one solution w = w ⁽⁰⁾ .

When t ^ 0 ⁺ , the solution of (3.2) is the KKT point of (3.1) as t ^ 0⁺.

For a given w ^{( 0 )} , rewrite H ( w , w ⁽⁰⁾ , t ) as H_w (0) ( w , t ). The zero-point set of H_w (0) is

H ^CC) = {( w , t ) | H w _w( w , t ) = 0}.

Since H ( w ⁽⁰⁾ , w ⁽⁰⁾ , t ) = 0 , we have H w - 1 ₀₎ (0) * ф .

Lemma 3.1 . Let H be defined as (3.2), let the conditions (H1)-(H3) hold. Then for almost all w ⁽⁰⁾ e Q ⁰ x Л⁺⁺ x R ₊₊ x R + ₊ x {0}, 0 is a regular value of H ( w , w ⁽⁰⁾ , t ) , and H w_₀) (0) consists of some smooth curves. Among them, a smooth curve, say Г w _{( 0 )} , is starting from ( w ⁽⁰⁾ ,1).

Proof: For any w(0) e Q0 x Л++ x R++ x R ++ x {0} and t e (0,1], we have dH (w, w(0), t)/d( X(0), x<0), X, u(0), §<0))

	'- tE n	0	Q ( X , X )	0	0 "
	0	- tE P	R ( x , X )	0	0	(3.4)
=	0	0	- 1	0	0
	Z 1	0	0	Z 2	0
	_ 0	- t e	§ 1 e p	0	- t Л
Where

Q ( X , X ) = (1 - 1 ) — ( V x F ( X , X , e t )), d X 1

R ( x , X) = (1 -1) — (V xF ( x , X, et)), dX zx =-tu(0)v (0)gt(x(0),e), z2 =-tG(x(0),e\ x e = diag(§(0)), Л = diag(X(0)), ep = (1,0, l ,0)T e Rp.

d H ( w , w ⁽⁰⁾, t ) d ( X ⁽⁰⁾, X ^й0, Л , u ⁽⁰⁾, § ^<0))

- ( - 1 ) n ^{+2 p +1} J p J x⁰⁰⁰ g ( x ⁽⁰⁾, e ) * 0 i = 1

Since X (⁰ >  0 ( i e P ),   G ( x ⁽⁰⁾ , e ) <  0 ( X ⁽⁰⁾ e Q e (1)) , 0

is a regular value of H ( w , w ⁽⁰⁾ , t ). According to

Parameterized Sard Theorem on smooth manifold, lemma 2.7, 0 is a regular value of mapping H w(0) for almost all w(0) e Qe (1) x Л++ x R++ x R++ x {0} . By the inverse image theorem2.8, H^-(10,(0) consists of some smooth curves. Because Hw(0) (w(0),1) = 0, there must be a smooth curve Гw(0) starting from (w(0), 1).

Lemma 3.2 Conditions of Lemma 3.1 and (H4) are satisfied. For a given w ⁽⁰⁾ e Q ⁰ xЛ⁺⁺ x R ₊₊ x R + ₊ x {0}, 0 is a regular value of H w ₍₀₎ , then Г w ₍₀₎ is a bounded curve in Q ⁰ xЛ⁺⁺x R ₊₊x R p + x R x (0,1].

Proof: From (3.2), it is easy to see that Г c Q ⁰ xЛ⁺⁺x R x R P x R x (0,1]. If Г ™ is an w (^{0)                         ++     ++}                             w ⁽⁰⁾

unbounded curve, then there exists a sequence of points {(w(k), tk)} сГw(0) such that ||(w(k), tk )|| ^да. Because Q0 xЛ++ and t e (0,1] are bounded sets, therefore there exists a subsequence of point {(w(ki), tk )} (for brevity, we will use k instead of ki in the rest part of this paper) such that x(k) ^ x e Q , 2(k) ^ Я e Л+ , tk ^ t e (0,1], and

I(u(k),jk),h(k))|рда , as k > / . (3.5) i) It is impossible of h(k) ^ да, ^k ^ да , as k ^ да that we can refer to theorem 5.2.2 in the book [15]

• ii)    If u ^{( k} ) ^ +да , from the fourth equality of (3.2), we have G ( x ^{( k} ) , 9t) ) = t_k ( u ^{( k )}) ^{- 1} u ⁽⁰⁾ G ( x ⁽⁰⁾, 9 ) ^ 0, i.e.

lim G ( x ^{( k}\ 9 t_k ) = G ( x , 9) ) = 0. k ^+да

From Lemma 2.5, we know V _xG ( x , 9 t ) * 0 .

From the first equality of (3.2), we have

(1 - t_fc ) [ V, F ( x ^{( k} ) , Я^k ) , 9t ^{( k} ) ) + u ^{( k} ) V, G ( x ^{( k} ) , 9t ^{( k} > )]

kx                  x(3.6)

+ t_k ( x ^{( k} ) - x ⁽⁰⁾) = 0

For t = 1, when k ^ да , lim(1 - tk)u(k)VxG(x(k),9tk) + x(k) - x(0) = 0

k "

Let lim(1 - t k ) u ^{( k} ) = a , thus k ^да

x(0) = a + x(3.8)

When a = 0    ,    (3.8) contradicts with

Q9(1) э x(0) * x e 8Q9(1); when a > 0 , (3.8) contradicts with Lemma2.6.

For t <  1, rewrite (3.6) as

(1 - t_k ) V _xF ( x ^{( k} ) , Я ^k ) , 9 t ^{( k} ) ) + (1 - t k ) u ^{( k} ) V _xG ( x ^{( k} \9t ^{( k} ) )

+ t k ( x ^{( k} ) - x ⁽⁰⁾)

= 0

(3.9)

As k ^ да , the second part at the left-hand side of (3.9) tends to infinity, but the first and third parts are bounded. This is impossible.

From i), ii) we conclude that Г w ₍₀₎ is bounded.

Theorem 3.1 ( convergence of the method). If conditions of H1~H4 are satisfied, then (3.1) has at least one solution.

For almost all w ⁽⁰⁾ e Q ⁰ x Л^{+ +} x R ₊₊ x R + ₊ x {0}, the zero-point set H w - 1 0) (0) of homotopy mapping (3.2) contains a smooth curve Г , , which starts from w (0)

( w ^{( 0 )}, 1 ) . The limit set T c Q x Л⁺ x R ₊ x R + x R x {0} of Г w ₍₀₎ is non-empty as t ^ 0 ⁺ , and every point in T is a solution of (3.1).

Specifically, if the length of Г w ₍₀₎ is finite and ( w * , 0) is the end point of Г w , ₀₎ , then w * is a solution of (3.1).

Proof ： By Lemma 3.1, 0 is a regular value of H _w (0) , and H w₀₎ (0) contains a smooth curve Г w ₍₀₎ starting from ( w ^{( 0 )}, 1 ) , for almost all w ⁽⁰⁾ e Q ⁰ x Л⁺⁺ x R ₊₊ x R + ₊ x {0}.

By the classification theorem of one-dimensional smooth manifold,, lemma 2.9, Г w ₍₀₎ is diffeomorphic to a

unit circle or the unit interval (0, 1]. Noticing that "     En         0       0      0 0 0        E      0     0 - e dHw.0>( w, t) = 0        - eT      0      0 0 dw w=w(0) t=1 u V xGT (x(0), 9)    0    G (x (0),9) 0 0 _      0         9      0     Л 0 is nonsingular, we know that Гwk) is not diffeomorphic to a unit circle. That is, Гw(0) is diffeomorphic to (0, 1].

Let ( w , t ) be a limit point of Г w ₍₀₎ as t ^ 0 . Only the following three cases are possible:

• i)    ( w , I ) eQ ⁰ xЛ⁺⁺x R ₊₊x R ₊ ^p ₊x R x {1};

• ii)    ( w , I ) e d ( Q x Л⁺ x R ₊ x R ₊ ^p ) x R x (0,1 ] ;

• iii)    ( w , t ) e Q x Л⁺ x R ₊ x R + x R x {0} .

Because the equation Hw(0) (w, 1) = 0 has only one solution (w(0),1) e Q0 xЛ++xR++xR++ xR x{1}, the case (i) is impossible. In case (ii), there must exist a sequence of (w(k), t,) e Г such that G(x(k), 9t,) ^ 0 . From the k        w(0)                                  k fourth equality of (3.2), we have u(k) ^+да , which contradicts Lemma 3.2.

As a conclusion, (iii) is the only possible case, and hence, w is a solution of (3.1).

Remark3.2 By Theorem 3.1, for almost all w ⁽⁰⁾ e Q ⁰ x Л⁺⁺ x R ₊₊ x R ₊ ^p ₊ x {0}, the homotopy (3.2) generates a smooth curve Г w ₍₀₎ . We call Г w ₍₀₎ as the homotopy path. Tracing numerically Г w ₍₀₎ from ( w ⁽⁰⁾,1) until t ^ 0⁺, one can find a solution of (3.1). Let s be the arclength of Г w , ₀₎ , we can parameterize Г w , ₀₎ with respect to s . That is, there exist continuously differentiable functions w ( s ), t ( s ), such that

H w ₍ 0) ( w ( s ), t ( s )) = 0,                    (3.10)

w (0) = w ⁽⁰⁾, t (0) = 1              (3.11)

Differentiating (3.10), we obtain the following theorem.

Theorem 3.2 The homotopy path Г w ₍₀₎ is deter-mined by the following initial value problem to the ordinary differential equation

^d H w (0) ⁽ w ^{( 5} ', t ^{( 5} ') ( w ( 5 )

Step 3: If w ^{( k + 1)} e Q x Л⁺ x R ₊ : let k = k + 1, go to Step 1.

If w ^{( k + 1)} eQx\ ' x R ₊x R p x R

^x R + p ^{x R} and t_{k + 1} >  S 3 ,

d ( w , t )

^{t ( 5} )

= 0

(3.12)

|| w ( 5 ), t ( 5 )|| = 1 w (0) = w ⁽⁰⁾ , t (0) = 1.

And the w component of the solution

(3.13) point

d k ^: = d k - t_k

tk

^k _, go to Step tk + 1

and t k + 1 < S let

2 and re-compute

( w ( 5 * ), t ( 5 * )) of (3.10), for t ( 5 * ) = 0 , is the solution of

(3.1).

IV. Tracing The Homotopy path

In this section, we discuss how to trace numerically the homotopy path Г . A standard procedure is the co ⁽⁰ )

predictor-corrector method[16], which uses an explicit difference scheme for solving numerically and a simple numerical example is given.

Algorithm 4.1 (MOP)'s Euler-Newton method).

Step 0: Give an initial point

(w(0), 1) e Q0 x Л++ x R++ x Rp+ x R x {1}, an initial step-length d0 > 0 and three small positive numbers s1, s2, s3. let k := 0

Step 1: Compute the direction ? ^{( k} ’ of predictor step:

• (a)    Compute a unit tangent vector Z^(k’ e R n ^{+ 2 p + 3} of

Г „ .0, ^at o ^{k )}, t k ) ;

• (b)    Determine the direction ? ^{( k 1} of the predictor step.

( ( k^{k + 1 )} , t_{k + 1}) for the initial point ( to k^{k )} , t_k ) .

If w ^{( k + 1)} gQxЛ⁺x R ₊ x R p x R , let о - d k    t k

^{+     +}                   k : =                  ,

² t k ^- t k + 1

go to Step 2 and re-compute ( o (⁽ k ^{+ 1 )} , t_{k + 1}) for the initial point ( o (^{( k )} , t k ) .

If w ^{( k + 1)} e Q x Л⁺ x R ₊ x R + x R and t_{k + 1} <  _S 3 , then stop.

Remark4.1 In Algorithm 4.1, the arclength parameter s is not computed explicitly. The tangent vector at a point on Г has two opposite directions, one ⁽⁰'

( the positive direction ) makes s increase, and another ( the negative direction ) makes s decrease, The negative direction will lead us back to the initial point, so we must go along the positive direction. The criterion in Step 1 (b) of Algorithm 4.1 that determines the positive direction is based on a basic theory of homotopy method [17], that

If the sign of the determinant

DH ( 0 ) ( O )^{( k}\ t k )

Z< k ) ^T

is

is, the positive

Г _{о (0)} keeps DH^ ® , t )

T

?

proposition.

Proposition

direction ? at any point ( ® , ц ) on the sign of the determinant

invariant. We have the following

4.1 If Г ₍₀₎ is a smooth curve of

CO '°'

( - 1 ) p , then ?^{(k )} = Z ^{( k}k

H o ⁽⁰⁾

¹ (0). Then the direction ? ⁽⁰⁾ of the predicted step at

If the sign of the determinant

DH^ ^k \ t k ) Z< k) ^T

the initial point ( o / ^{0 )} , 1) satisfies

is

sign

DH u o ,1)

( - 1 ) p , then ?^(k ’ =- Z^{(k )}

Step 2: Compute a corrector point ( co ^{( k + 1)} , t_{k + 1}):

(co ⁽ ' , t k ) = ( co)^k ' , t_k ) + d_k?^(k ' ,

( co ^{( k + 1)} , t , ₊.) = ( o^(k',"tk ) - DH ("co'^k',"tk ) ⁺ H(O^(k ' , "tk ), ' k + 1 X                 ' '             CO ('

where

DH _{ш (0)}( co) t ) ⁺ = DH _{ш (0)}( co) t ) ^T ( DH _{ш (0)}( co) t ) DH _{ш (0)}( ® , t ) ^T ) ^{- 1}

is the Moore-Penrose inverse of DH ,₀,( ю t ).

CO ( '

? ^{(0) T}

= ( - 1 ) p ^.

Proof : From

DH (0, ( ® ⁽⁰⁾,1) =

‘       E n	0	0	0	0	a
0	Ep	0	0	- e	в
0	T - e	0	0	0	0
u V xG ( x (0), У )	0	G ( x (0), 9 )	0	0	u (0) G ( x (0), 9 )
_         0	9	0	Л	0	Y

= ( M 1 M 2 )

^If ||я ( ® ^{( k +1)}, t k ₊ 1 )|| <  S 1 , ^let d k + 1

= min { d ₀,2 d_k } , go

to Step 3.

^If H _o ,0, ( o- ^{k + 1)} , t k + 1)||e ( S 1 , S 2 ), ^let d k + 1 = d k ,go ^to Step 3.

^If| H ^C ... ^{k + 1)} , t k + 1 '|| >  S 2^{, let} d k + 1 = max b^{- 25} d 1 d k I ,

go to Step 2.

a = -V _xF ( x ⁽⁰⁾, Я ⁽⁰⁾, 9 ) - u ⁽⁰⁾ V _xG ( x ⁽⁰⁾, 9 )

в = -V ^ F ( x ⁽⁰⁾, Я ⁽⁰⁾, 9 ) - г""' , у = ^ ⁽⁰⁾ ° ^⁽⁰⁾

M e R ( n ^{+ 2} p ^{+ 2) x} ( n ^{+ 2} p ^{+ 2} ' M e R ( ^{n + 2} p ^{+ 2} ' ^{x 1}

M 1 is nonsingular and M ₂ ^ 0. the unit tangent vector Z (0) of Г _{о (0)} at ( o /⁰⁾ ,1) satisfies

( M 1

Л „от л

^{Z 1}

_ (0)

= 0 , Z^ е R ^{n + 2} p ^{+ 2} , Z? e R .

Define we have

(0)           (0)      (0) T

Z = ( Z 1 , Z 2 ) , by a simple computation,

„<^0,        iT-hT >-<^0,

£ 1   = ^{- M} 1 ^M 2 ^Z 2 ,

p

I M 1| = ( - 1) p ^{+ 2} G <  x ⁽⁰⁾, У ) P П A .

i = 1

Hence

/)//( .!>

^ ( T

M ₁

-

- m T m 1 ^{- T}

M 1

( 0 ) ^T

M 2

( 0 ) ^T

min f = min {f., f,} f1 (x) = 2x12 + (x2 -1)2 + 3x32

f 2 ( x ) = ( x 1 + x ₂ + x ₃ - 1.0)²

5.t g 1 ( x ) = x 1 + x ₂ + x ₃ - 3

g ₂ ( x ) = 2 x 1 + 2 x ₂ + x ₃ - 4

g 3 ^{( x} ) = ^x 1 ^{- x} 2

g 4 ^{( x} ) = ^{- x} 1

g 5 ^{( x} ) = ^{- x} 2

g 6 ^{( x} ) = ^{- x} 3

M 1 0

M ₂

M ₂

（ 0 ）

^Z 2

1 + m T m 1 - ^tm 1 ^{- 1} m 2

-

= | M 1 1 (1 + M ₂ ^TM 1 ^{- T}M 1 ^{- 1} M ₂ ) Z

Because G < x ⁽⁰⁾, У ) <  0 and by the definition of the

direction of the predictor step, n ₂ <  0 and

( 1 + m T m 1 ^{- T}m 1 ^{- 1} m ₂ ) > 0

sign M ₁

TABLE I.

N umerical S imulation R esults of E xapmle 4.1

A <0)	x	A
(1/2, 1/2)	(0.0009,0.9992,0.0009)	(0.4871,0.5129)
(1/3, 2/3)	(0.0013,0.9984,0.0013)	(0.3195,0.6805)
(2/3, 1/3)	(0.0009,0.9995,0.0009)	(0.6560,0.3440)
h *	г	* u
-0.0001	(0.0001, 0.0001)	0.0034
-0.0002	(0.0002, 0.0002)	0.0035
-0.0002	(0.0002, 0.0002)	0.0041

p

= sign ] ( - 1) ^{p + 2} G < x ⁽⁰⁾, У ) P П A ^ = ( - 1 )

i = 1

p + 1

So

sign

DH ( ,.

n ^{(0) T}

= ( - 1 ) ^p .

As a conclusion, using aggregate homotopy method to solve convex multi-objective programming problems is a new approach. The multi-objective programming problem with multi-strains was transformed into singleobjective programming problem with single strain, then the aggregate homotopy method was used to get the minimal weak efficient solution. This method is simple, convenient and of great relevance to applications. It must be pointed out that for the non-convex multi-objective programming problems, more extensive work are needed.

In the following, we have tested the homotopy method by a simple numerical simulation. Let ( x^,x 2 ⁰⁾, x D = <0.1,1.0,0.1) , ( _ /". _ /") = (2.0,2.1) , h ⁽⁰⁾ = 0.0, u ⁽⁰⁾ = 1.6and _S 1 = 0.01, s ₂ = 1.0, S 3 = 10 ^{- 3} .

Acknowledgment

The numerical results of x * , A , h * , ^ *, u * , are listed in Table I. These results are computed by double precision.

Example 4.1

This work was supported by the NNSF(10771020) of China and National, the NNSF(20101599) of Jilin province.