淺談最佳化

一般來說，最佳化是從一組可行的候選人中尋找和選擇最佳元素的過程。在數學最佳化中，這個問題通常被表述為確定給定區域的函數的極值。極值或最佳值可以指函數的最小值或最大值，這取決於應用程式和特定問題。

數學最佳化的應用多種多樣，解決最佳化問題所必須採用的方法和演算法也是多種多樣的。由於最佳化是一個普遍重要的數學工具，它已經在科學和工程的許多領域中得到了發展和應用，而用於描述最佳化問題的術語在不同的領域之間也各不相同。舉幾個例子，例如，最佳化的數學函數可以稱為成本函數、損失函數、能量函數或目標函數。在這裡，我們使用了通用術語“目標函數”。

最佳化與方程的求解密切相關，因為在一個函數的最佳值時，它的導數或多變數情況下的梯度為零。相反，並不一定是正確的，但解決最佳化問題的方法是求解導數或梯度的零點，並檢驗結果的最佳性。但是，這種方法並不總是可行的，而且通常需要採取其他的數值方法，其中許多方法與根查找數值方法密切相關。

在這裡，我們的注意力限制在一個或多個因變數的實值函數的數學最佳化上. 許多數學最佳化問題都可以用這種方式來表述，但一個值得注意的例外，是離散變數上的函數最佳化，例如整數。

我們考慮的一般最佳化問題可化為一個極小化問題：min f(x)，它在m個等式約束   g(x)=0 和p 個不等式約束 h(x) <= 0 的條件下。這裡   f(x) 是   x 的實數值函數，它可以是純量函數，也可以是向量   x=t(x1,x2,…,xn)，而  g(x) 和 h(x) 可以是向量值函數：f：R^n -> R，g：R^n -> R^m 和    h：R^n -> R^p。請注意，最大化   f(x) 等價於極小 -f(x)，因此在不失去一般性的情況下，只考慮極小化問題就足夠了。

根據目標函數f(x)的性質以及等式和不等式約束g(x)和h(x)的性質，該式子包含了豐富的各種問題。在這種形式上，一般的數學最佳化是很難解決的，也沒有有效的方法來解決完全一般的最佳化問題。然而，對於許多重要的特殊情況，有許多有效的方法，因此在最佳化中盡可能多地瞭解目標函數和約束條件，才能解決問題。

根據函數f(x)、g(x)和h(x)的性質對最佳化問題進行分類。首先，如果x是純量，x是屬於 R，則問題是單變數或一維問題，如果x是向量，則為多元或多維問題，x是屬於 R^n。對於高維目標函數，在n較大的情況下，最佳化問題的求解難度越來越大，計算量也越來越大。如果目標函數和約束都是線性的，則該問題是線性最佳化問題或線性規劃問題。如果目標函數或約束是非線性的，則是非線性最佳化問題或非線性規劃問題。對於約束，重要的最佳化子類問題是無約束問題，以及具有線性和非線性約束的問題。最後，處理相等和不相等約束需要不同的方法。

一如果往，非線性問題比線性問題更難解決，因為它們有更廣泛的可能行為。一般的非線性問題既有局部極小，又有全域極小，這使得求解全域極小變得非常困難：反覆運算求解者往往收斂到局部極小，而不是全域極小，甚至如果存在局部極小和全域極小，甚至可能無法完全收斂。

但是，凸問題是一類可以有效求解的非線性問題的重要子類，它直接關係到嚴格局部極小值的存在和唯一整體極小值的存在。根據定義，函數在區間[a，b]上是凸的，如果該區間上的函數的值位於通過端點(a，f(a)) 和 (b，f(b)) 的直線的下方。這個條件可以很容易地推廣到多元情形，它意味著許多重要的性質，例如區間上存在唯一的最小值。由於凸問題具有很強的性質，即使它們是非線性的，凸問題也能得到有效的解決。局部和全域極小，凸和非凸函數的概念如下圖所示.

目標函數f(x)和約束g(x)和h(x)是否連續且光滑是對求解最佳化問題的方法和技巧有重要意義的另一個性質。這些函數或它們的導數或梯度中的不連續性給許多現有的最佳化問題的求解方法帶來了困難，在下面我們假定這些函數確實是連續的和光滑的。在相關的說明中，如果函數本身不完全已知，但由於測量或其他原因而包含雜訊，則有最佳化的許多方法可能不合適。

連續函數和光滑函數的最佳化與非線性方程的求解密切相關，因為函數f(x)的極值對應於其導數或梯度為零的點。因此，尋找f(x)最優值的候選值相當於求解(一般的非線性)方程組 diff(f(x)) = 0 [diff 表示為微分]。然而，對於 diff(f(x)) = 0 的解，即所謂的靜止點，並不一定對應於f(x)的最小值；它也可以是最大值或鞍點，參見下圖。

因此，通過求解 diff(f(x))=0 獲得的候選項應該被測試為最佳性。對於無約束目標函數，高階導數，或    hessian 矩陣

對於多變量情形，hessian 矩陣可以用來確定一個平穩點是否是一個局部極小值。特別是，如果二階導數為正，或    hessian  矩陣正定，則x*是一個局部極小值。負二階導數，或hessian 矩陣負定，則對應於一個局部極大值，一個零二階導數，或一個不定式  hessian 矩陣，對應於鞍點。

代數求解方程組 diff(f(x)) = 0 並檢驗最佳性的候選解是求解最佳化問題的一種可能策略。然而，這並不總是一種可行的方法。特別是，對於f(x)，我們可能沒有一個計算導數的解析運算式，由此產生的非線性方程組可能不容易求解，特別是不能找到它的所有根。對於這種情況，有一些替代的數值最佳化方法，其中有些類似于尋根的方法。