Homotopy Methods For Some Nonlinear Problems

In this paper, we are mainly devoting to studying the homotopy method for some nonlinear problems, i.e. solving the multiobjective programming problems in unbounded regions, modified aggregate constraint homotopy method for the nonlinear programming problems, solving the fixed point and nonlinear programming problems in a broader class of non-convex sets.Consider the following convex multiobjective programming problems (CMOP):where f(x) = (f(x),..., f_p(x))^T, g = (g₁(x),..., g_m(x))^T. In addition, we denoteΩ= {x∈Rⁿ : g_i(x) (?) 0, % = 1,... ,m},Ω⁰ = {x∈Rⁿ : g_i(x)) < 0, i = 1,..., m}, (?)Ω=Ω\Ω⁰, B{x) = {i∈(1,..., m) : g_i(x) = 0}.In [48]. Lin et al. introduced the concept of a minimal efficient solution (which can been seen in [5, 11] for the linear multiobjective programming problems) for CMOP and then presented a combined homotopy interior point method to find it. But they obtained the global convergence of the homotopy method under the assumption that the feasible set is bounded. In this paper, we attempt to complete this work in the unbounded set. To this end, we give the following two unbounded assumptions: Assumption A (A₁)Ω⁰ is nonempty;(A₂) For any x∈(?)Ω, the matrix {â–½g_i(x) : i∈B(x)} is of full column rank; (A₃) There exist someρ_i > 0, i = 1,..., p such that for any x∈Ωand d∈Rⁿ, we haveAssumption B(B₁)Ω⁰ is nonempty;(B₂) For any x∈(?)Ω, the matrix {â–½g_i(x) : i∈B(x)} is of full column rank;(B₃) There exists someξ∈Ωsuch thatare bounded;We obtaine the global convergence of the homotopy method under assumptions A and B, respectively. Several numerical examples are given to show that these two unbounded assumptions are effective.At last, we show the relations of assumptions A, B and the boundedness of the feasible set as follows:Lemma 1 IfΩsatisfies Assumption A, then it necessarily satisfies Assumption B.(a) By lemma 1 and example 2.3.3 of chapter two, it is easy to see that Assumption B is weaker than A.(b) Although Assumption B is weaker than A, but in some cases, it is difficult to testify Assumption B. At the same time, Assumption A is easy to testify, as can be seen in example 2.3.4 of chapter two.(c) It should be pointed out that Assumption B is the direct extension from the boundedness of O since Hence the results in this paper include the one in [48]. In addition, under Assumption B, we obtain the global convergence results without the convexity of f_i(x), i = 1,... ,p, hence the homotopy method is applied to some non-convex cases. Consider the following non-convex nonlinear programming problems:where the symbolsΩ,Ω⁰, (?)Ω=Ω\Ω⁰, B(x) are the same as the ones in the multiobjective programming problems. Besides, we denote R₊¹ = {y∈R¹ : y≥0}, R₊₊¹ = {y∈R¹ : y > 0}.Recently, using the idea of the aggregate function method, some important results were obtained on the nonlinear programming problems ([36, 37, 72], etc.). Especially in [82], by combining the idea of the aggregate function method with the combined homotopy interior point method, Yu et al. proposed the aggregate constraint homotopy method (denoted as ACH method). In that paper, they said that the main advantages of the ACH method are to reduce the scale of nonlinear programming problems largely. In this paper, we first introduce the concept of "positive irrelative" [45], then develop a modified ACH method under new assumptions. Using the modified ACH method, we solve a broader class of non-convex programming problems. In addition, the modified ACH method enlarges the scope of the initial points. It should be pointed out that the modified ACH method also possesses the main advantages of the ACH method.In the following, we give the assumptions and main result of chapter three. (C₁)Ω⁰ is nonempty andΩis bounded;(C₂) For any x∈(?)Ωandμ∈[0,1], {(1 -μ)â–½g_i(x) +μξ_i(x) : j∈B(x)} is positive irrelative, i.e. ifthen y_j = 0, (?)_j∈B{x);(C3) There exists a closed subsetΩ|^ (?)Ω⁰ with nonempty interior 0°, such that for any x∈(?)Ω, we haveTheorem 1 Let assumptions (C₁)—(C₃) be fulfilled, f, g_j, j = 1,...,m be three times continuously differentiable functions. In addition, letξ_j, j = 1,.. ., m be twice times continuously differentiable functions. Then there existsαθ∈(0,1], such that the conclusions of lemmas 3.2.2-3.2.7 hold for any [μ∈(0,1]. Consider the following homotopy equationwhereω= (x,y)∈Rⁿ×R₊¹,ω⁽⁰⁾ = (x⁽⁰⁾,y⁽⁰⁾∈(Ω|^)⁰×R₊₊¹. Then for almost everyω⁽⁰⁾ = (x⁽⁰⁾,y⁽⁰⁾)∈(Ω|^)⁰×R₊₊¹, there exists a C¹ curve (ω(s),μ(s)) of dimension 1 such thatAnd whenμ(s)→0,ω(s) tends to a pointω^* = (x^*,y^*). In particular, letλ^*_j = y^*β_j(x^*, 0), j = 1,..., m, then (x^*,λ₁^*,...,λ_m^*) is a solution of K-K-T equation of (2), i.e. x^* is a K-K-T point of (2).In 1978, Chow et al. [9] constructed the homotopyfor the bounded closed convex set. This homotopy is used by many authors to compute fixed points and solutions of nonlinear systems.There are many non-convex problems in practice, and certainly it is also very interesting and useful to solve numerically the fixed points of self-mapping F(x) in general nonconvex subsets in Rⁿ. However, to our knowledge, there has been hardly any implementable algorithm in this area. Until 1996, a combined homotopy interior point method [83] was proposed to numerically solve the fixed points of self-mapping F(x) in a class of nonconvex subsetsΩin Rⁿ, i.e.Ω= {x∈Rⁿ : g_i(x) < 0, i = 1,..., m} satisfying the normal cone condition.In this paper, we want to solve fixed points of F(x) in a broader class of nonconvex sets. Firstly, we extend the results in [83] to the general nonconvex set with both equality and inequality constraints; secondly, we use the concept of "positive independent" in [51] and thus introduce the C2 functionsα_i(x)∈Rⁿ, i = 1,...,m andβ_j(x)∈Rⁿ, j = 1,..., l. By using them, we can further make the combined homotopy interior point method solve fixed points of F(x) in more general nonconvex sets; lastly, several simple examples are given to show the extensions are effective. In addition, we give some ways in choosing the C² functionsα_i(x)∈Rⁿ, i = l,...,m andβ_j(x)∈Rⁿ j = 1,...,l appropriately. It should be pointed out that we deal with fixed point problems in the nonconvex sets consisting of both equality and inequality constraints, while the authors study nonlinear programming problems only with inequality constraints in [51], which results in the big differences between the homotopy and proof in this paper with the ones in [51]. Hence we think the extensions are not trivial.In the remaining part, we will use the following symbols:In addition, R₊^m and R₊₊^m represent the nonnegative and positive orthant of R^m, respectively.Now, we assume that there exist C2 functionsα_i(x)∈Rⁿ, i = 1,... ,m andβ_j(x)∈Rⁿ, j = 1,... ,l, such that the following assumptions hold: {D₁)Ω⁰ is nonempty andΩis bounded; (D₂) For any x∈Ω, a_i(x)∈Rⁿ, i =1,...,m andβ_j(x)∈Rⁿ, j = 1,..., l are positive independent with respect to , i.e. ifthen y_i = 0, u_i = 0, (?)_i∈B(x) and z_j = 0, j = 1,..., l.(D₃) Setβ(x) = (β₁(x),...,β_l(x))∈R^n×l, for any x∈Ω, we have(D₄) For any x∈Ω,â–½h(x) is of full column rank andâ–½h(x)^Tβ(x) is nonsin-gular.Under assumptions (D₁) - (D₄), we give the equivalent condition for the existence of fixed points as follows:Lemma 2 Let g_i(x), i = 1,..., m and h_j(x) = 0, j = 1,..., l be C³ functions and assumptions (D₁)—(D₄) hold. In addition, letα_i(x)∈Rⁿ, i = 1,..., m,β_j(x)∈Rⁿ, j = 1,..., l be C² functions. Then for any C² mapping F(x) : Rⁿ→Rⁿ satisfying F(Ω) (?)Ω, x^*∈Ω, is a fixed point of F(x) inΩif and only if there exist y^*∈R^m and z^*∈R^l, such that (x^*,y^*, z^*) is a solution of the equationwhereα(x) = (α₁(x),..., a_m(x))∈R^n×m and y² = (y₁², ...,y_m²)^T∈R^m.To solve for the fixed points of F(x) in more general nonconvex sets, we construct the following homotopy equation: whereω= (x, y, z)∈Rⁿ×R₊^m×R^l andω₀⁽⁰⁾ = (x⁽⁰⁾, y⁽⁰⁾)∈Ω⁰×R₊₊^m.Now, we give the main result of chapter four.Theorem 2 Let H be defined as (7), g_i(x), i =1,..., m and h_j(z), j = 1,..., l be C³ functions. In addition, let assumptions (D₁)—(D₄) hold,α_i(x), i = 1,..., m andβ_j(x), j = 1,..., l be C² functions. Then for any C² mapping F(x): Rⁿ→Rⁿ satisfying F(Ω) (?)Ω,(1) (existence of the fixed point) F(x) has a fixed point inΩ;(2) (homotopy method for computing the fixed point) for almost allω⁽⁰⁾ = (ω₀⁽⁰⁾,0)∈Ω⁰×R₊₊^m×R^l, there exists a C¹ curve (ω(s),μ(s)) of dimension 1 such thatAnd whenμ(s)→0,ω(s) tends to a pointω^* = (x^*,y^*,z^*). In addition, the component x^* of w^* is a fixed point of F(x) inΩ.In [51], for the nonlinear programming problems only with inequality constraints, Liu et al. proposed the quasi-normal cone condition, which is weaker than the normal cone condition. Using the new condition, they make the combined homotopy interior point method solve the nonlinear programming problems in more general non-convex sets. In this paper, we try to extend their results to the sets with both equality and inequality constraints. Through our study, we find that it is not easy to do this task for the existence of the equality constraints, which make the assumptions, homotopy equation and proof in this paper much different from the ones in [51]. Hence we think this work is not trival. The numerical examples show the extension is effective.Now we assume that there exist continuous mappingsα_i(x)∈Rⁿ, i = 1,..., m andβ(x)∈R^nxl, such that the following assumptions hold: (E₁)Ω⁰ is nonempty andΩis bounded; (E₂) For any x∈Ωandμ∈[0,1],α_i(x)∈Rⁿ, i = 1, ...,m,â–½h_j(x) +μ(β_j(x) -â–½h_j(x))∈Rⁿ, j = 1,..., l are positive independent with respect to then y_i = 0, u_i = 0, (?)_i∈B(x), and z_j = 0, j = 1,... ,l;(E₃) Setβ(x) = (β₁(x),…,β₁(x))∈R^n×l, for any x∈Ω, we have(E₄) For any x∈Ω,â–½h(x) is of full column rank andâ–½h(x)^Tβ(x) is nonsin-gular.Now we give the homotopy equation below:where .Theorem 3 Let H be defined as (8), f, g_i, i = 1,..., m and h_j, j = 1,..., l be three times continuously differentiale functions. In addition, let assumptions (E₁)—(E₄) hold,α_i, i = 1,..., m andβ_j, j =1,... ,l be twice times continuously differentiable functions. Then for almost allω⁽⁰⁾∈Ω⁰×R₊₊^m×R^l, there exists a C¹ curve (w(s),μ(s)) of dimension 1 such thatAnd whenμ(s)→0,ω(s) tends to a pointω^* = (x^*, y^*, z*). In particular, the component x^* ofω^* is a K-K-T point of the nonlinear programming problems.