Printer Friendly

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

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 [R.sup.n] 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 [C.sup.2] 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. Section 2 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 [member of] [R.sup.n], y [member of] [R.sup.m], z [member of] [R.sup.l], g(x) = [([g.sub.1](x), ..., [g.sub.m](x)).sup.T], h(x) = [([h.sub.1](x), ..., [h.sub.m](x)).sup.T], [nabla]g(x) = ([nabla][g.sub.1](x), ..., [nabla][g.sub.m](x)) [member of] [R.sup.nxm], [nabla]h(x) = ([nabla][h.sub.1](x), ..., [nabla][h.sub.l](x)) [member of] [R.sup.nxl], [alpha](x) = ([[alpha].sub.1](x), ..., [[alpha].sub.m](x)) [member of] [R.sup.nxm], [beta](x) = ([[beta].sup.1](x), ..., [[beta].sup.l](x)) [member of] [R.sup.nxl], X = {x [member of] [R.sup.n] : g(x) [less than or equal to] 0, h(x) = 0}, [X.sup.0] = {x [member of] [R.sup.n] : g(x) [less than or equal to] 0, h(x) = 0}, [R.sup.m.sub.+] = {x [member of] [R.sup.m] : x [greater than or equal to] 0}, [R.sup.m.sub.++] = {x [member of] [R.sup.m] : x > 0}, and B(x) = {i [member of] {1, ..., m} : [g.sub.i](x) = 0}.

In [18], we extended the results in [11] to more general sets under the following assumptions:

([A.sub.1]) [X.sup.0] is nonempty and X is bounded.

([A.sub.2]) For any x [member of] X, if

[summation over (i[member of]B(x))]([u.sub.i][nabla][g.sub.i] (x) + [y.sub.i][[alpha].sub.i] (x)) + [l.summation over (j=1)][z.sub.j][[beta].sub.j](x) = 0, [u.sub.i] [greater than or equal to] 0, [y.sub.i] [greater than or equal to] 0, [z.sub.j] [member of] [R.sup.1], (1)

then [u.sub.i] = 0, [y.sub.i] = 0, [for all]i [member of] B(x), and [z.sub.j] = 0, j = 1, ..., l.

(A3) The weak normal cone condition of X: for any x[ member of] X, we have

{x + [summation over (i[member of]B(x))] [y.sub.i][[alpha].sub.i] (x) + [beta] (x) z : [u.sub.i] [greater than or equal to] 0, i [member of] B (x), z [member of] [R.sup.l]} [intersection] X= {x}. (2)

(A4) For any x[member of]X, [nabla]h(x) is of full column rank and [nabla]h[(x).sup.T][beta](x) is nonsingular.

In this study, we introduce the following parameters to construct appropriate perturbations to the constraint functions:

[mathematical expression not reproducible], (3)

where [x.sup.(0)] is an arbitrarily given point. Then, set Y = diag([[gamma].sub.1], ..., [[gamma].sub.m]), [THETA] = diag([[theta].sub.1], ..., [[theta].sub.l]), [e.sub.m] = [(1, ..., 1).sup.T] [member of] [R.sup.m], X([lambda]) = {x [member of] [R.sup.n] : g(x) - [lambda]Y(g([x.sup.(0)]) + [e.sub.m]) [less than or equal to] 0, h(x) - [lambda][THETA]h([x.sup.(0)]) = 0}, [X.sup.0] ([lambda]) = {x [member of] [R.sup.n] : g(x) - [lambda]Y(g([x.sup.(0)]) + [e.sub.m]) < 0, h(x) - [lambda][THETA]h([x.sup.(0)]) = 0}, and I(x, [lambda]) = {i [member of] {1, ..., m} : [g.sub.i](x) - [lambda][[gamma].sub.i]([g.sub.i]([x.sup.(0)]) + 1) = 0}.

To solve fixed-point problems in more general nonconvex sets, we also introduce the continuous mappings [xi](x, u) = ([[xi].sub.1](x, [u.sub.1]), ..., [[xi].sub.m](x, um)) [member of] [R.sup.nxm] and [eta](x, v) = ([[eta.sub.]1](x, [v.sub.1]), ..., [[eta].sub.l](x, [v.sub.l])) [member of] [R.sup.nxl] which satisfy the following conditions:

([C.sub.1]) [X.sup.0]([lambda]) is nonempty and X([lambda]) is bounded.

