最優化原理中有哪些方法

A. 牛頓法、黃金分割法、二次插值法實驗（最優化1）

在生產過程、科學實驗以及日常生活中，人們總希望用最少的人力、物力、財力和時間去辦更多的事，獲得最大的效益，，所以最優化理論和方法日益受到重視。

無約束最優化計算方法是數隱森值計算領域中十分活躍的研究課題之一，快速的求解無約束最優化問題，除了自身的重要性以外，還體現在它也構成一些約束最優化問題的子問題。因此，對於無約束最優化問題，如何快速高精度的求解一直是優化工作者十分關心的事。本文驗證求解 一維無約束最優化問題 的三種線性搜索方法，分別是牛頓法、黃金分割法，二次插值法。

min ⁡f(x)=3x ⁴ - 4x ³ -12x ²

牛頓迭代法（Newton』s method）又稱為牛頓-拉夫遜方法（Newton-Raphson method）,它是牛頓在17世紀提出的一種在實數域和復數域上近似求解方程的方法,其基本思想是利用目標函數的二次Taylor展開，並將其極小化。牛頓法使用函數 f(x)的泰勒級數的前面幾項來尋找方程 "f(x)=0" 的根。牛頓法是求方程根的重要方法之一，其困改最大優點是在方程 "f(x)=0" 的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復根，此時非線性收斂，但是可通過一些方法變成線性收斂。

方程 f(x)=0 的根 x ^* 可解釋為曲線y=f(x)軸的焦點的橫坐標。如下圖：

設 x[k]是根 x ^* 的某個近似值，過曲線 y=f(x)上橫坐標為 x[k]的點P[k]引切線，並將該切線與 x軸的交點 的橫坐標 x_{k+1}_作為 x ^* 的新的近似值。鑒於這種幾何背景，牛頓法亦稱為切線法。

將f(x ^k+1 )在x=x ^k 處一階泰勒展開：

公式不打了
令函數趨於0，求與x軸交點：

分別取-1.5,0.4,1.0,1.6,2.8

在凸函數很初始點選取好的情況下，收斂快。

Ø 計算二階導數，計算量大

Ø 要求函數二階可微

Ø 收斂性與初始點選取有關

黃金分割法適用於[a,b]區間上的任何單股函數求極小值問題，對函數除要求「單峰」外不做其他要求，甚至可以不連續。因此，這種方法的適應面非常廣。黃金分割法也是建立在區間消去法原理基礎上的試探方法，即在搜索區間 ？內適當插入兩點 ？，並計算其函數值。 ？將區間分成三段，應用函數的單峰性汪攜判質，通過函數值大小的比較，刪去其中一段，是搜索區間得以縮小。然後再在保留下來的區間上作同樣的處理，如此迭代下去，是搜索區間無限縮小，從而得到極小點的數值近似解。

一 維搜索是解函數極小值的方法之一，其解法思想為沿某一已知方向求目標函數的極小值點。一維搜索的解法很多，這里主要採用黃金分割法（0.618法）。如圖所示

黃金分割法是用於一元函數 ？在給定初始區間 ？內搜索極小點？的一種方法。其基本原理是：依照「去劣存優」原則、對稱原則、以及等比收縮原則來逐步縮小搜索區間。

具體步驟是：在區間 ？內取點： ？分為三段。如果 ？,令？；如果 ？，令 <？,如果 ？都大於收斂精度？重新開始。因為 ？為單峰區間，這樣每次可將搜索區間縮小0.618倍或0.382倍，處理後的區間都將包含極小點的區間縮小，然後在保留下來的區間上作同樣的處理，如此迭代下去，將使搜索區 ？逐步縮小，滿足預先給定的精度時，即獲得一維優化問題的近似最優解。

[-2,0],[1,3]

很巧妙地使每次分割點都為上次的黃金分割點，可以復用上次運算的結果，簡化計算。它是優化計算中的經典演算法，以演算法簡單、收斂速度均勻、效果較好而著稱，是許多優化演算法的基礎，但它只適用於一維區間上的凸函數，即只在單峰區間內才能進行一維尋優，其收斂效率較低。

