最佳化問題

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

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

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

連續優化問題[編輯]

連續優化問題的規範形是^[1]

{\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}}

其中

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

組合優化問題A是四元組 $(I,\ f,\ m,\ g)$ ，其中

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

m(x,y)=g\left\{m(x,y'):y'\in f(x)\right\}.

對每個組合優化問題，有相應的決策問題：對某特定測度 $m_{0}$ ，是否存在可行解。例如，若有包含頂點u、v的圖G，優化問題可能是「找到u到v使用最少邊的路徑」，答案可能是4；相應的決策問題是「是否有u到v的路徑使用了少於10的邊數」，可以用簡單的「是否」回答。

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

^ Boyd, Stephen P.; Vandenberghe, Lieven. Convex Optimization (pdf). Cambridge University Press. 2004: 129. ISBN 978-0-521-83378-3.
^ Ausiello, Giorgio; et al, Complexity and Approximation Corrected, Springer, 2003, ISBN 978-3-540-65431-5