1、1,最優(yōu)化方法,2,前言 什么是最優(yōu)化 最優(yōu)化是一門應(yīng)用性相當(dāng)廣泛的學(xué)科, 它討論決策問題的最佳選擇之特性, 尋找最佳的計算方法, 研究這些計算方法的理論性質(zhì)及其實(shí)際計算表現(xiàn),研究內(nèi)容: 在有限種或無限種可行方案中挑選最優(yōu)方案, 構(gòu)造尋求最優(yōu)解的計算方法 研究目的: 主要解決最優(yōu)計劃、最優(yōu)分配、最優(yōu)決策、最佳設(shè)計、最佳管理等最優(yōu)化問題. 應(yīng)用領(lǐng)域：科學(xué)工程、國防、交通、管理、經(jīng)濟(jì)、金融、計算機(jī)等,3,學(xué)習(xí)本課程所需的數(shù)學(xué)知識,向量、向量的模(范數(shù))、向量的運(yùn)算、 線性相關(guān)與無關(guān)、基. 矩陣的運(yùn)算及性質(zhì)、矩陣的秩、特征值、正定性. 向量函數(shù)、連續(xù)性、可微性、梯度、海森矩陣、向量函數(shù)(多元函數(shù))的

2、Taylor定理,4,主要參考書目： 理論方面： (1)袁亞湘、孫文瑜著,最優(yōu)化理論與方法, 科學(xué)出版社, 2005 (2) 何堅勇, 最優(yōu)化方法, 清華大學(xué)出版社, 2007 計算方面： (3) 曹衛(wèi)華, 郭正, 最優(yōu)化技術(shù)方法及MATLAB的實(shí)現(xiàn), 化學(xué)工業(yè)出版社，2005 (4) 朱德通, 最優(yōu)化模型與實(shí)驗(yàn), 同濟(jì)大學(xué)出版社, 2003,5,其它參考書： (5)盧名高、劉慶吉編著, 最優(yōu)化應(yīng)用技術(shù), 石油工業(yè)出版社,2002 (6)唐煥文, 秦學(xué)志,實(shí)用最優(yōu)化方法, 大連理工大學(xué)出版社, 2004 (7)錢頌迪, 運(yùn)籌學(xué), 清華大學(xué)出版社, 1990 (8)解可新、韓健, 最優(yōu)化方法,

3、天津大學(xué)出版社, 2004,6,目錄,第1章 基本概念 第2章 線性規(guī)劃 第3章 線性搜索與信賴域方法 第4章 無約束最優(yōu)化方法 第5章 線性與非線性最小二乘問題 第6章 二次規(guī)劃 第7章 約束最優(yōu)化的理論與方法,7,第一章基本概念,8,1.1 最優(yōu)化問題簡介,9,第1章 基本概念,1.1 最優(yōu)化問題簡介 1.2 凸集和凸函數(shù) 1.3 最優(yōu)性條件 1.4 最優(yōu)化方法概述,10,舉 例,例：對邊長為a的正方形鐵板, 在四個角處剪去相等的正方形以制成方形無蓋水槽, 問如何剪法使水槽的容積最大？,解 設(shè)剪去的正方形邊長為x, 由題意易知, 與此相應(yīng)的水槽容積為 要使其最大, 則,令,得兩個駐點(diǎn)：,因

4、此, 每個角剪去邊長為,的正方形可使所制成的水槽容積最大,11,例:某制藥廠生產(chǎn)甲、乙兩種藥品, 生產(chǎn)這兩種藥品要消耗某種維生素. 生產(chǎn)每噸藥品所需要的維生素量, 所占用的設(shè)備時間, 以及該廠每周可提供的資源總量如下表所示:,已知該廠生產(chǎn)每噸甲、乙藥品的利潤分別為5萬元和2萬元.但根據(jù)市場需求調(diào)查的結(jié)果, 甲藥品每周的產(chǎn)量不應(yīng)超過4噸. 問該廠應(yīng)如何安排兩種藥品的產(chǎn)量才能使每周獲得的利潤最大？,12,定義: x1為生產(chǎn)甲種藥品的計劃產(chǎn)量數(shù), x2為生產(chǎn)乙種藥品的計劃產(chǎn)量數(shù). 目標(biāo)：要使總利潤最大化 max z=5x1+2x2 約束：每周資源總量的限制, 30 x1+20 x2160 5x1+