在求解一元函數?的極小點時，在搜索區間中用低次（通常不超過三次）插值多項式?來近似目標函數，後求該多項式的極小點（比較容易計算），並以此作為目標函數?的近似極小點。如果其近似的程度尚未達到所要求的精度時，反復使用此法，逐次擬合，直到滿足給定的精度時為止。

考慮二次多項式

則

令 ，得 。這意味著我們要求a，b。
今考慮在包含 的極小點 的搜索區間 中，給定三個點 ， ， ，滿足
< <
> <
利用三點處的函數值 ， ， 構造二次函數，並要求插值條件滿足

令 ，i=1,2,3。解上述方程組得

於是，二次函數 的極小點為

設 。求得 和 以後，如果
≤ ，當 > 時，
或者如果
≤ ，當 < 時。
則我們認為收斂准則滿足。如果 < ,則極小點估計為 ，否則為 。
若終止准則不滿足，則利用 提供的信息，從 ， ， 和 中選出相鄰的三個點，將原來的搜索區間縮小，然後重復上述過程，直到終止准則滿足為止。

初始步 給出?，?，?，滿足上述設計步驟。
步1 由上述設計步驟計算?。
步2 比較?和?的大小，如果?>?，則轉步3；否則轉步4。
步3 如果?≤?，則
?，?，?，?，
轉步5；否則?，?，轉步5。
步4 若?，則
?，?，?，?，
轉步5；否則?，?，轉步5。
步5 如果收斂准則滿足，停止迭代；否則轉步1，在新的搜索區間[?,?]上按公式計算二次插值函數的極小點?。

-2.5,-1.4,-0.3
-0.3,1.5,3.3.

插值法僅需計算函數值，不涉及導數、Hesse矩陣等的計算，計算起來相對比較簡單，能夠適用於非光滑和導數表達式復雜或表達式寫不出等種種情形。

當迭代步數較多時，計算過程比較復雜，計算量較大，計算起來比較麻煩。當迭代點離目標函數的最優解較遠時，追求線性搜索的精度反而會降低整個演算法的效率。

用符號推導畫圖

picture.py

Gold_ratio.py

Newton.py

Polynomial_interpolation.py

B. 最優化方法

最優化方法，是指解決最優化問題的方法。

所謂最優化問題，指在某些約束條件下，決定某些可選擇的變數應該取何值，使所選定的目標函數達到最優的問題。即運用最新科技手段和處理方法，使系統達到總體最優，從而為系統提出設計、施工、管理、運行的最優方案。

由於實際的需要和計算技術的進步，最優化方法的研究發展迅速。

最優化方法（也稱做運籌學方法）是近幾十年形成的，它主要運用數學方法研究各種系統的優化途徑及方案，為決策者提供科學決策的依據。

最優化方法的主要研究對象是各種有組織系統的管理問題及其生產經營活動。最優化方法的目的在於針對所研究的系統，求得一個合理運用人力、物力和財力的最佳方案，發揮和提高系統的效能及效益，最終達到系統的最優目標。

實踐表明，隨著科學技術的日益進步和生產經營的日益發展，最優化方法已成為現代管理科學的重要理論基礎和不可缺少的方法，被人們廣泛地應用到公共管理、經濟管理、工程建設、國防等各個領域，發揮著越來越重要的作用。

將介紹最優化方法的研究對象、特點，以及最胡亂彎優化方法模型的建立和模型的分析、求解、應用。主要是線性規劃問題陪芹的模型褲悶、求解（線性規劃問題的單純形解法）及其應用――運輸問題；以及動態規劃的模型、求解、應用――資源分配問題。

最優化方法：

1、微分學中求極值

2、無約束最優化問題

3、常用微分公式

4、凸集與凸函數

5、等式約束最優化問題

6、不等式約束最優化問題

7、變分學中求極值

C. 施工中常用的最優化方法有哪些簡述其基本原理

施工時，在禪歲實際測量的工作中，為了提高施工放樣的效率和准確性，施工單賀螞睜位會利用測量儀器，來簡化放樣工作。

二、設備原理：

1.從BIM模型中設置現場控制點坐標和建築物結構點坐標分量作為BIM模型復合對比依據，在BIM模型中創建放樣控制點。

2.在已通過審批的機電BIM模型中，設置機電管線支吊架點位布置，並將所有的放樣點導入專業軟體。

