优化问题

优化模型分工明确：约束排除不合法的选择，目标比较合法选择的好坏。安排一批作业时，“不能超过可用机器数”可以是约束，“最后一个作业尽早完成”可以是目标。改变任何一边都会改变问题：把截止时间写成必须满足的条件，与只在目标中惩罚迟到，并不一定产生相同答案。

同样，优化目标必须与决策粒度一致。若物品不可分，变量应表示整件选择；把它改成实数比例后，算法可能选择半件物品，这在新模型里完全合法，却不能直接交付原任务。先明确什么算一个可行对象，再讨论哪种算法更快，才能区分建模错误与求解错误。

还要区分“最接近的数值”和“确实达到它的选择”。在开区间 $F=(0,1)$ 上最小化 $f(x)=x$，可以让目标任意接近 $0$，所以最优值为 $0$；但 $0$ 不是可行点，没有最优解。一个算法不断给出更小的正数，并不因此发现了某个藏着的最小正数。

图中最大化 $f(x,y)=x+y$，可行域为 $F=\{(x,y):x\ge 0,y\ge 0,x+y\le 1\}$。最优值是 $1$，最优解集是 $F\cap \{x+y=1\}$，即两端点之间的线段，而不是整条无界直线。目标相同并不意味着最优选择唯一。

四种不同的求解结果 ​

在 $F=[0,1]$ 上最小化 $x^2$，最优值 $0$ 在 $x=0$ 取得。把可行域改成 $(0,1)$，最优值仍为 $0$，却不再取得：这叫下确界有限但没有最小值。

若约束同时要求 $x\ge 1$ 和 $x\le 0$，则 $F=\varnothing$，问题不可行。若 $F=\mathbb{R}$、$f(x)=x$，则对任何实数阈值都能找到更低的目标值，问题向下无界，$v^{\ast }=-\mathrm{\infty }$。不可行是没有合法选择，无界是存在目标越来越低的合法选择，两者不能用同一个“没有找到答案”混过去。

若使用可取扩展实值的目标，需要重新说明约定。常见做法是在环境空间中令不可行点的目标为 $+\mathrm{\infty }$；而若允许某个可行点直接取得 $-\mathrm{\infty }$，就不能再把“$v^{\ast }=-\mathrm{\infty }$”不加解释地当成上述实值目标的无界情形。

条件怎样保证最优解存在 ​

有限、非空的 $F$ 上，实值目标必有最小值，不需要连续性。对无限集合，存在性则需要额外结构。在 ${\mathbb{R}}^d$ 中，若 $F$ 非空且紧致、$f$ 连续，极值定理理路极值定理Extreme value theorem连续实值函数在非空紧空间上取得最大值和最小值。保证最优值被取得。闭且有界在有限维欧氏空间中给出紧致，不能不加条件地推广到任意无限维空间。

紧致是充分条件而非必要条件：在整个 $\mathbb{R}$ 上最小化 $x^2$ 仍有解。这里目标随着 $|x|\to \mathrm{\infty }$ 趋于 $+\mathrm{\infty }$，把足够好的候选限制在有界范围内；这类强制增长条件也能帮助建立存在性。

局部检查与全局结论 ​

当可行域带有距离或拓扑时，局部最优只要求附近没有更好可行点，全局最优要求整个 $F$ 都没有更好点。可导目标的梯度为零一般只是内点局部极值的必要条件：$f(x)=x^3$ 在 $0$ 的导数为零，却既不是局部最大也不是局部最小。边界最优点则未必满足梯度为零。

若 $F$ 凸且 $f$ 凸，每个局部最小点都是全局最小点。因为若远处存在更好点 $y$，沿 $x$ 到 $y$ 的线段走任意小的一步，凸性都会给出比 $f(x)$ 更低的值，立即违反局部最优。这项结论来自目标与可行域的结构，不来自优化算法声称“已经收敛”。

好的候选解与质量证书 ​

对最小化问题，一个可行候选 $\hat{x}$ 给出上界 $v^{\ast }\le f(\hat{x})$。若还能证明一个有限实数下界 $L\le v^{\ast }$，便同时知道 $v^{\ast }$ 有限，并得到

所以 $f(\hat{x})-L\le \epsilon$ 是一个可检验的加性误差证书。启发式算法可能快速找到可行解，却未必同时提供这样一个下界；“表现不错”与“距离最优值至多多少”是不同层次的结论。

例如把总处理量为 $17$ 的不可分作业安排到两台相同机器，最小化最大完工时间。无论怎样分配，至少一台承担不少于 $17/2$ 的工作量，所以 $L=8.5$ 是下界；若一个具体安排的两台负载为 $9$ 和 $8$，就知道其目标值与最优值相差至多 $0.5$。若所有作业时长为整数，最大负载也为整数，下界可加强为 $9$，于是这个安排已经最优。可行安排给上界，所有安排共同满足的限制给下界，两类证据合起来才得到结论。

乘性近似如 $f(\hat{x})\le \alpha v^{\ast }$ 通常用于非负目标，并需处理 $v^{\ast }=0$ 等边界。目标可以为负时，直接使用比值可能失去预期含义。即使目标非负，平移目标也会改变近似比：原最优值 $1$、候选值 $2$ 的比值为 $2$，统一加上 $100$ 后变成 $102/101$，虽然最优解集合完全相同。选择误差标准应先于比较求解器输出。

数学模型之外还要有计算模型 ​

同一个最短路目标，可以把路径作为边序列显式表示，也可以把可行性隐藏在查询接口后面；可获得的信息不同，复杂度问题便不同。数值优化还要说明系数编码、精度与停止规则。连续变量本身不意味着困难，离散变量本身也不意味着必须穷举；结构比这一二分更能决定方法。

学习算法中的经验风险最小化也是优化问题，但求解目标与统计目标分属两层：更精确地最小化训练损失，说明优化误差变小；是否改善总体预测，还取决于样本、模型类与泛化控制。把这两种误差分开，才知道继续优化正在解决哪一个问题。