5、x2 15 甲種藥品每周產(chǎn)量不應(yīng)超過4噸的限制 x14 計劃生產(chǎn)數(shù)不可能是負(fù)數(shù), x10 x20,13,數(shù)學(xué)模型為,這是一個如何合理的使用有限的資源, 使生產(chǎn)經(jīng)營的效益達(dá)到最大的數(shù)學(xué)規(guī)劃問題. 在滿足一組約束條件的限制下, 尋求決策變量x1, x2的決策值, 使目標(biāo)函數(shù)達(dá)到最大值.,14,例：某化工廠根據(jù)一項(xiàng)合同要求為用戶生產(chǎn)一種用甲、乙兩種原料混合配制而成的特種產(chǎn)品. 已知甲、乙兩種原料都含有A、B、C三種化學(xué)成分, 兩種原料分別所含三種化學(xué)成分的百分比含量, 以及按合同規(guī)定的產(chǎn)品中三種化學(xué)成分的最低含量如下表所示： 已知甲、乙兩種原料的成本分別是每公斤3元和2元, 廠方希望總成本達(dá)到最小,

6、 問如何配置該產(chǎn)品？,化學(xué)成分,15,定義 x1，x2分別為每公斤產(chǎn)品中甲, 乙兩種原料的數(shù)量, 目標(biāo)：使總成本最小化 min z=3x1+2x2 約束：配料平衡條件, x1+x2=1 產(chǎn)品中A、B、C三種化學(xué)成分的最低含量 12x1+3x24 2x1+3x22 3x1+15x25 非負(fù)性條件 x10, x20,化學(xué)成分,16,數(shù)學(xué)模型：,化學(xué)成分,這是一個原料配制問題, 是在生產(chǎn)任務(wù)確定的條件下, 合理的組織生產(chǎn), 使所消耗的資源數(shù)最少的數(shù)學(xué)規(guī)劃問題. 滿足一組約束條件的同時, 尋求變量x1和x2的值使目標(biāo)函數(shù)取得最小值.,17,例:某鐵器加工廠要制作100套鋼架, 每套要用長為2.9米,

7、2.1米和1.5米的圓鋼各一根. 已知原料長為7.4米, 問應(yīng)如何下料, 可使材料最??？ 分析：在長度確定的原料上截取三種不同規(guī)格的圓鋼, 可以歸納出8種不同的下料方案：,問題歸納為如何混合使用這8種不同的下料方案, 來制造100套鋼架, 且要使剩余的余料總長為最短.,18,設(shè) 表示用第j 種下料方案下料的原料根數(shù), j=1,2,8, 目標(biāo): 使余料總長度最小化 min z=0 x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8 約束：三種規(guī)格圓鋼根數(shù) x1+2x2+ x4+ x6 100 2x3+2x4+x5+ x6+3x7 100 3x1+x2+2x3

8、+3x5+x6+4x8 100 非負(fù)取整條件 xj0 (j=1,28)且取整數(shù),19,數(shù)學(xué)模型 s.t. 這是一個下料問題, 是在生產(chǎn)任務(wù)確定的條件下, 合理的組織生產(chǎn)， 使所消耗的資源數(shù)最少的數(shù)學(xué)規(guī)劃問題。 滿足一組約束條件的同時, 尋求變量x1至x8的值,使目標(biāo)函數(shù)取得最 小值.,且為整數(shù),20,最優(yōu)化的數(shù)學(xué)模型的一般形式: (1.1.1) 其中 為連續(xù)函數(shù), 通常還要求連續(xù)可微,21,目標(biāo)函數(shù) f(x) 決策變量 x 約束函數(shù) ci(x) 等式約束 ci(x)=0 (i=1, 2, .,m) 不等式約束 ci(x)0 (i=m+1, m+2, .,p) min 極小化 s.t. 受約束,

9、22,根據(jù)實(shí)際問題的不同要求, 最優(yōu)化模型有不同的形式, 但經(jīng)過適當(dāng)?shù)淖儞Q都可以轉(zhuǎn)換成上述一般的形式 例如, 對于求目標(biāo)函數(shù)f(x)極大的問題 max f ( x) 可轉(zhuǎn)換成求- f ( x) 極小的問題 其中,23,又如對于形如ci(x)0的不等式約束, 可同樣轉(zhuǎn)換成上述形式的不等式約束 hi (x)0 , 其中hi(x) =-ci(x) 還有像a(x)b(x)+c的不等式約束, 可通過令 h(x)=b(x)-a(x)+c 轉(zhuǎn)換成h(x)0的不等式約束形式,24,問題(1.1.1)是最優(yōu)化問題的一般數(shù)學(xué)表現(xiàn)形式. 只要在問題中存在任何約束條件, 就稱為約束最優(yōu)化問題. 只有等式約束 稱為等式

