工程分析/最佳化

最佳化

最佳化 是工程學中一個重要的概念。找到問題的任何解決方案都不如找到問題的唯一“最佳解決方案”。最佳化問題通常被重新格式化，使它們成為最小化問題，這是數學領域中得到充分研究的問題。

通常，在最佳化系統時，該系統的成本和收益被安排到一個成本函式中。然後，工程師的工作就是最小化這個成本函式（從而最小化系統的成本）。值得注意的是，在這一點上，“成本”這個詞可以有多種含義，具體取決於具體的問題。例如，成本可以指系統的實際貨幣成本（用於託管網站的計算機單元數量、連線費城和紐約所需的電纜數量）、系統的延遲（網站的載入時間、通訊網路的傳輸延遲）、系統的可靠性（手機網路中的掉話次數、汽車變速箱的平均壽命）或任何其他型別的因素，這些因素會降低系統的有效性和效率。

由於最佳化通常變成數學上的最小化問題，因此我們將在此討論最小化。

最小化

最小化是找到給定函式中數值最低點，或給定函式特定範圍內最低點的行為。數學和微積分的學生可能還記得使用函式的導數來找到函式的極大值和極小值。如果我們有一個函式 f(x)，我們可以透過求解以下方程中的 x 來找到極大值、極小值或鞍點（函式斜率為零但不是極大值或極小值的點）

${\frac {df(x)}{dx}}=0$

換句話說，我們正在尋找函式 f 導數的根以及 f 有角點的那些點。一旦我們有了函式的所謂臨界點（如果有），我們可以測試它們，看看它們是相對高（最大值）還是相對低（最小值）。在這個上下文中要記住的一些詞是

全域性最小值

函式的全域性最小值是該函式在任何地方的最低值。如果函式的定義域受限，比如 A < x < B，那麼最小值也會出現在邊界，這裡 A 或 B。

區域性最小值

函式的區域性最小值是該函式在某個小範圍內最低的值。因此，一個值可以是區域性最小值，即使存在更小的函式值，但不在一個小的鄰域內。

無約束最小化

無約束最小化是指在不需要考慮任何其他規則或注意事項的情況下對給定函式進行最小化。另一方面，約束最小化是指在必須同時滿足其他稱為約束的關係的情況下進行最小化的問題。

除了上述方法（我們對函式求導並將其設為零），還有幾種數值方法可用於找到函式的最小值。對於這些方法，有一些有用的計算工具，例如Matlab。

Hessian矩陣

如果Hessian矩陣 H(x) 是正定的，則函式在點 x 處有一個區域性最小值

$H(x)={\frac {\partial ^{2}f(x)}{\partial x^{2}}}$

其中 x 是函式的所有自變數的向量。如果 x 是一個標量變數，則 Hessian 矩陣簡化為函式 f 的二階導數。

牛頓-拉夫森方法

計算函式 f 最小值的牛頓-拉夫森方法使用迭代計算。我們可以定義序列

