最佳化問題

数学、工程学、计算机科学和经济学領域中，最佳化问题，或称优化问题（英語：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