10、約束最優(yōu)化問題,25,只有不等式約束 稱為不等式約束最優(yōu)化問題. 如果既有等式約束, 又有不等式約束, 則稱為混合約束問題.,26,如果問題中無任何約束條件, 則稱為無約束最優(yōu)化問題. 無約束最優(yōu)化問題的數(shù)學(xué)模型為 min f(x) , xRn , (1.1.2) 一般簡記為 min f (x),27,無約束最優(yōu)化問題是最優(yōu)化的基礎(chǔ) 一則很多實(shí)際的最優(yōu)化問題本身就是無約束最優(yōu)化問題 二則許多約束最優(yōu)化方法都是通過變換把約束最優(yōu)化問題轉(zhuǎn)換成無約束最優(yōu)化問題后, 用適當(dāng)?shù)臒o約束優(yōu)化方法求解.,28,根據(jù)模型(1.1.1)中函數(shù)的具體性質(zhì)和復(fù)雜程度, 最優(yōu)化問題又有許多不同的類型. 根據(jù)決策變量的取

11、值是離散的還是連續(xù)的分為離散最優(yōu)化和連續(xù)最優(yōu)化 離散最優(yōu)化通常又稱組合最優(yōu)化, 如整數(shù)規(guī)劃、資源配置、郵路問題、生產(chǎn)安排等問題都是離散最優(yōu)化問題的典型例子 離散最優(yōu)化問題的求解較之連續(xù)最優(yōu)化問題的求解難度更大, 本書只介紹連續(xù)最優(yōu)化的理論與方法.,29,根據(jù)連續(xù)最優(yōu)化模型中函數(shù)的光滑與否又分為光滑最優(yōu)化與非光滑最優(yōu)化 如果模型(1.1.1)中的所有函數(shù)都連續(xù)可微, 則稱為光滑最優(yōu)化 只要有一個函數(shù)非光滑, 則相應(yīng)的優(yōu)化問題就是非光滑優(yōu)化問題. 本書只研究光滑最優(yōu)化問題的求解方法,30,如果所有函數(shù)都是變量x=(x1, x2, , xn)T的線性函數(shù), 則稱(1.1.1) 為線性規(guī)劃問題.線性規(guī)

12、劃問題的一般形式為,31,上述線性規(guī)劃模型的矩陣向量表示為 其中c= (c1, c2, , cn)T , b1=(b1, b2, , bm)T , b2=(bm+1, , bp)T,32,當(dāng)模型(1.1.1)中的目標(biāo)函數(shù)f (x)是變量x 的二次函數(shù), 而所有約束都是x 的線性函數(shù)時稱為二次規(guī)劃問題.二次規(guī)劃問題的一般形式為 其中A1, A2的表示同線性規(guī)劃模型類似, c=(c1, c2, , cn)T , d 為純量, G為nn階對稱矩陣,33,只要模型(1.1.1)的函數(shù)中有一個關(guān)于x是非線性的, 就稱為非線性最優(yōu)化問題. 非線性最優(yōu)化問題是最一般的最優(yōu)化問題, 而線性規(guī)劃和二次規(guī)劃問題卻

13、是相當(dāng)重要的特殊的最優(yōu)化問題,34,如果點(diǎn)xRn 滿足最優(yōu)化模型(1.1.1)中的所有約束條件, 就稱其為可行點(diǎn)(feasible point) 所有可行點(diǎn)的全體稱為可行域 (feasible region) F表示可行域, 即 F= x | ci(x)=0, i= 1, 2 , , m, ci(x)0, i= m+1, , p,35,對于一個可行點(diǎn) , 考慮不等式約束ci(x)0 如果有ci(x)=0, 就稱約束ci(x)0在點(diǎn) 是有效約束或起作用約束(active constraint) , 并稱可行點(diǎn) 位于約束ci(x)0的邊界. 如果有ci(x)0, 就稱不等式約束ci(x)0 在點(diǎn)

