# Homotopy Method for a General Multiobjective Programming Problem under Generalized Quasinormal Cone Condition

Authors: X. Zhao; S. G. Zhang; Y. T. Yang; Q. H. Liu
Journal: Abstract and Applied Analysis
 (2012)

---

## Abstract

A combined interior point homotopy continuation method is proposed for solving general multiobjective programming problem. We prove the existence and convergence of a smooth homotopy path from almost any interior initial interior point to a solution of the KKT system under some basic assumptions.


---

## Body

## 1. Introduction

In this paper, for any two vectorsy=(y1,y2,…,yn)T and z=(z1,z2,…,zn)T in Rn, we use the following conventions:
(1.1)y=z,iffyi=zi,i=1,2,…,n;y<z,iffyi<zi,i=1,2,…,n;y≦z,iffyi≤zi,i=1,2,…,n;y≤z,iffyi≤zi,y≠z,i=1,2,…,n.We consider the following multiobjective programming problem:(MOP)(1.2)minf(x),s.t.g(x)≦0,h(x)=0,
where f=(f1,f2,…,fp)T:Rn→Rp, g=(g1,g2,…,gm)T:Rn→Rm, and h=(h1,h2,…,hs)T:Rn→Rs.Forλ=(λ1,λ2,…,λp)T∈Rp, let R+n and R++n denote the nonnegative and positive orthant of Rn. Respectively, let
(1.3)Ω={x∈Rn∣g(x)≦0,h(x)=0},Ω0={x∈Rn∣g(x)<0,h(x)=0},∂Ω=ΩΩ0,Λ+={λ∈R+p∣∑i=1p‍λi=1},Λ++={λ∈R++p∣∑i=1p‍λi=1},I={1,2,…,m},J={1,2,…,s},
and let
(1.4)B(x)={i∈{1,2,…,m}∣gi(x)=0}
denote the active index set at a given point.MOP has important application in many practical fields like production planning, structural designing, portfolio selection, and so forth. Research on it can be traced back to Pareto [1], Von Neumann and Morgenstern [2], and Koopmans [3] or even earlier. Especially, more and more attention has been paid to the homotopy method since Kellogg et al. [4], Smale [5], and Chow et al. [6] published the remarkable papers. The homotopy method now becomes an important tool for numerically solving complementary, variational inequalities, convex multiobjective programming, and nonlinear mathematical programming et al. [7–12] as a globally convergent method.Among many methods, the weighed sum method is popular and efficient. It transforms the MOP to a single-objective programming [13]:
(1.5)minλTf(x),s.t.g(x)≦0,∑i=1p‍λi=1,
where λ is the weight vector.Recently, Song and Yao [14] generalize the combined homotopy interior point method to the general multi-objective programming problem under the so-called normal cone condition instead of the convexity condition about the feasible set. In that paper, they proved the existence of the homotopy path under the following assumptions:(A1)
Ω0 is nonempty and bounded;(A2)
for allx∈Ω, the vectors {∇gi(x),i∈B(x),∇hj(x),j∈J} are linearly independent;(A3)
for allx∈Ω, {x+∑i∈B(x)ui∇gi(x)+∑j∈Jzj∇hj(x):zj∈R,ui≥0,j∈J,i∈B(x)}⋂‍Ω={x}.In [14], the combined homotopy method was given as follows:
(1.6)H¯(ω,ω(0),t)=[(1-t)(∇f(x)λ+∇g(x)u)+∇h(x)z+t(x-x(0))h(x)U×g(x)-tU(0)×g(x(0))(1-t)(1-∑i=1pλi)e-t(λ-λ(0))]=0,
where x(0)∈Ω0, u(0)>0, λ(0)>0, and ∑i=1p‍λi(0)=1. However, the solution simply yields λ=λ(0) for all t∈(0,1]. That is, λ is fixed. In fact, from the last equation, we have p(1-t)+(pt-p-t)∑i=1p‍λi+t=0. According to this, we know that λ≡λ0 for all of t∈[0,1].That is, these methods are all solving the single-objective programming problem.In [15], they present the concept of “positive linear independent” and weaken the assumptions than the ones in [14]. But in order to extend their results to a broader class of nonconvex multi-objective programming problems, we construct a new homotopy equation under generalized quasinorm cone condition in this paper and λ is not fixed in the calculation process.The paper is organized as follows. In Section2, we recall some notations and preliminaries results. In Section 3, we construct a new combined homotopy mapping and prove the existence and convergence of a smooth homotopy path from almost any interior initial point to the KKT points of MOP under some assumptions.   In Section 4, numerical results are given,which show that the method is feasible and effective.


