【doc】非线性规划的一类新增广拉格朗日
函数
excel方差函数excelsd函数已知函数 2 f x m x mx m 2 1 4 2拉格朗日函数pdf函数公式下载
非线性规划的一类新增广拉格朗日函数
童庆建筑
工程
路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理
学院
第13卷第3职JOURNALOFCHONGQINGINSTITUTEOFVo!.13No.3
1991~9月ARCHITECTUREANDENGINEERINGSept.1991 非线性规划的一类新增广拉格朗日函数
唐健
(基.础科学系)
捕要本文对二次连续可微约束优化问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
提出了一类增广拉格朗日|函数,证 明了谊函数的稳定点,极值点与愿约束优化问题稳定点及极值点之问的等价性. 关奠词非线性规,拉格朗日函数,不等式约柬
近年来,人们越来越重视研究用无约束技巧来求解非线性规划问题的各种方法.其中有
价值的精确罚函数法避免了乘子法所要求的一系列无约束极小化过程. 下面将证明在适当条件下,可定义一个可微函数Td(x,,c),求它的无约束极小解将产
生约束问题的解及相应乘子.这样,就可以利用各种有效的无约束优化方法得到,c) 的解,从而得到约束问题的解.
1增广拉格朗El函数的形成
考虑不等式约束的优化问题
(.)
…
minf(x
,
)
)?.
其中?R,,:R—,月,R—,,,?c.
记工(,)=,()十日()
L(,)=,()十g()+—cl【g()ll
对于等式约束优化问题,另一种较简便的增广拉氏函数被引进(作者在另一定中提出),形
式为
(,^,c)=工(,)+i1(c+TIIII?lig()II.+
百
d(
,柚 ,)珊(),k似
车土1990年'月20日收科.
108重庆建筑工程学院i991硅
这里T,d>o,T.U()是?×?对称正定阵,具有hr()^()的形式,hr()是?×打1的高矩阵,
h()的选取可使得^()g()非奇异.()的构造有好几种方法,该文有详述. 以下不妨假定h(x)Vg(x)非奇异,g(x)g()可逆,至少在极值点附近如此. 首先运用松弛变量}(i=1,2,…,打1)将问题(0)变为等式约束问题' rmin,()
(0){,
.
t.g()+YY=0
这里=(,),Y=diag(y+),Y=(I,Y2,…,一)
记G(=,)=,()+^(g()+Yy)
G(=,^)=,()+(g()+Yy)+Iig)+Yy. 则G(=,九)=工(,九)+YY
G(,九)=G(,九)+Ug()+YY_l
实际上这是问题(0)相应的拉氏及增广拉氏函数,其导数分别为: ,?
Gc,,=
【薹量''+x)r(g2YJ.2cYYy)Yy'y).c.,G(,九)=l+(g()+J(2),g()+,对等式约束问题(0,)建立新增广拉氏函数
(=,^,.):Gc(,^)+IIg()+YYI[+dG(= ,
^)();G(,)(3)
这里)=()?尺?.,(3)也可写为''
Sd(,九c)=,()+九(g()+Yy)+(c+可lAJl.)1ig()+yll. +L(,九)()工(,九)+2dJ.Y九(3)
在Sd(,^,c)中,由于变量Y有特殊结构,对(=,^,c)的无约束极小可首先对松弛变 Sd(,,c)=2y^+2(c+百I1叫1.)葺,(g()+Yy)十4dYl\X=o 这里A=diag(.)
从而得到对绐定,^,C,d使S0,^,0)极小的Y值
f(,^,c,d)~-max0,-g+()一一)
第3期唐建;非线性规划的一类新增广拉格朗日函数1O9 夸
其中
g(,,c,d)=(g,gi,…,g:)
g(,,c,d)=(,^,c,d)
而d(,,.)=minS,t(,,.)
(4)
=
G((小,c,d)')+丢(c+TilXll=~tIa()+l,(,(x,,d)il +dvG(,(,,c,d),)()G(,(,,c,d):)(5) :
工(,)+专+TI1~11)jig(圳P+萼(m)w())
+
毒{[^i(1+2df)+(c+TIfM)i1(c+Tll^f『:)')'ll4J =(,c)一专(c+'qlXli)llg,^,c',d)II
这里(,,c)=三(,)+1(c+TIlXlll")+罢三(,)似),(,?(6) 从而引进新的增广拉格朗日函数
d(,^,c)=udf,^,c)一昙(c+Tllll)Iia*(,^,c,d).jz
其中U,dx,^,c,d),g似,,c,d)分别由(6),(4)定义.
2基本性质
下面给出(,^,)稳定点与满足问题(0)的—必要性条件的点偶(,)之间的关 系.'''
(x,)满足问题(0)的—必要性条件系指下列条件成立: ()?0,(f=1,2,…,m)(7)
fg,()=0,({=1,2,…,m)(8)
.?0,(1=1,2,…,m)(9)
工(,)=0(10)
{生质1对变量,而言,Ta(x,^,c)?c.,且有导数
d(,,c)=三(,九)+(c+TIlll)Vg(x)(g()十l,(,,c,d)) +dr:L(x,,c)()三(,,c)
'
+
普壹(盟))州加)(11)
Vard(x,,c)=g()+Y(,,c,d)+~llg(x)+Yy(,,c,d)ll九
+dVg(x)()工(,)+4dY(,,c,d)(12)
1iO重庆建筑工程学院1991拄
证利用似'之展式()善,(),其中口j是中单位向量,由向量函数求导 法则可得结果.
定理I设()是(0)的K—点,则vc,d>o,有1)(,)是Td忸,^,c)的稳定点, 2)Td<,,c)=,(.
证由假设条件及(4)得
.
日j()+<.^,c,d)=0,Vi
g面+<i,c,d)y(x,X,c,d)=0 如日I<<0,卿=0,如<=o,由(137,Y(.c,d)=0. 故(,c,d)0
由(10),(137?,(14)推出.
,
,
vTd(-x
,X,c):0,Td(,,c)=,<西.
(13)
(14)
定理2设,^)是(,^,c)的稳定点,)+yf0.^,c.=.0,(1,2.…,). 则,^)也是(O)的一点.
.
,
证据设及(12)式得'.
g<)+y(,,c,d)Y(,,c,d)=0 j乃缸,^,c)=0.
于是^()VL《,^)=一4[Vg()h()]'(,,,)^' 又江,^,c)=0
可得^(乃(;,,):h(西上(西+d(;)L,)))(,i) ?+
d
2耋^(();,上矗『^)=0
从而推出
,m+州)V:晡嘛)+鲁)耋(警)[VD<< ×Yfx,^,c,d)^=0
可取适当范围(0,d'),使Vd?(0,d'),上式左端第一个方括弧内矩阵可逆.从而
江,,c,d);0
即
又
由假设
m
故
,()=一fjr(,^,c,d)=0
(),工<.^)=0
珊<)=h()h()正定,
工,)=0
(西+(i,c,d)y(,五,c,d)=0.
)?O
-c+}c;,,c,d)=max
.(.,一!一)=.,V
zaov
第3期唐建:非线性规划的一类新增广拉格胡丑函数ll1 即(7),(1O)式成立.
性质2设0是n×n可逆矩阵,n维实向量(e)是的同阶无穷小,则向蒸);=O?(8)
是8'的同阶或高阶无穷小.进一步假设O是正定矩阵,则y=O?(e)至少有一个元素,
其
绝对值是的同阶无穷小,因而y是8'的同阶无穷小量. 证因maxIY.I?llYll?OIlix(e)ll 1?f?n
又O可逆,故llOIl>O,即Y是的同阶或高阶无穷小量.如O正定,令=O?(e),
I=1,则
M=min{xOxIllxli=1)>O,且maxl2il?M/v:' 1?f?
事实上,若Vf,I<.M/v/,则Vllxll=1 'M0
oX=xTz?善IxII<i善-IxlI?肼,矛盾?
现在用(e)lllx(~)ll代替上式之(e),则相应2换为ylllx(e)II,运用上面的结果,至 少存在i使得
?.
.
...
兴)ll<lylI?lIyII<IIOllII)l1..一?
^y至少有一个元素其绝对值是的同阶无穷小量.
定理3设X×L是×的紧子集,且1)内(O)的可行点正规.2),+dh(); ?
L()()正定,3)limc?d=oo.则丑c>O,Vc~.
c,若(,^)?×L是似f^,c)
的稳定点,则;^)也是(O)的—点.
证先证明在定理假设条件下,丑;>o,Vc>~c,Td,,c)的稳定点(;,满足 g()+l,(,^,c,d)y(,^,,d)=0(15) 如果此结论成立,由定理2,(,^)就是问题(O)之—点了.
采用反证法证明该结论,设此结论不真,则存在序列{c-)趋于正无穷太,(,^-)为 "(,,cd之稳定点,但并不满足条件(15).
园X×工紧,f(机.^-))有子刊(不妨仍记为原序列)收敛到,^)?xL.对每点 (,^),VTa~(x,,,C?)=0,由(】1)式
h(x?),L(x?,^^)=一(c^+TIl^-I】)E1+d^(')L(^,^?)^(^)].h(?)Vg(x?)
+一
每dfi(xh?^(-^(竽)
?e:^(),L....-
令q={+dh(xhL(xk,k)h(xhh(xh)?妻(簧)v=L?日h(xjV工i B=Vg(xDh似^),X=(+l,(,^,^,d-)Y(?^^,^,dD
则上式为一'?
112重庆建筑工程学院1991拒
^()L(,)=一(c+l}^自ll.)E1+d^(^)?^(x1)3BX—d?(16)
(12)式变为'
+IIx}I.+daB?^(E)VL(',a)+4d^Y:九=0(16) ?
.'g+l,=ma<一l(L+2dA)X) y:':一(c+11lll.)Y'一2d^y2A^j 将(16),(16)式代入(16)式得
(16)
+TltxIl'一(c自+百^ll>d^[口(+d自^<)L?^(xD>B+4l,:IX一8dl,
'^^一1diBu=O'
令O=B(I+d'h(xOYr.上?h(x^))曰+4} 硅意l,A'h=^'Y^Y^ [o+瓮]一=赫一
由假设条件知td?趋于零,o正定,若.? 因此,存在充分大的,V?i,d声分小,而(o+喾]正定, 时,,—o,故也为无穷小量,胄性质2,其与害同阶. 注意.(?+}c,,c?,=max{(?,,—=》L}. 叠证明,v?百,,^)满足(15)... 令=c.十IIt,运用性质考虑下列情况, l>v,?一.
C.
(17)
d._0
(18)
(19)
从(18)式知,X=g(x^)+Y*y^=口(xO,(17)式变为 fo一士]X一?th=一粤Bu
.
,.
hd^..h.I
上式右端与磐同阶,左端第一项为O(1lXl1),第二项为O(育1tlXIIt),等式矛盾.故,C/,'c^.
=O,(15)式成立.
2)丑,,使(19)式不成立.
定义,;{,}使(i9)式不成立之如且?0).
(i)J?的情况.
v,?,,则存在{.)不趋于零,故Xi=一;尘=0(—)
第3期
V畦,,
唐建非线性规划的一类新增广拉格朗日函数113
因而为o(),(17)式左端主部为第一项,有某一元素为o(),而右端相应 元素与安同阶,矛盾.故X=0.
(ii),=的情况.'一,
定义,={fIi使(19)式成立',=={fIi使(19)式不成立.
注意;当lE1,gr(),当f?,Xr=o({『上)..
首先考虑X与lg,忸)l同阶的情况,这里,是,中使IgJ(扎)l最大的脚标.(17)式 左端某项f与Igf(xDI同阶.如i?,,有I口(?)【<I()I,右端相应项为l()I的高 阶无穷小.(坐),如有lf<,右端相应项为
),它是f{}f的高阶无穷小.两种情况均导致矛盾,故x=o. 其次考虑与f}f同阶的情况.同上一种情况推理类似,考虑^是否为零情形, 同样推得X=0.
综合上面1),2)两种情况,v?,一似.,)筠满足(15)式,这与假设矛盾,故结 论成立.
5主要结果
定毽4设似,)是(0)之—点,且1)叫毛(0)在的某紧子集上唯一的整体极 小值点,?int,2),)正则.则对上任何紧子集啊?intL),丑c>O,枷?c, 如定理3假设成立,那么似,"也是T,t(x,,c)在)c工上的唯一整体极小点. 链设结论不真,则v,,丑{协,))?XxL,社^,k)母枷,,它似是但.^,)在
X×工上的整体极小值点,但
Tat,(x^.,)?Td?似,,^)=,似)(20) 下面要证{丑p>O,丑,vk;~k,有
^一xll>~v(21) 或者?一xl1?p,但IIM-I{?p(22) 事实上由假设条件1),2)可定义p>O,使得有' 日(.^)=fIll—xll?p)X{^IlIx-Xll<v)cXx上 如弘',)?B(x,),由定理3,丑,v?,似',^')是(口)之一点,即有
,
7'd?(,,)=,('),g(?)《O.
立
成
式
浪
以
,?\,
O0
=
114重庆建筑工程学院1991年
由假设条件互自='与假设矛盾.推出(21)式或(22)式成立.
'×紧,(,)f'(,)?X×,由(20)式
1imSllp71d^(,^,)?,()'一
^^^
.g()+Y(,,..,0)y=0 ,.
,()?,()
由(23)式得a(x)?0
由(24)和条件1)得=,又因,7'd^拈h,,南)=0.
...,工(,^+(+fll^ll)Vg(Xi)((^)+Y~YA)+d^?()?,
(23)
(24)
+
警誊()L(xl,~h=o
,.1imvTd-(-,^,南)=工(,)o.
由假设条件2),=,这与(21)或(22)式矛盾.'
定曩5设(,_)是(O)的—点,设1)是(O)的孤立局部极小I2)定理3假设 成立.则丑c>0,Vc>~c,(,)也是Td(x,,c)的局部孤立极小点. 证明与定理4类似.
窟曩6设XX工是紧集且1)定理3假设成立}2)(O)的任何整体极小点总存在相应 乘子,使《,)是(O)的—点.则丑c>0,vc?c,如似,)?int(X工)是Td(x, ,c)的整体极小点,则是(O)的整体极小点,是相应的拉格朗日乘子. 证由定理3,7t-i>o,v?如(;)?int(×工)是7'd似,,c)的整体极小点, 则似,)也是(O)的—点..
由定理1知
,()=Td(,^,c)~Td(x,,c),V(,)?X×工
对(O)之任何一7'点,由定理1,
.
()?d(,,c)=,()
由条件.2),定理得证.
窟曩T设X×工是X中紧子集且1)定理3假设成立,2)在—点,严格互 补条件成立.则~tc>o,Vc?如似,)?x×工是Td(x,,c)的极小点,则是(0)的局 部极小点,是相应的拉格朗日乘子..
,-证,由假设和定理3知,协,)也是fO)的—点由定理l,Td(x,^c)=,() 因(;,-)是T似,,c)的局部极小点,故丑;,确邻域o(,^('),使得
.
,()?J(,,c),V(.)?D()XV(,(25)
考虑方程,)=h(x)v.L(x,)+2y=0
...(,)=o,",)EcI,a(;,_)=h(一x)一vg西非奇异,唐臆函数存在定理,丑Dc
D和连续可徽函数^(),使得v打?D,,()?^且似,())=0 即^()三(,())+2l,(,(),c,)()=9,(26)
第3期唐建t非线性规划的一类新增广拉格朗日函数115 由此,(),c):G伽,())十号+训())llg(x)+yIi. +
~--IIh()(,,())+2Yh()fl一2dV?()y()
+l,II =,<)+()(g()+Yy)1(c+tl()){日
一
2dv工?h()rye,)(27)
夸?D且g()?O.v,考虑情况l
1)jr}(,(),c,d)=0
自()一,....
.._)["丢(c+t)]?一d)+丢)?一d)(28) 2)jr(,(),c,d)>O
由(4)g}牡)+jr}(,(),c,d).一
(+,r)[+1(c+fl)(+jr}]=一(d}一丢,)(gi+) =一d}(g+})一jf?型
2(c+fl)
?一d}(g+jr)
由(28),(29)式
(g}+jr})+?(c+tliXll)()]?一axfcoj+}) VX?n,g()?O,由(25),(27),(3O)式
,)?rd,伽),c)?,()一dE2v,工枷,))h()Y?()+伽)Lg) +Y?()]
卉0,令d--~O,
,)?,牡)Vx?Dn(lg()?0)
参考文蕾
(29)
(30)
1VinateC.andPintosS..Ondifferentiahleexactpenaltyfunction.IOTA, 50(3).I986
2PowellM.J.D.andYuanY..Arecursivequadraticprogrammlngalgorithm thatusesdifferentiableexactpenaltyfunction,Math.Programming.35,1986 8HanS.P..OntheHessianofLagrangeandsecondorderoptirealitycondi—
tions.SIAMJ.ControlOptim..24(3),19$6
116重庆建筑工程学院1991年
4HanS.P..OntheaugmentedLagra~gianfunction.Math.ofOperationRe seareh,11(1).1886
5Pi1loDI.G.aDdGrippoL..AnewaugmentedLagrangialafunctionforine qualityconstrainedin?onlinearproKrammingprob1em$.JOTA,36,1982 (编辑t姚国安)
ANEWCLASSOFAUGMENTEDLAGRANIAN
FUNCTIONFORN0NLINEARPROGRAMMING
Tang]Jan
(DepartmentofNaturalScience)
ABSTRACTInthispaper.a/1ewclassofallgmentedLangrangian fllnetionforsolvingoptimizationproblemwithtwicecontinuouslydif—
ferentiableinequalityeonstraintsisstlldied.UndermildassumptionsOil theparametersofaugmentedfunction,theequivalenteofstationary pointsofthefllnctionalldK-Tpoints0ftherestrictedproblemispro—
vedaswe11astheirextremepointS.
KEYWORDSnonlinearprogrammingLagrangianfu/1ction,inequa1ity construints