14、是無效約束或不起作用約束(inactive constraint), 并稱 是約束ci(x)0 的內(nèi)點(diǎn) 在任意可行點(diǎn), 所有的等式約束都被認(rèn)為是有效約束,36,在一個可行點(diǎn), 所有有效約束的全體被稱為該可行點(diǎn)的有效集, 并記為 對于一可行點(diǎn) ,如果沒有一個不等式約束是有效的, 就稱 是可行域的內(nèi)點(diǎn),37,例圖1. 1 給出了由下述約束條件給出的可行域F: c1(x)=2x1+3x2+x3-6=0, x10, x20, x30 可行點(diǎn)x1 可行點(diǎn)x2 可行點(diǎn)x3,38,一個可行點(diǎn)x*F稱為問題(1.1.1)的(全局或總體)最優(yōu)解, 如果有 如果上述不等式對所有不同于x*的可行點(diǎn)x嚴(yán)格成立, 即

15、則稱x*為嚴(yán)格(全局或總體)最優(yōu)解.,39,對于可行點(diǎn)x*, 如果存在一個鄰域 使得成立 則稱x* 為優(yōu)化問題(1.1.1) 的局部最優(yōu)解, 其中0是一個小的正整, 范數(shù)可以是任意向量范數(shù), 但一般常用l2范數(shù),40,如果上述不等式對所有xN(x*)F, xx*嚴(yán)格成立, 則稱x*為嚴(yán)格局部極小點(diǎn),41,凸規(guī)劃,如果最優(yōu)化問題的目標(biāo)函數(shù)是凸的, 可行域是凸集, 則問題的任何最優(yōu)解(不一定唯一)必是全局最優(yōu)解, 這樣的最優(yōu)化問題稱為凸規(guī)劃,42,1.2 凸集和凸函數(shù),凸集的定義 定義1.2.1 集合 稱為凸的, 如果對于任意x, yD有 換句話說, 如果x, yD, 則連接x與y的直線段上的所有

16、點(diǎn)都在D內(nèi),線性約束條件,43,凸集定義的幾何解釋,44,X,X =X +(1- )X(2)， (0 1),X= X(1) +(1- )X(3)， (0 1),45,X,X =u1X(1) +u2X(2) +u3X(3),X= X(1) +(1- )X(3)， (0 1),46,凸集的性質(zhì),兩個凸集的交,和以及差仍然是凸集 對于任意非零實(shí)數(shù)a, 集合aD1=ax|xD1 也是凸集,47,定理1.2.2 設(shè) 是凸集, 則任意m 個點(diǎn)x(i)D( i= 1 , 2 , , m)的凸組合仍屬于D, 即有 其中 證明定理的結(jié)論可以用歸納法證明.根據(jù)凸集的定義, 定理的結(jié)論在m= 2時顯然成立. 設(shè)結(jié)論

17、在m= k 時成立, 我們證明結(jié)論在m=k+1時也成立.,48,設(shè) 考慮任意一組實(shí)數(shù),49,由于 , 我們有 由歸納假設(shè)有 再由凸集的定義得,50,定義1.2.3 設(shè) 為兩非空凸集, 若存在非零向量aRn 和實(shí)數(shù), 使得 則稱超平面 分離了集合D1和D2,51,如果更有 則稱超平面H 嚴(yán)格分離D1和D2,52,定理1.2.4 設(shè) 是非空閉凸集, 但 , 則 (1)存在唯一的點(diǎn) , 使得集合D到點(diǎn)y的距離最小, 即 (2) 是點(diǎn)y到集合D的最短距離點(diǎn)的充分必要條件為,53,1.3 最優(yōu)性條件,最優(yōu)性條件是指最優(yōu)化問題(1.1.1)的最優(yōu)解(局部的或全局的)所必須滿足的條件 常見并常用的有一階必要

18、條件和二階必要條件 先引入兩個同最優(yōu)解相關(guān)的基本概念可行方向和下降方向,54,定義1.3.1 設(shè)f(x)為定義在空間Rn上的連續(xù)函數(shù), 點(diǎn) , 若對于方向sRn存在數(shù)0使成立 則稱s為f(x)在 處的一個下降方向. 在點(diǎn) 處的所有下降方向的全體記為 下面的定理給出了在f(x)連續(xù)可微時下降方向同函數(shù)f(x) 的梯度f(x)之間的關(guān)系.,55,定理1.3.2 設(shè)函數(shù)f (x)在點(diǎn) 處連續(xù)可微, 如存在非零向量sRn使成立 則s是f(x)在點(diǎn) 處的一個下降方向 證明 對于充分小的0 , 將 在點(diǎn) 處展開有 由于0以及 , 那么存在 使得對任意 有,56,結(jié)合這兩式有 這就證明了s是f(x)在點(diǎn) 處

