| In this paper, we are mainly devoting to studying the primal-dual interiorpoint method and combined homotopy interior point method for somenonlinear problems. In charper 2, we propose a new merit function, calledexponent barrier penalty function, then accelerate the rate of convergence ofthe algorithm.First, we consider a nonlinear programming problem:where f(x) : (?)n→(?), g : (?)n→(?)m are twice continuously differentiable,and Ip is a subset of the index set {1,2,…, n}. Let p=|Ip| > 0, E be ap×n matrix whose rows consist of eit, i∈Ip, where ei∈(?)n denotes the ithcolumn vextor of identity matrix.Then problem (1) is written asNoteThe Lagrange function associated with problem (1) is whereω= (x, y, z)t y∈(?)m, and z∈(?)p are Lagrange multiplier vectorswhich correspond to the equality and inequality constraints, respectively. Forμ> 0, the perturbed Karush-Kuhn-Tucker(KKT) conditions associated with(1) are given byand (x',z')≥0, whereandμ> 0 is a barrier parameter, forμ= 0, these conditions are merely theKKT conditions.We take a new merit function as objective one, and get the descentdirections by the primal-dual conditions, then, we will give the relationshipbetween minimizers of functions F and Fe.The merit function Fe((?),μ):S→(?):Theorem 1 Suppose x' > 0, z > 0.I The following statements are equivalent: II A pointω= (x, y, z) is an unconstrained local minimizer of the functionF(ω,μ) if and only if x is an unconstrained local minimizer of the functionFe(ω,μ) andωsatisfiesφ(ω) = 0.To prove global convergence of algorithm, we need the following assumptions:(A1) The function f and gi,i = 1,…,m, are twice continuously differentiable.(A2) The sequence {ωk} generated by Algorithm LS remains in a compactsetΩof S×(?)m×(?)+p.(A3) The matrix Gk is uniformly bounded and the matrix Gk+Et(Xk)-1ZkE+1/μA(xk)tA(xk) is uniformly positive definite.Theorem 2 Suppose that Assumption (A1-A3) holds. Let an infinite sequence{ωk} be generated by Algorithm LS. Then there exists at least oneaccumulation point of {ωk}, and any accumulaton point of the sequence {ωk}is a SBKKT point.In next part, we consider the following nonlinear programming problem:where x∈(?)n, f : (?)n→(?), g : (?)n→(?)q.We use following assumptions:(B1) The second-order derivatives of f and g are continuous.(B2) The columns of the matrix [▽g(x), ei:i∈Ix0] are linear independent,where Ix0= {i : (?) xki= 0, i = 1,2,…, n}, ei denotes the ith columnof the n×n identity matrix. Also, the sequence {xk} is bounded. (B3) Strict complementarity of the solutionω* = (x*,y*,z*) is satisfied.(B4) The second-order sufficiency condition for optimality is satisfied at thesolution point; i.e., for all vectors 0≠v∈(?)n, such that▽gi(x*)Tv =0, i = 1,2,…,q,eiTv=0, for i∈Ix0, vT▽xx2L(x, y, z)v > 0.After adding the penalty and logarithmic barrier functions, we obtainan approximate formulation of the problem (5):The Lagrange associated with the optimization problem (5)is given byand the perturbed optimality conditions arewhereNewton's method applied to the system (7) leads to the following linearsystem at the k iteration for the Newton directions, To control the convergence, we need to introduce following merit function:Theorem 3 For anyε< 0, there existsα> 0, such that for any primaldualapproximation (x, y, z) such that y,z∈(?)++q, the primal-dual direction△p = (△x,△y), obtained as the solution of the system (8) with the primalregularization rule and the dual regularization parameterε< 0, is a descentdirection forφandTheorem 4 Let the assumption of the previous lemma hold and letεg bea sufficiently small positive scalar. Then, the algorithm converges to a limitpoint satisfying F(x, y, z; c,μ)=0 forμfixed.Now we will show the combined homotopy interior point method tosolve the nonlinear programming problems.Let us consider the following general nonlinear programming problem(GNLP):where x∈(?)n, f, gi,hi are sufficiently smooth, g(x) = (g1(x), g2(x),…, gm(x))t,h(x)=(h1(x),h2(x),…,hl(x))t.LetΩ1={x∈(?)n : g(x) = 0, h(x) < 0} be the strictly feasible set of(10).where (?),Ω0 are the closed set and open set ofΩrespectively. The normal cone condition of ft [47] For (?)x∈(?)Ω, the normalcone ofΩat x only meetsΩat x, i.e.The quasi normal cone ofΩ[49] The setΩis said to satisfy qusinormal cone condition w.r.t.η(x), if there exist a set of continuously differentiablemappingη1(x),η2(x),…,ηm(x), which are positive irrelative withregard to▽g(x), such that for any x∈(?)Ω,weaker normal cone ofΩ[25] There exists an open subsetΩ0 (?) (?)such that the normal cone ofΩat any x∈(?)Ωdoes not meet (?), i.e. (?)x∈(?)Ω,Under the weaker normal cone condition, the initial points shouldchoosen from a subset of the feasible set, and the structure of the homotopyneed some auxiliary mappings, so this may be difficult. And in thispart, We propose a new condition called "the shifted cone" condition, whichis more easier to satisfy comparied with the normal cone conditon or quasinormal cone condition. We can proof the existence and convergence of thehomotopy path under the weaker condition, and the scope of initial pointschosen is more widely.We construct a homotopy as follows:whereω= (x,y,z)∈(?)n+m+l,We need following assumptions: (C1)Ω1 is nonempty and bounded.(C2) (?)x∈(?)1, matrix(▽g(x),▽hi(x) : i∈I(x)) is a matrix of full columnrank (the regularity of the constraints).(C3) (The shifted cone condition) Let T(x,x0) : (?)n→(?)n be two timescontinuously, satisfies:(i) For any x0, T = 0 if and only if x = x0;(ii) (?)y∈(?)m,x∈(?)Ω1, if T(x, x0)≠0, then(iii) For any x0, matrix (?)x0/(?)T is full column rank.Lemma 1 Let H be (11), f, gi (i = 1,…, m) and hi(i=1,…,l)are three times continuously differentiable functions and let the conditions(C1)-(C3) hold. Then for almost allω0∈Ω, 0 is a regular value of Hω0:Ω×(0,1]→(?)n+m+l,and Hω0-1 consists of a smooth curve,Γω0, which issubjected to H(ω,ω0,μ) = 0, (ω(0),μ(0)) = (ω0 ,1).Theorem 5 Let H be (11), f, gi (i = 1,…,m) and hi (i = 1,…,l)arethree times continuously differentiable, suppose that conditions(C1)-(C3)hold. Then for ahnost allω0∈Ω, there exists a smooth curveΓω0, whichstarts from (ω0,1). Asμ→0,ω→ω*(x*,y*,z*), specifically, the componentx* ofω* inΓω0 is a KKT point of (10). |
PDF Full Text Request