


下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
基于仿射尺度方法的二次規(guī)劃問題求解
二規(guī)劃問題的求解是數(shù)學(xué)規(guī)劃和工業(yè)應(yīng)用的一個(gè)重要課題,也是解決一般非線性規(guī)劃問題的二次規(guī)劃算法的關(guān)鍵。在第一次解決二次規(guī)劃問題時(shí),使用了線性規(guī)劃的簡單方法和有效集法。1968年,該算法由karak提出。在提出了解算方法的內(nèi)部算法后,許多人使用了模仿參數(shù)算法進(jìn)行非線性計(jì)算。在本研究中,基于模仿參數(shù)方法的概念,將一般不確定的二次規(guī)劃問題轉(zhuǎn)化為球限制的二次規(guī)劃問題,并將二次規(guī)劃問題轉(zhuǎn)化為球限制的凸二次規(guī)劃問題,豐富了二次規(guī)劃問題的方法體系。1有qxqx考慮問題其中:Q∈Rn×n,Q不定,且Q是非奇異的實(shí)對(duì)稱矩陣,c,x∈Rn;A∈Rm×n,m≤n,秩(A)=m.記S={x|Ax=b,x≥0},SS={x|Ax=b,x≥0},S非空,且S為有界集.記SΟ={x|Ax=b,x>0},∥?∥代表歐氏范數(shù).給一初始可行點(diǎn)xk∈SO,使用仿射尺度技術(shù),產(chǎn)生子二次規(guī)劃問題其中:=XkQXk;=Xkc;Xk=diag(xk);=AXk;0<r<1.令Δx=x-e,這樣(QP2)可以寫成:記為的零空間的一組標(biāo)準(zhǔn)正交基,由于∈Rm×n,秩()=m,則∈Rn×(n-m).令Δx=Δy,這樣(QP3)就變成為如果得到(QP4)的一個(gè)局部最優(yōu)解為Δy*,也就得到了(QP2)的局部最優(yōu)解,從而也就產(chǎn)生了原問題的下一個(gè)迭代點(diǎn)xk+1=Xkˉx.定理1q(xk+1)≤q(xk)證明由于q(xk)=(e),q(xk+1)=().對(duì)(x)來說,e為初始可行點(diǎn),為局部最優(yōu)點(diǎn),故有ˉq(ˉx)≤ˉq(e).也即q(xk+1)≤q(xk).由于是(x)的局部最優(yōu)解,故滿足下列條件{ˉQˉx+ˉc-ˉAΤˉy+uk(ˉx-e)=0,ˉA(ˉx-e)=0∥ˉx-e∥≤r?uk(r-∥ˉx-e∥)=0,uk≥0(1)其中,uk為相應(yīng)的Lagrange乘子.令pk=+-T,sk+1=s(xk)=QXk+c-AT則uk=∥pk∥r?pk=Xksk+1那么xk+1=Xkˉx=Xk(e-rpk∥pk∥)下面給出仿射尺度算法.算法1Step1給出r,0<r<1,初始點(diǎn)x0∈So,容許誤差為ε,令k:=0.Step2形成(QP4),并解(QP4),得到Δy*,進(jìn)而求得(QP2)局部最優(yōu)解ˉx相應(yīng)的Lagrange乘子ˉy.Step3xk+1:=Xkˉx?yk+1:=ˉy.Step4若pk≤ε,則停止,x*:=xk+1;否則,k:=k+1,轉(zhuǎn)Step2.引理1對(duì)某一個(gè)0<k<∞,如果pk=0,則xk+1為問題(QP1)的K-T點(diǎn).證明見文獻(xiàn)中.定理2設(shè)以上算法產(chǎn)生的序列為{xk},{yk}收斂,進(jìn)而記ˉx=limk→∞xk,ˉy=limk→∞yk,則ˉx,ˉy對(duì)(QP1)是可行的,且ˉx,ˉy滿足一階必要條件和二階必要條件,即Qˉx+c-AΤˉy≥0?ˉX(Qˉx+c-AΤˉy)=0,且對(duì)?d∈G,有dTQd≥0.其中ˉy為Ax=b的Lagrange乘子,G={x∈Rn:Ax=0,且eΤjx=0,j∈J},J={j∈{1,2,?,n}:ˉxj=0}證明見文獻(xiàn)中.2xk-k-t下面的問題是如何求解(QP4).為了討論方便,把(QP4)寫成一般形式(QΡ){min12xΤQx+cΤxs.t.∥x∥≤r其中Q∈Rm×m,且QT=Q,Q非奇異,c∈Rm,0<r<1.記λ1,λn分別為Q的最小特征值和最大特征值,xk∈{x∈Rm:∥x∥≤r},讓?duì)?λn+η,η≥0,此時(shí)(ρI-Q)半正定,因此f(x)=12xΤQx+cΤx≤gk(x)+12(xk)Τ(ρΙ-Q)xkgk(x)=12ρ∥x∥2-xΤ[(ρΙ-Q)xk-c]這樣問題(QP)轉(zhuǎn)化為求解以下凸二次規(guī)劃問題(CQΡ){mingk(x)=12ρ∥x∥2-xΤ[(ρΙ-Q)xk-c]s.t.∥x∥≤r這是一個(gè)具有球約束的凸二次規(guī)劃問題.由?gk(x)=0,得到x=(ρΙ-Q)xk-cρ.設(shè)xk+1是(CQP)的一個(gè)解,則xk+1={(ρΙ-Q)xk-cρ,當(dāng)[JX-*2][JX*2](ρΙ-Q)xk-cρ[JX-*2][JX*2]≤r時(shí);(ρΙ-Q)xk-c∥(ρΙ-Q)xk-c∥r,當(dāng)[JX-*2][JX*2](ρΙ-Q)xk-cρ[JX-*2][JX*2]>r時(shí);(2)定理3設(shè)x0∈{x∈Rm:∥x∥≤r}是任意給定的一點(diǎn),那么迭代公式(2)產(chǎn)生的點(diǎn)列{xk}的每一個(gè)聚點(diǎn)x*都是(QP)的K-T點(diǎn).證明因?yàn)閤k+1是(CQP)的解,所以xk+1滿足(CQP)的K-T條件{ρxk+1-[(ρΙ-Q)xk-c]+λk+1xk+1=012λk+1(∥xk+1∥2-r2)=0,λk+1≥0(3)[ΚΗ*3D](4)其中λk+1是Lagrange乘子.顯然‖xk‖≤r,k=1,2,…,因此{(lán)xk}是有界的.不失一般性,設(shè)limk→∞xk=x*,如果‖xk‖<r,那么λk+1=0;如果‖xk‖=r,那么在式(3)兩邊關(guān)于xk+1做內(nèi)積得λk+1=?(ρΙ-Q)xk-c,xk+1?-ρr2r2,因此λ*=limk→∞λk+1=?(ρΙ-Q)x*-c,x*?-ρr2r2=-(x*)ΤQx*-cΤx*r2.綜上所述有ˉλ*={λ*?∥x∥=r0,∥x∥<r.在式(3)和(4)兩邊取極限得{Qx*+c+ˉλ*x*=0,12ˉλ*(∥x*∥2-r2)=0,ˉλ*≥0(5)[ΚΗ*3D](6)式(5)和(6)恰好是(QP)的K-T條件,因此x*是(QP)的一個(gè)K-T點(diǎn),ˉλ*是Lagrange乘子.于是得到算法2.算法2Step1設(shè)x0∈{x∈Rm:x≤r}?η≥0,容許誤差ε>0,ρ=λn+η,k:=0.Step2解(CQP)得到xk+1={(ρΙ-Q)xk-cρ,當(dāng)[JX-*2][JX*2](ρΙ-Q)xk-cρ[JX-*2][JX*2]≤r時(shí)(ρΙ-Q)xk-c∥(ρΙ-Q)xk-c∥r,當(dāng)[JX-*2][JX*2](ρΙ-Q)xk-
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 環(huán)游旅行記面試題及答案
- 服務(wù)項(xiàng)目的創(chuàng)業(yè)計(jì)劃書
- 安全機(jī)械傷害培訓(xùn)
- 慕課如何查看課件
- 氣動(dòng)元件的故障預(yù)測(cè)與健康管理考核試卷
- 七年級(jí)英語上冊(cè) Unit 3 Body Parts and Feelings Lesson 14 Colours and Feelings教學(xué)設(shè)計(jì) (新版)冀教版
- 液氨管理及泄漏的應(yīng)急救援處置考核試卷
- 海洋地質(zhì)調(diào)查考核試卷
- 沙灘足球場(chǎng)地平整與標(biāo)記考核試卷
- 紅火蟻防控課件
- 天冬中藥材種植可行性研究報(bào)告
- 肝腎綜合征演示文稿
- 國際關(guān)系理論智慧樹知到答案章節(jié)測(cè)試2023年外交學(xué)院
- 1.罌粟堿-經(jīng)典擴(kuò)血管藥物
- 配料記錄表(標(biāo)準(zhǔn)樣本)
- 《四川省平武縣大茅坡鉛鋅礦資源儲(chǔ)量核實(shí)及延伸詳查報(bào)告》礦產(chǎn)資儲(chǔ)量評(píng)審備案公示信息表
- 芯片手冊(cè)盛科sdk用戶開發(fā)指南
- 海淀八模語文
- GB/T 29312-2022低壓無功功率補(bǔ)償投切器
- 機(jī)臺(tái)操作指導(dǎo)書(注塑機(jī)安全操作規(guī)程)
- GB/T 9647-2015熱塑性塑料管材環(huán)剛度的測(cè)定
評(píng)論
0/150
提交評(píng)論