([C.sub.2]) [[xi].sub.i](x, 0) = 0, i = 1, ..., m, [[eta].sub.j](x, 0) = 0, j = 1, ..., l; besides, for any x [member of] X([lambda]), if [parallel](y, z, u, v)[parallel] [right arrow] [infinity], then

[parallel][summation over (i[member of]I(x,[lambda]))] ([y.sub.i][nabla][g.sub.i] (x) + [[xi].sub.i] (x, [u.sub.i])) + [nabla]h (x) z + [l.summation over (j=1)][eta] (x, [v.sub.j])[parallel] [right arrow] [infinity]. (4)

([C.sub.3]) For any x [member of] X([lambda]), if

[summation over (i[member of]I(x,[lambda]))] ([y.sub.i][nabla][g.sub.i] (x) + [[xi].sub.i] (x, [u.sub.i])) + [nabla]h (x) z + [l.summation over (j=1)] [eta] (x, [v.sub.j]) = 0, [y.sub.i] [greater than or equal to] 0, [u.sub.i] [greater than or equal to] 0, (5)

then [y.sub.i] = 0, [u.sub.i] = 0, [for all]i [member of] I(x, [lambda]), z = 0, [v.sub.j] = 0, j = 1, ..., l. Besides, the matrix [nabla]h[(x).sup.T][[nabla].sub.z]([[summation].sup.l.sub.j=1] [[eta].sub.j](x, [z.sub.j])) is nonsingular.

([C.sub.4]) When [lambda] = 0, 1, for any x [member of] X([lambda]), we have

{x + [summation over (i[member of]I(x,[lambda]))] [[xi].sub.i] (x, [u.sub.i]) + [l.summation over (j=1)][eta] (x, [v.sub.j]): [u.sub.i] [greater than or equal to] 0 for i [member of] I (x, [lambda]), [v.sub.j] [member of] [R.sup.1]} [intersection] X ([lambda]) = {x}. (6)

From the geometric perspective in [R.sup.2], we explain that the results in [18] are extended to more general nonconvex sets. Set [X.sub.1] = {x + [[summation].sub.i[member] of B(x)] [y.sub.i][[alpha].sub.i](x) + [beta](x)z}; note that [[summation].sub.i[member of]B(x) [y.sub.i][[alpha].sub.i](x) + [beta](x)z is the linear combinations of [[alpha].sub.i] (x) [member of] [R.sup.n], i = 1, ..., m, and [[beta].sub.j](x) [member of] [R.sup.n], j = 1, ..., l, and the set [X.sub.1] is not a bending cone surrounded by several radials or beelines; thus, many nonconvex sets cannot satisfy assumption ([A.sub.3]) in [18]. However, set [X.sub.2] = {x + [[summation].sub.i[member of]I(x,0)] [[xi].sub.i](x, [u.sub.i]) + [[summation].sup.l.sub.j=1] [[eta].sub.j](x, [v.sub.j])}. Note that [[alpha].sub.i](x) [member of] [R.sup.n], i = 1, ..., m, and [[beta].sub.j](x) [member of] [R.sup.n], j = 1, ..., l, are the special cases of [[xi].sub.i](x, [u.sub.i]) [member of] [R.sup.n], i = 1, ..., m, and [[eta].sub.j](x, [v.sub.j]) [member of] [R.sup.n], j = 1, ..., l; in many cases, [X.sub.2] may be a bending cone surrounded by several curves because [[xi].sub.i](x, [u.sub.i]), i = 1, ..., m, and [[eta].sub.j](x, [v.sub.j]), j = 1, ..., l, are arbitrary functions of [u.sub.i], i = 1, ..., m, [v.sub.j], j = 1, ..., l. This point enables many nonconvex sets to not satisfy assumption ([A.sub.3]) but to satisfy assumption ([C.sub.4]).

To solve fixed-point problems, we construct the following new homotopy equation:

[mathematical expression not reproducible], (7)

where P = (x, y, z) [member of] [R.sup.n+m+l], [P.sup.(0)] = ([x.sup.(0)], [y.sup.(0)], [z.sup.(0)]) [member of] [X.sub.0](1) x [R.sup.m.sub.++] x [R.sup.l], [alpha] [member of] [R.sup.n], Y = diag(y), and [Y.sup.(0)] = diag([y.sup.(0)]).

We rewrite H(P, [P.sup.(0)], [lambda]) as [mathematical expression not reproducible] for a given [P.sup.(0)]. The zero-point set of [mathematical expression not reproducible] is

[mathematical expression not reproducible]. (8)

Lemmas 1-4 will be used in the proof of our main results.

Lemma 1 (see [22]). Let [PHI]: [R.sup.n+1] [right arrow] [R.sup.n] be a [C.sup.1] map and 0 a regular value of [PHI]. Then, [[PHI].sup.-1](0) is a [C.sup.1] manifold of dimension 1. Lemma 2 (see [22]). A [C.sup.1] manifold of dimension 1 is diffeomorphic to a loop or an interval.

Lemma 3 (transversality theorem). Let Q, N, and P be smooth manifolds with dimensions q, m, and [??], respectively. Let W [subset] P be a submanifold of codimension p (i.e., the [??] = p + dimension of W). Consider a smooth map [PHI] : Q x N [right arrow] P. If [PHI] is transversal to W, then, for almost all a [member of] Q, [[PHI].sub.a](x) = [PHI](a, x) : N [right arrow] P is transversal to W. Recall that a smooth map h : N [right arrow] P is transversal to W if

{Range (Dh (x))} + {[T.sub.y]W} = [T.sub.y]P, whenever y = h (x) [member of] W, (9)

where Dh is the Jacobi matrix of h and [T.sub.y]W and [T.sub.y]P 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). Let V [subset] [R.sup.n] and U [subset] [R.sup.m] be open sets and [PHI] : V x U [right arrow] [R.sup.k] be a [C.sup.r] map, where r > max{0, m - k}. If 0 [member of] [R.sup.k] is a regular value of [PHI], then, for almost all a [member of] V, 0 is a regular value of [[PHI].sub.a] [equivalent to] [PHI](a, x).

