最優化理論與方法 習題答案匯 金海燕 第2-8章_第1頁
最優化理論與方法 習題答案匯 金海燕 第2-8章_第2頁
最優化理論與方法 習題答案匯 金海燕 第2-8章_第3頁
最優化理論與方法 習題答案匯 金海燕 第2-8章_第4頁
最優化理論與方法 習題答案匯 金海燕 第2-8章_第5頁
已閱讀5頁,還剩60頁未讀 繼續免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

2.1證:矩陣的秩(rank)是指矩陣中線性獨立行或列的最大數量,由題知矩陣??的秩是??,這意味著存在m個線性獨立的行(或列),這??個線性獨立的行(或列)不能被A中的其他行(或列)通過線性組合來表示,由于??是一個m×n矩陣,它最多有n列.由于??至少有m個線性獨立的列,并且它最多有n列,這意味著??個線性獨立的列必須全部存在,因此m必須小于或等于n.2.2證:方程組Ax=b有唯一解意味著對于給定的m×n矩陣A和向量b,存在一個唯一的向量x使得方程成立.如果A的秩rank(A)等于n,這意味著A的所有列向量都是線性獨立的,因此A是滿秩的.進一步,如果增廣矩陣[A∣b]的秩rank[??∣??]也等于??,這表明向量b可以由A的列向量唯一地線性組合表示,即b屬于A的列空間.由于A的列向量構成了Rn的一組基,這意味著存在唯一的線性組合系數x使得Ax=b成立.如果存在兩個不同的解x1?和x2?,它們都滿足Ax=b,那么A(x1?x2??)=0,但由于A的列向量是線性獨立的,唯一滿足這個方程的是x1?x2=0?,即x1=x2?.這證明了方程組Ax=2.3證:根據線性代數的知識,我們知道在??維空間Rn中,最多只能有n個線性無關的向量.如果有超過n個向量,它們必然是線性相關的.這意味著至少存在一組非全零的標量α1,α2…,αk?,現在,假設我們有k≥n+2個向量a1,a2…,ak.由于k≥n+1,根據題目給定的條件,這些向量一定是線性相關的.我們可以找到一組標量α1,α2…,αk,使得i=1kαiai=0,并且至少有一個αi≠0.為了滿足i=1kαi=0,我們可以進行如下操作:首先,選擇一個非零的標量αj,然后調整其他標量,使得αj?的值減去其他所有標量的和等于0.具體來說,我們可以設置αj=1,然后將α2.4證:(1)為了簡化計算,先對矩陣M進行行變換,即交換第i行和第i+(m?k)行(對于i=1,2,…,k),這樣可以將Mk,k塊移動到矩陣的左上角,同時Im?k?∣detM∣=|detMk,k根據分塊矩陣的行列式性質,當分塊矩陣的右上角是零矩陣時,其行列式等于主對角線子矩陣的行列式乘積;當分塊矩陣的右下角是單位矩陣時,其行列式等于左上角的子矩陣的行列式.因此:|detMk,kOk,m?kMm?k,kIm?k綜上,我們證明了∣detM∣=∣detMk,k∣(2)由(1)知∣detM∣=∣detMk,k∣.為了使得

detM=det(?Mk,k)

成立,我們需要考慮特別地,當Mk,k

