求解某类大规模凸二次规划问题的￡许方向法容

《求解某类大规模凸二次规划问题的￡许方向法容》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第12卷第1期扬州师院学报(自然科学版)VoII2．NoI1992年3月JournalofYan~zhouTeachersColle(NamralScienceMal"1992求解某类大规模凸二次规划问题的￡容许方向法万仲平王前(武汉冶盎建筑专科学校)(数学系)摘要利用e有效广义约束向量所张成的向量锥方法，通过求解一个低维的简单线性规划子问题获得一个下降可行方向从而构造出求解某类二次规划的算法，并对算法进行了收敛性分析与数值计算．从算法的构造来看，它适用于大规模问题的求解．关键词二次规划。e有救广义约束．线性规划子问题，下降可行方向中

2、围法分类号O221．1众所周知，二次规划的理论和算法的研究在非线性规划中占有十分重要的地位．这不仅由于许多实际问题可化为二次规划问题，而且一般的非线性规划问题可借助于一列二次规划问题来获得最优解．Il本文讨论如下二次规划问题：1rmin／~x)j妄口—Px，s．t．≤≤厣(I．I)‘其中P。。F∈R且

3、．1)的一个容许方向法．该算法主要是通过求解一个低维线性规划子问题得到一个下降可行方向．下面我们讨论：1下降可行方向的形成令Q一{xlxeR",≤≤F}．设某个s>1o，已求得第k次近似解x∈Q，令：R(x。5t)={0≤一I≤s}垒R：(1．2)Rpt)={／L0≤厣，一≤s}皇R：(1．3)搜索方向：本文于1991年12月5日收到第1期万仲平等：求解某类大规模凸二次规划问题的‘容许方向法，‘，11dt垒一。V／(x)+∑。e』一∑^，e(·)一：：其中。>I0。I>0。f∈R：u：，由下列线性规划子问题的最优解确定·Vt(x)d≤

4、一ed≤0，f∈：ed≤0。，∈：^+∑≤l，；：uR：c1‘5I‘jI≥0，≤0，≥0，f∈R其中V，()为，(x)在x处的梯度向量。e为第f个单位元坐标向量．如果问题(1．5)的最优解存在，设其解为“‘=(j：，，。‘)。其中^：=(，·，一(，。)．且：一z，⋯'f，}，：z，⋯，，，}_若‘d<0，则由(1．4)式定义的方向d=一：V／(x)+．∑一∑P(1·6)』‘：‘；为处的一个下降可行方向．即有定理1．1设某个8≥0，≠，若∈n处子问题(1．5)的最优解为‘，且‘<0，则由(1．6)式定义的方向d为问题(1．1)在‘处的

5、一个下降可行方向·证明据下降可行方向的定义，只须证明fV)dt<0dt≥0’i∈：(1_7)ledt≤0，，∈：ld≠0出于问题(1．5)和‘<0，(1．7)显然成立．推论设对某个8≥0，；0，~IVa：(i)若V／(x)≠0，则d=一V／(x)为处的一个下降可行方向；(ii)若V，()：0，则已为问题(1．1)的最优解．证明由假设=：UR：=0，x为n的内点，由无约束优化的有关理论，()显然成立．再由无约束优化的必要条件和日标函数的可微凸性知(ii)成立·l4扬州师院学报(自然科学版)1992年2算法描述2．1最优步长因子的选取在这

6、里我们要计算两个步长因子。是在方向d上的目标函数极小化步长Ta是一方向d上的不违反约束的最小步长．设(日)鲁l(x+Odt)=l(x)+oVl(x)dt+亏1日口t贝Ⅱ(0)=ICx)，(日)兰V)dt+。口t，因为4q为(日)=0的解，即当Qdt≠0，dt≠0时，：口t>0，且4=一(Qx一．P)d／d口d(2．1)2~fQd=0的情况，我们将在稍后讨论．令a一苗，(2．2)因此最优步长因子可取为：口tmin{acl，}(2．3)当口t=one，则有：p一枷ICx)=_f(x+Odtt，)一_f()+ov／(x)dt(2．4)、●，

7、J对每个非零正数0，目标函数值均下降，即有_f(x)≤／(x)，所以此时可取at=a(2．5)因此第+1次近似解“∈n。可由下式确定：⋯=+4^dt(=0,1，2，⋯)(2．6)2．2算法步骤1。任取x0∈n，选取s>0,01，规定约束数M。，置k=0；，f2。令st=3。按(】．2)与(1．3)式确定R：和R：及其相应约束数盯；4。若M0(即：U：=转5。，否则转6。；5。若IIV／(x)1≤，，则为近似最优解，迭代终止，否则令d=一V／(x)，转10。：6。若M>Mo，剐令Et一”t转3。，否则转7

8、。；7。求解子问题(1．5)得最优解’=(，^，：，)，d=一V／(x‘)+∑e一∑^e第1期万仲平等：求解某类大规模凸二次规划问题的￡容许方向法158。若口’>一1转9。，否则转lO。；9。若Et>。，．qii~E一f