Lemma 5. Let H be defined as in (7); let [g.sub.i](x), i = 1, ..., m, and [h.sub.j](x), j = 1, ..., l, be [C.sup.3] functions; let assumptions ([C.sub.1])-([C.sub.4]) hold; and let [[xi].sub.i](x, [u.sub.i]) [member of] [R.sup.n], i = 1, ..., m, and [[eta].sub.j](x, [v.sub.j]) [member of] [R.sup.n], j = 1, ..., l, be [C.sup.2] functions. Then, for almost all [x.sup.0] [member of] [X.sup.0](1), 0 is a regular value of map [mathematical expression not reproducible], and [mathematical expression not reproducible] consists of some smooth curves. Among them, a smooth curve, denoted by [mathematical expression not reproducible], starts from ([P.sup.(0)], 1).

Proof. We denote H(P, [P.sup.(0)], [lambda]) by [bar.H](P, [P.sup.(0)], [alpha], [lambda]) when [alpha] is considered as a variable. Let the Jacobian matrix of [bar.H](P, [P.sup.(0)], [alpha], [lambda]) be denoted by D[bar.H](P, [P.sup.(0)], [alpha], [lambda]). For any [lambda] [member of] (0, 1],

[mathematical expression not reproducible], (10)

where

[mathematical expression not reproducible]. (11)

Because [nabla]h[(x).sup.T] is a matrix of full row rank, [partial derivative][bar.H](P, [P.sup.(0)], [alpha], [lambda])/[partial derivative](x, [alpha], y) is of full row rank. Therefore, D[bar.H](P, [P.sup.(0)], [alpha], [lambda]) is also of full row rank, and 0 is a regular value of [bar.H](P, [P.sup.(0)], [alpha], [lambda]). By Lemma 4, for almost all [P.sup.(0)] [member of] [X.sup.0](1) x [R.sup.m.sub.++] x [R.sup.l], we obtain that 0 is a regular value of map [mathematical expression not reproducible]. By Lemma 1, [mathematical expression not reproducible] consists of several smooth curves. Because [mathematical expression not reproducible], then a [C.sup.1] curve (P(s), [lambda](s)) of dimension 1, denoted by [mathematical expression not reproducible], starts from ([P.sup.(0)], 1).

Lemma 6. Let H be defined as in (7); let [g.sub.i](x), i = 1, ..., m, and [h.sub.j] (x), j = 1, ..., l, be [C.sup.3] functions; let assumptions ([C.sub.1])-([C.sub.4]) hold; and let [[xi].sub.i](x, [u.sub.i]) [member of] [R.sup.n], i = 1, ..., m, and [[eta].sub.j](x, [v.sub.j]) [member of] [R.sup.n], j = 1, ..., l, be [C.sup.2] functions. Then, for almost all [x.sup.0] [member of] [X.sup.0](1), [mathematical expression not reproducible] is a bounded curve.

