最佳化問題

数学、工程学、计算机科学和经济学領域中，最佳化问题-{zh-cn:，或称优化问题;zh-tw:​;}-（Template:Lang-en）是指从所有Template:Link-en中找到最优良的解的问题。

根据变量是连续的或离散的，可将最佳化问题分为两类：

• 具有离散变量的最佳化问题称为离散优化，其中必须找到可数集合中的整数、排列或图等对象。
• 具有连续变量的最佳化问题称为连续优化，其中必须找到连续函数的最优值。它们可以包括约束问题和多模态问题。

最佳化问题和决定性问题（Template:Lang）、功能性问题（Template:Lang）不同，最佳化问题是：从问题的多个解中，求出最佳解。像背包问题（考虑不同价格和重量的物品，以及可承载一定重量的背包，如何选择物品，使背包中的物品的总价最高）即属于最佳化问题。

连续优化问题

连续优化问题的规范形是 $$\begin{array}{cccc}& \underset{x}{\mathrm{minimize}}& & f(x)\\ & \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& & g_i(x)\le 0,i=1,\dots ,m\\ & & & h_j(x)=0,j=1,\dots ,p\end{array}$$ 其中

• $f:{ℝ}^n\to ℝ$是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\{m(x,y^{\prime }):y^{\prime }\in f(x)\}.$$

对每个组合优化问题，有相应的决策问题：对某特定测度$m_0$，是否存在可行解。例如，若有包含顶点u、v的图G，优化问题可能是“找到u到v使用最少边的路径”，答案可能是4；相应的决策问题是“是否有u到v的路径使用了少于10的边数”，可以用简单的“是否”回答。

近似算法领域中，算法是为问题找到近似最优解。因此，通常的决策的定义是不充分的，因为其只指定了可行解。虽然可以引入合适的决策问题，但描述为优化问题更自然。

另见

• 计数问题
• 设计优化
• 艾克兰德变分原理

• 函数问题

• 运筹学
• 满意原则
• 搜索问题
• 半无限规划

外部链接

• Template:Cite web