# Solving Fixed-Point Problems with Inequality and Equality Constraints via a Non-Interior Point Homotopy Path-Following Method

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

---

## Abstract

In recent years, fixed-point theorems have attracted increasing attention and have been widely investigated by many authors. Moreover, determining a fixed point has become an interesting topic. In this paper, we provide a constructive proof of the general Brouwer fixed-point theorem and then obtain the existence of a smooth path which connects a given point to the fixed point. We also present a non-interior point homotopy algorithm for solving fixed-point problems on a class of nonconvex sets by numerically tricking this homotopy path.


---

## Body

## 1. Introduction

In recent years, fixed-point theorems have attracted increasing attention and have been widely investigated by many authors (e.g., [1–4] and the references therein) because these theorems play important roles in mechanics, physics, differential equations, and so on. The determination of a constructive proof of the fixed-point theorem and therefore finding a fixed point became an attractive topic. The homotopy method, as a globally convergent algorithm, is a powerful tool in handling fixed-point problems (e.g., [5–10] and the references therein). The general Brouwer fixed-point theorem states that if a bounded closed subset in Rn is diffeomorphic to the closed unit ball, then any continuous self-mapping in it has a fixed point. However, the abovementioned results generally require certain convexity assumptions; thus, the traditional homotopy method cannot be used to handle the general Brouwer fixed-point theorem. Until 1996, Yu and Lin [11] combined the ideas of interior point methods and homotopy methods to propose a homotopy interior path-following method (see [12–17] for more details) that provides a constructive proof of the general Brouwer fixed-point theorem on a class of nonconvex subsets, without constructing a homeomorphism for transforming the bounded closed set to the closed unit ball. In [18, 19], the authors furthermore extended the results in [11] to more general nonconvex sets with inequality and equality constraint functions by replacing the gradient mappings with the newly introduced C2 mappings.The expansion of the scope of initial point selection to improve the computational efficiency of an algorithm is an important research area. In [20], we applied appropriate perturbations to the constraint functions and developed a new homotopy method to expand the scope of initial point selection, but involving the inequality constraint cases only. In [21], using similar perturbations to the inequality constraints in [20], we mainly extended the results in [18] to unbounded cases by providing a set of unbounded conditions. It should be pointed out that the results in [18, 19] excluded the initial point selection; in addition, the researchers excluded the equality constraint cases, although the results in [20, 21] expanded the scope of initial point selection. It is difficult to construct appropriate perturbations and to guarantee the regularity of the homotopy matrix for the existence of the equality constraints. To overcome the difficulties mentioned above, we apply new perturbations to the equality constraints and construct a new homotopy matrix to guarantee its regularity. Therefore, we develop a non-interior point homotopy path-following method for solving fixed-point problems with inequality and equality constraints. We can select initial points easily and thus considerably improve the computational efficiency of the algorithm by using the new approach.This paper is organized as follows. Section2 introduces two parameters and constructs appropriate perturbations to the constraint functions to develop a non-interior point homotopy path-following method for solving fixed-point problems with equality and inequality constraints. Section 3 presents several experimental examples to illustrate the results in this paper.


## 2. Main Results