是奇異矩陣(即

detMk,k=0)時,無論Mk,k的符號如何變化,其行列式都是0.因此,在這種情況下,detM=det(?當Mk,k是非奇異矩陣(即

detMk,k≠0)時,detM

det(?Mk,k)

的符號是不同的(因為

det(?Mk,k?)=?detMk,k).此時,detM=det(?2.5證:(1)對集合S中任意兩點,及每個數,有由題設,有因此,,故S是凸集。(2)對集合S中任意兩點,及每個數,有由題設,有因此,,故S是凸集。(3)對集合S中任意兩點,及每個數,有由題設,有因此,,故S是凸集。2.6證:對任意兩點及每個數,根據集合S的定義,存在,使,由于C是凸集,必有,因此,,故S是凸集。2.7證:對任意兩點及每個數,存在,使,因此有,,而,故,即S是凸集。2.8證:用數學歸納法。當時,由凸集的定義知上式顯然成立。設時結論成立,當時,有由于時結論也成立。從而得證。2.9設A是m×n矩陣,B是l×n矩陣,,證明下列兩個系統恰有一個有解:系統1Ax≤系統2AT證由于Bx=Bx≤0因此系統1有解,即AB?根據Farkas定理,得(ATBT無解.記u無解.反之亦然。2.10設A是m×n矩陣,c∈Rn,則下列兩個系統恰有一個有解:系統1Ax系統2A證若系統1有解,即A有解,則根據Farkas定理,有A無解,即AA無解.反之,若ATy≥c,y≥0有解,即A有解,亦即A有解.根據Farkas定理,有A無解,即Ax無解.2.11證明Ax≤,.證根據Farkas定理,只需證明ATy無解,事實上,AT1對此線性方程組的增廣矩陣做初等行變換:1此線性方程組ATy=c的系數矩陣與增廣矩陣的秩不等,因此無解,即ATy2.12證明下列不等式組無解:證將不等式組寫作Ax<0根據Gordan定理,只需證明ATy=1ATy12.13判別下列函數是否為凸函數:(1)(2)(3)(4)(5)解:(1)為半正定矩陣,故是凸函數。為不定矩陣,故不是凸函數。因此Hesse矩陣為半正定矩陣,因此是凸函數。(4)于是Hesse矩陣為不定矩陣,故不是凸函數。(5)的Hesse矩陣為做合同變換:由此可得為不定矩陣,因此不是凸函數。2.14設,,是否為S上的凸函數?解:函數的Hesse矩陣為易知在集合S上不是半正定矩陣,如在點(0,1)處的Hesse矩陣是,是不定矩陣。因此不是S上的凸函數。2.15證明為嚴格凸函數的充要條件是Hesse矩陣A正定。證先證必要性。設是嚴格凸函數。根據定理1.4.14,對任意非零向量x及=0,必有(1)將在=0處展開,有(2)有(1)式和(2)式知由于式二次凸函數,因此即A正定。再證充分性。設A正定,對任意兩個不同點x和=0,根據中值定理,有根據定理1.4.14,是嚴格凸函數。2.16設f是定義在Rn上的函數,如果對每一點x∈Rn及正數t均有f(tx)=tf(x),則稱f為正齊次函數。證明Rn上的正齊次函數f為凸函數的充要條件是,對任何x(1),x(2)∈Rn,有證先證必要性。設正齊次函數是凸函數,則對任意兩點必有由于是正齊次函數,有代入前式得,即.再證充分性.設正齊次函數對任意的x(1),x(2)∈Rn滿足,則對任意的x(1),x(2)∈Rn及每個數λ∈0fλ因此是Rn上的凸函數。2.17證:假設有一個矩陣A,它的范數||A||<1,若把矩陣A乘以自己k次,得到的新矩陣Ak的范數不會超過??的范數的k次方,即||A||k≤||A||k.因為||A||<1,我們可以把||A||k想象成1元的k次方,這就像是一個不斷縮小的數列.這個數列的和是有限的.隨著k變得越來越大,||A||k會越來越小,最終趨近于0.這是因為每次k增加,||A||k2.18證:對于矩陣A,特征值λ滿足Ax=λx,其中x是非零向量.對于任意非零向量x,我們有:||Ax||≤||A||如果Ax=λx,那么:||λ||?||x||=||Ax||≤||A|||λ|≤||A||由于這個不等式對任意非零向量x都成立,特別是對于對應于最大特征值的單位特征向量,有:max1≤i≤n∣λi?(A)∣≤2.19解:(1)梯度是一個向量,其分量是函數對每個變量的偏導數.將函數??(x)展開得到:??(x)=(a1?x1?+a2?x2?+…+anxn))?(b1x1?+b2x2?+…+bnxn??).對于即梯度向量???(??)的第i個分量是ai(bT??)+bi(a(2)Hessian矩陣的每個元素fij是??(x)中元素的二階偏導數.由題知??(x)是兩個線性項的乘積,它的Hessian矩陣將會是一個對角矩陣,因為只有xi和對于??(x),Hessian矩陣??(x)由下式給出:對于對角線上的元素fii,我們有:fii=?2f?xi2=2(aTb),對于非對角線上的元素fij因此,Hessian矩陣??(x)可以表示為:??(x)=2(aTb)I,2.20解:已知??(t)=??(g(t)),根據鏈式法則有:df(t)dt=???(g(t)由g(t)=[3t+5,2t?6]T可得:dg(t)dt=[d(3t+5)dt,d(2t?6)dt]=[3,2],由??(x)=x126+x224得:???因此,df2.21解:要在同一張圖上繪制兩個函數的水平集,我們需要分別解出??1(x1,x2)=12和??2(x??1(x1,x2已知??1(x1,x2)=x12-x22??2(x1,x2)已知:??2(x1,x2)=2x1x2=16,可知:x1在一張平面坐標系中,我們可以繪制這些水平集.對于??1?,我們將x2作為參數,分別計算x1的正負平方根,得到兩個拋物線.對于??2?,我們同樣將x2?要尋找fx=[從第二個開始解得:x1=8x2,將x1代入第一個方程,有:8x22-x22=12,即:64x22-x22=12,x24+12故滿足題意的點[x1?,x2]T是:圖像如下:(橫坐標是x2,縱坐標是x12.22泰勒級數是函數在某一點的無窮級數展開,它可以用函數在該點的導數來表示.給定函數??(x)和展開點x0(1)已知函數??(??)=x1e?x2+x22+1,展開點x0=[1?,0]T,首先計算??(??)在x0處的值,即0階導數??(x0):??接下來,我們計算1階導數??′(??),由于??(??)是兩個變量x1和x2的函數,我們需要分別對x1和x2求偏導,求導可得:?f?x1=e?x2,計算2階導數??′′(??),?2f?x12=0,?2f?x22=x1e?x2+2,?2現在,我們可以寫出??(x)在x0處的泰勒級數展開式,忽略三次及更高階項??(x)=2+[1,-1]?[x1?1?,x2]T+12[x1?1?,x2]?0?1?13?(2)已知函數??(??)=x14+2x12x22+x24,展開點x0=[1?,1]T,首先計算??(??)在接下來,我們計算1階導數??′(??),由于??(x)是兩個變量x1和x2的函數,我們需要分別對x1和x2求偏導:?f?x1=4x13+4x1計算2階導數??′′(??),?2f?x12=12x1+4x22,?2f?x22=4x現在,我們可以寫出??(x)在x0??(x)=4+[8,8]?[x1?1?,x2?1]T+12[x1?1(3)已知函數??(??)=ex1?x2+ex1+x2+x1+x2+1,展開點x0=[1?,0接下來,我們計算1階導數??′(??),由于??(x)是兩個變量x1和x2的函數,我們需要分別對x1和x2求偏導:?f?x1=ex1?x計算2階導數??′′(??),?2f?x12=ex1?x2+ex1+x2,?2現在,我們可以寫出??(x)在x0??(x)=2e+2+[2e+1,1]?[x1?1?,x2]3.1用圖解法解下列線性規劃問題:解:以上各題的可行域均為多邊形界定的平面區域,對極小化問題沿負梯度方向移動目標函數的等值線,對極大化問題沿梯度方向移動目標函數的等值線,即可達到最優解,當最優解存在時,下面只給出答案。最優解最優值.最優解最優值實際上,本題最優解并不惟一,連結與的線段上的點均為最優解.可行域是空集,不存在極小點.最優解最優值3.2下列問題都存在最優解,試通過求基本可行解來確定各問題的最優解:解(1)約束系數矩陣和約束右端向量分別為目標系數向量相應的基本可行解及目標函數值分別為相應的基本可行解及目標函數值分別為基本可行解及相應的目標函數值分別為相應的基本可行解及目標函數值分別為綜上,得最優解約束系數矩陣和約束右端向量分別為目標系數向量相應的基本可行解及目標函數值分別為相應的基本可行解及目標函數值分別為相應的基本可行解及相應的目標函數值分別為相應的基本可行解及目標函數值分別為綜上,得最優解引進松弛變量化為標準形式:記作得到相應的基本可行解及目標函數值分別為得到相應的基本可行解及目標函數值分別為得到相應的基本可行解及目標函數值分別為得到相應的基本可行解及目標函數值分別為得到相應的基本可行解及目標函數值分別為得到相應的基本可行解及目標函數值分別為綜上,得最優解3.3設是的一個解,其中是矩陣,的秩為.證明是基本解的充要條件為的非零分量,對應的列線性無關。證先證必要性.設是基本解,記,則非零向量對應的列.由于線性無關,因此線性無關.再證充分性.設的非零分量對應的列線性無關.由于A的秩為,因此可擴充成一組基記于是可記作:,即是基本解.3.4已知LP問題如下:討論的值如何變化,該LP可行域的每個極點依次使目標函數達到最優?解:分析:目標函數等值線方程取不同得到不同的等值線。等值線和法向量目標函數的梯度,指向目標函數增大的方向。沿方向移動的等值線,目標函數增大,沿方向移動的等值線,目標函數減少。1.當(第一象限) 最優解 E點 最優解 DE邊界 最優解 D點 最優解 CD邊界 最優解 C點當時(第二象限)同理,根據法向量方向,最優解B點。當時(第三象限)最優解A點當時(第四象限)最優解E點用單純形方法解下列線性規劃問題:解:(1)用單純形方法求解過程如下:11080230190916000102001305000114102400最優解,最優值引入松弛變量,化為標準形式:用單純形方法求解過程如下:331003001016200112310000010181004010140400010310070011000最優解,最優值3-121007-2001012-438001101-3-100000210101000300110-10090011000301000010001000100011010044-1120106-112300112-3521000011101004502211010-201-1018-80-31-500-2011101004001010000求解下列線性規劃問題:解:(1)引入松弛變量,化為標準形式:用兩階段法求解,為此引入人工變量,解下列線性規劃:2410004112010051001121000100310130011000000000得到原線性規劃的一個基本可行解由此出發求最優解,過程如下:003103001100000003101300103120020-1000-10最優解,最優值(2)引入松弛變量,化為標準形式:用兩階段法求解,為此引入人工變量,解下列線性規劃:2110005310-110311000128420-100501/2-3/2100-1/24000-11-1111/41/40001/41/20200-10-2100-3/211/41/4-3/415/40100-1/2-1/21/21/2101/401/81/81/83/800000-1-10得到原線性規劃的一個基本可行解由此出發求最優解,過程如下:00-3/211/415/40100-1/21/21001/83/8001/40-11/8-1/86001160100-1/21/240101/23/2-1000-3/2-1/2最優解,最優值2-3100120-1182M-13M-10-M08M+1401-11910004.3解:證明用單純形方法求解線性規劃問題時,在主元消去前后對應同一變量的判別數有下列關系:習題1.寫出下列原問題的對偶問題解:(1)對偶問題如下:(2)對偶問題如下:2.解:(1)對偶問題如下:對偶問題的可行域是直線上的一段線,容易在坐標平面上畫出,這里從略。對偶問題優先解,最優值為-55.由于對偶問題的最優解中,,因此在原問題最優解處,有由于對偶問題在點(3,7)處第3、4個約束是松約束,因此原問題中,.代入方程組,得到原問題的最優解為最優值為-55.3.解:(1)將所求問題化為標準形式:用單純形方法求解:111106-1230191-1200001310300-61000100最優解,.(2)目標函數攝動后,問題改變為判別數行改變為,其中A是約束矩陣,按此式修改原來的最優表,得到表一:表11106001900令解得.當時,最優解為,最優解.當時,表1不再是最優表,進基,得到表2:表201310300當時,最優解,最優值.當時,進基,得到表3:表3111106-130119000當時,最優解,最優解.當時,表1不再是最優表,進基,修改表1,得到表4:表4111106034011500令當時,最優解,最優值.第6章習題6.1判斷下列函數是否在搜索區間為單峰函數?(1),;(2),;(3),(4),解:根據畫圖可知,(1)是;(2)是;(3)是;(4)是6.2用0.618法求解下列問題:要求精度,初始區間為。解:根據0.618試探法步驟,以此類推,得到函數迭代結果如表6.1所示。表6.11-22-0.47200.47201.04961.04962-20.4720-1.0557-0.47202.24211.04963-1.05570.4720-0.4720-0.11161.04961.00024-0.47200.4720-0.11160.11141.00021.00025-0.11160.47200.11140.24911.00021.00386-0.11160.24900.02620.11141.00001.00027-0.11160.1114-0.02640.02621.00001.00008-0.02640.11140.02620.05881.00001.00009-0.02640.05880.00610.02621.00001.00010-0.02640.0262-0.00630.00611.00001.000011-0.00630.02620.00610.01381.00001.00012-0.00630.01380.00140.00611.00001.000013-0.00630.0061-0.00160.00141.00001.000014-0.00160.0061 根據上表,經過13次迭代,最終得到: 極小點,通過問題的最優解可采用: 作為近似解。6.3用Fibonacci法求解下列問題:要求精度,初始區間為。計算Fibonacci法需要迭代的次數;解:,因此,需要迭代12次計算上述優化問題的最優解;解:根據Fibonacci試探法步驟,,以此類推,得到函數迭代結果如下表6.2:表6.21-11-0.23610.23610.04570.07202-10.2361-0.5279-0.23610.20920.04573-0.52790.2361-0.2361-0.05570.04570.00294-0.23610.2361-0.05570.05570.00290.00335-0.23610.0057-0.1247-0.05570.01380.00296-0.12470.0557-0.0557-0.01330.00290.00027-0.05570.0557-0.01330.01330.00020.00028-0.05570.0133-0.0292-0.01330.00080.00029-0.02920.0133-0.0133-0.00270.00020.000010-0.01330.0133-0.00270.00260.00000.000011-0.00270.01330.00260.00790.00000.000012-0.00270.00260.00260.00360.00000.0000 根據上表,經過12次迭代,最終得到: 極小點,通過問題的最優解可采用: 作為近似解。6.4求解下列問題:要求精度,初始區間為。(1)利用0.618法和Fibonacci法分別求解上述函數的最優解,并對比兩種方法求得最優解的精度誤差;解:根據0.618試探法步驟,以此類推,得到函數迭代結果如下表6.2:表6.21-21-0.8540-0.14601.71311.74722-2-0.1460-1.2918-0.85403.86001.71313-1.2918-0.1460-0.8540-0.58371.71311.42734-0.8540-0.1460-0.5837-0.41651.42731.46495-0.8540-0.4165-0.6869-0.58371.47571.42376-0.6869-0.4165-0.5837-0.51971.42731.42667-0.5873-0.4165-0.5197-0.48031.42661.43598-0.5873-0.4803-0.5442-0.51971.42451.42669-0.5873-0.5197-0.5593-0.54421.42461.424510-0.5593-0.5197-0.5442-0.53481.42451.424911-0.5593-0.5438-0.5499-0.54421.42441.424512-0.5593-0.5442-0.5535-0.54991.42441.424413-0.5535-0.5442 根據上表,經過12次迭代,最終得到: 極小點,通過問題的最優解可采用: 作為近似解。根據Fibonacci試探法確定迭代次數,因此,需要迭代13次得到函數迭代結果如下表6.3,表6.31-21-0.8541-0.14591.71341.74742-2-0.1459-1.2918-0.85413.86021.71343-1.2918-0.1459-0.8541-0.58361.71341.42724-0.8541-0.1459-0.5836-0.41641.42721.46495-0.8541-0.4164-0.6869-0.58361.47581.42726-0.6869-0.4164-0.5836-0.51971.42721.42667-0.5836-0.4164-0.5197-0.48031.42661.43598-0.5836-0.4803-0.5443-0.51971.42451.42669-0.5836-0.5197-0.5590-0.54431.42461.424510-0.5590-0.5197-0.5443-0.53441.42451.425011-0.5590-0.5344-0.5492-0.54431.42441.424512-0.5590-0.5443-0.5541-0.54921.42441.424413-0.5541-0.5443-0.5541-0.54411.42441.4245 根據上表,經過13次迭代,最終得到: 極小點,通過問題的最優解可采用: 作為近似解。(2)編寫matlab程序求解上述問題;0.618試探法代碼:a=-2;b=1;k=1;while(b-a>0.01)if(k==1)x1=a+0.382*(b-a);x2=a+0.618*(b-a);endf1=exp(2*x1)+(x1)^4+1;f2=exp(2*x2)+(x2)^4+1;if(f1>f2)a=x1;x1=x2;x2=a+0.618*(b-a);elseb=x2;x2=x1;x1=a+0.382*(b-a);endk=k+1;endFibonacci法代碼:a=-2;b=1;F=[1,1,2,3,5,8,13,21,34,55,89,144,233,377];n=13;sigma=0.05;fork=1:n-1if(k==1)x1=a+(F(n-k-1+1)/F(n-k+1+1))*(b-a);x2=a+(F(n-k+1)/F(n-k+1+1))*(b-a);endf1=exp(2*x1)+(x1)^4+1;f2=exp(2*x2)+(x2)^4+1;if(f1>f2)a=x1;x1=x2;x2=a+(F(n-k+1)/F(n-k+1+1))*(b-a);elseb=x2;x2=x1;x1=a+(F(n-k-1+1)/F(n-k+1+1))*(b-a);endendx1=x1;x2=x1+sigma;f1=exp(x1)+2*x1^2;f2=exp(x2)+2*x2^2;if(f1>f2)a=x1;elseb=x1;end(3)對比0.618法和Fibonacci法的計算量;·答:0.618法和Fibonacci法每次迭代計算量一致,而Fibonacci法要比0.618法多迭代一次,因此計算量Fibonacci法要大7.1求下列函數在各點的最速下降方向:(1),,解:,,(2),,解:,,(3),,解:,,(4),,解:,,7.2求下述函數:在點處的牛頓方向,并求解最優解。解:,第一次迭代,,第二次迭代,,第三次迭代,,第四次迭代,,第五次迭代,因此,最優解為。7.3利用最速下降法求解下述問題:在初始點為,迭代次數為2次的最優

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論