形式陈述

优化问题由可行集 $F$、目标函数 $f:F\to \mathbb{R}\cup \{\pm \mathrm{\infty }\}$ 以及最小化或最大化方向组成。最优值是 $\underset{x\in F}{inf}f(x)$ 或 $\underset{x\in F}{sup}f(x)$；达到该值的点才是最优解。可行集可能为空，最优值可能无界或虽有限却不被取得，因此“问题有定义”不等于“存在最优解”。

直觉

约束决定哪些方案允许，目标函数给方案打分；算法要在允许方案中找到最好者或证明不存在。

例子与边界

最短路把路径作为可行解、长度作为目标；SAT 可视为寻找满足约束的布尔赋值。开区间 $(0,1)$ 上最小化 $x$ 的下确界为 0，但没有最优点。离散优化、连续优化和随机优化的表示与复杂度不同，不能只凭同一符号混为一类。

推论与应用

该模型统一线性规划、组合优化、机器学习训练、资源配置与控制问题，并为可行性、最优性和近似保证提供共同语言。

参考资料

• Bernhard Korte and Jens Vygen, Combinatorial Optimization, 6th ed., Springer, 2018，Chs. 4–11。
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。