最佳化問題

數學、工程學、電腦科學和經濟學領域中，最佳化問題​（英語：Optimization problem）是指從所有可行解（英語：feasible solution）中找到最佳良的解的問題。

有關此主題的更廣泛資訊，請參見：數學最佳化。

根據變數是連續的或離散的，可將最佳化問題分為兩類：

• 具有離散變數的最佳化問題稱為離散最佳化，其中必須找到可數集合中的整數、排列或圖等對象。
• 具有連續變數的最佳化問題稱為連續最佳化，其中必須找到連續函數的最佳值。它們可以包括約束問題和多模態問題。

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

連續最佳化問題

連續最佳化問題的規範形是^[1] $${\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{j}(x)=0,\quad j=1,\dots ,p\end{aligned}}}$$ 其中

• ${\displaystyle f:\ \mathbb {R} ^{n}\to \mathbb {R} }$是n元向量x的目標函數，其值需要最小化；
• ${\displaystyle g_{i}(x)\leq 0}$稱作不等式約束；
• ${\displaystyle h_{j}(x)=0}$稱作等式約束；
• ${\displaystyle m\geq 0,\ p\geq 0}$。

若${\displaystyle m=p=0}$，則問題就是無約束最佳化問題。按照慣例，標準形定義了最小化問題。最大化問題可通過將目標函數取逆得到。

組合最佳化問題

主條目：組合最佳化

組合最佳化問題A是四元組${\displaystyle (I,\ f,\ m,\ g)}$，其中

• I是可行值集合；
• 給定可行值${\displaystyle x\in I,\ f(x)}$是可行解集；
• 給定可行值x、對應的可行解y，${\displaystyle m(x,\ y)}$表示y的測度，一般是正實數。
• g是目標函數，且須取極值。

我們的目標是為某可行值x找到最佳解，即可行解y，且滿足 $${\displaystyle m(x,y)=g\left\{m(x,y'):y'\in f(x)\right\}.}$$

對每個組合最佳化問題，有相應的決策問題：對某特定測度${\displaystyle m_{0}}$，是否存在可行解。例如，若有包含頂點u、v的圖G，最佳化問題可能是「找到u到v使用最少邊的路徑」，答案可能是4；相應的決策問題是「是否有u到v的路徑使用了少於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

外部連結

• How Traffic Shaping Optimizes Network Bandwidth. IPC. 2016-07-12 [2017-02-13].