# A Parameter Perturbation Homotopy Continuation Method for Solving Fixed Point Problems with Both Inequality and Equality Constraints

Authors: Menglong Su; Yufeng Shang; Wenzhuang Zhu
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

In this paper, we propose a parameter perturbation homotopy continuation method for solving fixed point problems on more general nonconvex sets with both inequality and equality constraints. By adopting appropriate techniques, we make the initial points not certainly in the set consisting of the equality constraints. This point can improve the computational efficiency greatly when the equality constraints are complex. In addition, we also weaken the assumptions of the previous results in the literature so that the method proposed in this paper can be applied to solve fixed point problems in more general nonconvex sets. Under suitable conditions, we obtain the global convergence of this homotopy continuation method. Moreover, we provide several numerical examples to illustrate the results of this paper.


---

## Body

## 1. Introduction

Fixed point theorems have been widely applied to many areas such as mechanics, physics, transportation, control, economics, differential equations, and optimization. Particularly the algorithm construction of computing a fixed point has attracted much attention and lots of results have appeared. The results of related research mentioned above are found in the literature (see [1–10], etc. and the references therein). Although the homotopy method has become a popular tool in dealing with fixed point problems (see [11–15], etc. and the references therein), this method still requires certain convexity assumptions. These convexity assumptions prevent the homotopy method from being extended to provide a constructive proof of the general Brouwer fixed point theorem, which does not require the convexity of the subsets in Rn. Recently, on a class of nonconvex subset that satisfies the normal cone condition, by introducing the ideas of Karmarkar’s interior point method into the homotopy method, Yu and Lin [16] proposed a combined homotopy interior point method to give a constructive proof of the general Brouwer fixed point theorem and hence solve fixed point problems numerically. In [17], by introducing C2 mappings α(x)=(α1(x),…,αm(x))∈Rn×m and β(x)=(β1(x),…,βl(x))∈Rn×l, we further extended the results in [16] to more general nonconvex sets with both inequality and equality constraint functions. In 2013, by introducing C2 functions ηi(x,ui)∈Rn, i=1,…,m, and ζj(x,vj)∈Rn, j=1,…,l, Zhu et al. [18] further extended the results in [17] to more general nonconvex sets. It should be pointed out that, in [18], the initial point x(0) must satisfy the equation h(x)=0. In fact, it is difficult to select such an initial point when the constraint function h(x) is complex. This point reduces the computational efficiency of the homotopy interior point method greatly. In this paper, we propose a parameter perturbation homotopy continuation method for solving fixed point problems with both inequality and equality constraints. By using this new homotopy continuation method, we can not only remove the assumption that the matrix ∇z∑j=1lζ(x,zj) is of full row rank in [18] but also can make the initial point x(0) only satisfy g(x)<0, without satisfying the equation h(x)=0. Moreover, we mainly extend the results in [19, 20] to more general nonconvex sets and provide a practical perturbation for the inequality constraints compared with the results in [20]. Under commonly used conditions in the literature, we obtain the global convergence of the parameter perturbation continuation method. Moreover, we provide several numerical examples to illustrate the results of this paper.This paper is organized as follows. Section2 contains the basic definitions and the required preliminary materials widely used in what follows. Section 3 is the main part, which exhibits a convergence proof of the parameter perturbation continuation method. Section 4 presents the use of the reduced predictor-corrector algorithms given by Allgower and Georg [11] to compute a number of experimental examples, which illustrate the results of this paper.


## 2. Preliminaries

