数学、工程学、计算机科学和经济学領域中，最佳化问题-{zh-cn:，或称优化问题;zh-tw:;}-（）是指从所有中找到最优良的解的问题。
根据变量是连续的或离散的，可将最佳化问题分为两类：
- 具有离散变量的最佳化问题称为离散优化，其中必须找到可数集合中的整数、排列或图等对象。
- 具有连续变量的最佳化问题称为连续优化，其中必须找到连续函数的最优值。它们可以包括约束问题和多模态问题。
搜索空间
在优化问题中，搜索空间是指所有满足问题约束条件、目标或目的的可能点或解的集合。这些点代表了可行的解，可以通过评估这些解来根据目标函数找到最优解。搜索空间通常由待优化的函数的定义域来定义，涵盖了所有满足问题要求的有效输入。
搜索空间的大小和复杂度会因问题而异，差异可能很大。例如，在连续优化问题中，搜索空间可能是由边界或约束条件定义的多维实值域。而在离散优化问题（如组合优化）中，搜索空间可能由有限个排列、组合或配置集合组成。
在某些情况下，“搜索空间”一词也可能指优化问题域本身，例如确定定义问题时最合适的变量或参数集。理解并有效探索搜索空间对于设计高效的算法至关重要，因为这直接影响计算复杂度以及找到最优解的可能性。
连续优化问题
连续优化问题的规范形是
\begin{align}
&\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{align}
其中
- f:\ \mathbb{R}^n\to \mathbb{R}是n元向量x的目标函数，其值需要最小化；
- g_i(x)\le 0称作不等式约束；
- h_j(x)=0称作等式约束；
- m\ge 0,\ p\ge 0。
若m=p=0，则问题就是无约束优化问题。按照惯例，标准形定义了最小化问题。最大化问题可通过将目标函数取逆得到。
组合优化问题
组合优化问题A是四元组(I,\ f,\ m,\ g)，其中
- I是可行值集合；
- 给定可行值x\in I,\ f(x)是可行解集；
- 给定可行值x、对应的可行解y，m(x,\ y)表示y的测度，一般是正实数。
- 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的边数”，可以用简单的“是否”回答。
近似算法领域中，算法是为问题找到近似最优解。因此，通常的决策的定义是不充分的，因为其只指定了可行解。虽然可以引入合适的决策问题，但描述为优化问题更自然。
另见
*
*
*
- 函数问题
- 运筹学
*
- 搜索问题
*
参考文献
外部链接
*
评论 (0)