# Homotopy Interior-Point Method for a General Multiobjective Programming Problem

Authors: X. Zhao; S. G. Zhang; Q. H. Liu
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

We present a combined homotopy interior-point method for a general multiobjective
programming problem. For solving the KKT points of the multiobjective programming problem,
the homotopy equation is constructed. We prove the existence and convergence of a smooth homotopy path
from almost any initial interior point to a solution of the KKT system under some basic assumptions.


---

## Body

## 1. Introduction

We consider the following multiobjective programming problem:(MOP)min⁡f(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.Since Kellogg et al. [1] and Smale [2] have published their remarkable papers, more and more attention has been paid to the homotopy method. As a globally convergent method, the homotopy method now becomes an important tool for numerically solving complementary problem and nonlinear mathematical programming problem [3–5].Among most interior-point methods for solving mathematical programming, one of the main ideas is numerically tracing the center path generated by the optimal solution set of the logarithmic barrier function. Usually, the strict convexity of the logarithmic barrier function or boundedness of the solution set is needed [6, 7]. Lin et al. [8] presented a new interior-point method, combined homotopy interior-point method (CHIP method), for convex nonlinear programming. Subsequently, Lin et al. [9] generalized the CHIP method to convex multi-objective programming with only inequality constraints. Recently, Song and Yao [10] generalized the combined homotopy interior-point method to the general multiobjective programming problem under the so-called normal cone condition. 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):z=(zj)∈Rs,ui≥0,i∈B(x)}⋂Ω={x},whereΩ={x∈Rn∣g(x)≦0,h(x)=0},Ω0={x∈Rn∣g(x)<0,h(x)=0},andB(x)={i∈{1,2,…,m}∣gi(x)=0}.In [10], the combined homotopy method was given as follows:(1.1)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]. 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, the method given in [10] just solves the single-objective programming problem.The purpose of this paper is to generalize the combined homotopy interior-point method for a general multiobjective programming problem (MOP) under quasinorm cone condition that weakens the assumptions more than the ones in [10] and constructs a new homotopy equation which is much different and simpler the that one given in [9].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 a KKT point of MOP under some assumptions. In Section 4, numerical results are given.


## 2. Some Definitions and Properties