19、的下降方向,57,58,可行方向,定義1.3.3 設(shè) 為一可行點(diǎn), sRn, 若存在非零方向序列S(k), k= 1 ,2 , 和正數(shù)序列 , k= 1, 2, 使成立 且有 ,則稱s是在 處的一個可行方向 在點(diǎn) 的所有可行方向的全體記為,59,有了可行方向和下降方向的概念,我們就很容易直觀的理解最優(yōu)化問題最優(yōu)解所滿足的最優(yōu)性條件. 顯然在一個最優(yōu)解處,不可能有任何一個既是可行的又是下降的方向. 因?yàn)楦鶕?jù)可行方向和下降方向的定義,如果存在任何可行的下降方向,我們就能沿著這個方向找到使函數(shù)值更小的可行點(diǎn),這與最優(yōu)解的定義相矛盾. 這就是由下述定理給出的一個最優(yōu)解所必須滿足的條件.,60,定理1.

20、3.4 考慮最優(yōu)化問題(1.1.1) , 設(shè)x*是問題的一個局部最優(yōu)解, 函數(shù)f(x)連續(xù)可微, 則成立有 證明 對于任意的可行方向sF(x*), 我們證明 對可行方向sF(x*), 存在可行點(diǎn)序列x(k)=x*+ks(k) 收斂于x* 其中s(k)0, k0 , 且s(k)s, k0 由泰勒展開式有,61,由于x*是局部最優(yōu)解, 對充分大的k有f(x(k)f(x*) 由此得 在上式兩端除以k , 再令k取極限得 這樣就證明了,62,最優(yōu)化問題的可行域一般是由于等式或不等式表示的約束條件確定的, 然而由定義1.3.3 所給出的可行方向同具體的約束條件無任何直接的聯(lián)系, 而由定理1.3.4 給出

21、的最優(yōu)性的條件對確定最優(yōu)解沒有任何直接的幫助. 為此, 有必要給出由確定可行域的約束條件表示的可行方向,63,定義1.3.5 設(shè) 為一可行點(diǎn), 可行域F由問題(1.1.1) 中的約束條件定. 設(shè)向量sRn非零, 且有 則稱s是可行域F在可行點(diǎn) 的約束線性化后的可行方向, 其中 表示在可行點(diǎn) 處的有效不等式約束集合. 記這樣的可行方向的全體為,64,對于這樣定義的可行方向, 如果在最優(yōu)解x*處有 成立, 那么定理1.3.4 就可以表示成 由于集合L(x*)是用問題的約束函數(shù)表示, 而集合D(x*)用問題的目標(biāo)函數(shù)表示, 我們就可用問題中的函數(shù)來表達(dá)最優(yōu)解的最優(yōu)性條件 下面的定理給出了在某一可行點(diǎn)

22、 處 成立的條件,65,定理1.3.6 設(shè)所有約束函數(shù)ci(x), i=1, 2, , p在可行點(diǎn) 處連續(xù)可微, 則有 (2)如果或者所有ci(x), i =1, 2, , m, i( ) 是x的線性函數(shù) 或者 , i=1, 2, , m, iL( )線性無關(guān), 則 成立.,66,證明 任取一個非零的可行方向 , 則存在可行點(diǎn)序列 , 其中k0,k0 和s(k) 0, s(k)s 由x(k)的可行性以及有效集的定義有,67,在上述兩式的兩端都同除以k后再對k取極限, 由函數(shù)的連續(xù)可微性得 這就證明了 ,由 的任意性證明了,68,定理1. 3. 6 的(2)中關(guān)于約束函數(shù)的條件稱為約束規(guī)范 有許

23、多不同的約束規(guī)范條件和表現(xiàn)形式, 但最常見也是最方便使用的還是由上述定理的(2)所給出的約束規(guī)范條件. 有了上面的準(zhǔn)備, 我們現(xiàn)在就可以給出最優(yōu)解的一階必要條件, 又稱Kuhn-Tucker條件,69,定理1.3.7 設(shè)x*F是最優(yōu)化問題(1.1.1) 的一個局部最優(yōu)解, f(x), ci(x), i= 1, 2, , p 在x*的一個鄰域內(nèi)連續(xù)可微. 如果對所有的等式約束和在x*的有效約束, 或者都是x的線性函數(shù), 或者他們在點(diǎn)x*的梯度向量線性無關(guān), 則存在向量 使成立 (1.3.2),70,證明 根據(jù)定理的條件, 由定理1.3.6在點(diǎn)x*成立有F(x*)=L(x*). 再據(jù)定理1.3.4

24、有 .根據(jù)集合D(x*)與L(x*) 的定義, 這以表示成下述不等式組無解 將上述不等式組改寫成,71,或矩陣向量的表示 其中 由不等式組(1.3.3)無解, 根據(jù)引理1.2.6 存在非負(fù)向量 y=(y(1), y(2), y(3)T使得 其中y(1)Rm, y(2)Rm, y(3)R|I(x*)|. 將上式展開得,72,令 并對非有效約束指標(biāo)i置 , 則有 對于不等式約束還有 又因?qū)τ行У牟坏仁郊s束有 對非有效的不等式約束有 所以有,73,在大部分最優(yōu)化研究的文獻(xiàn)中, 稱最優(yōu)解x*所滿足的一階必要條件(1.3.2)為Kuhn-Tucker條件或K-K-T條件 滿足Kuhn-Tucker條件的

25、點(diǎn)為Kuhn-Tucker點(diǎn)或K-K-T點(diǎn) 稱式(1.3.2)中的第三個等式為互補(bǔ)松弛條件 如果對于任意i=m+1, , p, ci(x*)和 中有且僅有一個取零值, 則稱嚴(yán)格互補(bǔ)松弛條件成立,74,由于無約束最優(yōu)化問題中無任何約束條件, 由定理1.3.7立即可以得到無約束最優(yōu)化問題最優(yōu)解的一階必要條件是 (1.3.4) 即在無約束最優(yōu)化問題的最優(yōu)解處, 任何方向都不是目標(biāo)函數(shù)的下降方向 習(xí)慣上把滿足條件(1.3.4)的點(diǎn)稱為平穩(wěn)點(diǎn)或駐點(diǎn),75,這是因?yàn)闊o約束問題的最優(yōu)點(diǎn)一定滿足條件(1.3.4)但滿足(1.3.4)的點(diǎn)不一定是無約束問題的局部最優(yōu)解 單變量函數(shù)f(x)=x3就提供了這樣的一個