## 2.  Some Definitions and Properties

Definition 2.1.
LetU⊂Rn be an open set, and let φ:U→RP be a smooth mapping. If Range[∂φ(x)/∂x]=Rp for all x∈φ-1(y), then y∈Rp is a regular value and x∈Rn is a regular point.Definition 2.2.
Letηi:Rn→Rn(i=1,2,…,m) and βj:Rn→Rn(j=1,2,…,s). For any x∈Ω,{∇gi(x),ηi(x):i∈B(x)} is said to be positive linear independent with respect to β(x), if
(2.1)β(x)z+∑i∈B(x)‍(yi∇gi(x)+uiηi(x))=0,z∈Rs,yi≥0,ui≥0
implies that
(2.2)z=0,yi=0,ui=0(i∈B(x)),
where β(x)=(β1(x),…,βs(x)).Lemma 2.3 (parametric form of the Sard theorem on a smooth manifold; see [16]).
LetQ,N,P be smooth manifolds of dimensions q,m,p. Respectively, let φ:Q×N→P be a Cr map, where r>max{0,m-p}. If 0∈P is a regular value of φ, then for almost all α∈Q, 0 is a regular value of φ(α,·).Lemma 2.4 (inverse image theorem; see [17]).
If 0 is a regular value of the mappingφα(·)≜φ(α,·), then φα-1(0) consists of some smooth manifolds.Lemma 2.5 (classification theorem of one-dimensional manifold; see [17]).
A one-dimensional  smooth manifold is diffeomorphic to a unit circle or a unit interval.The following four basic assumptions are commonly used in this paper:(C1)
Ω0 is nonempty and bounded;(C2)
for anyx∈Ω and t∈[0,1], there exists map η(x) and β(x), such that {∇gi(x),ηi(x):i∈B(x)} is positive linear independent with respect to ∇h(x)+t(β(x)-∇h(x));(C3)
for anyx∈∂Ω,
(2.3){x+∑i∈B(x)‍uiηi(x)+β(x)z:z∈Rs,ui≥0,i∈B(x)}⋂‍Ω={x}
(generalized quasinormal cone condition);(C4)
for anyx∈Ω, ∇h(x)Tβ(x) is nonsingular.Remark 2.6.
IfΩ satisfies the assumptions (A1)–(A3), then it necessarily satisfies the assumptions (C1)–(C4).
In fact, if we chooseη(x)=∇g(x) and β(x)=∇h(x), then it is easy to get the result. Clearly, if Ω satisfies the assumptions (C1)–(C4), then it does not necessarily satisfies the assumptions (A1)–(A3).


## 3. Main Results