LetR+n and R++n denote the nonnegative and positive orthants of Rn, respectively. For any two vectors y=(y1,y2,…,yn)T  and z=(z1,z2,…,zn)T  in Rn, we use the following conventions:(2.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.
Suppose that f=(f1,f2,…,fp)T:Rn→Rp, g=(g1,g2,…,gm)T:Rn→Rm,  and h=(h1,h2,…,hs)T:Rn→Rs  are three times continuously differentiable functions. Let(2.2)Ω={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(2.3)B(x)={i∈{1,2,…,m}gi(x)=0}
denote the active index set at a given point.Definition 2.1.
A pointx∈Ω  is said to be an efficient solution to multiobjective programming problem (MOP), if there is no y∈Ω such that f(y)≤f(x) holds.Definition 2.2.
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.3.
Letηi:Rn→Rn(i=1,2,…,m).  For any x∈Ω,{ηi(x):i∈B(x)}  is said to be positive linear independent with respect to ∇g(x)n  and ∇h(x)  if
(2.4)∇h(x)z+∑i∈B(x)(yi∇gi(x)+uiηi(x))=0,z∈Rs,yi≥0,ui≥0(i∈B(x))
implies that
(2.5)z=0,yi=0,ui=0(i∈B(x)).Lemma 2.4 (parametric form of the Sard Theorem on a smooth manifold; see [11]).
LetQ,Nand P be smooth manifolds of dimensions q,m and 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.5 (inverse image theorem; see [12]).
If 0 is a regular value of the mappingφα(·)≜φ(α,·), then φα-1(0) consists of some smooth manifolds.Lemma 2.6 (classification theorem of one-dimensional manifold; see [12]).
A one-dimensional smooth manifold is diffeomorphic to a unit circle or a unit interval.
The following three basic assumptions are commonly used in this paper:(C1)
Ω0 is nonempty and bounded;(C2)
for anyx∈Ω, there exists a positive linear independent map η(x) with respect to ∇g(x) and ∇h(x) such that, {ηi(x):i∈B(x)} is positive linear independent with respect to ∇g(x) and ∇h(x);(C3)
for anyx∈∂Ω, there exists a positive linear independent map η(x) with respect to ∇g(x) and ∇h(x), such that(2.6){x+∑i∈B(x)uiηi(x)+∑j∈Jzj∇hj(x):zj∈R,j∈{J},ui≥0,i∈B(x)}⋂Ω={x}
(quasinormal cone condition).Remark 2.7.
IfΩ satisfies assumptions (A1)–(A3),  then it necessarily satisfies assumptions (C1)–(C3).
In fact, if we chooseη(x)=∇g(x),  then it is easy to get the result. Clearly, if Ω satisfies assumptions (C1)–(C3),  then it does not necessarily satisfies assumptions (A1)–(A3).


## 3. Main Results

Letx∈Ω. We say that x is a KKT point of (MOP) if there exists (λ,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 multiobjective programming problem, the solution of the MOP can be obtained from the KKT system, and for a non-convex multi-objective programming problem, it is significant when we get 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)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)∈Rn×Rp×Rm×Rs, 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].Whent=1, the homotopy equation (3.2) becomes(3.3a)∇h(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 assumption(C3), we get z=0,x=x(0). Since g(x(0))<0, (3.3c) implies that u=u(0). Equation (3.3d) shows that λ=λ(0). That is, the equation H(ω,ω(0),1)=0 with respect to ω has only one solution ω=ω(0)=(x(0),λ(0),u(0),0).Whent=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.
Suppose thatH is defined as in (3.2) and let f,g, and h be three times continuously differentiable functions. In addition, let assumptions (C1)–(C3)  hold, and let ηi be two times continuously differentiable function. 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)∈Ω 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=1muj∇2gj(x)+t∑j=1muj2∇ηj(x))+∑k=1szk∇2hk(x)+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 the parametric form of the Sard theorem, for almost all ω(0)∈Ω0×Λ++×R++m×{0}, 0 is a regular value of Hω(0). By the 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), starting 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 that
(3.9){i∈{1,2,…,p}:lim⁡k→∞λ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 continuously differentiable functions. In addition, let  assumptions (C1)–(C3) hold, and let  ηi be two times continuously differentiable function. 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 of 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∇h(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∇h(x(0))|,
By assumption (C2), we know that |∇h(x(0))T∇h(x(0))|≠0. And because g(x(0))<0,λ(0)∈Λ++, we obtain that [∂Hω(0)(ω(0),1)/∂ω]  is nonsingular. Therefore, the smooth curve Γω(0), which starts from (ω(0),1), is 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), case (c) will not happen.
In case (b), becauseΩ and (0,1] are bounded sets and by assumption (C2), for any x∈Ω, there exists a positive linear independent map η(x) with respect to ∇g(x) and ∇h(x) such that {ηi(x):i∈B(x)} is positive linear independent with respect to ∇g(x) and ∇h(x). From the first equality 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 and by Theorem 3.2, there exists a sequence (denoted also by {(ω(k),tk)}⊂Γω(0)) such that
(3.12)x(k)⟶x*,λ(k)⟶λ*,‖u(k)‖⟶∞,z(k)⟶z*,tk⟶t*,ask⟶∞.
From the third equality 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 homotopy equation (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))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)+∇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+∇f(x(k))λ(k)-(x(k)-x(0))].
Because{uj(k)},j∉B(x*), are bounded and by assumption (C1), when k→∞, we observe that
(3.16)lim⁡k→∞(∑j∈B(x*)(1-tk)(∇gj(x(k))uj(k)+tkηj(x(k))(uj(k))2)+∇h(x(k))z(k)+(x(k)-x(0))=0).
Usingx(k)→x* and z(k)→z*(k→∞), we have from (3.16) that
(3.17)∑j∈B(x*)(∇gj(x*)lim⁡k→∞(1-tk)uj(k)+ηj(x*)lim⁡k→∞(1-tk)tk(uj(k))2)=-(∇h(x*)z*+x*-x(0)).
It is easy to see that the right-hand side of (3.17) is bounded. By assumption (C2) and (3.17), we get
(3.18)lim⁡k→∞(1-tk)uj(k)=0,lim⁡k→∞(1-tk)tk(uj(k))2=αj,j∈B(x*),
where αj≥0.
Then, we have(3.19)x(0)=x*+∇h(x*)z*+∑j∈B(x*)αjηj(x*),
which contradicts assumption (C3).
(ii)
Whent*∈[0,1), rewrite (3.14) as(3.20)∑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))z(k).
We know that, sinceΩ and {uj(k)},j∉B(x*) are bounded as k→∞, the right-hand side of (3.20) is bounded. But by assumptions (C2) and (C3), if uj(k)→∞(j∈B(x*)), then the left-hand side of (3.20) is infinite, this is a contradiction.
As a conclusion, (a) is the only possible case, andω* is a solution of the KKT system (3.1a)–(3.1c).
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.21)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 a solution of the KKT system.


## 4. Algorithm and Example

The following algorithm describes the numerical computation for Pareto optimal solutions.Algorithm 4.1 ((MOP) 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 (w(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.Remark 4.2.
In Algorithm4.1, the arc length parameter is not computed explicitly. The tangent vector at a point on Γω(0) has two opposite directions, one (the positive direction) makes s increase and the other (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 2 (b) of Algorithm 4.1 that determines the positive direction is based on a basic theory of homotopy method, that is, the positive direction γ at any point (ω,t) on Γω(0) keeps the sign of the determinant |DHω(0)(ω,t)γT| invariant.Example 4.3.
We have(4.3)min⁡f=min⁡{x12+x22,(x1+3)2+x22},s.t.g1(x)=(x1-3)2+x22-64≤0,g2(x)=(x1-5)2+x22-9≤0,h(x)=x1-x22-3=0.
The results are shown in Table 1.Table 1
Results of Example4.3.
x(0)x*f(x*)∥Hω*∥(4.000, −1.000)(7.1927, −2.0476)(55.9269, 21.7710)1.0e-003(3.000, 0.000)(3.7552, −0.8690)(14.8563, 1.3254)1.0e-013Example 4.4.
We have(4.4)min⁡f=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 Table 2.Table 2
Results of Example4.4.
x(0)x*f(x*)∥Hω*∥(1.0000, 2.0000, 0.0000, 1.0000, 1.0000)(−1.3074, −2.8605)(11.3566, −9.2942)1.0e-012(−1.0000, −2.0000, 1.0000, 1.0000, 1.0000)(−1.3073, −2.8603)(11.3550, −9.2930)1.0e-003



---

*Source: 497345-2012-04-29.xml*