26、例子. 在點(diǎn)x*=0, 有f(x*)=0, 但x*=0卻不是其最優(yōu)解. 這種情況同樣適用于約束最優(yōu)化問題, 即約束最優(yōu)化問題的最優(yōu)解在約束規(guī)范條件滿足時必定是Kuhn-Tucker點(diǎn), 但滿足Kuhn-Tucker條件的可行點(diǎn)未必是最優(yōu)解 下面的定理表明對于凸規(guī)劃問題Kuhn-Tucker條件卻是最優(yōu)解的充分條件.,76,定理1.3.8 設(shè)凸規(guī)劃問題的目標(biāo)函數(shù)與約束函數(shù)都連續(xù)可微, 如果在可行點(diǎn)x*處約束規(guī)范條件和Kuhn-Tucker條件成立, 則x*是問題的全局最優(yōu)解 證明設(shè)x*是Kuhn-Tucker點(diǎn),*是相應(yīng)的向量.根據(jù)凸規(guī)劃對函數(shù)的要求, 我們知, f(x)是凸函數(shù), ci(x)

27、, i=1, , m(如果m0)是線性函數(shù), ci(x),i=m+1, , p(如果pm)是凹函數(shù).因此對任意xF有,77,由于 , i= m+ 1, , p , 對任意xF有 . 因此對任意xF得 這就證明了x*是凸規(guī)劃問題的全局最優(yōu)解,78,Kuhn-Tucker條件中的向量*稱為最優(yōu)Lagrange乘子. 事實(shí)上, 引入問題(1.1.1)的Lagrange函數(shù) 那么我們可以看到條件(1.3.2)中的第一個方程可以寫成 即Lagrange 函數(shù)L(x,)關(guān)于x的一階偏導(dǎo)數(shù)在(x *,*)處取零值,79,如果不考慮在點(diǎn)x*的無效約束, 則在點(diǎn)x*的可行性條件ci(x*)=0, i= 1, 2

