优化问题 | Codeboy's Blog

形式陈述

问题、最优值与解集

一个最小化问题由决策空间、可行集 $F$ 和目标函数

f:F\longrightarrow\overline{\mathbb R}

组成，其中 $\overline{\mathbb R}=\mathbb R\cup\{\pm\infty\}$ 按通常的全序比较目标值。最优值与最优解集分别是

v^*=\inf_{x\in F}f(x), \qquad \operatorname*{argmin}_{x\in F}f(x) =\{x\in F:f(x)=v^*\}.

这两个对象不能混写： $v^*$ 是一个有序值，argmin 是达到该值的可行点集合。最大化问题把 infimum 换成 supremum；对实值目标也可通过最小化 $-f$ 转换方向。

可行集为空时问题不可行； $v^*=-\infty$ 时最小化目标向下无界； $v^*$ 有限而 argmin 为空时，下确界存在却没有点达到。只有当 $v^*\in\mathbb R$ 且 argmin 非空时，问题才同时拥有有限最优值和至少一个最优解。

约束表示与算法边界

可行集常由等式、不等式、组合规则或一个判定过程给出，但这些只是 $F$ 的表示。同一集合可以有冗余约束或完全不同的坐标描述；增加整数限制、改变允许精度或更换变量编码，也可能得到不同的可行集，而不只是换一种写法。

优化问题规定“哪些点可行、按什么次序比较”，算法则说明怎样访问目标和约束、何时停止以及交付什么证书。梯度、对偶、局部搜索和枚举都需要额外结构；不能从一个 argmin 符号直接推出可计算性、唯一性或运行时间。近似保证也必须声明它比较目标差、相对比率还是某种可行性违反，尤其在最优值为零或可取负时不能含混。

直觉

优化问题先规定“哪些对象能选”和“怎样比较好坏”，再谈算法怎样找到它们。下确界只描述可行值能逼近的边界，argmin 还要求某个可行点真正达到这条边界；可行性、有限最优值与最优解存在因此是三件不同的事。

例子与边界

存在、多解与不取到

在闭区间 $[0,2]$ 上最小化 $(x-1)^2$ ，最优值为 $0$ ，唯一最优点为 $x=1$ 。这里连续性与紧致性共同保证取到最小值；它们是这个实例的存在条件，不属于所有优化问题的定义。

在开区间 $(0,1)$ 上最小化 $f(x)=x$ 时， $v^*=0$ ，但每个可行点都还能向左改进，所以 argmin 为空。把下确界写成“最优解 0”会把不属于可行集的点伪装成答案。

在线性约束 $x+y\le1$ 、 $x,y\ge0$ 上最大化 $x+y$ ，整条边 $x+y=1$ 都是最优解，而最优值仍只有一个。若再要求 $x,y\in\{0,1\}$ ，可行对象从连续三角形变成三个离散点；目标公式未变，问题却已经不同。

线性规划、组合优化和统计经验准则都可实例化这套接口，但各自的结构与信息协议必须另行声明。特别是精确求出经验目标，并不自动控制未知分布上的总体风险；后者还包含统计学习问题的抽样层。

推论与应用

这套接口覆盖线性规划、组合优化、经验风险最小化与连续数值优化。进入具体领域时必须补上可行集表示、目标访问方式、数值精度和证书类型；近似比、加性误差或约束违反也应与最优值的符号和尺度相容。

参考资料

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。

形式陈述 ​

问题、最优值与解集 ​

约束表示与算法边界 ​

存在、多解与不取到 ​

反向链接

形式陈述

问题、最优值与解集

约束表示与算法边界

存在、多解与不取到