優(yōu)化設(shè)計理論基礎(chǔ)和存在條件

1、2022/8/11優(yōu)化設(shè)計理論基礎(chǔ)和存在條件 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/12f(X(1)=a2f(X)=a1f(X)=a2f(X)=a3f(X)=a4f(X(2)=a2X(2)=x1(2), x2(2)X(1)=x1(1), x2(1)Of(X)x2x1X*優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/13二維無約束最優(yōu)化設(shè)計問題幾何意義f(X(1)=a2f(X)=a1f(X)=a2f(X)=a3f(X)=a4f(X(2)=a2X(2)=x1(2), x2(2)X(1)=x1(1), x2(1)Of(X)x2x1X*優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/14x1x2f(x)f(x)

2、g(x)g1(x)g2(x)O優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/15x2x1X*1g4(X)g3(X)g1(X)g1(X)X*20.25f(X)=12.253.846.25f(X)=912123O優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/16二維目標(biāo)函數(shù)等值線形態(tài)分析X 1*x1x201123X 2*X 3*x1x2012323456X 1*優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/173-2 約束最優(yōu)解和無約束最優(yōu)解 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/18二維優(yōu)化問題進行幾何描述例 對二維優(yōu)化問題進行幾何描述。約束線、可行域、目標(biāo)函數(shù)等值線、約束極值點213x221-1-2-3-1-

3、2-4-5x1f(X)X*g1(X)g2(X)0優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/19幾何意義上來說明約束最優(yōu)解和無約束最優(yōu)解設(shè)已知目標(biāo)函數(shù)f(X)=x12+x22-4x1+4，受約束于g1(X)=x1-x2+20 g2 (X)=x1 0 g3 (X) =x2 0 g4 (X)=-x12+x2-1 0 求其最優(yōu)解X*和f(X*)。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/110 x1x2x2x1f(X)f(X)g1(X)g4(X)Og2(X)g4(X)g1(X)g3(X)f(X)等值線6.2543.810.251234O-212X*(1)X*(2)(b)(a)D優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2

4、022/8/1113-3 局部最優(yōu)解和全域最優(yōu)解 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/112X2*X1*f(X)x2x1優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1133-4 無約束目標(biāo)函數(shù)的極值點存在條件 一、函數(shù)的極值與極值點以一元函數(shù)為例說明函數(shù)的極值與極值點。如圖所示為定義在區(qū)間 a，b上的一元函數(shù)f(X)優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/114f(x)xf(a)f(x(1)f(x(2)x(1)f(x(3)f(b)x(3)x(2)ab優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/115 圖上有兩個特殊點x(1)與x(2) 在x(1)附近，函數(shù)f(x)的值以f(x(1)為最大；在x(2

5、)附近，函數(shù)值以f(x(2)為最小。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/116因此x(1)與x(2)即為函數(shù)的極大點與極小點，統(tǒng)稱為函數(shù)f(x)的極值點。f(x(1)與f(x(2)相應(yīng)地為函數(shù)的極大值與極小值，統(tǒng)稱為函數(shù)f(x)的極值。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/117需要注意，這里所謂極值是相對于點的附近鄰域各點而言的，僅具有局部的性質(zhì)，所以這種極值又稱為局部極值。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/118函數(shù)的最大值與最小值是指整個區(qū)間而言的。如圖中函數(shù)的最大值為f(b) ，函數(shù)的最小值為f(a) 。函數(shù)的極值并不一定是最大值或最小值。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022

6、/8/119二、極值點存在的條件 (一)一元函數(shù)(即單變量函數(shù))的情況 (1) 極值點存在的必要條件優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/120在高等數(shù)學(xué)中已經(jīng)學(xué)過：如果函數(shù)f(x)的一階導(dǎo)數(shù)f(x)存在，則欲使x*為極值點的必要條件為：f(x*) 0優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/121仍以圖中所示一元函數(shù)為例，由圖可見，在x(1)與x(2)處的f(x(1)與f(x(2)均等于零，即函數(shù)在該兩點處的切線與x軸平行。但使f(x) 0的點并不一定都是極值點。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/122f(x)xf(a)f(x(1)f(x(2)x(1)f(x(3)f(b)x(3)x(

7、2)ab優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/123使函數(shù)f(x)的一階導(dǎo)數(shù)f(x)0的點稱為函數(shù)的駐點。極值點(對存在導(dǎo)數(shù)的函數(shù))必為駐點駐點不一定是極值點駐點是否為極值點可以通過二階導(dǎo)數(shù)f(x)來判斷。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/124 (2)極值點存在的充分條件 若在駐點附近 f(x)0則該點為極大點； 若在駐點附近 f(x)0則該點為極小點。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/125在圖中的x(3)附近，其右側(cè)f(x)0，但其左側(cè)f(x)0，因此它不是極值點?？梢姡瘮?shù)二階導(dǎo)數(shù)的符號成為判斷極值點的充分條件。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件函數(shù)的偏導(dǎo)數(shù)偏導(dǎo)數(shù)是指在某坐標(biāo)軸

8、方向函數(shù)值的變化率連續(xù)可微的 n 維函數(shù) f(X)=f(x1, x2, xn)，在點 X(K)=x1(K), x2(K), xn(K)T的一階偏導(dǎo)數(shù)表示為 ， ， 三、多元函數(shù)的方向?qū)?shù)、梯度和赫賽矩陣優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/127函數(shù)的梯度 n維函數(shù)的梯度是函數(shù)各維一階偏導(dǎo)數(shù)組成的向量優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/128梯度的模是函數(shù)各維一階偏導(dǎo)數(shù)平方和的開方梯度與它的模的比值稱為梯度的單位向量優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/129函數(shù)梯度的性質(zhì)1、函數(shù)的梯度f(X(K)是函數(shù)在點X(K)的最速上升方向，而負梯度-f(X(K)是函數(shù)在點X(K)的最快下降方向

9、。 函數(shù)的梯度隨著點 X(K)在設(shè)計空間的位置不同而異，這只是反映了函數(shù)在點X(K) 鄰域內(nèi)函數(shù)的局部性質(zhì)。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1302、函數(shù)梯度的模 是在點X(K)函數(shù)變化率的最大值。 3、函數(shù)的梯度f(X(K)與在點X(K)的函數(shù)等值面正交。與點X(K)的函數(shù)等值面相切方向的函數(shù)變化率為零。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/131X(K)x1x2O上升方向變化率為零的方向（切線方向）下降方向最速下降方向最速上升方向（法線方向）f (X(K)f (X(K)優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/132注意，函數(shù)f(X)在某點X(K)的梯度向量f(X(K)僅反映f(

10、X)在點X(K)附近極小鄰域的性質(zhì)因而是一種局部性質(zhì)。函數(shù)在定義域內(nèi)的各點都各自對應(yīng)著一個確定的梯度 。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/133函數(shù)的赫森矩陣 函數(shù)的二階偏導(dǎo)數(shù)矩陣它是一個nn階的對稱矩陣優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/134赫森矩陣正定和負定的判定如果赫森矩陣行列式各階主子式全部大于零，即優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/135則它是正定的。如果各階主子式是相間的一負一正，則它是負定的。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/136設(shè)f(x)為定義在XDRn中的n元函數(shù)。向量X的分量x1, x2, xn，就是函數(shù)的自變量。設(shè)x(k)為定義域內(nèi)的個點，且在該

11、點有連續(xù)的n1階偏導(dǎo)數(shù)，則在該點附近可用泰勒級數(shù)展開，如取到二次項 多元函數(shù)的極值條件優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/137如用向量矩陣形式表示，則上式可寫為 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/138優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/139可簡寫為 式中 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/140f(X(k)是函數(shù)f(X)在點X(k)的一階偏導(dǎo)數(shù)矩陣，稱為函數(shù)在該點的梯度。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1412f(X(k)是函數(shù)f(X)在點X(k)的二階偏導(dǎo)數(shù)組成的，nn階對稱矩陣，或稱為f(X(k)的赫森(Hessian)矩陣，記作H(X(k) 。 優(yōu)化設(shè)計

12、理論基礎(chǔ)和存在條件2022/8/142公式中只取到泰勒級數(shù)二次項，稱為函數(shù)的二次近似表達式。極值點存在的必要條件。n元函數(shù)在定義域內(nèi)極值點X*存在的必要條件 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/143即對每一個變量的一階偏導(dǎo)數(shù)值必須為零，或者說梯度為零(n維零向量)。與一元函數(shù)對應(yīng)，滿足梯度為零只是多元函數(shù)極值點存在的必要條件，而并非充分條件；優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/144滿足f(X*)的點X*稱為駐點駐點是否為極值點，尚須通過二階偏導(dǎo)數(shù)矩陣來判斷。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/145極值點存在充分條件 如何判斷多元函數(shù)的一個駐點是否為極值點呢? 將多元函數(shù)f(X

13、)在駐點X*附近用泰勒公式的二次式近似地表示，則由式得 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/146由X*為駐點，f(X*)=0，于是有在X*點附近的鄰域內(nèi)，若對一切的X恒有 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/147亦即 則X*為極小點 否則，當(dāng)恒有 則X*為極大點 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/148根據(jù)矩陣?yán)碚撝?，由式得極小點的充分條件為： 亦即駐點赫森矩陣H(X*)必須為正定 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/149同理知極大點的充分條件為： 亦即駐點赫森矩陣H(X*)必須為負定。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/150而當(dāng) 亦即駐點赫森矩陣H(X*)既非正

14、定，又非負定，而是不定， f(X)在X*處無極值。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/151至于對稱矩陣正定、負定的檢驗，由線性代數(shù)可知：對稱矩陣 正定的條件是它的行列式|A|的順序主子式全部大于零，即優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/152 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/153負定的條件是它的行列式|A|中一串主子式為相間的一負一正的，即 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/154 至此，完全不難自行歸納得出無約束目標(biāo)函數(shù)極值點存在的充分必要條件和用數(shù)學(xué)分析作為工具對n維無約束優(yōu)化問題尋求最優(yōu)解。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/155無約束目標(biāo)函數(shù)的極值條

15、件 必要條件：在點X*=x1*, x2*, xn*T的一階偏導(dǎo)數(shù)為零（即梯度向量為零向量） 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/156充分條件：如果它的二階偏導(dǎo)數(shù)矩陣（即赫森矩陣）是負定的，則為極大點；如果它的二階偏導(dǎo)數(shù)矩陣是正定的，則為極小點。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/157求三維函數(shù)的極值點。 解：根據(jù)三維函數(shù)存在極值的必要條件，令梯度為零 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/158聯(lián)解得到優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/159計算點 的赫森矩陣 赫森矩陣行列式各階主子式 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/160優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1

16、61赫森矩陣是正定的， 是極小點。對應(yīng)的目標(biāo)函數(shù)值優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1623-5 函數(shù)的凸性 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/163x1x2x1x2OODX(2)X(1)X(2)X(1)D(a)(b)一、凸集與非凸集 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/164設(shè)D為n維歐氏空間中設(shè)計點X的一個集合，若其中任意兩點x(1)和x(2)的連線都在集合中，則稱這種集合是n維歐氏空間的一個凸集。二維函數(shù)的情況如圖所示，其中圖(a)為凸集，圖(b)為非凸集凸集的概念優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/165凸集非凸集凸集優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/166凸

17、函數(shù)的概念xx(2)x*x(1)Of(x)f(x(1)f(x*)f(x(2)xf(x)x(2)x*x(1)Of(x(1)f(x(2)f(x*)(a)(b)優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/167用一元函數(shù)來說明函數(shù)的凸性。如圖所示，圖(a)在x(1)、x(2)區(qū)間曲線為下凸的，圖(b)的曲線是上凸的，它們的極值點(極小點或極大點)在區(qū)間內(nèi)都是唯一的。這樣的函數(shù)稱為具有凸性的函數(shù)，或稱為單峰函數(shù)。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/168優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/169Of(x)xx(1)x(k)x(2)f(x(1)f(x(2)f x(1)+(1-)x(2)f(x(1)

18、+(1-)f(x(2)優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/170現(xiàn)用上圖所示定義于區(qū)間a,b的單變量函數(shù)來說明這一概念。若連接函數(shù)曲線上任意兩點的直線段，某一點x(k)的函數(shù)值恒低于此直線段上相應(yīng)的縱坐標(biāo)值時，這種函數(shù)就是凸函數(shù)，也就是單峰函數(shù)。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/171 若將式 中的符號“”改為“”則稱函數(shù)f(X)為嚴(yán)格凸函數(shù)。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/172 若將式 中的符號“”改為“”，函數(shù)曲線上凸(有極大點)通常稱為凹函數(shù)。顯然，若為凸函數(shù)，則-f(X)凹函數(shù)。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/173 三、凸函數(shù)的基本性質(zhì) 1） 若函數(shù)f1

19、(X)和f2(X)為凸集上的兩個凸函數(shù)，對任意正數(shù)a和bf(X)af1(X)+bf2(X) 仍為D集上的凸函數(shù)； 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1742) 若X(1)與X(2)為凸函數(shù)f(X)中的兩個最小點，則其連線上的一切點也都是f(X)的最小點。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/175四、凸函數(shù)的判定 判別法1： 若函數(shù)f(X)在D上具有連續(xù)一階導(dǎo)數(shù)，而D為D1內(nèi)部的一個凸集，則f(X)為D上的凸函數(shù)的充分必要條件為：對任意的X(1)與X(2) ，恒有 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/176判別法2： 若函數(shù)f(X)在凸集D上存在二階導(dǎo)數(shù)并且連續(xù)時，對f(X)在D

20、上為凸函數(shù)的充分必要條件為： 對于任意的XD， f(X)的赫森矩陣H(X)處處是正半定矩陣。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/177若赫森矩陣H(X)對一切XD都是正定的，則f(X)是D上的嚴(yán)格凸函數(shù)，反之不一定成立。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/178五、函數(shù)的凸性與局部極值及全域最優(yōu)值之間的關(guān)系 設(shè)f(X)為定義在凸集D上的一個函數(shù)，一般來說，f(X)的極值點不一定是它的最優(yōu)點。但是，若f(X)為凸集D上的一個凸函數(shù)，則f(X)的任何極值點，同時也是它的最優(yōu)點。若f(X)還是嚴(yán)格凸函數(shù)，則它有唯一的最優(yōu)點。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/179六 約束極值點存

21、在條件 1 有約束的極值問題 gi(X)0不等式約束， hj(X)=0等式約束優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/180 在約束條件下求得的函數(shù)極值點，稱為約束極值點。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1812 不等式約束問題的一階最優(yōu)性條件 起作用約束不起作用約束 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/182x1x2x2x1f(X)f(X)g1(X)g4(X)Og2(X)g4(X)g1(X)g3(X)f(X)等值線6.2543.810.251234O-212X*(1)X*(2)(b)(a)D優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/183起作用約束下標(biāo)集合用I表示或優(yōu)化設(shè)計理論基

22、礎(chǔ)和存在條件2022/8/184 在優(yōu)化實用計算中常需判斷和檢查某個可行點是否約束極值點，這通常借助于庫恩-塔克(KuhnTucker)條件(簡稱K-T條件)來進行。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/185 K-T條件可闡述為：如果X(k)是一個局部極小點，則該點的目標(biāo)函數(shù)梯度f(X(k)可表示成該點諸約束面梯度gi(X(k)的如下線性組合： gi(iI)在X(k)處可微；gi(iI)在X(k)處連續(xù)；gi(X(k) (iI)線性無關(guān)優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/186gi(iI)在X(k)處也可微，可寫成等價形式 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/187iI時， gi0

23、，wi0iI時， gi=0，對wi無限制wi g(X(k)=0，i=1，2，m稱為互補松弛條件 ；wi 0，i=1，2，m，亦稱拉格朗日乘子。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/188 等式約束性問題的最優(yōu)性條件幾何意義是明顯的：考慮一個約束的情況： 最優(yōu)性條件即：- f(x2*)x2* h (x2*)h(x)-f(x1*)h(x1*)這里 x1* -l.opt. f(x1*)與h(x1*) 共線，而x2*非l.opt.f(x2*) 與h(x2*)不共線。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1893 一般約束問題的一階最優(yōu)性條件 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/190 如果x

24、*是l.opt. ,對每一個約束函數(shù)來說，只有當(dāng)它是起作用約束時，才產(chǎn)生影響，如：g2(x)=0 x*g1(x)=0g1(x*)=0, g1為起作用約束優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/191K-T條件可闡述為：如果X(k)是一個局部極小點，則該點的目標(biāo)函數(shù)梯度f(X(k)可表示成該點諸約束面梯度gi(X(k)的如下線性組合： f、gi(iI)在X(k)處可微gi(iI)在X(k)處連續(xù)hj(X(k) (j=1，2，l)在X(k)處連續(xù)可微優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/192gi(iI)在X(k)處也可微，可寫成等價形式 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/193wi g(

25、X（k）)=0，i=1，2，m仍稱為互補松弛條件 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/194可以對K-T條件用圖形來說明。如果X(k)是一個局部極小點，則該點的目標(biāo)函數(shù)梯度f(X(k)應(yīng)落在該點諸約束面梯度gi(X(k) 、 hj(X(k)在設(shè)計空間所組成的錐角范圍內(nèi)。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/195如圖所示，圖(a)中設(shè)計點X(k)不是約束極值點，圖(b)的設(shè)計點X(k)是約束極值點。 X(k)h(X(k)g2(X(k)f(X(k)g1(X(k)g3(X(k)(a)X(k)g2(X(k)g3(X(k)g1(X(k)h(X(k)f(X(k)(b)優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2

26、022/8/196123412g1=0g2=0g4=0 x1g3=0 x2x*g2(x*)g1(x*)-f(x*)(3,2)T優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/197用K-T條件求解：優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/198優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/199優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1100可能的K-T點出現(xiàn)在下列情況： 兩約束曲線的交點：g1與g2，g1與g3，g1與g4，g2與g3，g2與g4，g3與g4。 目標(biāo)函數(shù)與一條曲線相交的情況： g1，g2， g3，g4 對每一個情況求得滿足K-T條件的點(x1，x2)T及乘子w1，w2，w3，w4，且wi

27、0時，即為一個K-T點。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1101下面舉幾個情況： g1與g2交點：x=(2,1)TS，I=1,2 則w3=w4=0 解優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1102優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1103優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1104優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1105七 最優(yōu)化設(shè)計的數(shù)值計算迭代方法 無約束優(yōu)化問題和約束優(yōu)化問題當(dāng)其數(shù)學(xué)模型確定以后求其最優(yōu)解，實質(zhì)上都屬于目標(biāo)函數(shù)的極值問題。兩者的優(yōu)化求解方法聯(lián)系緊密，其中無約束優(yōu)化方法又是優(yōu)化方法中最基本的方法。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件迭代算法的概念 迭代法

28、是一種重要的逐次逼近的方法。這種方法用某個固定格式反復(fù)計算和校正所求問題的近似解（如方程的根、函數(shù)的極值點等），使之逐次精確化，最后得到滿足精度要求的結(jié)果。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1107求一維方程 在 附近的一個根。 解：可將方程改寫為下列形式 用所給的初始值 近似代入上式的右端得到第一個近似解 由于 和 有較大偏差，再將 作為初始值，并且重復(fù)上面的計算步驟，如此繼續(xù)下去。這種逐步逼近的過程稱作迭代過程。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1108該例求解該一維方程迭代格式是隨著迭代次數(shù)逐漸增大，直至相鄰兩次迭代點 的偏差小于預(yù)先給定的精度值為止。優(yōu)化設(shè)計理論基礎(chǔ)和存

29、在條件2022/8/1109無約束最優(yōu)化算法，每次迭代都按選定方向S和一合適的步長向前搜索，可以寫出迭代過程逐次搜索新點的向量方程式 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1110迭代過程的每一步向量方程式，都可寫成如下的迭代格式 式中： X(k)第k步迭代的出發(fā)點； X(k+1)第k步迭代產(chǎn)生出的新點； S(k)是向量，代表第k步迭代的前進方向(或稱搜索方向)；優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1111 (k) 是標(biāo)量，代表第k步沿S(k)方向的迭代步長(或稱步長因子)。 在一系列的迭代計算k=1,2,過程中，產(chǎn)生一系列的迭代點(點列) X(0)， X(1)， ，X(k)， X(k+

30、1) 。為實現(xiàn)極小化，目標(biāo)函數(shù)的值應(yīng)一次比一次減小，即優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1112f(X(0)f(X(1) f(X(k) f(X(k1) 直至迭代計算滿足一定的精度時，則認(rèn)為目標(biāo)函數(shù)值近似收斂于其理論極小值。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1113優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1114優(yōu)化迭代算法的分類 搜索算法是一種迭代算法，搜索方向和步長因子構(gòu)成了每一次迭代的修正量，表明它們是決定算法好壞的重要因素。 在搜索方向上，使目標(biāo)函數(shù)取得極小值的步長因子，稱為該方向上最優(yōu)步長因子。在優(yōu)化設(shè)計中，求解最優(yōu)步長因子主要采用數(shù)值解法，即利用計算機通過反復(fù)的迭代計算

31、，求解出最優(yōu)步長因子的近似值。 目前已有很多優(yōu)化方法，各種方法的區(qū)別就在于確定方向和步長因子的方法不同。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1115 1、直接搜索法 這種方法只需要進行函數(shù)值的計算與比較來確定優(yōu)化的方向和步長。例如一維搜索中的黃金分割法、二次插值法等，在多維問題中的隨機方向法、共軛方向法和復(fù)合形法等。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/11162、間接搜索法 這種方法需要利用函數(shù)的一階或二階偏導(dǎo)數(shù)矩陣來確定優(yōu)化方向和步長，例如梯度法以負梯度矢量方向為搜索方向，就需要計算函數(shù)的一階偏導(dǎo)數(shù)矩陣。牛頓法則同時需要求出目標(biāo)函數(shù)的一階偏導(dǎo)數(shù)矩陣和二階偏導(dǎo)數(shù)矩陣的逆陣才能確定迭代

32、方向和步長。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1117 數(shù)值計算迭代方法：直接從目標(biāo)函數(shù)f(X)出發(fā)，構(gòu)造一種使目標(biāo)函數(shù)值逐次下降逼近，利用計算機進行迭代格式一步步搜索、調(diào)優(yōu)并最后逼近到函數(shù)極值點或達到最優(yōu)點優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1118根據(jù)確定搜索方向和步長的方法不同，數(shù)值計算尋優(yōu)可有許多方法，但其共同點是：1) 要具有簡單的邏輯結(jié)構(gòu)并能進行同一迭代格式的反復(fù)的運算：優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/11192)這種計算方法所取得的結(jié)果不是理論精確解，而是近似解. 其精度是可以根據(jù)需要加以控制的。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1120 一、迭代法的基本

33、思想及其格式迭代法是適應(yīng)于計算機工作特點的一種數(shù)值計算方法。其基本思想是：在設(shè)計空間從一個初始設(shè)計點X(0)開始，應(yīng)用某一規(guī)定的算法，沿某一方向S(0)和步長(0)產(chǎn)生改進設(shè)計的新點X(1) ，使得f(X(1) f(X(0) ，優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1121然后再從點X(1)開始，仍應(yīng)用同一算法，沿某一方向S(1)和步長(1) ，產(chǎn)生又有改進的設(shè)計新點X(2) ，使得f(X(2) f(X(1) ，這樣一步一步地搜索下去。 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1122使目標(biāo)函數(shù)值步步下降，直至得到滿足所規(guī)定精度要求的、逼近理論極小點的X*點為止。這種尋找最優(yōu)點的反復(fù)過程稱為

34、數(shù)值迭代過程。下圖為二維無約束最優(yōu)化迭代過程示意圖優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1123x1x2OX*X(4)X(3)X(2)X(1)X(0)優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1124二、迭代計算的終止準(zhǔn)則 希望迭代過程進行到最終迭代點到達理論極小點或者使最終迭代點與理論極小點之間的距離足夠小到允許的精度才終止迭代。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1125實際上對于一個待求的優(yōu)化問題，其理論極小點并不知道。只能從迭代過程獲得的迭代點序列X(0)， X(1)， ，X(k)， X(k+1) ，所提供的信息優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1126根據(jù)一定的準(zhǔn)則判斷出已

35、取得足夠精確的近似極小點時，迭代即可終止。最后所得的點即認(rèn)為是接近理論極小點的近似極小點。對無約束最優(yōu)化問題常用的迭代過程終止準(zhǔn)則一般有以下幾種。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1127 1) 點距準(zhǔn)則 當(dāng)相鄰兩迭代點 X(k)，X(k+1)之間的距離已達到充分小時，即小于或等于規(guī)定的某一很小正數(shù)時，迭代終止。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1128一般用兩個迭代點向量差的模來表示，即 也可用迭代點在各個坐標(biāo)軸上的分量來表示優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/11292) 函數(shù)下降量準(zhǔn)則 當(dāng)相鄰兩迭代點X(k)， X(k+1)的目標(biāo)函數(shù)值的下降量已達到充分小時，即小于或等于規(guī)定的某一很小正數(shù)時，迭代終止。優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1130一般用目標(biāo)函數(shù)值下降量的絕對值來表示，即當(dāng)|f(X(k)|1 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/1131 或用目標(biāo)函數(shù)值下降量的相對值來表示，即當(dāng)|f(X(k)|1 優(yōu)化設(shè)計理論基礎(chǔ)和存在條件2022/8/11323) 梯度準(zhǔn)則 當(dāng)目標(biāo)函數(shù)在迭代點X(k)的梯度已達到充分小時，即小于或等于規(guī)定的某一很小