28、, , m, iI(x*), 又可表示成 即Lagrange 函數(shù)關(guān)于的一階偏導(dǎo)數(shù)在(x*,*)處也取零值 因而(x*,*) 是Lagrange函數(shù)的一個平穩(wěn)點(diǎn),80,下面我們討論最優(yōu)解的二階最優(yōu)性條件, 為簡化討論, 假定在點(diǎn)x*處嚴(yán)格互補(bǔ)松弛條件成立, 并定義在點(diǎn)x* 處的有效約束的零可行方向集,81,定義1.3.9 設(shè)在可行點(diǎn)x*處嚴(yán)格互補(bǔ)松弛條件成立, 如果存在非零向量序列s(k)和正數(shù)序列k0使有 且有s(k)s,k0 , 則稱s為可行域在點(diǎn)x*處的零可行方向 所有這些方向的集合稱為零可行方向集, 記為Z(x*),82,稱滿足 的非零向量s為約束線性化后的零可行方向 所有這些方向的集

29、合稱為約束線性化后的零可行方向集, 記為Lz(x*) 集合Z(x*)是集合F(x*)的子集 集合Lz(x*)是集合L(x*)的子集 下面的定理給出了最優(yōu)解的二階必要條件,83,定理1.3.10 考慮最優(yōu)化問題(1.1.1), 設(shè)x*F是其最優(yōu)解, 且函數(shù)f(x)與ci(x), i=1, 2, , p 二階連續(xù)可微.又設(shè)定理1.3.6 的約束規(guī)范條件在x*成立, 從而存在Lagrange乘子向量*使Kuhn-Tucker 條件成立.設(shè)嚴(yán)格補(bǔ)松弛條件成立, 則有 其中 是Lagrange函數(shù)在(x*,*)處關(guān)于x的二階偏導(dǎo)數(shù)矩陣,84,證明 任取非零可行方向sZ(x*), 則存在可行點(diǎn)序列x(k)