Proof. Assume that [mathematical expression not reproducible] is an unbounded curve. Then, there exists a sequence of points [mathematical expression not reproducible] such that [parallel][P.sup.(k)], [[lambda].sub.k][parallel] [right arrow] [infinity]. Because X([lambda]) and (0, 1] are bounded, hence there exists a subsequence of points (denoted also by {([P.sup.(k)], [[lambda].sup.k])}) such that [x.sup.(k)] [right arrow] [x.sup.*], [parallel]([y.sup.(k)], [z.sup.(k)])[parallel] [right arrow] [infinity], and [[lambda].sub.k] [right arrow] [[lambda].sup.*] as k [right arrow] [infinity]. From the homotopy equation (7), we obtain

(1 - [[lambda].sub.k]) ([x.sup.(k)] - [PHI] ([x.sup.(k)]) + [m.summation over (i=1)] (1 - [[lambda].sub.k]) [[lambda].sub.k][nabla][g.sub.i] ([x.sup.(k)]) [y.sup.(k).sub.i]) + [m.summation over (i=1)] [[xi].sub.i] ([x.sup.(k)], (1 - [[lambda].sub.k]) [y.sup.(k).sub.i]) + (1 - [[lambda].sub.k]) x [[lambda].sub.k] ([nabla]h ([x.sup.(k)]) [z.sup.(k)] + [alpha]) + [l.summation over (j=1)] [[eta].sub.j] ([x.sup.(k)], [z.sup.(k).sub.j]) + [[lambda].sub.k] ([x.sup.(k)] - [x.sup.(0)]) = 0, (12)

h ([x.sup.(k)]) - [[lambda].sub.k][THETA]h ([x.sup.(0)]) = 0, (13)

[Y.sup.(k)] (g ([x.sup.(k)]) - [[lambda].sub.k]Y (g ([x.sup.(0)]) + [e.sub.m])) - [[lambda].sub.k][Y.sup.(0)] (g ([x.sup.(0)]) - Y (g ([x.sup.(0)]) + [e.sub.m])) = 0. (14)

Let

[mathematical expression not reproducible]. (15)

If J([x.sup.*]) [not equal to] 0, from (12), one obtains

[mathematical expression not reproducible]. (16)

The sixth to ninth parts in the left-hand side of (16) tend to infinity as k [right arrow] [infinity], but the other five parts are bounded, which is impossible. Therefore, the projection of the smooth curve [mathematical expression not reproducible] onto the z-plane is also bounded. Now, we can assume that [z.sup.(k)] [right arrow] [z.sup.*]. Simultaneously, I([x.sup.*]) [not equal to] 0.

If case (c) holds, then there exists a sequence of points [mathematical expression not reproducible] such that [parallel]([P.sup.(k)], [[lambda].sub.k])[parallel] [right arrow] [infinity]. Because X([lambda]) and (0, 1] are bounded, hence there exists a subsequence of points (denoted also by {([P.sup.(k)], [[lambda].sub.k])}) such that [x.sup.(k)] [right arrow] [x.sup.*], [parallel][y.sup.(k)][parallel] [right arrow] [infinity], [z.sup.(k)] [right arrow] [z.sup.*], and [[lambda].sub.k] [right arrow] [[lambda].sup.*] as k [right arrow] [infinity]. From (14), we obtain

[g.sub.i] ([x.sup.(k)]) - [[lambda].sub.k][[gamma].sub.i] ([g.sub.i] ([x.sup.(0)]) + 1) = [[lambda].sub.k] [([y.sup.(k).sub.i]).sup.-1] [y.sup.(0).sub.i] ([g.sub.i] ([x.sup.(0)]) - [[gamma].sub.i] ([g.sub.i] ([x.sup.(0)]) + 1)), i = 1, ..., m. (17)

When [[lambda].sup.*] > 0, the index set is

[mathematical expression not reproducible]. (18)

When [[lambda].sup.*] = 0, the index set is

[mathematical expression not reproducible]. (19)

(1) If [[lambda].sup.*] = 1, from (12), we obtain

[mathematical expression not reproducible]. (20)

By assumptions ([C.sub.2]), ([C.sub.3]), and (20), we obtain

[mathematical expression not reproducible], (21)

where [y.sup.*.sub.i] [greater than or equal to] 0. Therefore, from (20) and (21), we obtain