In this section, we need the following notations:Ω={x∈Rn:gi(x)≤0,i=1,…,m,hj(x)=0,j=1,…,l}, Ω0={x∈Rn:gi(x)<0,i=1,…,m,hj(x)=0,j=1,…,l}, R+m={x∈Rm:x≥0}, R++m={x∈Rm:x>0}, and B(x)={i∈{1,…,m}:gi(x)=0}, Ωg={x∈Rn:gi(x)≤0,i=1,…,m}, Ωg0={x∈Rn:gi(x)<0,i=1,…,m}, and ∂Ωg=Ωg∖Ωg0.In [18], the initial point x(0) is confined in the interior of Ω0; thus x(0) must satisfy h(x(0))=0 as well as g(x(0))<0. Once the equality constraint function h(x) is complex, it is difficult to select such an initial point x(0). This point may reduce the computational efficiency of the homotopy interior point method greatly. In this paper, we attempt to construct a new homotopy equation, which not only makes us remove the assumption that ∇z∑j=1lζ(x,zj) is of full row rank in [18] but also makes the initial point x(0) only satisfy g(x)<0, without satisfying the equation h(x)=0. To this end, we construct a new homotopy equation as follows: (1)Hw,w0,λ=1-λx-Φx+∑i=1mηix,1-λyi+∑j=1lζjx,1-λzj+λx-x0hx-λzy1g1A1λx+b1λ+λc1-λy10g1A1x0+b11+c1⋮ymgmAmλx+bmλ+λcm-λym0gmA1x0+bm1+cm=0,where w=(x,y,z)∈Rn×R+m×Rl, h(x)=(h1(x),…,hl(x))T∈Rl, and Ai(λ)∈Rn×n and bi(λ)∈Rn, i=1,…,m. Besides, ci∈R1, i=1,…,m, are constants. Set Ω(λ)={x∈Rn:gi(Ai(λ)x+bi(λ))+λci≤0,i=1,…,m,h(x)=0}, Ω0(λ)={x∈Rn:gi(Ai(λ)x+bi(λ))+λci<0,i=1,…,m,h(x)=0}, I(x,λ)={i∈{1,…,m}:gi(Ai(λ)x+bi(λ))+λci=0}, Ωg(λ)={x∈Rn:gi(Ai(λ)x+bi(λ))+λci≤0,i=1,…,m}, Ωg0(λ)={x∈Rn:gi(Ai(λ)x+bi(λ))+λci<0,i=1,…,m}, and ∂Ωg(λ)=Ωg(λ)∖Ωg0(λ).Next, we make the following assumptions:( A 1 )  Ω0 is nonempty and Ωg(λ) is bounded.( A 2 )   η i ( x , 0 ) = 0, i=1,…,m, and ζj(x,0)=0, j=1,…,l; besides, for any x∈Ωg(λ) and for any u∈R+m and v∈Rl, if (u,v)→∞, then (2)∑i∈Ix,ληix,ui+∑j=1lζx,vj⟶∞.( A 3 )   ∀ x ∈ Ω, if (3)∑i∈Bxηix,ui+∑j=1lζx,vj=0,ui≥0,then ui=0, ∀i∈B(x), and vj=0,j=1,…,l. In addition, for any x∈Ωg(λ),∇h(x) is a matrix of full column rank.( A 4 )   ∀ x ∈ Ω, we have (4)x+∑i∈Bxηix,ui+∑j=1lζx,vj:ui≥0,i∈Bx∩X=x.Besides, ∀x∈∂Ωg(λ), we have (5)x+∑i∈Ix,ληix,ui:ui≥0,i∈Ix,λ∩Ωgλ=x.Example 1.
To find a fixed point of self-mappingΦ(x)=(x1,-x2)T in Ωg={x1,x2∈R2:x12+x22≤1,x1-1.05)2+x22≥4, in this example, set g1(x)=x12+x22-1 and g2(x)=-(x1-1.05)2-x22+4; the original feasible set Ωg (See Figure 1) is so small that we cannot find an initial point easily. However, set A1(λ)=I2×2, A2(λ)=I2×2, b1(λ)=(0,0)T, b2(λ)=(-0.45λ,0)T, c1=0, and c2=0; then(6)g1A1λx+b1λ+λc1=g1x,g2A2λx+b2λ+λc2=-x1-1.05-0.45λ2-x22+4.When λ=1, the perturbated feasible set Ωg(1) (see Figure 2) becomes big enough to find an initial point more easily than before.
For givenw(0), rewrite H(w,w(0),λ) as Hw(0)(w,λ). The zero-point set of Hw(0) is (7)Hw0-10=w,λ∈Ωgλ×R+m×Rl×0,1:Hw0w,λ=0.Figure 1
The original feasible setΩg of Example 1.Figure 2
The perturbated feasible setΩg(1) of Example 1.Remark 2.
In [18], to guarantee that the homotopy smooth curve is diffeomorphic to a unit interval (0,1], we need to prove that the matrix(8)∂H~w0w0,1∂w=I0∇z∑j=1lζx0,zj0∇hx0T00Y0∇gx0Tdiaggx00is nonsingular, where H~ is the homotopy in [18]. This requires that the matrix ∇z∑j=1lζ(x,zj) be of full row rank. In new homotopy (1), the matrix(9)∂Hw0w0,1∂w=I00∇hx0T0-IAB0is nonsingular without requiring the assumption that the matrix ∇z∑j=1lζ(x,zj) is of full row rank, where (10)A=Y0∇xg1A11x0+b11,…,∇xgmAm1x0+bm1T,B=diag⁡g1A11x0+b11+c1,…,gmAm1x0+bm1+cm.Remark 3.
Whenλ=1, the homotopy in [18] becomes(11)∑j=1lζjx,zj+x-x0=0,hx=0,Ygx-Y0gx0=0.It is easy to see that the initial point x(0) must satisfy h(x)=0 as well as g(x)≤0. This point makes the choice of initial points become difficult when the function h(x) is complex. However, from new homotopy (1), when λ=1, we have(12)x-x0=0,hx-z=0,yigiAi1x+bi1+ci-yi0giAi1x0+bi1+ci=0,i=1,…,m.From (12), we conclude that x(0) only needs to satisfy gi(Ai(1)x+bi(1))+ci≤0, i=1,…,m, without satisfying the equation h(x)=0.In the following, we recall some basic definitions and results from differential topology, which will be used in our main result of this paper.The inverse image theorem (see [21]) tells us that if 0 is a regular value of the map Hw(0), then Hw(0)-1(0) consists of some smooth curves. And the regularity of Hw(0) can be obtained by the following lemma.Lemma 4 (parameterized Sard’s theorem).
LetV⊂Rn and U⊂Rm be open sets, and let Φ:V×U→Rk be a Cr map, where r>max⁡{0,m-k}. If 0∈Rk is a regular value of Φ, then, for almost all a∈V, 0 is a regular value of Φa≡Φ(a,·).