$x^{n+1}=x^{n}-{\frac {f'(x)}{f''(x)}}$

其中

$f'(x)={\frac {df(x)}{dx}}$

$f''(x)={\frac {d^{2}f(x)}{dx^{2}}}$

當我們重複上述計算，代入 n 的連續值時，我們的解將收斂於真實解。但是，這個過程將需要無限次迭代才能收斂，但是如果真實解的近似值就足夠了，你可以在僅幾次迭代後停止，因為該序列收斂得相當快（二次收斂）。

最速下降法

牛頓-拉夫森方法可能很棘手，因為它依賴於函式 f 的二階導數，這在很多時候可能很難（如果不是不可能）準確計算。然而，最速下降法不需要二階導數，但它需要選擇一個適當的標量 ε，該標量不能任意選擇（但也不能使用固定公式計算）。最速下降法由以下迭代計算定義

$x^{n+1}=x^{n}-\epsilon {\frac {df(x)}{dx}}$

其中epsilon需要足夠小。如果epsilon太大，迭代可能會發散。如果發生這種情況，需要選擇新的epsilon值，並重復該過程。

約束最小化

約束最小化是在一定數量的稱為約束的附加規則下找到函式最小值的過程。例如，我們可以說“找到f(x)的最小值，但g(x)必須等於10”。這類問題更難，但Khun-Tucker定理以及Karush-Khun-Tucker定理有助於解決它們。

約束有兩種型別：等式約束和不等式約束。我們將分別考慮它們，然後是混合約束。

等式約束

Khun-Tucker定理是一種在等式約束g(x)下最小化函式f(x)的方法。該定理如下所示

給定成本函式f和以下形式的等式約束g

$g(x)=0$,

然後我們可以透過構造f和g的拉格朗日函式將此問題轉換為無約束最小化問題

$L(x)=f(x)+\langle \Lambda ,g(x)\rangle$

其中Λ是拉格朗日乘子，< , >表示向量空間Rⁿ（其中n是等式約束的數量）的標量積。我們將在後面更詳細地討論標量積。如果我們對這個方程關於x求導，我們可以找到這個整個函式L(x,Λ)的最小值，這將是我們函式f的最小值。

${\frac {df(x)}{dx}}+\left\langle \Lambda ,{\frac {dg(x)}{dx}}\right\rangle =0$

$g(x)=0$

這是一個包含n+k個方程和n+k個未知變數（n個Λ和k個x）的方程組。

不等式約束

與上述方法類似，假設我們有一個成本函式f，以及以下形式的不等式約束

$g(x)\leq 0$

然後我們可以再次取這個的拉格朗日函式

$L(x)=f(x)+\langle \Lambda ,g(x)\rangle$

但現在我們必須使用以下三個方程/不等式來確定我們的解

${\frac {df}{dx}}=0$

$\langle \Lambda ,g(x)\rangle =0$

$\Lambda \geq 0$

最後兩個方程可以這樣解釋

如果$g(x)<0$，那麼$\Lambda =0$

如果 $g(x)\leq 0$，那麼 $\Lambda \geq 0$

利用這兩個附加方程/不等式，我們可以用與上述類似的方法求解。

混合約束

如果我們有一組等式和不等式約束

$g(x)=0$

$h(x)\leq 0$

我們可以將它們組合成一個拉格朗日函式，並新增兩個附加條件

$L(x)=f(x)+\langle \Lambda ,g(x)\rangle +\langle \mu ,h(x)\rangle$

$g(x)=0$

$\langle \mu ,h(x)\rangle =0$

$\mu \geq 0$

無限維最小化

上述方法在分析中涉及的變數是有限維向量（如R^N中的向量）時效果很好。然而，當我們試圖最小化比向量更復雜的某些東西時，例如函式，我們需要以下概念。我們考慮存在於L₂(R^N)的子空間中的函式，這是一個無限維向量空間。我們將定義術語泛函如下

泛函

泛函是一個對映，它接受一個或多個函式作為引數，並返回一個標量值。

假設我們考慮時間t的函式x（N=1）。進一步假設我們有一個固定函式f，它包含兩個變數。利用該函式，我們可以關聯一個成本泛函J

$J[x]=\int _{a}^{b}f(x,t)dt$

其中，我們明確地考慮了f定義中的t。為了最小化這個函式，就像所有最小化問題一樣，我們需要對函式求導並將其導數設為零。但是，我們需要稍微更復雜的導數版本，因為x是一個函式。這就是Gateaux導數進入該領域的原因。

Gateaux導數

我們可以用以下極限定義Gateaux導數

$\delta F(x,h)=\lim _{\epsilon \to 0}{\frac {1}{\epsilon }}[F(x+\epsilon h)-F(x)]$

這類似於方向h上導數的經典定義。簡單地說，我們對x在方向h上求取了F的導數。h是時間的任意函式，與x在同一個空間（這裡我們談論的是L₂空間）。與一維情況類似，如果上述極限存在，則函式在x處可微。我們可以使用Gateaux導數來找到我們上面泛函的最小值。

尤拉-拉格朗日方程

我們現在將使用上面討論的Gateaux導數來找到以下型別函式的最小值

$J(x(t))=\int _{a}^{b}f(x(t),x'(t),t)dt$

因此，我們必須找到以下方程的解

$\delta J(x)=0$

該解是尤拉-拉格朗日方程

${\frac {\partial f}{\partial x}}-{\frac {d}{dt}}{\frac {\partial f}{\partial x'}}=0$

忽略 x 是 t 的函式這一事實，以常規方式進行偏導。該方程的解要麼是成本函式 J 的最大值、最小值，要麼是鞍點。

示例：最短距離

我們常說兩點之間最短距離是直線。我們可以用尤拉-拉格朗日方程來證明這條規則。

如果我們在 R² 中有兩個點 a 和 b ，我們想要找到連線這兩個點的最小曲線 (x,y(x)) 。線元素 ds 讀作

$ds={\sqrt {dx^{2}+dy^{2}}}$

我們試圖最小化的函式定義為

$J[y]=\int _{a}^{b}ds$

或

$J[y]=\int _{a}^{b}{\sqrt {1+\left({\frac {dy}{dx}}\right)^{2}}}dx$

我們可以對函式 J 求 Gateaux 導數，並將其設為零以找到這兩個點之間的最小函式。將平方根記為 f ，我們得到

$0={\frac {\partial f}{\partial y}}-{\frac {d}{dx}}\left({\frac {\partial f}{\partial y'}}\right)=y''{\frac {1}{\left(1+y^{\prime 2}\right)^{3/2}}}\;.$

已知線元素將是有限的，這歸結為方程

${\frac {d^{2}y}{dx^{2}}}=0$

其眾所周知的解為

$y(x)=mx+n={\frac {b_{y}-a_{y}}{b_{x}-a_{x}}}(x-a_{x})+a_{y}\;.$