《解约束优化问题的投影梯度型中心方法(英文)》由会员分享，可在线阅读，更多相关《解约束优化问题的投影梯度型中心方法(英文)（7页珍藏版）》请在金锄头文库上搜索。
1、Journal ofM athematical Research global convergence.Classif ication AM S(1991) 40C30, 49 M 37?CCL O 221. 2, O 2241. IntroductionM ethod of centers is a class of i mportant algorithm s for nonlinear programm ing, w hichhas the advantages of feasible directionsmethod and penalty function method, and c
2、an over2come some of their shortcom ings such as the requirement of feasibility of initial point for theformer and the uncertainty of penalty factor for the later1, 2. How ever, the existingmeth2ods of centersonly consider inequality constraints and use the subproblem sof linear?quadrat2ic programm
3、ing to generate the search directions .In this paper, w e consider the follow ing problem:(N P) m inf(x), s. t.xR= xRng j(x)0,jL;aT ix-bi= 0,iM,w heref,gjC1(jL).LandMare finite index sets .Since the linear constraints can betreated directly, and some of the constraints may be required to be satisfie
4、d in practice, w edivideLinto two subsets:L=L1L2such thatL1L2=, and use onlygj(jL2)to con2struct the merit(distance)function of(N P)w ith the parameteryRn:f(x,y) = maxf(x) -f(y) -r(y),gj(x) -(y),jL2,(1. 1)573Received Nov. 25, 1994. 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserv
5、ed.w herer 0,(y)= max0,gj(x),jL2.Then for the current iteration pointxkR1= xRng j(x)0,jL1;aT ix-bi= 0,iM,(1. 2)by using the projected gradient direction to generate the descent feasible direction of theparametric programm ing(Pxk): m inf(x,xk)xR1 atx=xk, a projected gradient typemethod of centers fo
6、r(N P)is obtained. U nder the assumption of nondegeneracy, the globalconvergence of the method is proved.The method is si mple in computation and flexible inform.2. Def in itions and NotationsDef in ition 2. 1 Given yRn,J 0suchthat xS,(0,S, detNJ(x,)(x)TN J(x,)(x) S,(2. 3)w hereNJ(x) = ?gj(x),jJ;ai,
7、iM, forJL;J(x,) =I1(x,)I2(x,),I1(x,) = jL1gj(x)-,I2(x,) = jL2gj(x) -(x)-.673 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.Proof The proof is si m ilar to that of 4, Th. 1 and is om itted.L etxR1,J1I1(x),J2I2(x),J=J1J2such that detNJ(x)TN J(x) 0. DenoteBJ(x)=NJ(x) NJ(x)TN J(
8、x) - 1,PJ(x) =E-NJ(x)BJ(x)T,uJ(x) = -BJ(x)T?f(x), de2fine the follow ing directionsdJ(x) = -PJ(x)?f(x) +BJ(x) vJ(x) -(x)J,(2. 4)w here forjJ=J1J2,vj J(x) =uj J(x),ifuj J(x) 0.(2. 5)and foriM,vi J(x)= 0;j J=1, ifjJ,0, ifjM;(x)0.(2. 6)Lemma 2. 3 (1)L et(J,x)=PJ(x)?f(x)2+uT J(x)vJ(x)+r(x),then(J,x)0,an
9、d(J,x)= 0imp lies that x is a K uhn2T ucker(K2T)point of(N P);(2)If(J,x) 0and(x) 0such that-(J,x)+(x)uT J(x)J 0(x) -gj(x)uj J(x)0(2. 8)hence(J,x)0.If(J,x)= 0, thenPJ(x)?f(x) = 0,uT J(x)vJ(x) = 0 and(x) = 0, w eobtain?f(x) +NJ(x)uJ(x) = 0,uT J(x)vJ(x) = jJ1J2,ujJ(x) 0, then the conditions in L emma 3
10、 (2)hold.3. Algorithm and Its ConvergenceAlgorithmStep 0 Givenx0R 1;1,2,(0, 1),0 0; k:k0, li mkk= 0.Setk: = 0.Step 1 SetJi,k=Ii(xk,k),i= 1, 2;Jk=J1,kJ2,k.Step 2 If detNJk(xk)TN Jk(xk) k, then go to Step 3; else, setk=1kgo back to Step 1.Step 3 Compute(Jk,xk).If(Jk,xk)= 0, stops; else, go to Step 4.S
11、tep 4 Computedk=dJk(xk)by the formula(2. 4).Step 5 Compute stepsizetk 0 by one of the follow ing rules:Rule 1xk+tkdkR 1,f(xk+tkdk,xk)f(xk,xk)= 0, andf(xk+tkdk,xk)m in t0f(xk+tdk,xk)xk+tdkR1 +k;Rule 2xk+tkdkR 1,f(xk+tkdk,xk)f(xk,xk)= 0,tk-t3k k, w heret3kis an opti malsolution of the problem m in0t f
12、(xk+tdk,xk)xk+tdkR 1, 0;Rule 3tk= maxt# f(xk+tdk,xk)f(xk,xk) +2tf3 J2,k(xk,xk;dk),xk+tdkR 1,w here#= 0,1,2,.Step 6 Setxk+ 1: =xk+tkdk,k+ 1: =kor0,k: =k+ 1, go back to Step 1.Lemma 3. 1A f ter entering S tep1f rom S tep2f inite tim es,the algorithm m ust go to S tep3.Lemma 3. 2Ifthe algorithm generat
13、es inf inite sequencexkw hich has a cluster point x3,thenli mk+f(xk+ 1,xk)= li mk+f(xk+ 1,xk)-f(xk,xk) = 0.Theorem 3. 1T he algorithm either stops at a K2T point xkof(N P)af ter f inite iterations orgenerates an inf inite sequencexkof w hich each cluster point is a K2T point of(N P).Proof By L emma
14、2. 3, w e need only to prove the second conclusion.L etx3be a cluster of xk such that xk-K x3, then by L emma 2. 2, there exists0 such thatk 0,kK. SinceJ1,k,J2,kare the subsets of the finite index setsL1,L2re2spectively, w e can assume thatJi,k=Ji,kK(i= 1, 2), thusJk=J=J1J2,kK, andJiIi(x3),i= 1, 2;J
15、J(x3).873 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.Sincef,gjC1(jL), w e havePJ(xk)?f(xk) -K PJ(x3)?f(x3),BJ(xk) -K BJ(x3),uJ(xk) -K uJ(x3).(3. 1)Furthermore, vJ(xk) is bounded, hence there exists an infinite subsetK1ofKsuch thatvJ(xk) -K1 vJ.Therefore,(J,xk) -K1 (J,x3) =PJ(x3)?f(x3)2+uJ(x3)Tv J(x3) +r(x3)0,(xk)-K1 (x3)=(J,x3)?(uJ(x3)Tv J+ 1)anddk=dJ(xk) -K1 d3=dJ(x3) =-PJ(x3)?f(x3)+BJ(x3) vJ-(x3)J.Now , w e prove that(J,x3)= 0.If(J,x3) 0, then(x3) 0 and -(J,x3) +(x3)uJ(x3)T J 0,t(0,),ktsu