In this section, we use the following notations:x∈Rn, y∈Rm, z∈Rl, gx=g1x,…,gmxT, hx=h1x,…,hmxT, ∇gx=∇g1x,…,∇gmx∈Rn×m, ∇hx=∇h1x,…,∇hlx∈Rn×l, αx=α1x,…,αmx∈Rn×m, βx=β1x,…,βlx∈Rn×l, X=x∈Rn:gx≤0,hx=0, X0=x∈Rn:gx≤0,hx=0, R+m=x∈Rm:x≥0, R++m=x∈Rm:x>0, and Bx=i∈1,…,m:gix=0.In [18], we extended the results in [11] to more general sets under the following assumptions:A
1  X0 is nonempty and X is bounded.A
2  For any x∈X, if(1)∑i∈Bxui∇gix+yiαix+∑j=1lzjβjx=0,ui≥0,yi≥0,zj∈R1,then ui=0, yi=0, ∀i∈Bx, and zj=0, j=1,…,l.A
3 The weak normal cone condition of X: for any x∈X, we have(2)x+∑i∈Bxyiαix+βxz:ui≥0,i∈Bx,z∈Rl∩X=x.A
4 For any x∈X, ∇hx is of full column rank and ∇hxTβx is nonsingular.In this study, we introduce the following parameters to construct appropriate perturbations to the constraint functions:(3)γi=2gix0,gix0>0,1,gix0=0,0,gix0<0,i=1,…,m,θj=1,hjx0≠0,0,hjx0=0,j=1,…,l,where x0 is an arbitrarily given point. Then, set Υ=diagγ1,…,γm, Θ=diagθ1,…,θl, em=1,…,1T∈Rm, X(λ)={x∈Rn:g(x)-λΥ(g(x0)+em)≤0, h(x)-λΘh(x(0))=0}, X0(λ)={x∈Rn:g(x)-λΥ(g(x0)+em)<0, h(x)-λΘh(x(0))=0}, and Ix,λ=i∈1,…,m:gix-λγigix0+1=0.To solve fixed-point problems in more general nonconvex sets, we also introduce the continuous mappingsξx,u=ξ1x,u1,…,ξmx,um∈Rn×m and ηx,v=η1x,v1,…,ηlx,vl∈Rn×l which satisfy the following conditions:C
1
X
0
λ is nonempty and Xλ is bounded.C
2
ξ
i
x
,
0
=
0, i=1,…,m, ηjx,0=0, j=1,…,l; besides, for any x∈Xλ, if y,z,u,v→∞, then(4)∑i∈Ix,λyi∇gix+ξix,ui+∇hxz+∑j=1lηx,vj⟶∞.C
3 For any x∈Xλ, if(5)∑i∈Ix,λyi∇gix+ξix,ui+∇hxz+∑j=1lηx,vj=0,yi≥0,ui≥0,then yi=0, ui=0, ∀i∈Ix,λ, z=0, vj=0, j=1,…,l. Besides, the matrix ∇hxT∇z∑j=1lηjx,zj is nonsingular.C
4 When λ=0,1, for any x∈Xλ, we have (6)x+∑i∈Ix,λξix,ui+∑j=1lηx,vj:ui≥0fori∈Ix,λ,vj∈R1∩Xλ=x.From the geometric perspective in R2, we explain that the results in [18] are extended to more general nonconvex sets. Set X1=x+∑i∈Bxyiαix+βxz; note that ∑i∈Bxyiαix+βxz is the linear combinations of αix∈Rn,i = 1,…,m, and βjx∈Rn, j=1,…,l, and the set X1 is not a bending cone surrounded by several radials or beelines; thus, many nonconvex sets cannot satisfy assumption A3 in [18]. However, set X2=x+∑i∈Ix,0ξix,ui+∑j=1lηjx,vj. Note that αix∈Rn, i=1,…,m, and βjx∈Rn, j=1,…,l, are the special cases of ξix,ui∈Rn, i=1,…,m, and ηjx,vj∈Rn, j=1,…,l; in many cases, X2 may be a bending cone surrounded by several curves because ξix,ui, i=1,…,m, and ηjx,vj, j=1,…,l, are arbitrary functions of ui, i=1,…,m,vj, j=1,…,l. This point enables many nonconvex sets to not satisfy assumption A3 but to satisfy assumption C4.To solve fixed-point problems, we construct the following new homotopy equation:(7)HP,P0,λ=1-λx-Φx+∑i=1m1-λλ∇gixyi+∑i=1mξix,1-λyi+1-λλ∇hxz+α+∑j=1lηjx,zj+λx-x0hx-λΘhx0Ygx-λΥgx0+em-λY0gx0-Υgx0+em=0,where P=x,y,z∈Rn+m+l, P0=x0,y0,z0∈X01×R++m×Rl, α∈Rn, Y=diagy, and Y0=diagy0.We rewriteHP,P0,λ as HP0P,λ for a given P0. The zero-point set of HP0 is(8)HP0-10=P,λ∈Rn×R+m×Rl×0,1:HP0P,λ=0.Lemmas 1–4 will be used in the proof of our main results.Lemma 1 (see [22]).
LetΦ:Rn+1→Rn be a C1 map and 0 a regular value of Φ. Then, Φ-10 is a C1 manifold of dimension 1.Lemma 2 (see [22]).
AC1 manifold of dimension 1 is diffeomorphic to a loop or an interval.Lemma 3 (transversality theorem).
LetQ, N, and P be smooth manifolds with dimensions q, m, and p~, respectively. Let W⊂P be a submanifold of codimension p (i.e., the p~=p+ dimension of W). Consider a smooth map Φ:Q×N→P. If Φ is transversal to W, then, for almost all a∈Q, Φa·=Φa,·:N→P is transversal to W. Recall that a smooth map h:N→P is transversal to W if(9)RangeDhx+TyW=TyP,whenevery=hx∈W,where Dh is the Jacobi matrix of h and TyW and TyP denote the tangent spaces of W and P at y, respectively.In this paper,W=0; thus, Lemma 3 corresponds to Lemma 4.Lemma 4 (parameterized Sard’s theorem).
LetV⊂Rn and U⊂Rm be open sets and Φ: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,·.Lemma 5.
LetH be defined as in (7); let gix, i=1,…,m, and hjx, j=1,…,l, be C3 functions; let assumptions(C1)–(C4) hold; and let ξix,ui∈Rn, i=1,…,m, andηjx,vj∈Rn, j=1,…,l, be C2 functions. Then, for almost all x0∈X01, 0 is a regular value of map HP0:Rn×R+m×Rl×0,1→Rn+m+l, and HP0-10 consists of some smooth curves. Among them, a smooth curve, denoted by ΓP0, starts from P0,1.Proof.
We denoteHP,P0,λ by H¯P,P0,α,λ when α is considered as a variable. Let the Jacobian matrix of H¯P,P0,α,λ be denoted by DH¯P,P0,α,λ. For any λ∈0,1,(10)∂H¯P,P0,α,λ∂x,α,y=Aλ1-λIB∇hxT00Y∇gxT0diaggx-λΥgx0+em,where(11)A=1-λI-∇Φx+∑i=1m1-λλ∇2gixyi+∑i=1m∇xξix,1-λyi+1-λλ∇2hxz+∑j=1l∇xηjx,zj+λI,B=1-λ2λ∇gxT+1-λ∑i=1m∇yiξix,1-λyiT.Because ∇hxT is a matrix of full row rank, ∂H¯P,P0,α,λ/∂x,α,y is of full row rank. Therefore, DH¯P,P0,α,λ is also of full row rank, and 0 is a regular value of H¯P,P0,α,λ. By Lemma 4, for almost all P0∈X01×R++m×Rl, we obtain that 0 is a regular value of map HP0:Rn×R+m×Rl×0,1→Rn+m+l. By Lemma 1, HP0-10 consists of several smooth curves. Because HP0P0,1=0, then a C1 curve Ps,λs of dimension 1, denoted by ΓP0, starts from P0,1.Lemma 6.
LetH be defined as in (7); let gix, i=1,…,m, and hjx, j=1,…,l, be C3 functions; let assumptions(C1)–(C4) hold; and let ξix,ui∈Rn, i=1,…,m, and ηjx,vj∈Rn, j=1,…,l, be C2 functions. Then, for almost all x0∈X01, ΓP0 is a bounded curve.Proof.
Assume thatΓP0 is an unbounded curve. Then, there exists a sequence of points Pk,λk⊂ΓP0 such that Pk,λk→∞. Because Xλ and 0,1 are bounded, hence there exists a subsequence of points (denoted also by Pk,λk) such that xk→x∗, yk,zk→∞, and λk→λ∗ as k→∞. From the homotopy equation (7), we obtain(12)1-λkxk-Φxk+∑i=1m1-λkλk∇gixkyik+∑i=1mξixk,1-λkyik+1-λkλk∇hxkzk+α+∑j=1lηjxk,zjk+λkxk-x0=0,(13)hxk-λkΘhx0=0,(14)Ykgxk-λkΥgx0+em-λkY0gx0-Υgx0+em=0.Let (15)Ix∗=i∈1,…,m:limk→∞⁡yik=∞,Jx∗=j∈1,…,l:limk→∞⁡zjk=∞.If Jx∗≠∅, from (12), one obtains(16)1-λkxk-Φxk+∑i∉Ix∗1-λk2λk∇gixkyik+∑i∉Ix∗ξixk,1-λkyik+λkxk-x0+1-λkλk∇hxkzk+α+∑j=1lηjxk,zjk+∑i∈Ix∗1-λk2λk∇gixkyik+∑i∈Ix∗ξixk,1-λkyik=0.The sixth to ninth parts in the left-hand side of (16) tend to infinity as k→∞, but the other five parts are bounded, which is impossible. Therefore, the projection of the smooth curve ΓP0 onto the z-plane is also bounded. Now, we can assume that zk→z∗. Simultaneously, Ix∗≠∅.
If case (c) holds, then there exists a sequence of pointsPk,λk⊂ΓP0 such that Pk,λk→∞. Because Xλ and 0,1 are bounded, hence there exists a subsequence of points (denoted also by Pk,λk) such that xk→x∗, yk→∞, zk→z∗, and λk→λ∗ as k→∞. From (14), we obtain(17)gixk-λkγigix0+1=λkyik-1yi0gix0-γigix0+1,i=1,…,m.When λ∗>0, the index set is(18)Ix∗,λ∗=i∈1,…,m:limk→∞⁡yik=∞. When λ∗=0, the index set is(19)I0x∗,0=i∈1,…,m:limk→∞⁡yik=∞⊂Ix∗,0.(1) If λ∗=1, from (12), we obtain(20)xk-x0+∑i∈Ix∗,11-λk2λk∇gixkyik+∑i∈Ix∗,1ξixk,1-λkyik+1-λkλk∇hxkzk+α+∑j=1lηjxk,zjk=-∑i∉Ix∗,11-λk2λk∇gixkyik-∑i∉Ix∗,1ξixk,1-λkyik+1-λkΦxk-x0.By assumptions C2, C3, and (20), we obtain(21)limk→∞⁡1-λkyik=yi∗,where yi∗≥0. Therefore, from (20) and (21), we obtain(22)x∗+∑i∈Ix∗,1ξix∗,yi∗+∑j=1lηjxk,zj∗=x0,which contradicts assumption C4.
(
2
) If 0<λ∗<1, from (12), we obtain(23)∑i∈Ix∗,λ∗1-λk2λk∇gixkyik+∑i∈Ix∗,λ∗ξixk,1-λkyik=-∑i∉Ix∗,λ∗1-λk2λk∇gixkyik-∑i∉Ix∗,λ∗ξixk,1-λkyik-1-λkλk∇hxkzk+α-∑j=1lηjxk,zjk-1-λkxk-Φxk-λkxk-x0.When k→∞, because Xλ∗ and yik, i∉Ix∗,λ∗, are bounded, the right-hand side of (23) is bounded. But, by assumption C2, if yik→∞, i∈Ix∗,λ∗, then the left-hand side of (23) tends to be infinite. This results in a contradiction.
(
3
) If λ∗=0, then the proof is similar to that of (12) because the nonempty index set I0x∗,0⊂Ix∗,0.Now, we aim to prove our main result, that is, Theorem7.Theorem 7.
LetH be defined as in (7) and let assumptions(C1)–(C4) hold. Then, for almost all P0∈X01×R++m×0, there exists a C1 curve Ps,λs of dimension 1 such that(24)HPs,P0,λs=0,P0,λ0=P0,1.When λs→0, Ps tends to be point P∗=x∗,y∗,z∗, the x-component of which is a fixed point of Φx in X.Proof.
By Lemmas5 and 6, we obtain that there exists a C1 curve ΓP0 starting from P0,1. For any P0∈X01×R++m×Rl, it is easy to show that ∂P0HP0,1/∂P is nonsingular. By Lemma 2, we conclude that ΓP0 is diffeomorphic to a unit interval.
LetP∗,λ∗ be a limit point of ΓP0, and then the following cases may occur:
(a)P∗,λ∗=x∗,y∗,z∗,λ∗∈X×R+m×Rl×0.
(b)P∗,λ∗=x∗,y∗,z∗,λ∗∈X01×R++m×Rl×1.
(c)P∗,λ∗=x∗,y∗,z∗,λ∗∈∂Xλ∗×R+m×Rl×0,1.
Whenλ=1, the homotopy equation (7) becomes(25)∑j=1lηjx,zj+x-x0=0,(26)hx-Θhx0=0,(27)Ygx-Υgx0+em-Y0gx0-Υgx0+em=0.From (26) and (27), we obtain x∈X01. Then, assumption C4, together with (25), yields that x=x0. By assumption C2, we obtain zj=0, j=1,…,l. Besides, it follows from (27) that y=y0. Then, (25)–(27) have a unique solution P=P0=x0,y0,0 in X01×R++m×Rl×1; therefore, case (b) is impossible.
In case (c), we prove thaty∗∉∂R+m. If y∗∈∂R+m, then there exist i0∈1,…,m and a sequence of points Pk,λk⊂ΓP0 such that yi0k→yi0∗=0 as k→+∞. From (14), we obtain(28)yi0kgi0xk-λkγi0gi0x0+1=λkyi00gi0x0-γi0gi0x0+1.When k→+∞, because Xλ and 0,1 are bounded, the left-hand side of (28) tends to be 0. Simultaneously, the right-hand side of (28) tends to be λ∗yi00gi0x0-γi0gi0x0+1, which is strictly less than 0. This results in a contradiction.
Then, we prove thatx∗∉∂Xλ∗. If x∗∈∂Xλ∗, then there exist i0∈1,…,m and a sequence of points Pk,λk⊂ΓP0 such that gi0xk-λkγi0gi0x0+1→0, yi0k→∞ as k→+∞. This contradicts Lemma 6; thus, case (c) is also impossible.
From the above discussion, we conclude that case (a) is the only possible case. Therefore,P∗ is a solution of (7) when λ=0, and x∗ is a fixed point of Φx in X.By differentiating the first equation in (24), we obtain Theorem 8, which, together with Theorem 7, can reduce various predictor-corrector algorithms (see [8] and the references therein).Theorem 8.
The homotopy pathΓP0 is determined by the following initial value problem to the ordinary differential equation:(29)DHPs,λsP˙sλ˙s=0,P0,λ0=P0,1,where s is the arc length of the curve ΓP0.In implementing the predictor-corrector algorithm, we must proceed along the positive direction of the unit tangent vectorv at a point on ΓP0. The criterion that determines the positive direction is based on the condition that v maintains the sign of the determinant of DHP0P,λT,vT. In the first iteration, the sign is determined by the following lemma.Lemma 9.
IfΓP0 is smooth, then the positive direction v0 at the initial guess P0,1 satisfies signDHP0P0,1v0T=-1m+l+1.Proof.
Note thatDHP0P0,1=∂HP0P0,1/∂P,λ:(30)=I0∇z∑j=1lηjx0,zj0a0∇hx0T00-Θhx0Y0∇gx0Tdiaggx0-λΥgx0+em0b0=M1,M2,where(31)a=Φx-x0+∑i=1m3λ-2∇gixyi-∑i=1m∂ξix,1-λyi∂λ+1-2λ∇hxz+α,a0=aP=P0,λ=1,b0=-Y0gx0-ϒgx0+em,M1∈Rn+m+l×n+m+l,M2∈Rn+m+l×1.The tangent vector v0 at P0,1 satisfies(32)M1,M2v0=M1,M2v10v20=0,where v10∈Rn+m+l and v20∈R1. From (32), we obtain v10=-M1-1M2v20.
Therefore, the determinant ofDHP0P0,1v0T is(33)DHP0P0,1v0T=M1M2v10Tv20T=M1M2-M2TM1-T1v20=M1v201+M2TM1-TM1-1M2=I0∇z∑j=1lηjx0,zj0∇hx0T00Y0∇gx0Tdiaggx0-λΥgx0+em0·v201+M2TM1-TM1-1M2=-Idiaggx0-λΥgx0+emv201+M2TM1-TM1-1M2=-1l·diaggx0-λΥgx0+em·v201+M2TM1-TM1-1M2.Because gx0-λΥgx0+em<0, 1+M2TM1-TM1-1M2>0, and v20>0, the sign of the determinant DHP0P0,1v0T is -1m+l+1.


