第6章

代數方程與最優化問題的計算機求解高等應用數學問題的MATLAB求解清華大學出版社2008CAI課件開發：薛定宇、劉瑩瑩、董雯彬2/1/2023第6章代數方程與最優

化問題的計算機求解代數方程的求解無約束最優化問題求解有約束最優化問題的計算機求解混合整數規劃問題的計算機求解線性矩陣不等式問題求解多目標優化問題求解動態規劃及其在路徑規劃中的應用2/1/20236.1代數方程的求解代數方程的圖解法多項式型方程的準解析解法一般非線性方程數值解非線性矩陣方程求解2/1/20236.1.1代數方程的圖解法一元方程的圖解法二元方程的圖解法2/1/2023

一元方程的圖解法用ezplot()函數可以繪制出給定的隱函數

曲線，所以可以用圖解法從給出的曲線和

線的交點上讀出所有的實數解。2/1/2023例6.1用圖解法求解方程：MATLAB求解命令證明：2/1/2023

二元方程的圖解法使用ezplot()函數將所有的方程都畫出來，得出曲線后就可以通過讀取交點坐標的方式得出聯立方程的根2/1/2023例6.2用圖解法求解聯立方程：畫第一個函數：畫第二個函數：2/1/20236.1.2多項式型方程的準解析解法特殊的高階方程如多項式型方程，可以被求解出Abel-Ruffini定理證明5階以上的多項式型方程沒有解析解一般的數值算法得出的解不精確得出高精度解的方法存在很多方程可以轉換成多項式方程2/1/2023例6.3試用圖解方法求解二元方程MATLAB求解命令：2/1/2023求解多項式型方程的函數調用格式最簡調用方式直接得出根指定變量2/1/2023例6.4使用solve()函數求解MATLAB求解命令：證明：2/1/2023例6.5試求解MATLAB求解命令：證明：2/1/2023最后一個式子改寫成MATLAB求解命令：2/1/2023例6.6試求解MATLAB求解命令：2/1/2023證明：2/1/2023例6.7試求解帶有參數的方程MATLAB求解命令：2/1/20236.1.3一般非線性方程數值解求出已知多元方程的一個實數根的函數調用格式最簡求解語句一般求解語句2/1/2023選擇方法和修改控制精度的函數調用格式獲得默認的常用變量設置控制參數或2/1/2023求解數值代數方程組的步驟設置變量，使等式變成如下所示按如下方式描述等式M-函數匿名函數Inline函數，不推薦使用求解方程組檢驗階的正確性2/1/2023例6.8Lambert函數，是變量，

是方程的解，對不同的，求解

然后繪制

求解策略和過程使用for循環使用匿名函數描述生成w向量繪制函數曲線MATLAB求解語句：2/1/2023MATLAB表述直接求解，使用lambertw函數2/1/2023例6.9數值方法求解選擇變量把原始常微分方程組(ODEs)變為變成矩陣形式2/1/2023描述方程的方法M-函數匿名函數Inline函數2/1/2023當初值選為當使用另一個搜索初始點注意：選擇不同的初值可以得出不同的結果2/1/2023例6.10數值方法解使用solve()函數：使用圖解法求初始值：2/1/2023重新設置相關精度的控制變量所期望的精度可能無法達到然而，在算精度制下的最好結果可以得到2/1/20236.1.4非線性矩陣方程求解Riccati

方程（第4章）更多的非線性矩陣方程，例如，廣義Riccati方程類Riccati方程還有很多很多的矩陣方程2/1/2023函數fsolve()只能求解出，而不是，其中，是向量不是矩陣將矩陣方程轉換成向量方程向量轉換成矩陣

數學表述

MATLAB表述矩陣轉換成向量數學表述MATLAB表述Riccati方程求解2/1/2023以向量的形式描述Riccati方程的殘差求解Riccati方程的新函數2/1/2023例6.11求解下列Riccati方程組：

其中2/1/2023are()

函數可能會得出一個解重新使用MATLAB命令：另一個解：2/1/2023例6.12給定其中求出并檢驗全部的根2/1/2023對于類Riccati方程另一個M-函數另一個矩陣方程求解函數2/1/2023重新使用MATLAB命令注意：有些解可能很難得到，需要反復調用多次上述函數2/1/2023已通過檢驗的可能解

2/1/20236.2無約束最優化問題求解解析解法和圖解法基于MATLAB的數值解法全局最優解與局部最優解利用梯度求解最優化問題帶有變量邊界約束的最優化問題求解2/1/2023無約束最小化問題的數學描述目標函數是一個標量函數向量決定變量，或優化變量物理意義：求取一組

向量，使得最優化目標函數

為最小最大化問題數學描述2/1/20236.2.1解析解法和圖解法無約束最優化問題的必要條件：其中，是最優點方程的求解可能會更難，有時可能需要二階導數運算2/1/2023例6.13研究下式的最優性繪制函數的一階導數2/1/2023求一階導數為零的點，并驗證二階導數為正2/1/20236.2.2基于MATLAB的數值解法得出數值解的函數調用格式最簡求解語句或一般求解格式或2/1/2023描述目標函數M-函數匿名函數Inline函數（不推薦使用）在匿名函數或inline函數中無法使用中間變量2/1/2023例6.14給定

，求其最小值

使用函數fminsearch()：使用函數fminunc()：2/1/2023繪制出搜索過程中間點的軌線：2/1/2023結果：2/1/20236.2.3全局最優解與局部最優解最小值存在的必要條件是使用搜索方法，從初始值出發，可能找到唯一的一個這樣的點，它是全局最小值2/1/2023例6.15給定觀察不同的初值得出的最小值構造目標函數初值是2/1/2023初值是在

內的曲線：在

內的曲線2/1/20236.2.4利用梯度求解最優化問題有時，僅利用目標函數提供的信息，很難得到最優解。這是由于求解最優化問題收斂速度一般較慢，尤其是變量較多的最優化問題可以利用梯度信息解決上述問題2/1/2023例6.16求Rosenbrock

函數的無約束最優化問題繪制三維等高線圖：2/1/2023無梯度信息求梯度矩陣：2/1/2023編寫目標函數：求解最優化問題2/1/20236.2.5帶有變量邊界約

束的最優化問題求解帶有變量邊界約束的最優化問題的數學描述

其中，符號s.t.表示subjecttoJohnD'Errico,woodchips@fminsearchbnd()函數在隨書光盤中給出2/1/2023帶有變量邊界約束的最優化問題求解的語句調用格式最簡求解語句

一般求解格式2/1/2023例6.17求解Rosenbrock問題其中，和

MATLAB求解語句2/1/20236.3有約束最優化

問題的計算機求解約束條件與可行解區域線性規劃問題的計算機求解二次型規劃的求解一般非線性規劃問題的求解2/1/20236.3.1約束條件與可行解區域有約束非線性最優化問題的一般描述為其中，所有的

滿足約束條件該范圍稱為可行解區域2/1/2023例6.18圖解方法求解：目標函數描述可行解區域描述2/1/2023可行區域圖解說明2/1/20236.3.2線性規劃問題的計算機求解線性規劃(LP)問題的一般數學描述為所有都是線性的注意，約束的標準形式2/1/2023求解LP問題的函數調用格式2/1/2023例6.19試求解下面的線性規劃問題2/1/2023MATLAB求解語句：2/1/2023例6.20求解下列LP問題：先將原問題轉換為最小值問題2/1/2023MATLAB求解命令2/1/2023例6.21是求解下列LP問題雙下標描述2/1/2023將原問題轉換成單下標自變量原問題改寫成2/1/2023MATLAB求解命令2/1/20236.3.3二次型規劃的求解一般二次型規劃問題的數學表示為首先建立矩陣表述2/1/2023求解二次型規劃問題的函數調用格式2/1/2023例6.22試求解下面的四元二次型規劃問題首先求出相關矩陣形式2/1/2023展開目標函數得寫成矩陣形式2/1/2023MATLAB求解語句其中，忽略了常數302/1/20236.3.4一般非線性規劃問題的求解一般非線性規劃問題其中，物理解釋：在給出的約束條件下，找出向量，使目標函數達到最小值2/1/2023簡化描述求解出非線性規劃問題2/1/2023例6.23試求解下面非線性規劃問題為目標函數和約束函數編輯M-函數，后者返回兩個變量2/1/2023編輯非線性約束函數編輯目標函數2/1/2023使用函數fmincon()求解2/1/2023簡化非線性約束條件函數：求出結果：2/1/2023例6.24利用梯度信息求解如下問題，并比較結果

2/1/2023推導Jacobian矩陣編寫目標函數2/1/2023使用函數fmincon()得出結果2/1/20236.4混合整數規劃

問題的計算機求解整數線性規劃問題的求解一般非線性整數規劃問題與求解0-1規劃問題求解2/1/20236.4.1整數線性規劃問題的求解整數線性規劃的一般數學描述其中，

為變量

的子集2/1/2023求解整數線性規劃問題的函數調用格式該免費工具箱，可以由MathWorks公司網站下載，也可以由本書光盤得出當前版本的ipslv_mex()函數不能用于低于MATLAB7.*的版本2/1/2023求解下列線性整數規劃問題，其中，各個變量全為整數例6.252/1/2023MATLAB求解命令2/1/2023采用窮舉算法，假定

的各個元素均為202/1/2023得出次最優解混合整數規劃問題，要求

為整數，其他兩個變量為任意數2/1/20236.4.2一般非線性整

數規劃問題與求解分枝定界算法是一種最常用的處理非線性整數規劃或混合規劃問題的算法免費工具箱由

Mr.Keort

Kuipers提供

koertkuipers@該工具箱也附在由隨書光盤上在MATLABR2008a中，薛定宇老師對其進行了簡單的修改2/1/2023函數調用格式向量表示變量必須是整數，當表示變量可以是實數fun變量要是一個被引用的文件名，而不能是@...的形式如果err返回空，則求解成功2/1/2023補丁語句調用前調用后，截斷多余的數字2/1/2023例6.26假定,使用函數bnb20()求解線性整數規劃問題(ILP)編輯目標函數（不要編輯非匿名函數）2/1/2023求解出ILPerrmsg是空，求解成功2/1/2023如果要求

為整數，其他兩個變量為任意數，則2/1/2023窮舉法小結優點保證得出全局最優值除了最優值，還可以得出次最優值對于小規模問題，求解簡便缺點帶來很重的計算負擔和極大的內存使用不可能求解大型甚至中型問題2/1/2023例6.27求出修改的Rosenbrock問題其中，并且是整數目標函數2/1/2023MATLAB求解語句：2/1/2023選擇區間給定區間，使用窮舉法2/1/20236.4.30-1規劃問題求解0-1線性規劃問題MATLAB求解函數0-1非線性規劃問題，使用函數bnb20()將下界定義一個全為0的向量將上界定義一個全為1的向量直接使用函數bnb20()2/1/2023例6.28求解0-1線性規劃問題MATLAB求解語句：2/1/2023枚舉方法2/1/2023例6.29運用函數bnb20()求解下列問題構造目標函數：2/1/2023MATLAB求解語句：2/1/20236.5線性矩陣不等式問題求解線性矩陣不等式的一般描述Lyapunov不等式線性矩陣不等式問題分類線性矩陣不等式問題的MATLAB求解基于YALMIP工具箱的最優化求解方法2/1/20236.5.1線性矩陣不等式的一般描述線性矩陣不等式(LMI)的數學描述其中，為多項式系數向量，又稱為決策向量，為實對稱矩陣或復Hermit矩陣2/1/2023如果LMI矩陣是負定矩陣，那么解是凸集其中，多個線性矩陣不等式可以合并成單一的線性矩陣不等式2/1/20236.5.2Lyapunov不等式Lyapunov不等式的數學描述

其中，

是對稱矩陣2/1/2023構造MATLAB函數求取2/1/2023接上頁函數調用格式：2/1/2023例6.30給定試求出其線性矩陣不等式表示。對于矩陣，寫出相應的線性矩陣不等式MATLAB求解語句：2/1/2023對于X矩陣線性矩陣不等式形式的數學描述2/1/2023對于的符號矩陣結果：2/1/2023給定分塊矩陣其中，

是方陣，那么，下述三種況等價Schur補性質2/1/2023數學描述其中，原非線性不等式可以等價地變換成下述線性矩陣不等式代數Riccati不等式2/1/20236.5.3線性矩陣不等式問題分類可行解問題可行解問題實際上就是求下述的解其中要找到最小值如果找到的

，則得出的解是原問題的可行解，否則會提示無法找到可行解。2/1/2023線性目標函數最優化問題給定這樣的問題可以用普通的線性規劃方法求解2/1/2023廣義特征值最優化問題廣義特征值問題可以視為線性矩陣不等式問題的最一般的問題.表達式由該式演化可以得到更一般的不等式其中，是矩陣的廣義特征值歸納出下面的最優化問題2/1/20236.5.4線性矩陣不等式

問題的MATLAB求解用MATLAB描述線性矩陣不等式創建LMI模型定義需要求解的變量其中，是未知矩陣類型的標記2/1/2023描述分塊形式給出線性矩陣不等式

其中通常，該項是APB如果,那么k=-k如果flag==‘s’,該項是如果該項是常數，那么P=0，并且忽略B完成LMI模型描述2/1/2023求解LMI問題可行解問題線性目標函數問題廣義特征值問題2/1/2023例6.31給定對于Riccati不等式試求出該不等式的一個正定可行解2/1/2023MATLAB求解語句：2/1/20236.5.5基于YALMIP工

具箱的最優化求解方法YALMIP(yetanotherLMIpackage)由瑞典Link?ping

大學電子工程專業的JohanL?fberg博士開發,

johanl@isy.liu.se現在，它以成為最優化問題建模和求解的一種簡便求解方法接近數學形式本書的隨書光盤附帶最新的版本2/1/2023決策變量的聲明對稱矩陣長方形矩陣整數變量二項形式其它形式，例如Hankel矩陣，hankel()2/1/2023約束可以通過[]來聲明最優化問題求解求解可行解問題求解目標函數的最優化問題2/1/2023允許設定選項，如算法選擇提取得出的解矩陣2/1/2023例6.32給定使用YALMIP工具箱求解Riccati不等式2/1/2023MATLAB求解命令比使用魯棒控制工具箱(RCT)更方便2/1/2023例6.33求解線性規劃問題MATLAB求解語句2/1/2023假設決策變量是整數2/1/2023例6.34對于線性系統其中2/1/2023采用LMI方法也可以求解系統的范數，其數學描述為

求解線性系統模型的范數2/1/2023MATLAB求解命令：2/1/20236.6多目標優化問題求解多目標優化模型無約束多目標函數的最小二乘求解多目標問題轉換為單目標問題求解多目標優化問題的Pareto解集極小極大問題求解目標規劃問題求解2/1/20236.6.1多目標優化模型多目標最優化問題的一般表示為其中，2/1/2023例6.35

三種糖果，單價每公斤4，2.8和2.4元，買糖果不超過20元，總量不得少于6公斤，

和

不得少于3公斤，設計方案設

購買量為

公斤，則2/1/20236.6.2無約束多目標

函數的最小二乘求解設目標函數將其轉換成單目標問題MATLAB函數調用格式2/1/2023例6.36求解下面無約束非線性多目標規劃問題的最小二乘解2/1/2023MATLAB求解語句使用函數fmincon()2/1/20236.6.3多目標問題轉

換為單目標問題求解線性加權變換及求解線性規劃問題的最佳妥協解線性規劃問題的最小二乘解2/1/2023

線性加權變換及求解單目標優化算法不能直接由于求解多目標優化問題，需要將其變換成單目標優化問題線性加權變換的數學描述其中，且2/1/2023例6.37重新考慮例6.35，求解如下最優化問題2/1/2023不同加權系數下的方案2/1/2023不同加權系數下的最優方案2/1/2023

線性規劃

問題的最佳妥協解特殊的線性規劃數學描述目標函數不是一個向量，而是一個矩陣每一個目標函數2/1/2023最佳妥協解的求解步驟如下單獨求解每個單目標函數的最優化問題，得出最優解通過規范化構造單獨的目標函數最佳妥協解變換成單目標線性規劃2/1/2023最佳妥協解（最大值）的求解程序2/1/2023例6.38重新考慮例6.35，求解如下最優化問題2/1/2023MATLAB求解語句：2/1/2023例6.39求解如下最優化問題2/1/2023MATLAB求解語句：2/1/2023