Letx∈Ω be a KKT point of MOP; our aim is to find (λ,u,z)∈R+p+m×Rs, such that (3.1a)∇f(x)λ+∇g(x)u+∇h(x)z=0,(3.1b)Ug(x)=0,(3.1c)1-∑i=1p‍λi=0,where ∇f(x)=(∇f1(x),…,∇fp(x))∈Rn×p, ∇g(x)=(∇g1(x),…,∇gm(x))∈Rn×m, ∇h(x)=(∇h1(x),…,∇hm(x))∈Rn×s.Meanwhile, the KKT system of MOP is (3.1a)–(3.1c).For a convex multi-objective programming problem, the solution of the MOP can be obtained from the KKT system. And for a nonconvex multi-objective programming problem, it is significant that we can obtain a solution of the KKT system.To solve the KKT system (3.1a)–(3.1c), we construct a homotopy equation as follows:
(3.2)H(ω,ω(0),t)=[(1-t)(∇f(x)λ+∇g(x)u+tη(x)u2)+[∇h(x)+t(β(x)-∇h(x))]z+t(x-x(0))h(x)U×g(x)-tU(0)×g(x(0))(1-t)(1-∑i=1pλi)e-t(λ5/2-(λ(0))5/2)]=0,
where ω(0)=(x(0),λ(0),u(0),z(0))∈Ω0×Λ++×R++m×{0}, ω=(x,λ,u,z)∈Ω×Rp+m+s, u2=(u12,u22…,um2)T∈Rm, λ5/2=(λ15/2,λ25/2,…,λp5/2)T∈Rp, U=diag(u), e=(1,1,…,1)T∈Rp, and t∈[0,1].Ast=1, the homotopy equation (3.2) becomes (3.3a)β(x)z+(x-x(0))=0,(3.3b)h(x)=0,(3.3c)Ug(x)-U(0)g(x(0))=0,(3.3d)λ5/2=(λ(0))5/2.By the assumption(C3), we get z=0, x=x(0). Since g(x(0))<0 and x=x(0), (3.3c) implies that u=u(0). Equation (3.3d) shows that λ=λ(0). That is, H(ω,ω(0),1)=0 with respect to ω has only one solution ω=ω(0)=(x(0),λ(0),u(0),0).Ast=0, H(ω,ω(0),t)=0 turns to the KKT system (3.1a)–(3.1c).For a givenω(0), rewrite H(ω,ω(0),t) as Hω(0)(ω,t). The zero-point set of Hω(0) is
(3.4)Hω(0)-1={(ω,t)∈Ω×R++p+m×Rs×(0,1]:H(ω,ω(0),t)=0}.Theorem 3.1.
Supposef,g, and h are three times continuous differentiable functions. In addition, let the assumptions (C1)-(C2) hold and ηi,βj twice times continuously differentiable functions. Then for almost all initial points ω(0)∈Ω0×Λ++×R++m×{0}, 0 is a regular value of Hω(0) and Hω(0)-1 consists of some smooth curves. Among them, a smooth curve, say Γω(0), is starting from (ω(0),1).Proof.
Denote the Jacobi matrix ofH(ω,ω(0),t) by DH(ω,ω(0),t). For any ω(0)∈Ω0×Λ++×R++m×{0} and t∈[0,1], we have DH(ω,ω(0),t)=(∂H/∂ω,∂H/∂ω(0),∂H/∂t). Now, we consider the submatrix of DH(ω,ω(0),t).
For any(x,x(0),λ(0),u(0))∈Rn×Ω0×Λ++×R++m,
(3.5)∂H∂(x,x(0),λ(0),u(0))=[Q-tIn00∇h(x)T000U∇g(x)T-tU(0)∇g(x(0))T0-tdiag(g(x(0)))0052t(λ(0))3/2Ip0],
where Q=(1-t)(∑i=1p‍λi∇2fi(x)+∑j=1m‍uj∇2gj(x)+t∑j=1m‍uj2∇ηj(x))+[∇2h(x)+t(∇β(x)-∇2h(x))]z+tIn.
We obtain that(3.6)rank∂H∂(x,x(0),λ(0),u(0))=n+p+m+s.
That is, 0 is a regular value ofH. By parametric form of the Sard theorem, for almost all ω(0)∈Ω0×Λ++×R++m×{0}, 0 is a regular value of Hω(0). By inverse image theorem, Hω(0)-1(0) consists of some smooth curves. Since H(ω(0),ω(0),1)=0, there must be a smooth curve, denoted by Γω(0), that starts from (ω(0),1).Theorem 3.2.
Let assumptions (C1)-(C2) hold. For a given ω(0)=(x(0),λ(0),u(0),z(0))∈Ω0×Λ++×R++m×{0}, if 0 is a regular value of Hω(0), then the projection of the smooth curve Γω(0) on the component λ is bounded.Proof.
Suppose that the conclusion does not hold. Since (0,1] is bounded, there exists a sequence{(ω(k),tk)}⊂Γω(0), such that
(3.7)tk→t*,∥λ(k)∥→∞.
From the last equality of (3.2), we have
(3.8)(1-tk1-tk⋯1-tk)-((1-tk)λ1(k)+(1-tk)∑i≠1λi(k)+tk(λ1(k))5/2(1-tk)λ2(k)+(1-tk)∑i≠2λi(k)+tk(λ2(k))5/2⋯(1-tk)λp(k)+(1-tk)∑i≠pλi(k)+tk(λp(k))5/2)-tk((λ1(0))5/2(λ2(0))5/2⋯(λp(0))5/2)=0.
If we assume ∥λ(k)∥→+∞(k→∞), this hypothesis implies
(3.9){i∈{1,2,…,p}:limk→∞λi(k)=∞}≠Φ.
Sincetk→t*, λ(k)>0, it follows that the second part in the left-hand side of some equations in (3.8) tends to infinity as k→∞. But the other two parts are bounded. This is impossible. Thus, the component λ is bounded.Theorem 3.3.
Letf,g, and h be three times continuous differentiable functions. In addition, let the assumptions (C1)–(C4) hold and ηi,βj twice times continuously differentiable functions. Then, for almost all of ω(0)∈Ω0×Λ++×R++m×{0}, Hω(0)-1(0) contains a smooth curve Γω(0)⊂Ω×R+p×R+m×Rs×(0,1], which starts from (ω(0),1). As t→0, the limit set T×{0}⊂Ω×Λ+×R+m×Rs×{0} of Γω(0) is nonempty and every point in T is a solution of the KKT system (3.1a)–(3.1c).Proof.
From the homotopy equation (3.2), it is easy to see that Γω(0)⊂Ω×R+p×R+m×Rs×(0,1]. By Theorem 3.1, for almost all ω(0)∈Ω0×Λ++×R++m×{0}, 0 is a regular value of Hω(0) and Hω(0)-1 contains a smooth curve Γω(0) starting from (ω(0),1). By the classification theorem of one-dimensional smooth manifolds, Γω(0) is diffeomorphic to a unit circle or the unit interval (0,1].
Noticing that(3.10)|∂Hω(0)(ω(0),1)∂ω|=|In00β(x(0))∇h(x(0))T000U(0)∇g(x(0))T0diag(g(x(0)))00-52(λ(0))3/2Ip00|=(-1)s|diag(g(x(0)))||-52(λ(0))3/2Ip||∇h(x(0))Tβ(x(0))|.
Becauseg(x(0))<0, λ(0)∈Λ++ and by the assumption (C4), we know that [∂Hω(0)(ω(0),1)/∂ω] is nonsingular. Therefore, the smooth curve Γω(0) starts from (ω(0),1) diffeomorphic to (0,1].
Let(ω*,t*) be a limit point of Γω(0); only three cases are possible:(a)
(ω*,t*)∈Ω×Λ+×R+m×Rs×{0};(b)
(ω*,t*)∈∂(Ω0×R+p+m)×Rs×(0,1];(c)
(ω*,t*)∈Ω×R+p+m×Rs×{1}.
BecauseH(ω(0),ω(0),1)=0 has a unique solution (ω(0),1), the case (c) will not happen.
In case (b), becauseΩ and (0,1] are bounded sets and by the assumption (C2), for any x∈Ω and t∈[0,1], there exists map η(x) and β(x) such that, {∇gi(x),ηi(x):i∈B(x)} is positive linear independent with respect to ∇h(x)+t(β(x)-∇h(x)). From the first equation of (3.2), we get that the component z of Γω(0) is bounded.
If case(b) holds, then there exists a sequence {(ω(k),tk)}⊂Γω(0), such that
(3.11)∥(ω(k),tk)∥→∞.
BecauseΩ and (0,1] are bounded, there exists a subsequence (denoted also by {(ω(k),tk)}⊂Γω(0)) such that
(3.12)x(k)→x*,λ(k)→λ*,∥u(k)∥→∞,z(k)→z*,tk→t*,ask→∞.
By the third equation of (3.2), we have
(3.13)g(x(k))=tk(U(k))-1U(0)g(x(0)).
Hence, the active index set B(x*) is nonempty.
From the first equation of (3.2), it follows that
(3.14)(1-tk)(∇f(x(k))λ(k)+∇g(x(k))u(k)+tkη(x(k))(u(k))2)+[∇h(x(k))+tk(β(x(k))-∇h(x(k)))]z(k)+tk(x(k)-x(0))=0.
(i) Whent*=1, rewrite (3.14) as
(3.15)∑j∈B(x*)‍(1-tk)(∇gj(x(k))uj(k)+tkηj(x(k))(uj(k))2)+tkβ(x(k))z(k)+(1-tk)∇h(x(k))z(k)+(x(k)-x(0))=-(1-tk)[∑j∉B(x*)‍∇gj(x(k))uj(k)+tkηj(x(k))(uj(k))2=-(1-tk)+∇f(x(k))λ(k)-(x(k)-x(0))∑j∉B(x*)‍(uj(k))2].
From the fact thatuj(k) is bounded for j∉B(x*) and by the assumptions (C1) and (C2), when k→∞, we observe that
(3.16)∑j∈B(x*)‍(∇gj(x*)limk→∞(1-tk)uj(k)+ηj(x*)limk→∞(1-tk)tk(uj(k))2)=-(β(x*)z*+x*-x(0)).
It is easy to see that the right-hand side of the equation is bounded. By the assumption(C2), we have
(3.17)limk→∞(1-tk)uj(k)=0,limk→∞(1-tk)tk(uj(k))2=αj,j∈B(x*),
where αj≥0.
Then, we have(3.18)x(0)=x*+β(x*)z*+∑j∈B(x*)‍αjηj(x*),
which contradicts the assumption (C3).
(ii) Whent*∈[0,1), rewrite (3.14) as
(3.19)∑j∈B(x*)‍(1-tk)(∇gj(x(k))uj(k)+tkηj(x(k))(uj(k))2)=-(1-tk)[∑j∉B(x*)‍(∇gj(x(k))uj(k)+tkηj(x(k))(uj(k))2)+∇f(x(k))λ(k)]-tk(x(k)-x(0))-[∇h(x(k))+tk(β(x(k))-∇h(x(k)))]z(k).
We know that, sinceΩ and uj(k), j∉B(x*) are bounded as k→∞, the right-hand side of (3.19) is bounded. But by the assumption (C2), if uj(k)→∞(j∈B(x*)), then the left-hand side of (3.19) is infinite; this is a contradiction.
As a conclusion,(a) is the only possible case, and ω* is a solution of the KKT system.
Lets be the arc-length of Γω(0). We can parameterize Γω(0) with respect to s.Theorem 3.4.
The homotopy pathΓω(0) is determined by the following initial-value problem for the ordinary differential equation
(3.20)DHω(0)(ω(s),t(s))[·ω·μ]=0,ω(0)=ω(0),t(0)=1.
The component ω* of the solution point (ω(s*),t(s*)),   for t(s*)=0, is the solution of the KKT system.


