複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/最優化/10588719
複製
複製成功

最優化

鎖定
最優化是應用數學的一個分支，主要指在一定條件限制下，選取某種研究方案使目標達到最優的一種方法。最優化問題在當今的軍事、工程、管理等領域有着極其廣泛的應用。
中文名
最優化
外文名
Optimization
分    類
無約束問題、約束問題等
主要研究
使目標達到最優
運    用
軍事、工程、管理等領域

目錄

  1. 1 發展歷史
  2. 2 常見方法
  3. 3 數學模型
  1. 4 問題分類
  2. ▪ 約束類型
  3. ▪ 目標約束函數
  1. ▪ 變量的類型
  2. 5 最優解最優值

最優化發展歷史

隨着科學技術的日益發展，許多工程的核心問題最終都歸結為優化問題。因此，最優化已經成為工程技術人員必不可少的計算工具。在計算機已經廣為普及的今天，一些大規模的優化問題的求解可以在一台普通的計算機上實現，使得最優化方法得到了比以往任何時候都更加廣泛的應用。如今，最優化方法已成為工程技術人員所必需具備的研究工具。

最優化常見方法

1. 梯度下降法（Gradient Descent）
梯度下降法是最早最簡單，也是最為常用的最優化方法。梯度下降法實現簡單，當目標函數是凸函數時，梯度下降法的解是全局解。一般情況下，其解不保證是全局最優解，梯度下降法的速度也未必是最快的。梯度下降法的優化思想是用當前位置負梯度方向作為搜索方向，因為該方向為當前位置的最快下降方向，所以也被稱為是”最速下降法“。最速下降法越接近目標值，步長越小，前進越慢。
2. 牛頓法（Newton's Method）和擬牛頓法（Quasi-Newton Methods）
牛頓法
牛頓法是一種在實數域和複數域上近似求解方程的方法。方法使用函數f(x)的泰勒級數的前面幾項來尋找方程f(x) = 0的根。牛頓法最大的特點就在於它的收斂速度很快。
擬牛頓法
擬牛頓法是求解非線性優化問題最有效的方法之一，其本質思想是改善牛頓法每次需要求解複雜的Hessian矩陣的逆矩陣的缺陷，它使用正定矩陣來近似Hessian矩陣的逆，從而簡化了運算的複雜度。擬牛頓法和最速下降法一樣只要求每一步迭代時知道目標函數的梯度。通過測量梯度的變化，構造一個目標函數的模型使之足以產生超線性收斂性。這類方法大大優於最速下降法，尤其對於困難的問題。另外，因為擬牛頓法不需要二階導數的信息，所以有時比牛頓法更為有效。如今，優化軟件中包含了大量的擬牛頓算法用來解決無約束，約束，和大規模的優化問題。
3. 共軛梯度法（Conjugate Gradient）
共軛梯度法是介於最速下降法與牛頓法之間的一個方法，它僅需利用一階導數信息，但克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hesse矩陣並求逆的缺點，共軛梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優化最有效的算法之一。在各種優化算法中，共軛梯度法是非常重要的一種。其優點是所需存儲量小，具有步收斂性，穩定性高，而且不需要任何外來參數。
4. 啓發式優化方法
啓發式方法指人在解決問題時所採取的一種根據經驗規則進行發現的方法。其特點是在解決問題時,利用過去的經驗，選擇已經行之有效的方法，而不是系統地、以確定的步驟去尋求答案。啓發式優化方法種類繁多，包括經典的模擬退火方法、遺傳算法、蟻羣算法以及粒子羣算法等等。
5. 拉格朗日乘數法的基本思想
作為一種優化算法，拉格朗日乘子法主要用於解決約束優化問題，它的基本思想就是通過引入拉格朗日乘子來將含有n個變量和k個約束條件的約束優化問題轉化為含有（n+k）個變量的無約束優化問題。拉格朗日乘子背後的數學意義是其為約束方程梯度線性組合中每個向量的係數。
將一個含有n個變量和k個約束條件的約束優化問題轉化為含有（n+k）個變量的無約束優化問題，拉格朗日乘數法從數學意義入手，通過引入拉格朗日乘子建立極值條件，對n個變量分別求偏導對應了n個方程，然後加上k個約束條件（對應k個拉格朗日乘子）一起構成包含了（n+k）變量的（n+k）個方程的方程組問題，這樣就能根據求方程組的方法對其進行求解。

