跳转到内容

最优化问题

本页使用了标题或全文手工转换
维基百科,自由的百科全书

数学工程学电脑科学经济学领域中,最优化问题,或称优化问题(英语:Optimization problem)是指从所有可行解英语feasible solution中找到最优良的解的问题

根据变量连续的或离散的,可将最优化问题分为两类:

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

连续优化问题

连续优化问题的规范形[1] 其中

  • n元向量x目标函数,其值需要最小化;
  • 称作不等式约束
  • 称作等式约束;

,则问题就是无约束优化问题。按照惯例,标准形定义了最小化问题最大化问题可通过将目标函数取逆得到。

组合优化问题

组合优化问题A是四元组,其中

  • I是可行值集合
  • 给定可行值是可行解集;
  • 给定可行值x、对应的可行解y表示y测度,一般是正实数。
  • g是目标函数,且须取极值

我们的目标是为某可行值x找到最优解,即可行解y,且满足

对每个组合优化问题,有相应的决策问题:对某特定测度,是否存在可行解。例如,若有包含顶点uvG,优化问题可能是“找到uv使用最少边的路径”,答案可能是4;相应的决策问题是“是否有uv的路径使用了少于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 

外部链接