## 3. Convergence Analysis

In this section, we are devoted to giving the global convergence analysis of the parameter perturbation homotopy continuation method.Lemma 5.
LetH be defined as in (1), let gi(x), i=1,…,m, and hj(x), j=1,…,l, be C3 functions, let assumptions (A1)–(A4) hold, and let ηi(x,ui)∈Rn, i=1,…,m, and ζj(x,vj)∈Rn, j=1,…,l, be C2 functions. Then, for almost all x0∈Ωg0(1), 0 is a regular value of map Hw(0):Rn×R+m×Rl×0,1→Rn+m+l, and there exists a C1 curve (w(s),λ(s)) of dimension 1 such that(13)Hws,w0,λs=0,w0,λ0=w0,1.Proof.
Whenx(0) is considered as a variable, let the Jacobian matrix of Hw(0)(w,λ) be denoted by DHw(0)(w,λ), for any λ∈(0,1]:(14)∂Hw0w,λ∂x,x0,y0=C-λI0∇hxT00D-λA1A-λB,where(15)C=1-λI-∇Φx+∇x∑i=1mηix,1-λyi+∇x∑j=1lζjx,1-λzj+λI,D=Y∇xg1A1λx+b1λ,…,∇xgmAmλx+bmλT.Because gi(Ai(1)x(0)+bi(1))+ci<0, i=1,…,m, and ∇h(x) is a matrix of full column rank, then ∂Hw(0)(w,λ)/∂(x,x(0),y(0)) is a matrix of full row rank. Moreover, it is easy to show that DHw(0)(w,λ) is of full row rank and thus 0 is a regular value of Hw(0)(w,λ). By the parameterized Sard’s theorem, for almost all x(0)∈Ωg0(1), 0 is a regular value of the map Hw(0):Rn×R+m×Rl×(0,1]→Rn+m+l. By the inverse image theorem, Hw(0)-1(0) consists of some smooth curves. Because Hw(0)(w,1)=0 has a unique solution w(0)=(x(0),y(0),h(x(0))), then there exists a C1 curve (w(s),λ(s)) (denoted by Γw(0)) of dimension 1 such that (16)Hws,w0,λs=0,w0,λ0=w0,1.Lemma 6.
LetH be defined as in (1), let gi(x), i=1,…,m, and hj(x), j=1,…,l, be C3 functions, let assumptions (A1)–(A4) hold, and let ηi(x,ui)∈Rn, i=1,…,m, and ζj(x,vj)∈Rn, j=1,…,l, be C2 functions. Then, for almost all x(0)∈Ωg0(1), Γw(0) is a bounded curve.Proof.
Assume thatΓw(0) is an unbounded curve. Then there exists a sequence of points {(w(k),λk)}⊂Γw(0) such that (w(k),λk)→∞. Because Ωg(λ) and (0,1] are bounded, hence there exists a subsequence of points (denoted also by {(w(k),λk)}) such that x(k)→x∗, (y(k),z(k))→∞, and λk→λ∗ as k→∞. From homotopy equation (1), we have(17)1-λkxk-Φxk+∑i=1mηixk,1-λkyik+∑j=1lζjxk,1-λkzjk+λkxk-x0=0,(18)hxk-λkzk=0,(19)yikgiAiλkxk+biλk+λkci-λyi0giA1x0+bi1+ci=0,i=1,…,m.Let (20)Ix∗=i∈1,…,m:limk→∞⁡yik=∞,Jx∗=j∈1,…,l:limk→∞⁡zjk=∞.From (19), we have(21)giAiλkxk+biλk+λkci=-λkyik-1yi0giAi1x0+bi1+ci,i=1,…,m.If J(x∗)≠∅, rewrite (17) as(22)1-λkxk-Φxk+∑i∉Ix∗ηixk,1-λkyik+λkxk-x0+∑j=1lζjxk,1-λkzjk+∑i∈Ix∗ηixk,1-λkyik=0.By assumption (A2), the previous three parts in the left-hand side of (22) are bounded, but the other two parts tend to infinity as k→∞; this is impossible. Now we can assume that z(k)→z∗. At the same time we have I(x∗)≠∅. From (21), it is easy to show that x∗∈∂Ωg(λ).
( 1 ) If λ∗=1, from (17), when k→∞, then (1-λk)yi(k)→0, i∉I(x∗,1), and (1-λk)yi(k)→yi∗, i∈I(x∗,1). Therefore(23)x0=x∗+limk→∞⁡1-λkxk-Φxk+limk→∞⁡∑i∈Ix∗,1ηixk,1-λkyik+limk→∞⁡∑i∉Ix∗,1ηixk,1-λkyik+limk→∞⁡∑j=1lζjxk,1-λkzjk=x∗+∑i∈Ix∗,1ηix∗,yi∗,which contradicts assumption (A4).
( 2 ) If 0<λ∗<1, rewrite (17) as(24)∑i∈Ix∗,λ∗ηixk,1-λkyik+λkxk-x0+1-λkxk-Φxk=-∑i∉Ix∗,λ∗ηixk,1-λkyik-∑j=1lζjxk,1-λkzjk.When k→∞, because Ωg(λ) and yi(k), i∉I(x∗,λ∗), are bounded, then the right-hand side of (24) is bounded. However, if yi(k)→∞, i∈I(x∗,λ∗), by assumption (A2), the left-hand side of (24) tends to infinity. This results in a contradiction.
( 3 ) When λ∗=0, because the nonempty index set I(x∗)⊂B(x∗), the proof of (3) is similar to that of (2).Now we give the main results of this section.Theorem 7.
LetH be defined as in (1), let gi(x), i=1,…,m, and hj(x), j=1,…,l, be C3 functions, let assumptions (A1)–(A4) hold, and let ηi(x,ui)∈Rn, i=1,…,m, and ζj(x,vj)∈Rn, j=1,…,l, be C2 functions. Then, for any C2 mapping Φ(x): Rn→Rn satisfying Φ(Ω)⊂Ω, Φ(x) has a fixed point in Ω. In addition, for almost all x(0)∈Ωg0(1), homotopy equation (1) determines a smooth curve Γw(0) starting from (w(0),1). The limit set T⊂Ω×R+m×Rl×{0} of Γw(0) is nonempty; and x-component of any point in T is a fixed point of Φ(x) in Ω.Proof.
By Lemma5, for almost all x(0)∈Ωg0(1), there exists a smooth curve Γw(0) starting from (w(0),1). Because ∂Hw(0)(w(0),1)/∂w is nonsingular, by the classification theorem of one-dimensional smooth manifold, Γw(0) is diffeomorphic to a unit interval.
Let(w∗,λ∗)=(x∗,y∗,z∗,λ∗). Then the following three cases are possible: (a)
(w∗,λ∗)=(x∗,y∗,z∗,λ∗)∈Ωg×R+m×Rl×{0}.(b)
(w∗,λ∗)=(x∗,y∗,z∗,λ∗)∈Ωg0(1)×R++m×Rl×{1}.(c)
(w∗,λ∗)=(x∗,y∗,z∗,λ∗)∈∂(Ωg(λ∗)×R+m×Rl)×(0,1].Because Hw(0)(w,1)=0 has a unique solution w(0) in Ωg0(1)×R++m×Rl×{1}, so case (b) is impossible.
In case (c), first, we prove thaty∗∉∂R+m. If y∗∈∂R+m, then there exist i0∈{1,…,m} and a sequence of points {(w(k),λk)}⊂Γw(0) such that yi0(k)→yi0∗=0 as k→+∞. From the third equation in (1), we have(25)yi0kgi0Ai0λkxk+bi0λk+λkci0=λkyi00gi0Ai01x0+bi01+ci0.When k→+∞, because Ωg(λ) and 0,1 are bounded, the left-hand side of (25) tends to 0. At the same time, the right-hand side of (25) tends to λ∗yi0(0)(gi0(Ai0(1)x(0)+bi0(1))+ci0), which is strictly less than 0. This results in a contradiction.
Then we prove thatx∗∉∂Ωg(λ). If x∗∈∂Ωg(λ), then there exist j0∈{1,…,m} and a sequence of points {(w(k),λk)}⊂Γw(0) such that gj0(Aj0(λ)x(0)+bj0(λ))+λcj0→0; yj0(k)→∞ as k→+∞. This contradicts Lemma 6, so case (c) is also impossible.
From the above discussion, we obtain that case (a) is the unique possible case. Whenλ→0, from (1), w∗ is a solution of the equation(26)x-Φx+∑i=1mηix,yi+∑j=1lζjx,zj=0,hx=0,Ygx=0,gx≤0,y≥0.When x∗∈Ωg0, we have g(x∗)<0 and h(x∗)=0, so x∗∈Ω0. From the third equation in (26), we obtain y∗=0. Then the first equation in (26) yields(27)x∗+∑j=1lζjx∗,zj∗=Φx∗.It follows from assumption (A3) and Φ(x∗)∈X that ∑j=1lζj(x∗,zj∗)=0. Then we easily show that x∗=Φ(x∗) by using assumption (A3).
Whenx∗∈∂Ωg, we have gi(x∗)<0, i∉B(x∗), gi(x∗)=0, i∈B(x∗), and h(x∗)=0, so x∗∈∂Ω. Because gi(x∗)<0, i∉B(x∗), from the third equation in (26), yi∗=0, ∀i∉B(x∗). Then (26) yields(28)x∗+∑i∈Bx∗ηix∗,yi∗+∑j=1lζjx∗,zj∗=Φx∗.It follows from assumption (A4) and Φ(x∗)∈Ω that (29)∑i∈Bx∗ηix∗,yi∗+∑j=1lζjx∗,zj∗=0.By using assumption (A3), one obtains z∗=0 and yi∗=0 for i∈B(x∗), and thus x∗=Φ(x∗). This completes the proof.


