最佳化問題

數學工程學計算機科學經濟學領域中,最佳化問題​(英語:Optimization problem)是指從所有可行解英語feasible solution中找到最優良的解的問題

根據變量連續的或離散的,可將最佳化問題分為兩類:

最佳化問題和決定性問題Decision problem)、功能性問題Function problem)不同,最佳化問題是:從問題的多個解中,求出最佳解。像背包問題(考慮不同價格和重量的物品,以及可承載一定重量的背包,如何選擇物品,使背包中的物品的總價最高)即屬於最佳化問題。

連續優化問題

連續優化問題的規範形[1]   其中

  •  n元向量x目標函數,其值需要最小化;
  •  稱作不等式約束
  •  稱作等式約束;
  •  

 ,則問題就是無約束優化問題。按照慣例,標準形定義了最小化問題最大化問題可通過將目標函數取逆得到。

組合優化問題

組合優化問題A是四元組 ,其中

  • I是可行值集合
  • 給定可行值 是可行解集;
  • 給定可行值x、對應的可行解y 表示y測度,一般是正實數。
  • g是目標函數,且須取極值

我們的目標是為某可行值x找到最優解,即可行解y,且滿足  

對每個組合優化問題,有相應的決策問題:對某特定測度 ,是否存在可行解。例如,若有包含頂點uvG,優化問題可能是「找到uv使用最少邊的路徑」,答案可能是4;相應的決策問題是「是否有uv的路徑使用了少於10的邊數」,可以用簡單的「是否」回答。

近似算法領域中,算法是為問題找到近似最優解。因此,通常的決策的定義是不充分的,因為其只指定了可行解。雖然可以引入合適的決策問題,但描述為優化問題更自然。[2]

另見

參考文獻

  1. ^ Boyd, Stephen P.; Vandenberghe, Lieven. Convex Optimization (pdf). Cambridge University Press. 2004: 129 [2024-03-07]. ISBN 978-0-521-83378-3. (原始內容存檔 (PDF)於2021-05-09). 
  2. ^ Ausiello, Giorgio; et al, Complexity and Approximation Corrected, Springer, 2003, ISBN 978-3-540-65431-5 

外部連結