A Nonsmooth L-M Method For The Solution Of The Generalized Nonlinear Complementarity Problem

The generalized nonlinear complementarity problem, denoted by GNCP, is to find a vector x* Rn such thatwhere F and G are continuous functions from Rn to Rm, K is a nonempty closed convex cone in Rm, and K?denotes the polar cone of K.In this thesis, we consider the case that m = n, F and G are both continuously differentiate on Rn, K, is a polyhedral cone in Rn, that is, there exist A Rsxn, B e Rtxn such thatIt is easy to verify that its polar cone K has the following representation: To construct a superlinear convergent algorithm for the solution of GNCP, we now formulate GNCP as a system of equations via the Fischer function :R2 Rl defined byDefine vector-valued function : Rn+s+t Rn+s+t and real-valued function / : Rn+s+t R as follows:wherethen the following result is straightforward.Theorem 1.1.1 x* is a solution of GNCP if and only if there exist \1 RS, X e Rt, such thatThe thesis is organized as follows.In chapter 1, we introduce background and development of the GNCP, some basic definitions and their property, and some property of functions and f.Chapter 2 contains the following contents.(1) Existence and Uniqueness of solutionsTheorem 2.1.2 Assume there exists some fj, > 0 such thatand the mapping F-1 is continuous in addition. Then GNCP(F, G, K) has a unique solution.(2) Stationary Point ConditionsTheorem 2.2.1 Suppose that z*=(x*, A*,A2) is a stationary point ofF'(x*) is nonsingular, and G'(x*)[F'(x*)}"1 is positive definite in the null space of B, then x* is a solution of GNCP(F, G, K).Theorem 2.2.2 Let )C = R+. If (a;*, A*) is a stationary ofZiF'(x*) is nonsingular, and G'(x*)[F'(x*)]~l is a P-matrix, then x* is a solution of the GNCP(F,G,K).(3) Nonsingularity conditionTheorem 2.3.1 If z* = (x*, A*, A^) is a stationary point ofF'(x*) and G'(x*) are non-singular, B is a row-full-rank matrix, and AF'(x*} [G'(x*)]-1 AT is a P-matrix, then for any V € d^(z*), V is nonsingular. Theorem 2.3.2 For the following optimizationIf (a;*, A*) # Rn+s, G'(x*} is nonsingular, and the matrix AF'(x*)[G'(x*)]~1AT is a P-matrix, then for any V # (x*, A*), V is non-singular. (4) Algorithm and Convergence Algorithm Step 1: Choose any point z?€ Ptn+s+t, parameters cr,/3 €Step 2: If , stop; otherwise, go to Step 3. Step 3: Choose an element be the solution of the linear systemwherStep 4: Let mk be the smallest non-negative integer m such thatLet zk+l := zk + amkdk, k := k + 1, go to Step 2.Theorem 2.4.1 Any accumulation point of the sequence {zk} generated by Algorithm is a stationary point ofmin f(z).Theorem 2.4.2 Let {zk} be the sequence generated by Algorithm. Assume that z* is an accumulation point of {zk}, and a BD- regular solution of V(z)=0, then1) the entire sequence {zk} superlinearly converges to z* and2) {zk} converges to z* Q-quadratically if F' and G'(x*} are both Lips-chitzian.(5) Computational ExperimentsBefore doing our computational experiments, we should find a way to calculate an element of (AF(x), 1).Lemma 2.5.1 For x ∈ Rn and 1 € Rs, choose v G Rs such that vi = 0 for index i with [A1]i = 0 and [AF(x)]i = 0.LetwhereifandifThenor more precisely,(6) Discussions about the Boundedness of the Level Setwe consider a special case such that B = 0, A is a symmetric and nonsin-gular matrix. Then f(x) can be written asFor this function, we have the following result %}Assume that mappings F, G : Rn → .R?are Lipschitz continuous and there exist some // > 0 such thatThen the level set L(x0) = {x ∈ Rn \ f(x] < f(x0)} is bounded for all x0 ∈ Rn. For one word, in this thesis, the generalized nonlinear complementarity problem (GNCP) denned on a polyhedral cone is reformulated as a system of nonsmooth equations. Based on this reformulation, the famous Levenberg-Marquardt (L-M) algorithm is employed for its solution. Theoretical results that relate the stationary points of the merit functio...