Path And Tunnel Following Algorithm For Solving Multi-objective Programming Problem

The Multi-object Programming Problem(MPP) is a special optimizationproblem. It is regarded by more and more people since the multi-object pro-gramming problem is important in economics and engineering. However, thisclass of optimization problems are very complicate. It is diferent from thesingle-object programming problem, so those theories of single-object program-ming problem are not applicable to the MPP. Therefore, serious attention hasrecently been paid to theory and numerical method.Theoretically, people havemade some achievements since they committed to establish a set of theorysystem which parallel to the single-object programming problem.On the otherhand, the efective algorithms are not enough.Although there has been a lotof research. The main work of this dissertation is that the path and tunnelfollowing algorithm for solving multi-objective programming problem is pre-sented under appropriate conditions and study the convergence, which expandthe range of combined homotopy interior point for solving multi-objective pro-gramming problem.This dissertation is organized as follows:Chapter1: We summarize the past and the present in the theory andalgorithm about multi-object programming problem and the difcult in theresearch. On the other hand, we describe the developmental process of thehomotopy interior-point method. Chapter2:We summarize the main theory of multi-object programming problem involved in this dissertation.Chapter3:We study the path following algorithm for solving multi-object programming problem on the non-convex regional.In this chapter, we consider the MPP as follows: wheref=(f1,f2,…, fp)T:Rnâ†'Rp, g=(g1,g2,…,9m)T:Rnâ†'Rm h=(h1,h2…,hs)T:Rnâ†'RsFirstly, we consider the advantage in solving optimization problem about path following algorithm and put forward the path following algorithm for solving this kind of problem on the normal cone condition. Meanwhile, we construct a new combined homotopy equation and prove the existence and convergence of the homotopy path.Secondly, in accordance with the defects of path following algorithm on normal cone condition, we put forward the path following algorithm on the quasi-normal cone condition, the modified quasi-normal cone condition and the modified weake quasi-normal cone condition combined with the characteistics of normal cone and (weak)quasi-norm cone. Meanwhile, we prove the existence and convergence of the homotopy path under weaker conditions.Let x∈Ω, we call that x is a KKT point of MPP, if there exists (λ, u, z)∈R_P+m×Rs.such that Meanwhile, the KKT system of MPP is (1a)-(1c).In [83], assumptions as follows:(A1)Ω0is nonempty and bounded;(A2)(?)x∈Ω,{â–½gi(x),i∈B(x),â–½hj(x),j∈J} is linear independent;In addition, the definition of "positive linea independent" is given in [59]. In order to extend it to non-convex multi-object programming problem and weaken the assumptions in literature [83], we do some works for inequality con-strained part firstly, introduce "positive linea independent mapping". Then take into consideration the equality constraint part, we construct a new ho-motopy equation under different assumptions.Assumptions â… :(B1)Ω0is nonempty and bounded;(B2) 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);(B3) For any x∈(?)Ω, there exists a positive linear independent map η(x) with respect toâ–½g(x) andâ–½h(x), such that (quasi-normal cone condition)Remark If Ω satisfies the Assumptions (A1)-(A3), then it necessarily satisfies the Assumptions (B1)-(B3).In fact, if we choose η(x)=â–½g(x), then it is easy to get the result. Clearly, if Ω satisfies the Assumptions (B1)-(B3), then it does not necessarily satisfies the Assumptions (A1)-(A3).To solve the KKT system (1a)-(1c), we construct a homotopy equation as follows 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/2J,λ25/2,…,λp5/2)T∈Rp U=diag(u), e=(1,1,…,1)T∈Rp and t∈[0,1].Theoreml Suppose that f, g and h be three times continuous differen-tiable functions. In addition, let the Assumptions (B1)-(B2) hold and ηi be twice times continuously differentiable function. Then for almost all initial points ω(0)∈Ω0×Λ||×R||m×{0},0is a regular value of Hω(0) and Hω(0)1consists of some smooth curves. Among them, a smooth curve, say Γω(0), is starting from (ω(0),1).Theorem2Let Assumptions(B1)-(B2)hold.For a given ω(0)(x(0),λ(0),u(0),z(0))∈Ω0×Λ-+×R++m×{0}, if0is a regular value of Hω(then the projection of the smooth curve Γω(0) on the component A is bounded.Theorem3Suppose that f, g and h be three times continuous differen-tiable functions. In addition, let the Assumptions (B1)-(B3) hold and ηi be twice times continuously differentiable function. Then, for almost all ofω(0)∈Ω0×Λ++×R++m×{0}, Hω(0)-1contains a smooth curve Γw(0)(？) Ω×R|p×R-m×Rs×(0,1], which starts from (ω(0),1). As lâ†'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 (1a)-(1c). Theorem4Homoty path Γω(0) is denned by: for t(s*)=0, ω*is one solution of (1a)-(1c). Assumptions â…¡:(C1)Ω0is nonempty and bounded;(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));(C3) For any x∈(?)Ω,(modified quasi-normal cone condition)(C4) For any x∈Ω,â–½h(x)Tβ(x) is nonsingular.Remark If Ω satisfies the Assumptions (A1)-(A3), then it necessarily sat-isfies 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).Under modified quasi-norm cone condition, we construct a homotopy equation as follows: H(ω,ω(01),t)= where ω(0)=(x(0),λ(0),u(0),z(0))∈Ω0×Λ++×R++m×x{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 andt∈[0,1].As t=1, the homotopy equation becomesBy the Assumption (C3), we get z=0,x=x(0) Since g(x(0))<0and x=x(0)(c) implies that u=u(0).(d) shows that λ=λ(0). That is, the equation H(ω,ω(0),1)=0with respect to uj has only one solution ω=ω(0)(x(0),λ(0),u(0),0).As t=0, H(ω,ω(0))=0turns to the KKT system (1a)-(1c).For a given ω(0) rewrite H(ω,ω(0),t) as Hω(0)(ω, t). The zero-point set of Hω(0) isTheorem5Suppose that/, g and h are three times continuous differen-tiable functions. In addition, let the Assumptions (C1)-(C2) hold and ηi,βj be twice times continuously differentiable functions. Then for almost all initial points ω(0)∈Ω0×A++×R+-m×{0},0is a regular value of Hω(0) and Hω(0)-1consists of some smooth curves. Among them, a smooth curve, say Γω(0), is starting from (ω(0),1).Theorem6Let Assumptions (C1)-(C2) hold. For a given ω(0)=(x(0),λ(0) u(0),z(0))∈Ω0×Λ++×R++m×{0}, if0is a regular value of Hω(0), then the projection of the smooth curveΓω(0) on the component λ is bounded.Theorem7Suppose that f, g and h be three times continuous differen-tiable functions. In addition, let the Assumptions (C1)-(C4) hold and ηi,βj be twice times continuously differentiable functions. Then, for almost all of ω(0)∈Ω0×Λ++×B++m×{0}, Hω(0)-1contains a smooth curve Γω Ω×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 (1a)-(1c).Theorem8Homoty path Γω(0)is denned by: for t(s*)=0, ω*is one solution of (1a)-(1c).In order to extend the existing results to the general non-convex multi-objet programming problem,weaken the restrictions of the non-convex con-strains reginal.We define the modified weak quasi-norm cone condition and construct a new combined homotopy equation,which extends the scope for solving multi-object programming problem by the path following algorithm. The Assumptions as follows:(C1)Ω0is nonempty and bounded;(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)y,(C3) For any x∈(?)Ω,(modified quasi-normal cone condition)(C4) For any x∈Ω,â–½h{x)Tβ{x) is nonsingular. To solve the KKT system (1a)-(1c), we construct a homotopy equation as follows: H(ω,ω(0),t)=where ω(0)=(x(0),λ(0),u(0),z(0))∈Ω10×Λ++×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].Theorem9Suppose that f, g and h are three times continuous differen-tiable functions. In addition, let the Assumptions (C1)-(C2) hold and ηi,βj be twice times continuously differentiate functions. Then for almost all initial points ω(0)∈Ω10×Λ++×R++m×{0},0is a regular value of Hω(0) and Hω(0)-1consists of some smooth curves. Among them, a smooth curve, say Γω(0), is starting from (ω(0),1).TheoremlO Let Assumptions (C1)-(C2) hold.For a given ω(0)(x(0),λ(0),u(0),z(0))∈Ω10×Λ++×R++m×{0}, if0is a regular value of Hω(then the projection of the smooth curve Γω(0) on the component A is bounded.Theoremll Suppose that f,g and h be three times continuous differ-entiable functions.In addition, let the Assumptions (C1)-(C4) hold and ηi,βj be twice times continuously differentiable functions. Then, for almost all of ω(0)∈Ω10×Λ++×R++m×{0},Hω(0)-1(0) contains a smooth curve Γω Ω×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 (1a)-(1c).Theoreml2Homoty path Γω(0) is denned by: ω(0)=ω(0)=1, for t(s*)=0, ω*is one solution of (1a)-(1c).Chapter4: We study the tunnel following algorithm for solving multi-object programming problem.We really hope to find a kind of tunnel following algorithm for solving MPP by homoyopy, and try to obtain some or all of the efficient solutions (weak efficient solutions). This chapter has two sections:In the first section, we consider the convex Multi-objective programming with inequality constraints as follows: wheref=(f1,f2,…,fP)T: Rnâ†'Rp, g=(g1,g2,…,gm)T: Rnâ†'Rm are convex functions. Assumptions as follows:(H1) Ω0is nonempty and bounded;(H2)(?)x∈(?)Ω,{â–½gi(x)|i∈B(x)} is linear independent.If there exists (x,λ,u)∈Ω×R+p+m, such that whereâ–½f{x)=(â–½f1(x),???,â–½fP(x))∈Rn×p,â–½g(x)=(â–½g1(x),…,â–½gm(x))∈Rn×m. Then x isa KTT point of (2),(a)-(c) are KKT system of (2).In order to solve (a)-(c), the homoty equation as follows: where ω(0)=(x(0),u(0))∈Ω0×R++m,λ(0)∈Λ++,ω=(x,u)∈Ω×R+m,λ∈R+m,t∈[0,1].Theoreml Let f,g∈Cr(r≥3) are convex functions, and Ω0≠(?), then for almost ω(0)∈Ω0×R++m,0is Hω(0) a, and Hω(0)-1consists of a smooth manifold(ω(0),λ,1)(a homotopy tunnel), say Vω(Theorem2Let f,g∈Cr(r≥3) are convex functions, and (H1,H2) be hold. For ω(0)∈Ω0×R++m, if0is a regular value of Hω(0), then Vω(0) is a bounded and smooth tunnel.Theorem3Let f,g∈Cr(r≥3) are convex functions, and (H1,H2) be hold, then (2) has solution. For almost all of ω(0)∈Ω0×R++m, Vω(0) is a homotopy tunnel, which starts from (ω(0),λ,1). When tâ†'0, the limit set S×{0}∈Ω×R+m×Λ+×{0} of Vω(0) is nonempty, and every point of S is a solution of (2). Especially, if Vω(0) is finite, and (ω,λ,0) is the limite point of Vω(0), then(ω,λ) is a solution of (2).Theorem4The curve Tω(0) of the Homotopy tunnel Vω(0) which stats from (ω(0),λ,1), is denned as follows: If t(s*)=0, then (ω*(s), λ(s)) is one solution of (3).In the second section, we consider the Multi-objective programming prob-lem on the non-convex region. Firstly, we consider the convex Multi-objective programming with inequal-ity constraints. where f=(f1,f2,…, fp)T: Rnâ†'R0, g=(g1,g2,…, gm)T: Rnâ†'Rn Assumptions as follows:(A1)Ω0is nonempty and bounded;(A2)(?)x∈Ω,{â–½gi(x),i∈B(x)} is linear independent; where Ω={x∈Rn|g(x)≦0,h(x)=0},Ω0={x∈Rn|g(x)<0},B(x)={i∈{1,2,…m}|gi(x)=0}.If there exists (x,λ,u)∈Ω×R+p+m, such that whereâ–½f(x)=(â–½f1(x),…,â–½fp(x))∈Rn×p,â–½g(x)=(â–½91(x),…,â–½gm(x))∈Rn×m. Then x sa KKT point of (4),(a)-(c) is the KKT system of (4).To solve the KKT system (a)—(c), we construct a homotopy equation as follows: where ω(0)=(x(0),u(0))∈Ω0×R++,λ(0)∈Λ++, ω=(x,u)∈R+m+p,λ∈Λ+,e=(1,1,---,1),U=diag(u) and|λ5/2-λ(0)5/2)=(|λ15/2|-(λ1(05/2|,|λ25/2-(λ2(0))5/2|,…,|λP5/2-(λP(0)5/2|T∈RpWhen t=1, the homotopy equation becomes x-x(0)=0, Ug(x)-U(0)g(x(0))=0, e|λ5/2-λ(0)5/2|=0We can get (ω,λ)=(ω(0),λ(0).When t=0, the homotopy equation becomes (a)—(c).For a given ω(0), rewrite H(ω,ω(0), t) asHω(0)(ω, t). The zero-point set of Hω(0) is Hω(0)-1={(ω,t)∈Ω×R++p+m×Rs×(0,1]: H(ω,ω(0),t)=0}.Theoreml Suppose that f, g be three times continuous differentiable functions, and Ω0≠0. then, for almost all of (ω(0), λ(0))=(x(0),n(0),λ(0)∈Ω0×R++m×Λ++,and t∈[0,1],0is a regular value of Hω(0),and Hω(0)-1(0) consists of a homotopy tunnel, say Vω(0), is starting from (ω(0),λ(0),1).Theorem2Let (A1)-(A2) be hold, for (ω(0),λ(0))=(ω(0),λ(0))∈Ω0×R++m×Λ++. If0is a regular value of Hω(0), then the component A of Vω(0) is bounded.Theorem3Suppose that f, g be three times continuous differentiable functions, and let (A1)-(A3) be hold, then, for almost all of (ω(0),λ(0))(x(0),u(0),λ(0))∈Ω0×R++m×Λ++, if0is a regular value of Hω(0), then Vω(0) is a bounded and smooth tunnel.Theorem4Suppose that/, g be three times continuous differentiable functions, and let (A1)-(A3) hold,then, for almost all of (ω(0),λ(0))(0(0),u(0),λ(0))∈Ω0×R++m×Λ++, Hω(0) contains a homotopy tunnel Vω(which starts from (ω(0),λ(0),1), the limit set S of Vω(0) is nonempty and every point in S is a solution of (4).Theorem5The curve Tω(0) of the Homotopy tunnel Vω(0) which stats from (ω(0),λ,1), is denned as follows: t(0)=1,λ=λ,ω(0)=ω(0) If t(s*)=0, then (ω*(s), λ(s)) is a solution of (4).Secondly, we consider the MPP as follows: min f(x) s.t. g(x)≦0, h(x)=0, wheref=(f1, f2,…, fp)T: Rnâ†'Rp, g=(g1,g2,…,gm)T: Rnâ†'Rm h=(h1,h2…,hs)T: Rnâ†'Rs. Assumptions as follows:(A1) Ω0is nonempty and bounded;(A2)(?)x∈Ω,{â–½gi(x),i∈B(x),â–½hj(x),j∈J} is linear independent;{x}; where Ω={x∈Rn|g(x)≦0,h(x)=0},Ω0={x∈Rn|g(x)<0,h(x)0},B(x)={i∈{1,2,…m}|gi(x)=0If there exists (x,λ,u,z)∈Ω×R+p+m×Rs, such that whereâ–½f(x)=(â–½f1(x),…,â–½fp(x))∈Rn×p,â–½g(x)=(â–½g1(x),…,â–½gm{x))∈Rn×m,â–½h(x)=(â–½h1(x),…,â–½hs(x))∈Rn×s. then x is a KKT point of MPP,(1a)-(1c) is the KKT system.To solve the KKT system (la)—(lc), we construct a homotopy equation as follows: where ω(0)=(x(0),u(0),z(0))∈Ω0×R++m×{0},λ(0)∈Λ++, ω=(x,u,z)∈R+m+p×Rs,λ∈Λ+, e=(1,1,…,1), U=diag(u) and|λ5/2-λ(0)5/2|=(|λ15/2-(λ1(0)5/2|,|λ25/2-(λ2(0))5/2|,…,|λp5/2-(λp(0))5/2|)T∈RpWhen t=1, the homotopy equation becomesâ–½h(x)z+x-x(0)=0, h(x)=0, Ug(x)-U(0)g(x(0))=0,We can get (ω,λ)=(ω(0),λ(0)).When t=0, the homotopy equation becomes (1a)-(1c).For a given ω(0), rewrite H(ω,ω(0),t) as Hω(0)(ω,t). The zero-point set of Hω(0) is Hω(0)-1={(ω,t)∈Ω×R++p+m×Rs×(0,1]: H(ω,ω(0),t)=0}.Theorem6Suppose that f, g and h be three times continuous differen-tiate functions, and Ω0≠0. then, for almost all of (ω(0),λ(0))=(x(0),u(0),z(0),λ(0))∈Ω0×R++m×{0}×Λ++,and t∈[0,1],0is a regular value of Hω(0), and Hω(0)-1(0) consists of a homotopy tunnel, say Vω(0), is starting from (ω(0),λ(0),1).Theorem7Let (A1)-(A2) be hold, for (ω(0),λ(0))=(x(0),u(0),λ(0))∈Ω0×R+=m×Λ++. If0is a regular value of Hω(0), then the component A of Vω(is bounded. Theorem8Suppose that f, g and h be three times continuous differen-tiable functions, and let (A1)-(A3) hold, then, for almost all of (ω(0),λ(0)=(x(0),u(0),z(0),λ(0))∈Ω0×R++m×{0} x Λ++,if0is a regular value of Hω(0) then Vω(0) is a bounded and smooth tunnel.Theorem9Suppose that f,g and h be three times continuous differen-tiate functions, and let (A1)-(A3) hold, then, for almost all of (ω(0),λ(0))=(x(0),u(0),z(0),λ(0))∈Ω0×R++m×{0}×Λ++, Hω(0)-1(0) contains a homotopy tunnel Vω(0), which starts from (ω(0),λ(0),1), the limit set S of Vω(0) is nonempty and every point in S is a solution of the KKT system (1a)-(1c).TheoremlO The curve Tω(0) of the homotopy tunnel Vω(0) which stats from (ω(0),λ,1), is denned as follows: t(0)=1,λ=λ,ω(0)=ω(0) If t(s*)=0, then (ω*(s),λ(s)) is a solution of (1a)-(1c).