## 4. Numerical Results

For almost allw(0)∈Ωg0(1)×R++m×Rl, by Theorem 7, the homotopy generates a C1 curve Γw(0) by differentiating the first equation of (13); we get the following theorem.Theorem 8.
The homotopy pathΓw(0) is determined by the following initial value problem to the ordinary differential equation(30)DHw0ws,λsw˙sλ˙s=0,w0,λ0=w0,1,where s is the arc length of the curve Γw(0).Remark 9.
LetA=DHw(0)(w(s),λ(s)), v=(w˙(s)T,λ˙(s))T, and y(s)=(w(s),λ(s)). Thus, (30) can be rewritten as(31)Av=0,y0=w0,1.By solving the equation Av=0 in (31), we obtain a solution v. Thus, (30) becomes the following initial value problem:(32)dyds=v,y0=w0,1.By Theorems 7 and 8, for almost all w(0)∈Ωg0(1)×R++m×Rl, the solution curve Γw(0) of (30) exists. Because the initial value problem (32) is equivalent to (30), the solution of (32) also exists for every s.Now, we discuss how to solve the initial value problem (32). Generally, if we use the numerical methods developed to address the initial value problems of ordinary differential equations to solve (32) alone, then the step length must be sufficiently small to ensure that the sequence {(w(k),λk)} is close enough to the solution curve. Using such methods may greatly increase the computational cost. Because the goal is to try to find a point (w,λ) (when λ is approximately zero) instead of tracking the smooth curve Γw(0) very precisely, it is desirable to combine the numerical methods for solving initial value problems of ordinary differential equations with other methods to develop more efficient methods that are later called predictor-corrector methods [11].Below, we describe the implementation of a standard predictor-corrector method in detail. Suppose that we have obtained a sequence of points(w(i),λi), i=1,…,k, starting with an initial guess (w(0),1). To obtain (w(k+1),λk+1), we must compute the tangent vector v. By the basic theory of homotopy methods, the vector v satisfies the following conditions:(a)
v=1.(b)
v keeps the sign of the determinant of (AT,v)T invariant.We then consider the following system:(33)Av=0,v=1,which can enable us to obtain a unit tangent vector v(k) at (w(k),λk). One of the main solution strategies for (33) is based on the QR decomposition. For more details, the reader is referred to [11]. By Theorem 7, the matrix A∈R(n+m+l)×(n+m+l+1) is of full row rank. From (33), the unit tangent vector v at a point on Γw(0) has two opposite directions: one (the positive direction) makes s increase, and the other (the negative direction) makes s decrease. Because the negative direction will lead us back to the initial point, we must go along the positive direction. In the following discussion, for convenience, A is denoted by DHw(0)(w,λ). The criterion that determines the positive direction is based on condition (b). In the first iteration, the sign is determined by the following lemma.Lemma 10.
IfΓw(0) is smooth, then the positive direction v(0) at the initial guess (w(0),1) satisfies (34)signDHw0w0,1v0T=-1m+l+1.Proof.
Because(35)DHw0w0,1=∂Hw0w0,1∂w,λ=I00a0∇hx0T0-I-hx0AB0b0=M1,M2,where(36)a=-x-Φx-∑i=1m∂ηix,1-λyi∂λ-∑j=1l∂ζjx,1-λzj∂λ,a0=aw=w0,λ=1,bi=∂yigiAiλx+biλ+λci∂λ-yi0giA1x0+bi1+ci,i=1,…,m,b0=b1,…,bmTw=w0,λ=1,M1∈Rn+m+l×n+m+l,M2∈Rn+m+l×1,the tangent vector v(0) at (w(0),1) satisfies(37)M1,M2v0=M1,M2v10v20=0,where v1(0)∈Rn+m+l and v2(0)∈R1. From (37), it is easy to show that v1(0)=-M1-1M2v2(0). Therefore, the determinant of DHw(0)(w(0),1)v(0)T is (38)DHw0w0,1v0T=M1M2v10Tv20T=M1M2-M2TM1-T1v20=M1v201+M2TM1-TM1-1M2=I00∇hx0T0-IAB0v201+M2TM1-TM1-1M2=-IBv201+M2TM1-TM1-1M2=-1l·diagg1A11x0+b11+c1,…,gmAm1x0+bm1+cm·v201+M2TM1-TM1-1M2.Because gi(Ai(1)x(0)+bi(1))+ci<0, i=1,…,m, (1+M2TM1-TM1-1M2)>0 and v2(0)>0, the sign of the determinant DHw(0)(w(0),1)v(0)T is (-1)m+l+1.Therefore, by using the Euler method, for some small step lengthhk>0 (not too small), we are able to obtain a predictor point (w¯(k),λ¯k)=(w(k),λk)+hkv(k). Here, we do not substitute more complicated algorithms for the Euler method because the predictor point does not need to be close enough to the smooth curve Γw(0) if only it lies in the interior of the convergence domain of Newton’s method during the corrector phase.Next, we may perform a corrector step. Set(39)DHw0w,λ+=DHw0w,λTDHw0w,λDHw0w,λT-1,which is the Moore-Penrose inverse of DHw(0)(w,λ). The corrector phase then tries to identify a corrector point (w(k+1),λk+1) on the path Γw(0). The corrector step is usually carried out by Newton’s method that uses the Moore-Penrose inverse of DHw(0)(w,λ), starting with (w¯(k),λ¯k) and proceeding until Hw(0)(w(k+1),λk+1) is approximately zero. The following pseudocode describes the basic steps of a generic predictor-corrector method.Algorithm 11 (Euler-Newton method).
⁡
Step  0. Provide an initial guess (w(0),1), an initial step length h0>0, and three small positive numbers ϵ1>0, ϵ2>0, and ϵ3>0. Set k=0.
Step  1. Compute the direction η(k) of the predictor step: (a)
Compute a unit tangent vectorv(k).(b)
Determine the directionη(k) of the predictor step as follows:
If the sign of the determinantDHw(0)(w(k),λk)v(k)T is (-1)m+l+1, then η(k)=v(k).If the sign of the determinantDHw(0)(w(k),λk)v(k)T is (-1)m+l, then η(k)=-v(k).
Step  2. Compute a corrector point (w(k+1),λk+1). (40)w¯k,λ¯k=wk,λk+hkηk,wk+1,λk+1=w¯k,λ¯k-DHw0w¯k,λ¯k+Hw0w¯k,λ¯k.IfHw(0)(w(k+1),λk+1)≤ϵ1, then let hk+1=min{h0,2hk}, and go to Step  3.IfHw(0)(w(k+1),λk+1)∈(ϵ1,ϵ2), then let hk+1=hk, and go to Step  3.IfHw(0)(w(k+1),λk+1)≥ϵ2, then let hk+1=max{2-25h0,(hk/2)}, k=k+1, and go to Step  2.
Step  3. If λk+1≤ϵ3, then stop. Otherwise, k=k+1, and go to Step  1.By using homotopy (1) and the predictor-corrector algorithm, we give several numerical examples to illustrate the work in this paper. In each example, we set ϵ1=1·e-3, ϵ2=1·e-6, and h0=0.02. The behaviors of homotopy paths are shown in Figures 3, 4, and 5. Computational results are given in Table 1, where x(0) denotes the initial guess, IT denotes the number of iterations, H denotes the value of Hw(0)(w(k),λk) when the algorithm stops, and x∗ denotes the fixed point.Table 1
Numerical results of Examples12–14.
Example x ( 0 ) I T λ ∗ H x ∗ Φ ( x ∗ ) 2 (−0.5, 0.3) 12 0.000000 0.000000 (−0.977199, 0.000000) (−0.977199, 0.000000) (−0.5, −0.3) 13 0.000000 0.000000 (−0.977377, 0.000000) (−0.977377, 0.000000)  3 (4, 2) 9 0.000000 0.000000 (3.000000, 0.000000) (3.000000, 0.000000) (4, −2) 7 0.000000 0.000000 (3.000000, −0.000001) (3.000000, −0.000001)  4 (−3, 1) 10 0.000000 0.000000 (−0.000000, −2.500000) (−0.000000, −2.500000) (3, 1) 10 0.000000 0.000000 (0.000000, −2.500001) (0.000000, −2.500001)Figure 3
The pathways generated by homotopy (1).Figure 4
The pathways generated by homotopy (1).Figure 5
The pathways generated by homotopy (1).Example 12 (see Example1).
In this example, we select two initial pointsx1(0)=(-0.5,0.3) and x2(0)=(-0.5,-0.3) in Ωg0(1). The pathways generated by homotopy equation (1) are shown in Figure 3. When λ→0, we can find a fixed point x∗=(-0.977199,0) of Φ(x) in Ωg following the homotopy pathways Γw(0)1 and Γw(0)2, respectively.Example 13.
To find a fixed point of self-mappingΦ(x)=(x1,-x2)T in (41)Ω=x1,x2∈R2:3x1+2x22-9=0,-4x2-13≤0,4x2-13≤0,in this example, we introduce the C2 functions ξ(x,y)=∇g(x)y and ζ(x,z)=(-8,0)Tz. Assumptions (A1)–(A4) are easily verified. We set Ωg0={(x1,x2)∈R2:-4x2-13<0,4x2-13<0} and select two initial points x3(0)=(4,2) and x4(0)=(4,-2) in Ωg0. The initial points can be more easily selected in Ωg0 than in Ω0, because Ω0 contains the equality constraint 3x1+2x22-9=0. The pathways generated by homotopy equation (1) are shown in Figure 4. When λ→0, we can find a fixed point x∗=(3,0) of Φ(x) in Ω following the homotopy pathways Γw(0)3 and Γw(0)4, respectively.Example 14.
To find a fixed point of self-mappingΦ(x)=(-x1,x2)T in Ω=x1,x2∈R2:2x2+3x12+5=0,-x1-4.5≤0,x1-4.5≤0, In this example, we introduce the C2 functions ξ(x,y)=∇g(x)y and ζ(x,z)=(0,-6)Tz. Assumptions (A1)–(A4) are easily verified. We set Ωg0={(x1,x2)∈R2:-x1-4.5<0,x1-4.5<0} and select two initial points x5(0)=(-3,1) and x6(0)=(3,1) in Ωg0. The initial points can be more easily selected in Ωg0 than in Ω0, because Ω0 contains the equality constraint 2x2+3x12+5=0. The pathways generated by homotopy equation (1) are shown in Figure 5. When λ→0, we can find a fixed point x∗=(0,-2.5) of Φ(x) in Ω following the homotopy pathways Γw(0)5 and Γw(0)6, respectively.


## 5. Conclusions

In this paper, we apply appropriate perturbations to the constraint functions and hence develop a parameter perturbation homotopy continuation method for solving fixed point problems with both inequality and equality constraints. Our results make initial points of the algorithm be chosen more easily than the previous results in the literature and improve the efficiency of the algorithm greatly. Because fixed point problems have been widely applied to many areas such as mechanics, physics, transportation, control, economics, differential equations, and optimization, our results may be useful to propose a powerful solution tool for dealing with these practical problems. In the future, we want to propose new techniques to extend our results to more general nonconvex sets and extend the method proposed in this paper to solve the periodicity problems of some important differential equations.



---

*Source: 4067202-2017-02-13.xml*