[x.sup.*] + [summation over (i[member of]I([x.sup.*],1))] [[xi].sub.i] ([x.sup.*], [y.sup.*.sub.i) + [l.summation over (j=1)] [[eta].sub.j] ([x.sup.(k)], [z.sup.*.sub.j]) = [x.sup.(0)], (22)

which contradicts assumption ([C.sub.4]).

(2) If 0 < [[lambda].sup.*] < 1, from (12), we obtain

[mathematical expression not reproducible]. (23)

When k [right arrow] [infinity], because X([[lambda].sup.*]) and [y.sup.(k).sub.i], i [not member of] I([x.sup.*], [[lambda].sup.*]), are bounded, the right-hand side of (23) is bounded. But, by assumption ([C.sub.2]), if [y.sup.(k).sub.i] [right arrow] [infinity], i [member of] I([x.sup.*], [[lambda].sup.*]), then the left-hand side of (23) tends to be infinite. This results in a contradiction.

(3) If [[lambda].sup.*] = 0, then the proof is similar to that of (12) because the nonempty index set [I.sub.0]([x.sup.*], 0) [subset] I([x.sup.*], 0).

Now, we aim to prove our main result, that is, Theorem 7.

Theorem 7. Let H be defined as in (7) and let assumptions ([C.sub.1])-([C.sub.4]) hold. Then, for almost all [P.sup.(0)] [member of] [X.sup.0](1) x [R.sup.m.sub.++] x {0}, there exists a [C.sup.1] curve (P(s), [lambda](s)) of dimension 1 such that

H (P (s), [P.sup.(0)], [lambda] (s)) = 0, (P (0), [lambda] (0)) = ([P.sup.(0)], 1). (24)

When [lambda](s) [right arrow] 0, P(s) tends to be point [P.sup.*] = ([x.sup.*], [y.sup.*], [z.sup.*]), the x-component of which is a fixed point of [PHI](x) in X.

Proof. By Lemmas 5 and 6, we obtain that there exists a [C.sup.1] curve [mathematical expression not reproducible] starting from ([P.sup.(0)], 1). For any [P.sup.(0)] [member of] [X.sup.0](1) x [R.sup.m.sub.++] x [R.sup.l], it is easy to show that [mathematical expression not reproducible] is nonsingular. By Lemma 2, we conclude that [mathematical expression not reproducible] is diffeomorphic to a unit interval.

Let ([P.sup.*], [[lambda].sup.*]) be a limit point of [mathematical expression not reproducible], and then the following cases may occur:

(a) ([P.sup.*], [[lambda].sup.*]) = ([x.sup.*], [y.sup.*], [z.sup.*], [[lambda].sup.*]) [member of] X x [R.sup.m.sub.+] x [R.sup.l] x {0}.

(b) ([P.sup.*], [[lambda].sup.*]) = ([x.sup.*], [y.sup.*], [z.sup.*], [[lambda].sup.*]) [member of] [X.sup.0](1) x [R.sup.m.sub.++] x [R.sub.l] x {1}.

(c)([P.sup.*], [[lambda].sup.*]) = ([x.sup.*], [y.sup.*], [z.sup.*], [[lambda].sup.*]) [member of] [partial derivative](X([[lambda].sup.*]) x [R.sup.m.sub.+] x [R.sup.l]) x (0, 1].

When [lambda] = 1, the homotopy equation (7) becomes

[l.summation over (j=1)][[eta].sub.j] (x, [z.sub.j]) + x - [x.sup.(0)] = 0, (25)

h (x) - [THETA]h ([x.sup.(0)]) = 0, (26)

Y (g (x) - Y (g ([x.sup.(0)]) + [e.sub.m])) - [Y.sup.(0)] (g ([x.sup.(0)]) - Y (g ([x.sup.(0)]) + [e.sub.m])) = 0. (27)

From (26) and (27), we obtain x [member of] [X.sup.0](1). Then, assumption ([C.sub.4]), together with (25), yields that x = [x.sup.(0)]. By assumption ([C.sub.2]), we obtain [z.sub.j] = 0, j = 1, ..., l. Besides, it follows from (27) that y = [y.sup.(0)]. Then, (25)-(27) have a unique solution P = [P.sup.(0)] = ([x.sup.(0)], [y.sup.(0)], 0) in [X.sup.0](1) x [R.sup.m.sub.++] x [R.sub.l] x {1}; therefore, case (b) is impossible.

In case (c), we prove that [y.sup.*] [not member of] [partial derivative][R.sup.m.sub.+]. If [y.sup.*] [member of] [partial derivative][R.sup.m.sub.+], then there exist [i.sub.0] [member of] {1, ..., m} and a sequence of points [mathematical expression not reproducible] such that [mathematical expression not reproducible]. From (14), we obtain

[mathematical expression not reproducible]. (28)

When k [right arrow] +[infinity], because X([lambda]) 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 [mathematical expression not reproducible], which is strictly less than 0. This results in a contradiction.

Then, we prove that [x.sup.*] [not member of] [partial derivative]X([[lambda].sup.*]). If [x.sup.*] [member of] [partial derivative]X([[lambda].sup.*]), then there exist [i.sub.0] [member of] {1, ..., m} and a sequence of points [mathematical expression not reproducible]. 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.sup.*] is a solution of (7) when [lambda] = 0, and [x.sup.*] is a fixed point of [PHI](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 [mathematical expression not reproducible] is determined by the following initial value problem to the ordinary differential equation:

[mathematical expression not reproducible], (29)

where s is the arc length of the curve [mathematical expression not reproducible].

In implementing the predictor-corrector algorithm, we must proceed along the positive direction of the unit tangent vector V at a point on [mathematical expression not reproducible]. The criterion that determines the positive direction is based on the condition that V maintains the sign of the determinant of [mathematical expression not reproducible]. In the first iteration, the sign is determined by the following lemma.

Lemma 9. If [mathematical expression not reproducible] is smooth, then the positive direction [v.sup.(0)] at the initial guess ([P.sup.(0)], 1) satisfies sign [mathematical expression not reproducible].

Proof. Note that [mathematical expression not reproducible]:

[mathematical expression not reproducible], (30)

where

[mathematical expression not reproducible]. (31)

The tangent vector [v.sup.(0)] at ([P.sup.(0)], 1) satisfies

[mathematical expression not reproducible], (32)

where [v.sup.(0).sub.1] [member of] [R.sup.n+m+l] and [v.sup.(0).sub.2] [member of] [R.sup.1]. From (32), we obtain [v.sup.(0).sub.1] = -[M.sup.-1.sub.1][M.sub.2][v.sup.(0).sub.2].

Therefore, the determinant of [mathematical expression not reproducible] is

[mathematical expression not reproducible]. (33)

Because g([x.sup.(0)]) - [lambda]Y(g([x.sup.(0)]) + [e.sub.m]) < 0, (1 + [M.sup.T.sub.2] [M.sup.-T.sub.1] [M.sup.-1.sub.1] [M.sub.2]) > 0, and [v.sup.(0).sub.2] > 0, the sign of the determinant [mathematical expression not reproducible] is [(-1).sup.m+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 [[epsilon].sub.1] = 1 x e - 3, [[epsilon].sub.2] = 1 x e - 6, and [h.sub.0] = 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 [x.sup.(0)] denotes the initial guess, IT is the number of iterations, H is the value of [mathematical expression not reproducible] when the algorithm stops, and [x.sup.*] is the fixed point.

Example 1. One finds a fixed point of self-mapping [PHI](x) = [([x.sub.1], 2 - [x.sub.2]).sup.T] in

X = {([x.sub.1], [x.sub.2]) [member of] [R.sup.2] : [x.sub.1] - 3 [less than or equal to] 0, [([x.sub.1] - 2).sup.2] + [([x.sub.2] - 1).sup.2] - 9 = 0}. (34)

Let [xi](x, y) = [nabla]g(x)y and [eta](x, z) = (24+2([x.sub.1] - 2), 2[([x.sub.2] - 1)).sup.T]z, and then assumptions ([C.sub.1])-([C.sub.4]) are satisfied. Based on the results of this study, we select initial points [x.sup.(0).sub.1] = (1, 2) and [x.sup.(0).sub.2] = (-3, -2) which are not confined to the interior of the feasible sets. We obtain a fixed point [x.sup.*] = (-1, 1) of [PHI](x) in X when [lambda] [right arrow] 0, following the discrete homotopy pathways [mathematical expression not reproducible] and [mathematical expression not reproducible], as illustrated in Figure 1.

Example 2. One finds a fixed point of self-mapping [PHI](x) = [([x.sub.1], -[x.sub.2]).sup.T] in the set

X = {([x.sub.1], [x.sub.2])[member of] [R.sup.2] : -[x.sub.1] - [x.sup.2.sub.2] + 8 [less than or equal to] 0, 3[x.sub.1] - 2[x.sup.2.sub.2] - 1 = 0}. (35)

Let [xi](x, y) = [nabla]g(x)y and [eta](x, z) = [(6, 0).sup.T]z, and then assumptions ([C.sub.1])-([C.sub.4]) are satisfied. Based on the results of this study, we can select initial points [x.sup.(0).sub.3] = (-2, 1) and [x.sup.(0).sub.4] = (-2, -1) which are not confined to the interior of the feasible sets. We obtain a fixed point [x.sup.*] = (0.333333, 0) of [PHI](x) in X when [lambda] [right arrow] 0, following the discrete homotopy pathways [[mathematical expression not reproducible] and [mathematical expression not reproducible], as illustrated in Figure 2.

Example 3. One finds a fixed point of self-mapping [PHI](x) = [(-[x.sub.1], [x.sub.2]).sup.T] in the set

X = {([x.sub.1], [x.sub.2]) [member of] [R.sup.2] : -[x.sub.1] - 2[pi] [less than or equal to] 0, [x.sub.1] - 2[pi] [less than or equal to] 0, [x.sub.2] - 10 cos(2[x.sub.1]) = 0}. (36)

Let [C.sup.2] functions [xi](x, y) = [nabla]g(x)y and [eta](x, z) = [(0, 10).sup.T]z, and then assumptions ([C.sub.1])-([C.sub.4]) are satisfied. Based on the results of this study, we can select initial points [x.sup.(0).sub.5] = (-3, 3) and [x.sup.(0).sub.2] = (3, 3) which are not confined to the interior of the feasible sets. We obtain a fixed point [x.sup.*] = (0, 10) of [PHI](x) in X when [lambda] [right arrow] 0, following the discrete homotopy pathways [mathematical expression not reproducible] and [mathematical expression not reproducible], as illustrated in Figure 3.

https://doi.org/10.1155/2017/3456834

Conflicts of Interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (nos. 11671188 and U1304103), Innovation Scientists Technicians Troop Construction Projects of Henan Province (no. C20150027), and Innovation Scientists Technicians Troop Construction Projects of Luoyang Normal University (no. 2014-CXTD-001).

References

[1] B. Bollobas, W. Fulton, A. Katok, F. Kirwan, and P. Sarnak, Fixed Point Theory and Applications, Cambridge University Press, London, UK, 2004.

[2] S. Heikkila and K. Reffett, "Fixed point theorems and their applications to theory of Nash equilibria," Nonlinear Analysis. Theory, Methods & Applications. An International Multidisciplinary Journal, vol. 64, no. 7, pp. 1415-1436, 2006.

[3] L.-J. Lin and Z.-T. Yu, "Fixed-point theorems and equilibrium problems," Nonlinear Analysis. Theory, Methods & Applications. An International Multidisciplinary Journal, vol. 43, no. 8, pp. 987-999, 2001.

[4] S. Park, "Fixed points and quasi-equilibrium problems," Mathematical and Computer Modelling, vol. 32, no. 11-13, pp. 1297-1304, 2000.

[5] R. B. Kellogg, T. Y. Li, and J. Yorke, "A constructive proof of the Brouwer fixed-point theorem and computational results," SIAM Journal on Numerical Analysis, vol. 13, no. 4, pp. 473-483, 1976.

[6] S. N. Chow, J. Mallet-Paret, and J. A. Yorke, "Finding zeroes of maps: homotopy methods that are constructive with probability one," Mathematics of Computation, vol. 32, no. 143, pp. 887-899, 1978.

[7] J. C. Alexander and J. A. Yorke, "The homotopy continuation method: numerically implementable topological procedures," Transactions of the American Mathematical Society, vol. 242, pp. 271-284, 1978.

[8] E. L. Allgower and K. Georg, Introduction to Numerical Continuation Methods, SIAM Society for Industried and Applied Mathematics, Philadelphia, Pa, USA, 2003.

[9] C. B. Carcia and W. I. Zangwill, "An approach to homotopy and degree theory," Mathematics of Operations Research, vol. 4, no. 4, pp. 390-405, 1979.

[10] Y. Li and Z. H. Lin, "A constructive proof of the Pincare-Birkhoff theorem," Transactions of the American Mathematical Society, vol. 347, no. 6, pp. 2111-2126, 1995.

[11] B. Yu and Z. Lin, "Homotopy method for a class of nonconvex Brouwer fixed-point problems," Applied Mathematics and Computation, vol. 74, no. 1, pp. 65-77, 1996.

[12] X. Fan and B. Yu, "A smoothing homotopy method for solving variational inequalities," Nonlinear Analysis. Theory, Methods & Applications. An International Multidisciplinary Journal, vol. 70, no. 1, pp. 211-219, 2009.

[13] H. W. Li and Q. H. Liu, "A method to construct a quasi-normal cone for a class of complexity nonconvex sets and its applications in solving noncovex programming," Acta Mathematicae Applicatae Sinica, vol. 32, no. 3, pp. 400-412, 2009.

[14] H.-J. Xiong and B. Yu, "An aggregate deformation homotopy method for min-max-min problems with max-min constraints," Computational Optimization and Applications, vol. 47, no. 3, pp. 501-527, 2010.

[15] Y. Xiao, H. J. Xiong, and B. Yu, "Truncated aggregate homotopy method for nonconvex nonlinear programming," Optimization Methods & Software, vol. 29, no. 1, pp. 160-176, 2014.

[16] Z. Zhu, B. Yu, and L. Yang, "Globally convergent homotopy method for designing piecewise linear deterministic contractual function," Journal of Industrial and Management Optimization, vol. 10, no. 3, pp. 717-741, 2014.

[17] Z. Zhou and B. Yu, "A smoothing homotopy method for variational inequality problems on polyhedral convex sets," Journal of Global Optimization, vol. 58, no. 1, pp. 151-168, 2014.

[18] M. Su and Z. Liu, "Modified homotopy methods to solve fixed points of self-mapping in a broader class of nonconvex sets," Applied Numerical Mathematics, vol. 58, no. 3, pp. 236-248, 2008.

[19] Z. Zhu, B. Yu, and Y. Shang, "A modified homotopy method for solving nonconvex fixed points problems," Fixed Point Theory and Applications, vol. 14, no. 2, pp. 531-544, 2013.

[20] M. Su, B. Yu, and S. Shi, "A boundary perturbation interior point homotopy method for solving fixed point problems," Journal of Mathematical Analysis and Applications, vol. 377, no. 2, pp. 683-694, 2011.

[21] M. Su and X. Qian, "Existence of an interior path leading to the solution point of a class of fixed point problems," Journal of Inequalities and Applications, vol. 2015, no. 30, 2015.

[22] A. Capietto and F. Zanolin, "A continuation theorem for the periodic BVP in flow-invariant ENRs with applications," Journal of Differential Equations, vol. 83, no. 2, pp. 244-276, 1990.

Menglong Su (1,2) and Yufeng Shang (3)

(1) School of Mathematics, Luoyang Normal University, Luoyang 471934, China

(2) Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China

(3) Section of Mathematics, Aviation University of Air Force, Changchun 130022, China

Correspondence should be addressed to Menglong Su; sumenglongjlu@163.com

Received 10 July 2017; Revised 1 October 2017; Accepted 15 October 2017; Published 16 November 2017

Academic Editor: Rosana Rodriguez-Lopez

Caption: Figure 1: The discrete homotopy pathways of Example 1.

Caption: Figure 2: The discrete homotopy pathways of Example 2.

Caption: Figure 3: The discrete homotopy pathways of Example 3.
Table 1: Numerical results of Examples 1-3.

Examples    [x.sup.(0)]   IT   [[lambda].sup.*]      H

Example 1      (1,2)      5        0.000000       0.000000
             (-3, -2)     8        0.000000       0.000000

Example 2     (-2,1)      7        0.000000       0.000000
             (-2, -1)     8        0.000000       0.000000

Example 3     (-3, 3)     11       0.000000       0.000000
              (3, 3)      11       0.000000       0.000000

Examples    [x.sup.(0)]         [x.sup.*]

Example 1      (1,2)      (-1.000000, 1.000002)
             (-3, -2)     (-1.000000, 0.999999)

Example 2     (-2,1)       (0.333333, 0.000000)
             (-2, -1)     (0.333333, -0.000000)

Example 3     (-3, 3)     (-0.000000, 10.000000)
              (3, 3)      (-0.000000, 10.000000)

Examples    [x.sup.(0)]     [[PHI]([x.sup.*])

Example 1      (1,2)      (-1.000000, 1.000002)
             (-3, -2)     (-1.000000, 0.999999)

Example 2     (-2,1)       (0.333333, 0.000000)
             (-2, -1)     (0.333333, -0.000000)

Example 3     (-3, 3)     (-0.000000, 10.000000)
              (3, 3)      (0.000000, 10.000000)
COPYRIGHT 2017 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2017 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Su, Menglong; Shang, Yufeng
Publication:Mathematical Problems in Engineering
Article Type:Report
Date:Jan 1, 2017
Words:5814
Previous Article:Multisensors Cooperative Detection Task Scheduling Algorithm Based on Hybrid Task Decomposition and MBPSO.
Next Article:Seismic Response of Long-Span Triple-Tower Suspension Bridge under Random Ground Motion.
Topics:

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |