代數(shù)方程與最優(yōu)化問題的計算機求解

第6章

代數(shù)方程與最優(yōu)化問題的計算機求解高等應用數(shù)學問題的MATLAB求解清華大學出版社2008CAI課件開發(fā)：薛定宇、劉瑩瑩、董雯彬3/4/2024第6章代數(shù)方程與最優(yōu)

化問題的計算機求解代數(shù)方程的求解無約束最優(yōu)化問題求解有約束最優(yōu)化問題的計算機求解混合整數(shù)規(guī)劃問題的計算機求解線性矩陣不等式問題求解多目標優(yōu)化問題求解動態(tài)規(guī)劃及其在路徑規(guī)劃中的應用3/4/20246.1代數(shù)方程的求解代數(shù)方程的圖解法多項式型方程的準解析解法一般非線性方程數(shù)值解非線性矩陣方程求解3/4/20246.1.1代數(shù)方程的圖解法一元方程的圖解法二元方程的圖解法3/4/2024

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

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

線的交點上讀出所有的實數(shù)解。3/4/2024例6.1用圖解法求解方程：MATLAB求解命令證明：3/4/2024

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

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

然后繪制

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

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

數(shù)學表述

MATLAB表述矩陣轉換成向量數(shù)學表述MATLAB表述Riccati方程求解3/4/2024以向量的形式描述Riccati方程的殘差求解Riccati方程的新函數(shù)3/4/2024例6.11求解下列Riccati方程組：

其中3/4/2024are()

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

3/4/20246.2無約束最優(yōu)化問題求解解析解法和圖解法基于MATLAB的數(shù)值解法全局最優(yōu)解與局部最優(yōu)解利用梯度求解最優(yōu)化問題帶有變量邊界約束的最優(yōu)化問題求解3/4/2024無約束最小化問題的數(shù)學描述目標函數(shù)是一個標量函數(shù)向量決定變量，或優(yōu)化變量物理意義：求取一組

向量，使得最優(yōu)化目標函數(shù)

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

，求其最小值

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

內的曲線：在

內的曲線3/4/20246.2.4利用梯度求解最優(yōu)化問題有時，僅利用目標函數(shù)提供的信息，很難得到最優(yōu)解。這是由于求解最優(yōu)化問題收斂速度一般較慢，尤其是變量較多的最優(yōu)化問題可以利用梯度信息解決上述問題3/4/2024例6.16求Rosenbrock

函數(shù)的無約束最優(yōu)化問題繪制三維等高線圖：3/4/2024無梯度信息求梯度矩陣：3/4/2024編寫目標函數(shù)：求解最優(yōu)化問題3/4/20246.2.5帶有變量邊界約

束的最優(yōu)化問題求解帶有變量邊界約束的最優(yōu)化問題的數(shù)學描述

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

一般求解格式3/4/2024例6.17求解Rosenbrock問題其中，和

MATLAB求解語句3/4/20246.3有約束最優(yōu)化

問題的計算機求解約束條件與可行解區(qū)域線性規(guī)劃問題的計算機求解二次型規(guī)劃的求解一般非線性規(guī)劃問題的求解3/4/20246.3.1約束條件與可行解區(qū)域有約束非線性最優(yōu)化問題的一般描述為其中，所有的

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

3/4/2024推導Jacobian矩陣編寫目標函數(shù)3/4/2024使用函數(shù)fmincon()得出結果3/4/20246.4混合整數(shù)規(guī)劃

問題的計算機求解整數(shù)線性規(guī)劃問題的求解一般非線性整數(shù)規(guī)劃問題與求解0-1規(guī)劃問題求解3/4/20246.4.1整數(shù)線性規(guī)劃問題的求解整數(shù)線性規(guī)劃的一般數(shù)學描述其中，

為變量

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

的各個元素均為203/4/2024得出次最優(yōu)解混合整數(shù)規(guī)劃問題，要求

為整數(shù)，其他兩個變量為任意數(shù)3/4/20246.4.2一般非線性整

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

Mr.Keort

Kuipers提供

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

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

其中，

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

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

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

問題的MATLAB求解用MATLAB描述線性矩陣不等式創(chuàng)建LMI模型定義需要求解的變量其中，是未知矩陣類型的標記3/4/2024描述分塊形式給出線性矩陣不等式

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

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

大學電子工程專業(yè)的JohanL?fberg博士開發(fā),

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

求解線性系統(tǒng)模型的范數(shù)3/4/2024MATLAB求解命令：3/4/20246.6多目標優(yōu)化問題求解多目標優(yōu)化模型無約束多目標函數(shù)的最小二乘求解多目標問題轉換為單目標問題求解多目標優(yōu)化問題的Pareto解集極小極大問題求解目標規(guī)劃問題求解3/4/20246.6.1多目標優(yōu)化模型多目標最優(yōu)化問題的一般表示為其中，3/4/2024例6.35

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

和

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

購買量為

公斤，則3/4/20246.6.2無約束多目標

函數(shù)的最小二乘求解設目標函數(shù)將其轉換成單目標問題MATLAB函數(shù)調用格式3/4/2024例6.36求解下面無約束非線性多目標規(guī)劃問題的最小二乘解3/4/2024MATLAB求解語句使用函數(shù)fmincon()3/4/20246.6.3多目標問題轉

換為單目標問題求解線性加權變換及求解線性規(guī)劃問題的最佳妥協(xié)解線性規(guī)劃問題的最小二乘解3/4/2024

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

線性規(guī)劃

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

線性規(guī)劃

問題的最小二乘解多目標線性規(guī)劃問題的最小二乘表示則最小二乘解可以由函數(shù)直接得出3/4/2024例6.40給定如下最優(yōu)化問題，試求其最小二乘解3/4/2024MATLAB求解語句：3/4/20246.6.4多目標優(yōu)化

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

在Gianluca

Dorini

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

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

改寫成將偏差對

引入目標函數(shù)使得嚴格的不等式約束盡可能小地被突破，相應的最優(yōu)化問題稱為目標規(guī)劃問題。3/4/2024數(shù)學描述形式其中，

為原始的多目標向量，

為各個目標函數(shù)的加權系數(shù)，

為用戶人為引入的目標3/4/2024MATLAB函數(shù)調用格式3/4/2024例6.44試用目標規(guī)劃方法求解下式3/4/2024兩個目標函數(shù)可以接受的目標分別是20和6，將其權重設置80%和20%3/4/20246.7動態(tài)規(guī)劃及其

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

有向圖最短

路徑問題的手工求解有向圖與最優(yōu)路徑搜索是很多領域都能遇到的常見問題應用動態(tài)規(guī)劃理論，通常需要由終點反推回起點，搜索最優(yōu)路徑3/4/2024例6.45有向圖路徑如下，數(shù)字為從該路徑所花費的時間，試求出從節(jié)點①到節(jié)點⑨的最優(yōu)路徑。最短路徑為：3/4/2024

有向圖搜索及圖示函數(shù)調用格式建立有向圖對象求解最短路徑問題函數(shù)view()可以顯示有向圖3/4/2024例6.46試求出從節(jié)點①到節(jié)點⑨的最優(yōu)路徑。3/4/2024建立關聯(lián)矩陣并顯示圖3/4/2024求出最短路徑3/4/2024

Dijkstra最

短路徑算法及實現(xiàn)編輯MATLAB程序實現(xiàn)Dijkstra算法3/4/2024接上頁3/4/2024函數(shù)的調用格式其中，W為關聯(lián)矩陣