3.進入現場，使用BIM放樣機器人對現場放樣控制點進行數據採集，即刻定位放樣機器人的現場坐標。

4.通過平板電腦選取BIM模型中所需放樣點，指揮機器人發射紅外激光自動照準現實點位，物枯實現「所見點即所得」，從而將BIM模型精確的反應到施工現場。

D. 最優化問題求解方法

在求解最優化問題中，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）條件是兩種最常用的方法。在有等式約束時使用拉格朗日乘子法，在有不等約束時使用KKT條件。

我們這里提到的最優化問題通常是指對於給定的某一函數，求其在指定作用域上的全局最小值(因為最小值與最大值可以很容易轉化，即最大值問題可以轉化成最小值問題)。提到KKT條件一般會附帶的提一下拉格朗日乘子。對學過高等數學的人來說比較拉格朗日乘子應該會有些印象。二者均是求解最優化問題的方法，不同之處在於應用的情形不同。

一般情況下，最優化問題會碰到一下三種情況：

這是最簡單的情況，解決方法通常是函數對變數求導，令求導函數等於0的點可能是極值點。將結果帶回原函數進行驗證即可。

設目標函數為f(x)，約束條件為h_k(x)，形如:
s.t. 表示subject to ，「受限於」的意思，l表示有l個約束條件。

則解決方法是消元法或者拉格朗日法。消元法比較簡單不在贅述，這里主要講拉格朗日法，因為後面提到的KKT條件是對拉格朗日乘子法的一種泛化。

作為一種優化演算法，拉格朗日乘子法主要用於解決約束優化問題，它的基本思想就是通過引入拉格朗日乘子來將含有n個變數和k個約束條件的約束優化問題轉化為含有（n+k）個變數的無約束優化問題。拉格朗日乘子背後的數學意義是其為約束方程梯度線性組合中每個向量的系數。

如何將一個含有n個變數和k個約束條件的約束優化問題轉化為含有（n+k）個變數的無約束優化問題？拉格朗日乘數法從數學意義入手，通過引入拉格朗日乘子建立極值條件，對n個變數分別求偏導對應了n個方程，然後加上k個約束條件（對應k個拉格朗日乘子）一起構成包含了（n+k）變數的（n+k）個方程的方程組問題，這樣就能根據求方程組的方法對其進行求解。

首先定義拉格朗日函數F(x)：

然後解變數的偏導方程：

我們上述討論的問題均為等式約束優化問題，但等式約束並不足以描述人們面臨的問題，不等式約束比等式約束更為常見，大部分實際問題的約束都是不超過多少時間，不超過多少人力，不超過多少成本等等。所以有幾個科學家拓展了拉格朗日乘數法，增加了KKT條件之後便可以用拉格朗日乘數法來求解不等式約束的優化問題了。

設目標函數f(x)，不等式約束為g(x)，有的教程還會添加上等式約束條件h(x)。此時的約束優化問題描述如下：

則我們定義不等式約束下的拉格朗日函數L，則L表達式為：

其中f(x)是原目標函數，hj(x)是第j個等式約束條件，λj是對應的約束系數，gk是不等式約束，uk是對應的約束系數。

常用的方法是KKT條件，同樣地，把所有的不等式約束、等式約束和目標函數全部寫為一個式子L(a, b, x)= f(x) + a g(x)+b h(x)，

首先，我們先介紹一下什麼是KKT條件。

KKT條件是指在滿足一些有規則的條件下, 一個非線性規劃(Nonlinear Programming)問題能有最優化解法的一個必要和充分條件. 這是一個廣義化拉格朗日乘數的成果. 一般地, 一個最優化數學模型的列標准形式參考開頭的式子, 所謂 Karush-Kuhn-Tucker 最優化條件，就是指上式的最優點x∗必須滿足下面的條件:

1). 約束條件滿足gi(x∗)≤0,i=1,2,…,p, 以及,hj(x∗)=0,j=1,2,…,q

2). ∇f(x∗)+∑i=1μi∇gi(x∗)+∑j=1λj∇hj(x∗)=0, 其中∇為梯度運算元;

3). λj≠0且不等式約束條件滿足μi≥0,μigi(x∗)=0,i=1,2,…,p。