## 4. Algorithm and Numerical Example

Algorithm 4.1.
MOP’s Euler-Newton method.Step 1.
Give an initial point(ω(0),1)∈Ω0×R++p+m×{0}×{1}, an initial step length h0>0, and three small positive numbers ε1,ε2,ε3. Let k:=0.Step 2.
Compute the directionγ(k) of the predictor step.(a)
Compute a unit tangent vectorξ(k)∈Rn+p+m+s+1 of Γω0 at (ω(0),tk).(b)
Determine the directionγ(k) of the predictor step.If the sign of the determinant|DHω(0)(ω(k),tk)ξ(k)T| is (-1)p+m+s+pm+ps+ms+1, take γ(k)=ξ(k).If the sign of the determinant|DHω(0)(ω(k),tk)ξ(k)T| is (-1)p+m+s+pm+ps+ms, take γ(k)=-ξ(k).Step 3.
Compute a corrector point(ω(k+1),tk+1):
(4.1)((ω*)(k),(t*)k)=(ω(k),tk)+hkγ(k),(ω(k+1),tk+1)=((ω*)(k),(t*)k)-DHω(0)((ω*)(k),(t*)k)+Hω(0)((ω*)(k),(t*)k),
where
(4.2)DHω(0)(ω,t)+=DHω(0)(ω,t)T(DHω(0)(ω,t)DHω(0)(ω,t)T)-1
is the Moore-Penrose inverse of DHω(0)(ω,t).If∥Hω(0)(ω(k+1),tk+1)∥≤ε1, let hk+1=min{h0,2hk}, and go to Step 4.If∥Hω(0)(ω(k+1),tk+1)∥∈(ε1,ε2), let hk+1=hk, and go to Step 4.If∥Hω(0)(ω(k+1),tk+1)∥≥ε2, let hk+1=max{(1/2)h0,(1/2)hk}, and go to Step 3.Step 4.
Ifω(k+1)∈Ω×R+p+m×Rs and tk+1>ε3, let k=k+1 and go to Step 2.
Ifω(k+1)∈Ω×R+p+m×Rs and tk+1<-ε3, let hk:=hk(tk/(tk-tk+1)), go to Step 3, and recompute  (ω(k+1),tk+1) for the initial point (ω(k),tk).
Ifω(k+1)∉Ω×R+p+m×Rs, let hk:=(hk/2)(tk/(tk-tk+1)), go to Step 3, and recompute (ω(k+1),tk+1) for  the initial point (ω(k),tk).
Ifω(k+1)∈Ω×R+p+m×Rs, and |tk+1|≤ε3, then stop.Example 4.2 (see [9]).
Consider(4.3)minf=min{x12+x22+x32+x42+x52,3x1+2x2-13x3+0.01(x4-x5)3};s.t.g1(x)=x12+x22+x32+x42-10≤0;h1(x)=4x1-2x2+0.8x3+0.6x4+0.5x52=0;h2(x)=x1+2x2-x3-0.5x4+x5-2=0.
The results are shown in Table1.Table 1
Results for Example4.2.
x
(
0
)
x
*
f
(
x
*
)
∥
H
ω
*
∥
(1.0000, 2.0000, 0.0000, 1.0000, 1.0000)
(
-
1.3074
,
-
2.8605
,
-
1.0470,
0.4103,0.4475)
(
11.3566
,
-
9.2942
)
1.0
e
-
012
(−1.0000,  −2.0000, 1.0000, 1.0000, 1.0000)
(
-
1.3073
,
-
2.8603
,
-
1.0470,
0.4102,0.4476)
(
11.3550
,
-
9.2936
)
1.0
e
-
013
Now, we compare the same example with the one in [9] under the same initial point.
x
(
0
)
x
*
f
(
x
*
)
∥
H
ω
*
∥
(1.0000, 2.0000, 0.0000, 1.0000, 1.0000)
(
0.3077,0.5374
,
-
0.2703,
-0.1336,0.2804)
(
0.5330,2.0873
)
6.6
e
-
016
(−1.0000,  −2.0000, 1.0000, 1.0000, 1.0000)
(
-
2.2124
,
-
2.0383
,
0.8241,
-0.5208,8.8528)
(
88.3715
,
-
19.2246
)
4.1
e
-
014Example 4.3.
Consider(4.4)minf=min{x12+x22,x1};s.t.g1(x)=-x2-6≤0;g2(x)=x2-6≤0;h1(x)=x1-x22-3=0.
(
1
) Since ∇h(x)=(1,-2x2)T, it is easy to see that the assumption (A3) in [14] and the assumption (C3) in [15] are not satisfied at most points in feasible set. Hence, we introduce the functions ηi(x)(i=1,2) and β(x).
(
2
) Let ηi(x)=∇gi(x)(i=1,2) and β(x)=(10,0)T. It is easily verified that the feasible set satisfies the assumptions (C1)–(C4). The results are shown in Table 2.Table 2
Results for Example4.3.
x
(
0
)
x
*
f
(
x
*
)
∥
H
ω
*
∥
(
12.0000,3.0000
)
(
3.0004,0.0000
)
(
11.3566
,
-
9.2942
)
1.0
e
-
012
(
12.0000
,
-
3.0000
)
(
3.0003,0.0000
)
(
11.3550
,
-
9.2936
)
1.0
e
-
013



---

*Source: 591612-2012-09-04.xml*