30、 =x*+ks(k)使得ci(x(k)=0, i= 1, 2, , m, iI(x*), 其中k0 , s(k)s.由于對于無效不行約束有*i=0 , 因而對這樣的序列有 由各函數(shù)的二階連續(xù)可微性, 并利用Kuhn-Tucker 條件有,85,由于x*是局部最優(yōu)解, 對充分大的k有f (x(k) f(x*)成立, 由此得,86,在上式兩邊同除以 后再令k取極限得,87,由于定理1.3.6 的約束規(guī)范條件成立時有Z(x*) =Lz(x*)成立, 上述定理二階必要條件可以用下述更直接的方式給出,88,定理1.3.11 設(shè)x*F是問題(1.1.1) 的最優(yōu)解且函數(shù)f (x)與ci(x), i=1 ,

31、 2 , , p 二階連續(xù)可微.又設(shè)定理1.3.6 的約束規(guī)范條件在點(diǎn)x*成立, 從而存Lagrange乘子向量*使Kuhn-Tucker條件成立.如果嚴(yán)格互補(bǔ)松弛條件在x*成立, 則 對一切滿足 的方向s均成立 下面的定理則給出了最優(yōu)解的二階充分條件,89,定理1.3.12 考慮最優(yōu)化問題(1.1.1) , 函數(shù)f (x)與ci(x) , i=1, 2, , p均二階連續(xù)可微.設(shè)對于可行點(diǎn)x*存在Lagrange乘子向量* 使Kuhn-Tucker條件成立.若成立有 則x*是問題(1.1.1)的嚴(yán)格局部最優(yōu)解,90,證明 定理的證明采用反證法. 設(shè)x*不是問題的嚴(yán)格局部最優(yōu)解, 則存在收斂于

32、x*的可行點(diǎn)序列x(k), x(k)x*, k=1, 2, , 使成立 f(x(k)f(x*), k=1, 2, 不失一般性, 設(shè) 并令 ，則 且k0, 因此s F(x*)=L(x*),91,由函數(shù)f(x)的連續(xù)可微性有 由此得 在上式兩端除以k后再令k取極限得 (1.3.5) 由于sL(x*)而 , 有兩種可能性,92,(a) ,即存在有指標(biāo)i0I(x*)使得sTci(x*)0, 這時由Kuhn-Tucker條件有 這與式(1.3.5)相矛盾, 這一矛盾表明 不成立, 因而有sZ(x*),93,(2)由x(k)的可行性和*, i 0 , i= m+ 1 , , p , 有,94,注意到f(x

33、(k)f(x*) , 由上式得 兩邊除以 , 并令k取極限得 這與定理的條件相矛盾, 由此證明了x*是問題的嚴(yán)格局部最優(yōu)解,95,當(dāng)定理1.3.6 的約束規(guī)范條件在x*處成立時, 有Z(x*)=Lz(x*)成立, 這上述二階充分條件可用下述更直接的方式給出.,96,定理1.3.13 設(shè)最優(yōu)化問題(1.1.1)的函數(shù)f(x) 與ci(x), i= 1, 2, , p 均二階連續(xù)可微, 在可行點(diǎn)x*處定理1.3.6 的約束規(guī)范條件成立.若存在Lagrange乘子向量* 使Kuhn-Tucker條件和嚴(yán)格松弛互補(bǔ)條件成立, 且對所有滿足 的非零向量s有 則x*是問題(1.1.1)的一個嚴(yán)格局部最優(yōu)解

34、.,97,由于無約束最優(yōu)化問題無任何約束, 由上述幾個最優(yōu)解的二階條件(必要的和充分的) , 直接可以得到無約束最優(yōu)化問題最優(yōu)解的下列二階必要條件和二階充分條件,98,定理1.3.14 ( 二階必要條件) 設(shè)x*是無約束最優(yōu)化問題的一個最優(yōu)解, f(x)在x*的一個鄰域內(nèi)二階連續(xù)可微, 則有f(x*)=0, 且f(x)在x*的二階Hesse陣正半定, 即成立,99,定理1.3.15 (二階充分條件)設(shè)f ( x) 在x* 的一個鄰域內(nèi)二階連續(xù)可微,且有f(x*)=0, 2f (x*)正定, 即成立 則x*是f(x)的無約束優(yōu)化問題的一個嚴(yán)格局部最優(yōu)解,100,1.4 最優(yōu)化方法概述,以下述簡單

35、的無約束最優(yōu)化問題為例 根據(jù)最優(yōu)性的一階必要條件, 最優(yōu)解必定是方程 的解,101,由f( x)的連續(xù)性, 當(dāng)x-有f(x)-和x有f(x), 上述方程的解存在 但我們卻無法得出解的任何解析表達(dá)式 因此求最優(yōu)化問題的解, 一般用迭代的方法, 其基本思想為, 給定最優(yōu)解的一個初始估計, 記為x(0),方法產(chǎn)生一個逐步改善的有限或無限的迭代序列x(k) 在x(k)是有限點(diǎn)列時,它的最后一個點(diǎn)是Kuhn-T ucker點(diǎn); 在 x( k) 是無限點(diǎn)列時, 其任意一個聚點(diǎn)是Kuhn-Tucker 點(diǎn), 并在對最優(yōu)解的估計滿足指定的精度要求時停止迭代,102,根據(jù)最優(yōu)性的一階必要條件, 最優(yōu)解一定是Ku

36、hn-Tucker點(diǎn) 因此理論上由迭代法所確定的解一般是Kuhn-Tucker點(diǎn) 再由方法的其他一些特性, 如下降性可以確保所得的Kuhn-Tucker點(diǎn)是所論問題的最優(yōu)解或最優(yōu)解的近似,103,基本的迭代格式,算法1.4.1 (最優(yōu)化方法的基本迭代格式) 1. 給定最優(yōu)解的一個初始估計x(0), 置k = 0; 2. 如果x(k)滿足對最優(yōu)解估計的終止條件, 停止迭代; 3. 確定一個改善x(k)的修正量(k) ; 4. 得到最優(yōu)解的一個更好的估計x(k+1)=x(k)+(k), 置k= k+1后轉(zhuǎn)步2,104,迭代法涉及問題,基本格式中涉及初始點(diǎn)的選取; 迭代點(diǎn)好壞的判定; 迭代的終止條件

37、; 以及最重要也是最關(guān)鍵的修正量(k)的確定,105,初始點(diǎn)的選取,初始點(diǎn)的選取依賴于方法的收斂性能 一個算法稱為收斂的, 如果算法產(chǎn)生的序列x(k)滿足 其中x*是問題的Kuhn-Tucker點(diǎn),106,全局收斂和局部收斂,一個算法如果對于任意給定的初始點(diǎn)都能夠收斂, 就說這個方法全局收斂或整體收斂 有些算法只有當(dāng)初始點(diǎn)接近或充分接近最優(yōu)解時才有收斂性, 稱這樣的算法為局部收斂的方法 因此對于全局收斂的算法, 初始點(diǎn)的選取可以沒有任何的限制 對于局部收斂的算法, 則要求初始點(diǎn)應(yīng)盡可能接近最優(yōu)解,107,然而由于最優(yōu)解是未知的, 選取一個好的初始點(diǎn)也是一個困難的問題.對于大量實(shí)際的最優(yōu)化問題一般可以從以前的實(shí)踐經(jīng)驗(yàn)確定合適的最優(yōu)解的初始估計,1