




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、第三講非線性規(guī)劃4約束極值問題(1)問題minf(X),問題R X(X) 0,j 1,11思路:有約束 無約束;非線性 線性;復雜 簡; 一、最優(yōu)性條件1.可行下降方向(有用約束,可行方向,下降方向)(1)有用(效)約束設1式的f (X),gj(X)有一階連續(xù)偏導設X(0)是一個可行解,下一步考察時,要討論約束第1頁共25頁分析:應有gj(X(0) 0若gj(x(0) o, 則在U (X(0)內, 有gj(x)o,此時各個方向均可選.若 gj(X(0) 0,gj(x(0)0則X(0) ggj(x(0)0第2頁共25頁故稱gj(X) 0是X(0)點的有效約束.(2)可行方向(對可行域來說) 設X
2、(0)為可行點,P為某方向,0, 00的梯度若存在0 0, 00的梯度則稱P是X點的一個可行方向.(a)可行方向P與有效約束gj(X(0) gj(X)關系是:gj(X(0)TP 0.記有效約束下標集第3頁共25頁J j|gj(x(0)0,1 j 1若p為x 若p為x (0)的可行方向存在0 0,使得當gj(x(0)從而dgj(X(0) P)dP),則0, o,有gj(x(0)o,j Jgj(X(0)TP 0,j J第4頁共25頁(0) 0(0) 0(b)反之,若gj(X(0) )TP 0,則P必為可行方向.Qgj(X(0) P) gj(X(0)gj(X(0)TP o()對有效約束gj(X(0)
3、 0,只要 充分小,得第5頁共25頁gj(X(0) P) 0,所以P是可行方向;對無效約束gj(X(0) 0,同樣只要 充分小就有gj (X(0) P) 0 ,故P也是可行方向;事實上,對無效gj(X(0) 0, P都是可行方向.(3)下降方向(對目標函數(shù)來說)設X(0) R,對某P方向,若在 0, 0, 0 0 內,有f(X(0) P) f(X(0)第6頁共25頁則稱P是一個下降方向.下降方向判定:若f(X(0)TP 0,則P是X(0)的一個下降方向因為 f(X) f(X(0) P)f(X) f(X(0)TP o(), 只要充分小,都有f(X) f(X(0). (4)可行下降方向 若X(0)
4、 R的某方向P是可行方向+下降方向, 則稱P是X(0)的可行下BI方向.第7頁共25頁即存在0 0,當 0, 0時,有g/X P) 0 且 f(X(0) P) f (X (0),是繼續(xù)尋優(yōu)方向.討論:X(0)非極小值點存在可行下降方向 P;X (0)極小值點無可行下降方向P;(可行但不下降,或下降不可行)第8頁共25頁定理(局部極(最)小必要條件)設X是min f(X),X gX) 0局部極小點. f(X),gj(X), j J (有效約束下標集)在X處可 微,gj(X), j J在X處連續(xù),則在X處無可行下降方向 P,即不存在P ,使* Tgj(X)Tp o,j j, f(X*)TP o,(
5、)證 否則由(*)及前面的分析,可找出可行下降點 X非局部極小值點矛盾.第9頁共25頁如圖 所示如圖 所示2.庫恩塔克條件(局部最小的必要條件) 是非線性規(guī)劃中最重要成果之一Gordan引理(不加證明)設A, A2,., A是l個n維向量,則第10頁共25頁P , AT P 0,j 1,2,., lj0,不全為零,使jAj0.j i(不指向同側的向量,正組合為零)(如l=3,n=2)若同側,則有P(圖a),否則無P(圖b),但可正組為0.Fritz John 定理設X是1極小值點,f(X)和gj(X)有一階連續(xù)偏導數(shù),則存在不全為零的0, 1,., l ,使i0 f(X ) j gj(X )
6、0j 1jgj(X ) 0, j 1,2,.,lj 0,j 1,2,.,l證明因X是問題1的解,故由定理4,不存在可行下降方向P,使第12頁共25頁f(X )TP 0gj(x)tp 0, j j由Gordan引理,存在不全為零非負數(shù)o, j,j J使0 f(X ) j gj(x)0j j對無效約束j J ,令j 0,則j gj(X ) 0從而有(對所有l(wèi))第13頁共25頁l0 f (X ) j gj(X )0j i且有 jgj(X) 0, j 0, j 1,2.l ,證畢.注1:類似于條件極值的必要條件.注2若0 0,則有效約束的gj (X )正線性相關同側有可行下降方向X非極值點.故一般設g
7、j(X )線性無關 0 0.以上條件稱為 Fritz John條件,X 稱為Fritz John 點.第14頁共25頁(3)必要條件(庫恩-塔克條件)設X是極小值點,f(X)和gj(X)有一階連續(xù)偏導,且有效約束梯度線性無關,則1 ,., l ,使if(x ) j gj(x)0j ijgj(X ) 0, j 1,2.lj 0,j 1,2,.,l證明 由Fritz John引理,gj(X ) j J線性無關第15頁共25頁得 00,作 j 0/ 00,即得.式2=庫恩-塔克條件. 式2=庫恩-塔克條件. 簡稱K-T條件,K-T點. 對一般非線性規(guī)劃min f (X),h(x)o,i imgj(X
8、) 0, j 1,l它的K-T條件如下設X是3極小值點,相應點=庫恩-塔克點.min f (X), hi(X) 0,hi(X) 0,i 1mgj(X) 0,j 1,l相應函數(shù)有一階連續(xù)偏導第16頁共25頁且有效約束的hi(X )和 gj(X ), j J線性無 TOC o 1-5 h z 關,則 (1, 2,m)DM (1,., i)T, 使 mlf(X ) i hi(X ) j gj(X ) 0 i 1j 1 HYPERLINK l bookmark18 o Current Document jgj(X ) 0,j 1,2,.,ij 0, j 1,2,., l其中 1, 2,m, 1,.,
9、l稱為廣義Lagrange乘子. 注1對凸規(guī)劃,K-T條件也是充分的.第17頁共25頁設Xk為某可行解 若Xk是極小點, 且gi(xk)0, 和g2(xk)0, 則f(x(k)必與,kk、gi(X )和g2(X )同側,否則有可行下降方向由gi(Xk)和g2(Xk)線性無關kkf(X )1 gi(X )2 g2(X )第18頁共25頁0例10用庫恩-塔克條件解非線性規(guī)劃02max f (x) (x 4)1 x 614 6第19頁共25頁14 6min f(x) (x 4) TOC o 1-5 h z 解變?yōu)?gi(x) x 10,g2(x) 6x0f(x)2(x 4), gi(x) 1, g2
10、(x)1 ,引入廣義拉格朗日乘子1, 2,則有2(x4) i 20l(x 1) 0, , f所以,具體分析如下2(6 x ) 0第20頁共25頁若10,若10,2若10,2若10,2若10,2所以最大值點注:f (x) TOC o 1-5 h z 0: x1,點;f (x)9 (16)0:x4, f (x )0;0: x6, f (x )4 (24)x 1,最大值f (x ) 9 .x 1,最大值f (x ) 9 .,八2(x 4)非凸函數(shù),第21頁共25頁附加例題(略)用K-T條件解非線性規(guī)劃一一 2min f (x) (x 3) 0 x5min f (x) (x 3)2, 解 gi(x) x 0,(是凸規(guī)劃)g2(x) 5x01,f(x) 2(x 3), gi(x) 1, g21,第22頁共25頁2(x3)1 x 0所以,具體分析如下.2(5 x ) 01,20若10,20,引出矛盾,無解;若10,20,解得 x0,16,非K-T 點;若i0,20,解得 x5,14,非K-T 點;若10,20,解得x 3 , f (x) 0全局
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 大數(shù)據(jù)公司股權轉讓及數(shù)據(jù)處理與分析服務協(xié)議
- 股東投資款回收終止合作協(xié)議
- 股權質押貸款背景下的股權轉讓合同范例
- 跨界融合股東出資及商業(yè)模式創(chuàng)新協(xié)議范本
- 內部股東股權分配及轉讓協(xié)議范本:員工持股計劃
- 2025-2030中國人造土壤市場經營形勢與未來發(fā)展方向研究報告
- 注水站增效措施方案
- 設備維修實施方案
- 門面招商后期服務方案
- 礦井防洪演練方案
- GB/T 6075.3-2011機械振動在非旋轉部件上測量評價機器的振動第3部分:額定功率大于15 kW額定轉速在120 r/min至15 000 r/min之間的在現(xiàn)場測量的工業(yè)機器
- GB/T 5594.4-2015電子元器件結構陶瓷材料性能測試方法第4部分:介電常數(shù)和介質損耗角正切值測試方法
- GB/T 15558.1-2015燃氣用埋地聚乙烯(PE)管道系統(tǒng)第1部分:管材
- GB/T 11060.8-2020天然氣含硫化合物的測定第8部分:用紫外熒光光度法測定總硫含量
- 國開??啤锻鈬膶W》十年期末考試題庫及答案
- 浙江義務教育學校校園飲水質量提升工程建設和維護浙江教育廳
- 林州重機710采煤機電控箱裝配流程
- 個人求職簡歷兩頁 (46)應聘履歷參考模板可編輯修改
- JJF 1847-2020 電子天平校準規(guī)范(高清版)
- 統(tǒng)編版小學語二升三銜接閱讀專項訓練—課外閱讀(二)【含答案】
- 積分會員管理系統(tǒng)excel表格模板
評論
0/150
提交評論