## 3. Numerical Results

In this section, the numerical results provided below are obtained through the predictor-corrector algorithm. In each example, we setϵ1=1·e-3, ϵ2=1·e-6, and h0=0.02. The behavior of homotopy paths is graphically illustrated, which can deliver a visual insight into the performance of our computer code. Computational results are summarized in Table 1, where x0 denotes the initial guess, IT is the number of iterations, H is the value of HP0Pk,λk when the algorithm stops, and x∗ is the fixed point.Table 1
Numerical results of Examples1–3.
Examples
x
0
I
T
λ
∗
H
x
∗
Φ
x
∗
Example1
(1, 2)
5
0.000000
0.000000
(−1.000000, 1.000002)
(−1.000000, 1.000002)
(−3, −2)
8
0.000000
0.000000
(−1.000000, 0.999999)
(−1.000000, 0.999999)
Example2
(−2, 1)
7
0.000000
0.000000
(0.333333, 0.000000)
(0.333333, 0.000000)
(−2, −1)
8
0.000000
0.000000
(0.333333, −0.000000)
(0.333333, −0.000000)
Example3
(−3, 3)
11
0.000000
0.000000
(−0.000000, 10.000000)
(−0.000000, 10.000000)
(3, 3)
11
0.000000
0.000000
(−0.000000, 10.000000)
(0.000000, 10.000000)Example 1.
One finds a fixed point of self-mappingΦx=x1,2-x2T in(34)X=x1,x2∈R2:x1-3≤0,x1-22+x2-12-9=0.Let ξx,y=∇gxy and ηx,z=24+2x1-2,2x2-1Tz, and then assumptions C1–C4 are satisfied. Based on the results of this study, we select initial points x10=1,2 and x20=-3,-2 which are not confined to the interior of the feasible sets. We obtain a fixed point x∗=-1,1 of Φx in X when λ→0, following the discrete homotopy pathways ΓP01 and ΓP02, as illustrated in Figure 1.Figure 1
The discrete homotopy pathways of Example1.Example 2.
One finds a fixed point of self-mappingΦx=x1,-x2T in the set(35)X=x1,x2∈R2:-x1-x22+8≤0,3x1-2x22-1=0. Let ξx,y=∇gxy and ηx,z=6,0Tz, and then assumptions C1–C4 are satisfied. Based on the results of this study, we can select initial points x30=-2,1 and x40=-2,-1 which are not confined to the interior of the feasible sets. We obtain a fixed point x∗=(0.333333,0) of Φx in X when λ→0, following the discrete homotopy pathways ΓP03 and ΓP04, as illustrated in Figure 2.Figure 2
The discrete homotopy pathways of Example2.Example 3.
One finds a fixed point of self-mappingΦx=-x1,x2T in the set(36)X=x1,x2∈R2:-x1-2π≤0,x1-2π≤0,x2-10cos⁡2x1=0. Let C2 functions ξx,y=∇gxy and ηx,z=0,10Tz, and then assumptions C1–C4 are satisfied. Based on the results of this study, we can select initial points x50=-3,3 and x20=3,3 which are not confined to the interior of the feasible sets. We obtain a fixed point x∗=0,10 of Φx in X when λ→0, following the discrete homotopy pathways ΓP05 and ΓP06, as illustrated in Figure 3.Figure 3
The discrete homotopy pathways of Example3.



---

*Source: 3456834-2017-11-16.xml*