線性規劃

問題的最小二乘解多目標線性規劃問題的最小二乘表示則最小二乘解可以由函數直接得出2/1/2023例6.40給定如下最優化問題，試求其最小二乘解2/1/2023MATLAB求解語句：2/1/20236.6.4多目標優化

問題的Pareto解集對于雙目標函數的問題，將可行解的離散點在二維平面上顯示出來從得出的可行解離散點提取出區域左下角的一條曲線，這個曲線上的點都是原問題的解，稱為Pareto解集2/1/2023YiCao

在Gianluca

Dorini

貢獻的Pareto解集提取程序的基礎上，開發了改進的快速提取程序函數調用格式其中，

為可行解、離散點構成的列向量，向量為標志向量，指示可行解離散點是否為Pareto解集中的點2/1/2023例6.41采用上述的離散點分析方法重新研究下述的多目標優化問題2/1/2023對原始問題中花費的錢數取一系列離散點原始問題可以改寫成單目標的線性規劃問題2/1/2023MATLAB求解語句：2/1/2023例6.42重新考慮例6.35，試提取其Pareto解集2/1/2023MATLAB求解語句：2/1/20236.6.5極小極大問題求解極小極大問題的數學描述極小極大問題是在最不利的條件下尋找最有利決策方案的一種方法2/1/2023直接求解極小極大問題的函數調用格式其中，目標函數為向量形式描述，用匿名函數、inline()函數和M-函數均可以表示新目標函數2/1/2023例6.43試求解下面的極小極大問題2/1/2023選擇隨機數為初值2/1/2023有了fminimax()函數，還可以求解相關的變形問題極小極小問題極小極大問題2/1/20236.6.6目標規劃問題求解最優化問題求解過程中，發現找不到可行解時，要放松約束條件。如，不等式約束條件

改寫成將偏差對

引入目標函數使得嚴格的不等式約束盡可能小地被突破，相應的最優化問題稱為目標規劃問題。2/1/2023數學描述形式其中，

為原始的多目標向量，

為各個目標函數的加權系數，

為用戶人為引入的目標2/1/2023MATLAB函數調用格式2/1/2023例6.44試用目標規劃方法求解下式2/1/2023兩個目標函數可以接受的目標分別是20和6，將其權重設置80%和20%2/1/20236.7動態規劃及其

在路徑規劃中的應用圖的矩陣表示方法有向圖的路徑尋優無向圖的路徑最優搜索2/1/20236.7.1圖的矩陣表示方法圖是由節點和邊構成的。邊是連接兩個節點的直接路徑。如果邊是有向的，則圖稱為有向圖，否則稱為無向圖在計算機中，圖用矩陣表示，即關聯矩陣MATLAB語言還支持關聯矩陣的稀疏矩陣表示方法2/1/2023構造關聯矩陣的稀疏矩陣函數調用格式其中，為起始節點向量，為終止節點向量，為邊權值向量，這里各個向量最后的一個值使得關聯矩陣為方陣2/1/2023稀疏矩陣可以由full()函數變換成常規矩陣，而常規矩陣可以由sparse()函數轉換成稀疏矩陣注意：在若第i和j節點間不存在邊，則可令，當然，也有的算法要求2/1/20236.7.2有向圖的路徑尋優有向圖最短路徑問題的手工求解有向圖搜索及圖示Dijkstra最短路徑算法及實現2/1/2023

有向圖最短

路徑問題的手工求解有向圖與最優路徑搜索是很多領域都能遇到的常見問題應用動態規劃理論，通常需要由終點反推回起點，搜索最優路徑2/1/2023例6.45有向圖路徑如下，數字為從該路徑所花費的時間，試求出從節點①到節點⑨的最優路徑。最短路徑為：2/1/2023

有向圖搜索及圖示函數調用格式建立有向圖對象求解最短路徑問題函數view()可以顯示有向圖2/1/2023例6.46試求出從節點①到節點⑨的最優路徑。2/1/2023建立關聯矩陣并顯示圖2/1/2023求出最短路徑2/1/2023

Dijkstra最

短路徑算法及實現編輯MATLAB程序實現Dijkstra算法2/1/2023接上頁2/1/2023函數的調用格式其中，W為關聯矩陣