課程報告
學生姓名
學號院系專業二ｏ一二年十一月十日
最優化方法是近幾十年形成的，它主要運用數學方法研究各種系統的優化途徑及方案，為決策者提供科學決策的依據。最優化方法的主要研究物件是各種管理問題及其生產經營活動。最優化方法的目的在於針對所研究的系統，求得乙個合理運用人力、物力和財力的最佳方案，發揮和提高系統的效能及效益，最終達到系統的最優目標。
實踐表明，隨著科學技術的日益進步和生產經營的日益發展，最優化方法已成為管理科學的重要理論基礎和不可缺少的方法，被人們廣泛地應用到公共管理、經濟管理、工程建設、國防等各個領域，發揮著越來越重要的作用。這就是我理解的整個課程的流程。在這整個學習的過程當中，當然也會遇到很多的問題，不論是從理論上的還是從實際將演算法編寫出程式來解決一些問題。
下面給出學習該課程的必要性及結合老師講解以及在作業過程中遇到的問題來闡述自己對該課程的理解。
20世紀40年代以來，由於生產和科學研究突飛猛進地發展，特別是電子計算機日益廣泛應用，使最優化問題的研究不僅成為一種迫切需要，而且有了求解的有力工具。因此最優化理論和演算法迅速發展起來，形成乙個新的學科。至今已出現線性規劃、整數規劃、非線性規劃、幾何規劃、動態規劃、隨機規劃、網路流等許多分文。
最優化理論與演算法包括線性規劃單純形方法、對偶理論、靈敏度分析、運輸問題、內點演算法、非線性規劃k-t條件、無約束最優化方法、約束最優化方法、引數線性規劃、運輸問題、線性規劃路徑跟蹤法、信賴域方法、二次規劃路徑跟蹤法、整數規劃和動態規劃等內容。
最優化理論所研究的問題是討論在眾多的方案中什麼樣的方案最優以及怎樣找出最優方案。這類問題普遍存在。例如，工程設計中怎樣選擇設計引數，使得設計方案滿足設計要求，又能降低成本；資源分配中，怎樣分配有限資源，使得分配方案既能滿足各方面的基本要求，又能獲得好的經濟效益；生產評價安排中，選擇怎樣的計畫方案才能提高產值和利潤；原料配比問題中，怎樣確定各種成分的比例，才能提高質量，降低成本；城建規劃中，怎樣安排基本單位的合理布局，才能方便群眾，有利於城市各行各業的發展；農田規劃中，怎樣安排各種農作物的合理布局，才能保持高產穩產，發揮地區優勢；軍事指揮中，怎樣確定最佳作戰方案，才能有效地消滅敵人，儲存自己，有利於戰爭的全域性；在人類活動的各個領域中，諸如此類，不勝列舉。
最優化這一數學分支，正是為這些問題的解決，提供理論基礎和求解方法，它是一門應用廣泛、實用性強的學科。
一、 最優化學習的必要性
最優化，在熱工控制系統中應用非常廣泛。為了達到最優化目的所提出的各種求解方法。從數學意義上說，最優化方法是一種求極值的方法，即在一組約束為等式或不等式的條件下，使系統的目標函式達到極值，即最大值或最小值。
從經濟意義上說，是在一定的人力、物力和財力資源條件下，使經濟效果達到最大，或者在完成規定的生產或經濟任務下，使投入的人力、物力和財力等資源為最少。
通過老師的講解，我們了解不同型別的最優化問題可以有不同的最優化方法，即使同一型別的問題也可有多種最優化方法。反之,某些最優化方法可適用於不同型別的模型。最優化問題的求解方法一般可以分成解析法、直接法。
1、 直接法
當目標函式較為複雜或者不能用變數顯函式描述時，無法用解析法求必要條件。此時可採用直接搜尋的方法經過若干次迭代搜尋到最優點。這種方法常常根據經驗或通過試驗得到所需結果。
對於一維搜尋(單變數極值問題)，一維搜尋介紹了**分割法即為0.618法（前提是存在單峰區間（所以在此時要提出使用進退法來得到該單峰區間））、二分法（效率最高，但是必須求取函式的導數不好求）、拋物線法（不推薦）；對於多維搜尋問題(多變數極值問題)。
**分割法是一維搜尋方法，只針對一元函式來求解。**分割法的侷限性在於要求是單峰函式，所以要先用進退法找到乙個函式的其中乙個單峰。步驟就是在區間[a,b]中取點x1=a+0.
382(b-a)，x2=a+0.618(b-a)，如果f(x1)>f(x2),說明選取的步長太小，要擴大，令a=x1，x1=x2，再求新的x2;如果f(x1)<=f(x2)，步長選取過大，縮小步長，令b=x2，x2=x1，再求新的x1，迴圈。這樣做每次可將搜尋區間縮小0.
382倍或0.618倍，直至縮為最小點。該演算法為收斂速度很快的一維搜尋方法。
前提是要先利用進退法選擇乙個下降的單峰區間（即**分割法的單峰搜尋區間）。
進退法用進退法來確定下單峰區間，即**分割法的搜尋區間。
2、 線性規劃問題
單純形法對於一般形式的線性規劃問題，引入鬆弛變數或者剩餘變數來化為標準型，可以將引入的變數作為初始基變數，該基變數對應的單位陣可以作為乙個初始基可行解，然後進行單純形法求解過程。如果線性規劃是非退化的,則按照進基,離基迭代一次後,目標函式值有所下降.經過有限次迭代之後,一定可以得到乙個基可行解,使得其所有判別數非負(得到最優解),或者其有乙個判別數是負的,但對應列向量的所有分量非正(線性規劃無最優解)。
而對於一般標準型的線性規劃問題，約束方程組的係數矩陣中不包含單位陣，從而需要引入人工變數，構造乙個單位矩陣，得到初始基可行解的方法。而利用單純形法求解問題最關鍵的環節是初始基可行解的求解，因為單純形法的迭代過程是在已有乙個初始基可行解的前提下進行的，而常用的方法有兩種，一是大m法，二是兩階段法。
大m單純形法，其中m定義為乙個比較大的數，通常比係數矩陣中的係數大乙個數量級，與引入的人工變數結合構造輔助線性規劃問題，從而也在係數矩陣中構造出了單位陣，對應的變數值作為一組初始基可行解進行單純形法的迭代運算。在取得的最優解中人工變數全為零，即m的引入不影響目標函式的最優解。
對偶單純形法，單純形法與對偶單純形法是對偶的可以互相轉換可以簡化求解過程，而對偶之間只有最優解是相等的。單純形法保證解可行，而對偶單純形法保證對偶規劃解可行。不同點在於對偶單純形法的最優性判別是已知線性規劃問題的基矩陣b及它所對應的基解的所有的判別數非負（即xb=b-1b>=0）時有最優解。
對偶單純形法並不是解對偶線性規劃問題的單純形法，而是根據對偶原理求解原線性規劃問題的另一種單純形法。
3、 無約束最優化問題
解析法只適用於目標函式有明顯的解析表示式的情況。求解方法是：先求出最優的必要條件，得到一組方程或不等式，再求解這組方程或不等式，一般是用求導數的方法求出必要條件，通過必要條件將問題簡化，因此也稱間接法。
這種方法針對的是無約束最優化，主要考慮下降演算法包括最速下降法、newton法、共軛梯度法、擬newton法等。
最速下降法是求梯度的方法中效率最低的方法，它所提供的下降方向只是眼前下降最快的方向，用圖形表示是一種鋸齒形的路線，收斂速度慢，但是迭代計算量小、演算法簡單。它的原理就是沿著負梯度方向就是下降速度最快的方向，主要步驟就是取初值以及允許誤差，求取函式的負梯度，若梯度範數小於允許誤差，此時得到最優解。反之，得到此時的xk再用一維搜尋求取合適的步長滿足最小函式值方程，計算下乙個xk+1值，求出梯度，迴圈計算最小函式值找到最優解。
最速下降法
基本思想：最速下降法是應用目標函式的負梯度方向作為每一步迭代的搜尋方向，因為每一步都取負梯度方向的最優步長。使用條件：目標函式在迭代點處必須可微，且導數不為0。
特點：沿負梯度方向尋優的最優梯度法，其搜尋路徑實際上是成直角的鋸齒形前進的，它是在某一點附近的最速下降方向，是一區域性性質，開始時步長較大，收斂速度較快，但越接近極小點，步長越小，收斂速度越慢。
newton法有很快的收斂速度，但它只是區域性收斂的。所以提出共軛梯度法。如果在共軛方向法中初始的共軛向量恰好取為初始點x0處的負梯度-g0，而以下各共軛方向pk由第k迭代點xk處的負梯度-gk與已經得到的共軛向量pk-1的線性組合來確定，那麼就構成了一種具體的共軛方向法。
因為每乙個共軛向量都是依賴於迭代點處的負梯度而構造出來的，所以稱為共軛梯度法。產生的n個共軛方向
newton法，演算法流程如下：
(1) 取初始點，置精度要求，置
(2) 如果，則停止計算（作為無約束問題的解）；否則求解線性方程組，得到
(3) 置，，轉(2)
牛頓迭代法是求方程根的重要方法之一。
約束最優化方法包括：kuhn-tucker 條件，既約梯度法及凸單純行法，罰函式法及乘子法。罰函式法包括簡單罰函式法、內點罰函式法和乘子法。
約束最優化方法：問題
約束集共軛梯度法的效果介於最速下降法和newton法之間，既能克服最速下降法的慢收斂性，又避免了newton法的計算量大和具有區域性收斂性的缺點，因而是比較有效的演算法。而且共軛方向法中的共軛梯度法，由於其存貯量小，可用來求解大規模（n較大）無約束優化問題。
基本思想：共軛梯度法是對最速下降法進行了修正的一種尋優方法，它是使搜尋方向為共軛方向（將負梯度方向旋轉乙個角度），即每步的搜尋方向都要對該步的負梯度方向做乙個修正。
演算法特點：共軛梯度法利用了各步搜尋方向關於互為共軛的性質，它是利用梯度資訊尋找共軛方向的；共軛梯度法具有二次終結的性質，這一點與共軛方向法相同，且其儲存量小，不需儲存矩陣，只需儲存向量，在大規模問題中具有明顯優勢；但在實踐中由於初始點選擇不當或計算機的捨入誤差等原因，會出現二次終結時精度不高的情況。此時，可繼續迭代或重新開始新一輪共軛梯度法搜尋或改用其他數值演算法以滿足高精度的要求。
無約束最優化的直接法；單純形調優法（與線性規劃中的不同，是針對非線性的問題的求解方法）。單純形法求解控制系統引數優化。具體過程是給定尋優引數初值，然後利用matlab優化工具箱來構造誤差目標函式（給定控制物件引數），再進行以下四步操作：
反射，延伸，擴張和收縮。在此過程中有很多問題，開始不熟悉優化工具箱，所以無法建立誤差目標函式；而且利用優化工具箱無法加入延遲環節；確定各個計算公式的係數（反射、擴大、收縮、壓縮）的值是個大問題，對最壞值的判斷很關鍵，什麼條件下被取代的一系列的問題，最後得出最優解（但是得到的引數pi都非常大），則在simulink搭建該**系統（不知道應該如何建立被控物件的延遲環節的函式），將優化後的引數帶入，觀察分析所得曲線卻能很好的滿足系統效能優化。對於如此大的引數，在實際應用中肯定是會造成該系統劇烈振盪的不穩定的。
4、 約束最優化問題
約束最優化方法是指對於一般非線性規劃模型的求解方法。懲罰函式法(包括外罰函式法和閘函式法)是一種有效的求解方法。而在構造罰函式的過程中，對於不等式約束和等式約束的構造方式是不一樣的：
對於不等式約束是用對數或者是倒數來構造，而對於等式約束則是求平方和來構造。步驟是：構造罰函式是為了將約束問題改變為無約束的問題進行求解，將問題簡單化。
內罰函式的步驟選取初始資料，給定初始內點（必須是可行的（即保證在可行域內），這樣最終結果就能夠保證是可行的）、初始罰因子、縮小係數、允許誤差，k為迭代次數，構造罰函式，求解無約束問題（在求解無約束問題時用下降演算法來求解即可，最有效的方法就是用擬牛頓法，而在實際時用的是最速下降法求解，問題是該如何給出約束條件，是將約束條件化作矩陣形式來構造罰函式），得到下乙個解，判斷終止條件是否滿足，反之，則改變引數重新迴圈，直到得到最優解。與外罰函式法的唯一不同就是它的初始內點是在可行域內，保證了最優解的可行性。經過實踐檢驗來看，罰函式法是一種比較有效的解約束最優化問題的方法。
最優化理論與方法第一章習題
1 1設計一體積為5m3，長度不小於4m的無蓋鐵皮箱。若鐵皮的單位面積密度是常數，試確定其長 寬 高的尺寸使其質量最小。解 由於鐵皮箱面密度為常數，因此問題轉化為鐵皮箱總面積最小。設鐵皮箱的長 寬 高分別為x，y，z。則 1 2 一矩形截面懸臂梁如圖，其體積質量密度為m。要求在自重條件下自由端撓度不...
最優化方法綜述
1.引論 1.1應用介紹 最優化理論與演算法是乙個重要的數學分支，它所研究的問題是討論在眾多的方案中什麼樣的方案最優以及怎樣找出最優方案。這類問題普遍存在。例如，工程設計中怎樣選擇設計引數，使得設計方案滿足設計要求，又能降低成本 資源分配中，怎樣分配有限資源，使得分配方案既能滿足各方面的基本要求，又...
最優化的面試方法與運用
以 ldquo 工作說明書 rdquo 為指引內容的招聘面試 面談 是通過 準備資料 自然匯入 營造氣氛 合適提問 面試小結和回顧複審六個步驟的過程 關鍵是找到應職者的特質 專長和主要能力 以適合使用和能夠達至即時上崗的量度。筆者認為，最優化的面試方法是 結構化 程式 情景化 角色 個人面試 溝通 ...