最優化數學模型

最優化問題的共同特點是：求滿足一定條件的變量x1，x2，…，xn，使某函數f(x1，x2，…，xn)取得最大值或者最小值。由於f(x1，x2，…，xn)的最大問題可以轉化為-f(x1，x2，…，xn)的最小問題，所以較多時候只討論最小問題。這裏的函數f(x1，x2，…，xn)稱為目標函數或者評價函數；變量x1，x2，…，xn稱為決策變量；需要滿足的條件稱為約束條件；用以構成約束條件的函數稱為約束函數。

最優化問題分類

最優化約束類型

1、無約束問題
求x=(x1，x2，…，xn)T使函數f(x)=f(x1，x2，…，xn)達到最小值，記為min f(x)。
2、約束問題
根據約束函數的類型又可分為以下幾類：
（1）等式約束問題：求x=(x1，x2，…，xn)T使其在滿足l個等式約束條件hj(x)=0，j=1，2，…，l的情況下，使函數f(x)=f(x1，x2，…，xn)達到最小值，記為如圖1公式
圖1 圖1
（2）不等式約束問題：求x=(x1，x2，…，xn)T 使其在滿足m個不等式約束條件gi(x)≥0，i=1，2，…，m 的情況下，使函數f(x)=f(x1，x2，…，xn)達到最小值，記為如圖2公式
圖2 圖2
（3）混和約束問題或稱一般約束問題：求x=(x1，x2，…，xn)T使其在滿足m個不等式約束條件
gi(x)≥0，i=1，2，…，m以及l個等式約束條件hj(x)=0，j=1，2，…，l的情況下，使函數
f(x)=f(x1，x2，…，xn)達到最小值，記為如圖3公式
圖3 圖3
以上各問題中的函數f(x)=f(x1，x2，…，xn)稱為目標函數，函數gi(x)、hj(x)稱為約束函數。滿足約束條件的點x構成的集合，稱為可行解集合，亦稱可行區或可行域。 [1] 

最優化目標約束函數

最優化問題也稱為規劃問題。
如果最優化問題的目標函數為f(x)，約束條件為gi(x)≥0，i=1，2，…，m則：
當f(x)和gi(x)均為線性函數時，稱此最優化問題為線性規劃；
當f(x)和gi(x)不全為線性函數時，稱此最優化問題為非線性規劃；
當f(x)為二次函數，而gi(x)全為線性函數時，稱此最優化問題為二次規劃。

最優化變量的類型

對於最優化問題，如果變量x=(x1，x2，…，xn)T的各分量只能取整數，則相應的最優化問題稱為整數規劃。
如果變量x=(x1，x2，…，xn)T 的部分分量只能取整數，則相應的最優化問題稱為混合整數規劃。
如果變量x=(x1，x2，…，xn)T 的各分量只能取0和1，則相應的最優化問題稱為0-1規劃。

最優化最優解最優值

設最優化問題為(P)
，D={ x∣gi(x)≥0，i=1，2，…，m}
定義1：
如果有x*∈D使得
，即∃x*∈D，使得對∀x∈D有f(x)≥f(x*)，則稱x* 為問題（P）的全局最優解，稱f(x*)為全局最優值。
在定義中，如果當∀x∈D且x≠x*時恆有f(x)>f(x*)，則稱x*為問題（P）的嚴格全局最優解，稱f(x*)為嚴格全局最優值。
定義2：
如果有x*∈D及δ>0，使得當x∈D ∩ Nδ(x*)時恆有f(x)≥f(x*)，則稱x*為問題（P）的局部最優解，稱f(x*)為局部最優值。
這裏的Nδ(x*)={x∣‖x－x*‖ <δ}為x*的δ鄰域。範數‖▪‖指的是
同樣，定義中，如果當x≠x* 時可將 “≥”改為 “>”，則稱x* 為問題（P）的嚴格局部最優解，稱f(x*)為嚴格局部最優值。 [2] 
參考資料