3.1 优化问题的语言与分类

前一章的多数结论以取什么值最好的形式收尾：极大似然估计选择使似然最大的参数，最小二乘选择使残差平方和最小的系数，正则化估计在选择拟合程度时还要权衡复杂度的代价。这些问题的共同结构是：在一组允许的选择中，寻找使某个指标达到最优的那一个。把这一结构形式化，就得到优化问题（optimization problem）。

本节的任务是建立一套描述优化问题的语言，并给出一张分类地图。语言部分包括决策变量、目标函数、约束与最优解的定义；分类部分按凸性、光滑性、约束形式与信息完整程度划分问题的类型，并说明每一类对应的算法家族。分类之所以重要，原因在于优化没有万能方法：同一个算法在凸问题上可能有全局收敛保证，在非凸问题上只保证收敛到驻点；在光滑问题上可以用梯度，在非光滑问题上必须改用次梯度或近端算子。选错类别的代价超出效率范围，收敛保证会完全失效。

本节最后讨论凸性为什么在优化中处于核心位置，以及优化与机器学习之间的对应关系。后续各节都建立在本节的记号之上。

3.1.1 从实际问题到优化问题

三个组成部分

一个优化问题由三部分组成。

决策变量（decision variable）$\mathbf{x}\in {\text{R}}^n$ 表示可以调整的量，$n$ 是问题的维数。它是待求的对象，取值空间由问题本身决定：资源分配量非负、概率向量落在单纯形上、网络权重是任意实数。

目标函数（objective function）$f:{\text{R}}^n\to \text{R}$ 是需要最小化或最大化的量。它把每个决策方案映射为一个数值，使不同方案可以比较。

约束（constraint）限定决策变量的可行范围。约束分为等式约束与不等式约束两类，前者写成 $h_j(\mathbf{x})=0$，后者写成 $g_i(\mathbf{x})\le 0$。满足全部约束的变量集合称为可行域（feasible set），记作

$$\mathcal{X}=\{\mathbf{x}\in {\text{R}}^n|g_i(\mathbf{x})\le 0,i=1,\dots ,m;h_j(\mathbf{x})=0,j=1,\dots ,p\}$$

无约束问题的可行域是整个 ${\text{R}}^n$。

标准形式

为了叙述统一，约定优化问题一律写成最小化形式：

$$\begin{array}{rl}\underset{\mathbf{x}}{min}& f(\mathbf{x})\\ \text{s.t.}& g_i(\mathbf{x})\le 0,i=1,\dots ,m\\ & h_j(\mathbf{x})=0,j=1,\dots ,p\end{array}$$

最大化问题通过取负号转化：$maxf(\mathbf{x})$ 等价于 $min-f(\mathbf{x})$，最优解相同，最优值相差一个符号。后文不再区分两者。

四个例子

最小二乘拟合。给定数据 $({\mathbf{x}}_i,y_i)$，寻找使预测误差平方和最小的系数：

$$\underset{\mathit{\beta }}{min}\sum _{i=1}^n{(y_i-{\mathbf{x}}_i^T\mathit{\beta })}^2$$

无约束、目标函数是二次函数、凸。上一章已给出闭式解，这类问题是优化的理想情形。

投资组合。给定各资产的预期收益向量 $\mathit{\mu }$ 与协方差矩阵 $\mathbf{\Sigma }$，在目标收益下最小化风险：

$$\begin{array}{rl}\underset{\mathbf{w}}{min}& {\mathbf{w}}^T\mathbf{\Sigma }\mathbf{w}\\ \text{s.t.}& \sum _i{w}_i=1,{\mathbf{w}}^T\mathit{\mu }\ge r,w_i\ge 0\end{array}$$

二次目标、线性约束、凸问题。$\mathbf{w}$ 是各资产的权重，等式约束要求资金全部投出，不等式约束禁止做空。

逻辑回归训练。给定二分类数据，寻找使对数似然最大的系数：

$$\underset{\mathit{\beta }}{min}\sum _{i=1}^n[\log (1+e^{{\mathbf{x}}_i^T\mathit{\beta }})-y_i{\mathbf{x}}_i^T\mathit{\beta }]$$

无约束、目标函数光滑凸、没有闭式解。这类问题需要迭代算法，梯度法与牛顿法都可以用。

物流调度。把货物从若干个仓库运到若干个客户点，最小化总运输成本，同时满足供应量与需求量。若运输量可以连续分配，问题是线性规划；若要求车辆按整条路线服务客户，问题是组合优化，决策变量取整数值，可行域离散。

四个例子展示了优化问题在结构上的差别：目标函数的形状、约束的类型、变量的取值方式各不相同。下一小节把这些差别整理成分类。

3.1.2 最优解的概念

全局最优与局部最优

全局最优解（global minimizer）是可行域上使目标函数取值最小的点：

$$f({\mathbf{x}}^{\ast })\le f(\mathbf{x}),\mathrm{\forall }\mathbf{x}\in \mathcal{X}$$

对应的函数值 $f({\mathbf{x}}^{\ast })$ 称为最优值（optimal value），记作 $f^{\ast }$。全部全局最优解构成的集合称为最优解集（optimal set）。最优解集可以包含多个点（目标函数有平坦区域时），也可以为空（目标函数在可行域上无下界时）。

局部最优解（local minimizer）只要求在某个邻域内最优：存在 $\delta >0$，使得

$$f({\mathbf{x}}^{\ast })\le f(\mathbf{x}),\mathrm{\forall }\mathbf{x}\in \mathcal{X}\cap \{\parallel \mathbf{x}-{\mathbf{x}}^{\ast }\parallel \le \delta \}$$

局部最优解可能不是全局最优。梯度类算法通常只能保证收敛到局部最优或驻点，这是非凸优化与凸优化在保证强度上的根本差别。

若不等式对邻域内所有 $\mathbf{x}\ne {\mathbf{x}}^{\ast }$ 严格成立，称为严格局部最优解。允许目标值略微高于最优值的点称为近似最优解：给定精度 $ϵ>0$，满足 $f(\mathbf{x})\le f^{\ast }+ϵ$ 的点都是可接受的输出。实际算法给出的都是近似最优解，收敛速率描述的是达到给定精度所需的迭代次数。

存在性与紧性

最优解是否存在需要单独讨论。Weierstrass 定理给出一个充分条件：若可行域 $\mathcal{X}$ 是非空紧集（有界闭集），且目标函数连续，则最优解存在。

非紧的可行域上最优解可能不存在。例：$\underset{x}{min}{e}^{-x}$ 在 $\text{R}$ 上的下确界为 $0$，但没有任何点取到 $0$，因为 $e^{-x}$ 只在无穷远处趋于零。函数值序列不断下降却不收敛到任何点，这类情形称为下确界不可达。

处理方式有两种：把问题限制在一个紧集上（加上变量的上下界，这在工程问题中往往合理），或者接受近似最优解而不追求最优值的精确取到。机器学习中的无约束问题通常属于后一类：目标函数在无穷远处趋于常数或下降但无界，算法给出的是在有限时间内达到的近似解。

最优解不唯一的常见原因

平局与对称性是主要原因。目标函数含常数方向（在某个方向上取值不变）时，解在一条直线或一个平面上都不变；问题具有对称性时，对称变换把一个最优解映射为另一个，两者同时最优。机器学习中的非凸问题还可能出现多个孤立的局部最优，它们之间的距离很远，对应的预测性能相近。

解不唯一会带来两个实际影响。算法输出的具体点取决于初始值与迭代路径，报告结果时需要说明这一点而不是把某一次运行的结果当作唯一答案。解的稳定性也受影响：数据微小扰动可能使算法跳到另一个解上，使结果看起来不连续。

import numpy as np

# 一维非凸函数的局部最优与全局最优
def f(x):
    return np.sin(3 * x) + 0.3 * x ** 2 - 0.5 * x

grid = np.linspace(-4, 4, 2001)
values = f(grid)

# 全局最优
idx = np.argmin(values)
print(f"网格上的全局最优：x = {grid[idx]:.4f}，f = {values[idx]:.4f}")

# 局部最优：比左右相邻网格点都小的位置
interior = np.arange(1, len(grid) - 1)
local = interior[(values[interior] < values[interior - 1]) & (values[interior] < values[interior + 1])]
print("全部局部最优：")
for i in local:
    print(f"  x = {grid[i]:+.4f}，f = {values[i]:+.4f}")
# 多个局部最优中只有一个是全局最优，梯度下降从不同初值出发会落到不同的点

3.1.3 优化问题的分类

按凸性分类

凸优化问题（convex optimization）要求目标函数是凸函数、不等式约束函数是凸函数、等式约束函数是仿射函数。凸问题的局部最优解就是全局最优解，这一性质使算法可以给出全局收敛保证，也使最优性条件从必要变为充分（3.2 节与 3.6 节）。

非凸优化问题（non-convex optimization）包括其余全部情形。深度学习训练、混合模型拟合、聚类都属于这一类。非凸问题的困难不在于算法无法运行，而在于理论保证的种类发生变化：可以证明收敛到驻点（梯度为零的点），可以证明逃出鞍点的速度，但一般无法证明收敛到全局最优。

介于两者之间的是有结构可以利用的非凸问题。目标函数在局部满足凸性的问题（如逐段凸函数）可以用凸方法分段处理；目标函数是凸函数与低秩约束的组合时，可以用凸松弛近似。把这些结构识别出来，是非凸问题求解的主要工作。

按约束分类

无约束优化（unconstrained optimization）的可行域是整个空间，最优性条件只涉及目标函数的梯度与海森矩阵，算法设计只需要考虑函数的局部信息。线性回归、逻辑回归、神经网络训练都属于这一类。

有约束优化（constrained optimization）分为等式约束、不等式约束与两者混合三类。约束改变了最优性条件的形式：最优点不必是梯度为零的点，梯度方向可以被约束边界的法方向抵消一部分，这正是拉格朗日乘子与 KKT 条件的来源（3.6 节）。

约束的存在还改变了算法的可行路径。投影梯度法在每步之后把点投影回可行域；内点法在目标函数中加入障碍项，把约束逐步推向边界；罚函数法把约束违反量加入目标，把有约束问题转化为一系列无约束问题。三类方法在 3.6 节与 3.7 节讨论。

按光滑性分类

光滑优化（smooth optimization）要求目标函数可微且梯度连续（通常还要求梯度 Lipschitz 连续）。光滑问题可以用梯度法，收敛速率与梯度的 Lipschitz 常数直接相关。

非光滑优化（nonsmooth optimization）出现在目标函数含绝对值、范数或最大值函数时。$L_1$ 正则化的目标包含 $\parallel \mathit{\beta }{\parallel }_1$，在坐标轴上是不可导的尖点。非光滑问题的处理方式有两种：改用次梯度（收敛慢），或者利用函数的特殊结构使用近端算子（收敛快）。后者是稀疏优化中的主流方法，见 3.7 节。

按信息与规模分类

确定性优化给定精确的目标函数与梯度；随机优化（stochastic optimization）只能获取带噪声的函数值或梯度估计。机器学习的训练目标通常是全数据集上的期望损失，实际计算只能用一个小批量的样本估计梯度，因此属于随机优化。噪声的存在改变了步长的选择规则：步长必须随迭代衰减或按噪声水平自适应，固定的大步长会导致在最优解附近持续震荡。

稀疏与大规模问题还带来存储与计算上的限制。变量数达到百万级时，$n\times n$ 的海森矩阵无法存储（需要 ${10}^{12}$ 个浮点数），只能使用一阶方法或利用矩阵的低秩与稀疏结构。变量可分离或数据可分解时，分布式与并行算法可以把计算分摊到多台机器上。

下表汇总四类划分与对应的代表算法。

划分维度	类别	代表算法
凸性	凸问题	内点法、投影梯度、近端梯度
	非凸问题	随机梯度下降、信赖域、拟牛顿
约束	无约束	梯度下降、牛顿法、BFGS
	有约束	投影法、罚函数、增广拉格朗日、内点法
光滑性	光滑	梯度法、加速梯度、牛顿法
	非光滑	次梯度法、近端梯度、ADMM
信息	确定性	全套确定性算法
	随机	SGD、方差缩减、自适应方法

3.1.4 凸性为什么处于核心位置

凸性把优化从启发式搜索变成有完备理论的数学问题。它带来四项具体收益。

局部即全局。凸函数的任一局部最优解都是全局最优解。证明只用到凸性的定义：若 ${\mathbf{x}}^{\ast }$ 局部最优但存在 $\mathbf{y}$ 使 $f(\mathbf{y})<f({\mathbf{x}}^{\ast })$，则线段上靠近 ${\mathbf{x}}^{\ast }$ 的点（由凸组合给出）的函数值可以严格小于 $f({\mathbf{x}}^{\ast })$，与局部最优矛盾。这一性质消除了初值选择的顾虑：凸问题从任何初值出发都会收敛到同一个最优值。

最优性条件由必要变为充分。一般问题中梯度为零只是最优解的必要条件（还可能是鞍点或极大点），凸问题中梯度为零是最优解的充要条件。条件变强之后，算法停止准则也变得可靠：梯度范数足够小就是收敛的证据。

对偶理论成立。凸问题在一定条件下满足强对偶，原问题与对偶问题的最优值相等。这一结论给出了检验最优性的方法（原问题的可行解与对偶问题的可行解给出最优值的上下界，两者接近时解接近最优），也给出了分解算法的结构，见 3.6 节。

收敛速率有明确的表达式。凸问题的收敛速率由两个常数决定：梯度的 Lipschitz 常数 $L$ 与强凸参数 $m$，两者的比值是条件数 $\kappa =L/m$。速率表达式的普遍形式是精度 $ϵ$ 所需的迭代次数关于 $\kappa$ 的某个幂次，算法之间的差别就体现在这个幂次上（3.3 节与 3.4 节）。

非凸问题缺少这四项收益，只能借助局部凸性、随机扰动的分析或经验规律来处理。判断一个实际问题能否转化为凸问题，因而成为建模阶段最有价值的工作之一。

3.1.5 优化在机器学习中的位置

训练即优化

监督学习的目标是找一个函数使预测误差的期望最小：

$$\underset{\mathit{\theta }}{min}{E}_{(\mathbf{x},y)\sim \mathcal{D}}\left[\ell (y,f_{\mathit{\theta }}(\mathbf{x}))\right]$$

真实分布 $\mathcal{D}$ 未知，实践中用训练集上的经验风险（empirical risk）替代：

$$\underset{\mathit{\theta }}{min}\frac{1}{n}\sum _{i=1}^n\ell (y_i,f_{\mathit{\theta }}({\mathbf{x}}_i))$$

这一替换把统计问题转化为优化问题，两者的关系是上一章反复出现的主题：优化在训练集上做，泛化靠正则化与交叉验证控制。

常见损失与正则项的优化性质

组成部分	函数形式	凸性	光滑性
平方损失	$(y-{\mathbf{x}}^T\mathit{\beta }{)}^2$	凸	光滑
逻辑损失	$\log (1+e^{-y{\mathbf{x}}^T\mathit{\beta }})$	凸	光滑
合页损失	$max(0,1-y{\mathbf{x}}^T\mathit{\beta })$	凸	非光滑
$L_2$ 正则	$|\mathit{\beta }{|}_2^2$	凸	光滑
$L_1$ 正则	$|\mathit{\beta }{|}_1$	凸	非光滑
神经网络损失	复合函数	非凸	一般光滑

表格的意义在于把模型与算法对应起来：平方损失加 $L_2$ 正则可以写成线性方程组求解（最小二乘的正则化版本），逻辑损失加 $L_1$ 正则需要近端梯度法，含合页损失的支持向量机需要二次规划或坐标下降，神经网络的训练依赖随机的、只利用一阶信息的算法。

正则化的优化解释

上一章把正则化解释为对复杂度的惩罚或先验的体现，从优化的角度看它还有第三层解释：约束的软化。硬约束问题

$$\underset{\mathit{\theta }}{min}L(\mathit{\theta })\text{s.t.}\parallel \mathit{\theta }\parallel \le c$$

与其拉格朗日形式

$$\underset{\mathit{\theta }}{min}L(\mathit{\theta })+\lambda \parallel \mathit{\theta }\parallel$$

在一定条件下有相同的解集，$\lambda$ 与 $c$ 之间一一对应。这一等价关系（3.6 节给出推导）说明带正则的优化与带约束的优化是同一个问题的两种写法：前者便于用无约束算法求解，后者便于控制约束的物理含义。

三类不同的优化

机器学习系统中同时存在三种优化，它们的对象与时间尺度不同。训练优化在固定模型结构与超参数下寻找参数，是本章讨论的主体。超参数优化在外层搜索学习率、正则强度、网络结构这些量，目标函数没有解析形式且每次评估代价高昂，常用贝叶斯优化与网格搜索。推理与决策优化在模型训练完成后求解，例如在推荐系统中求解满足约束的最优分配、在强化学习中求解最优策略。三者不宜混用同一套算法与收敛判据。

3.1.6 困难的主要来源

非凸性与鞍点

非凸问题的驻点中，梯度为零的点既可能是局部极小，也可能是局部极大或鞍点（saddle point）。高维空间中鞍点的数量通常远多于局部极小：一个函数的二阶导数在各个方向上符号不同即可构成鞍点，维度越高这种组合越容易出现。梯度下降在鞍点附近会停滞，改进方法包括加入动量、使用二阶信息判断负曲率方向、以及利用随机梯度的噪声自然逃离。3.8 节讨论这些机制。

病态条件数

目标函数的等高线是狭长的椭球时，不同方向上的曲率差别很大，梯度方向与指向最优解的方向严重偏离，梯度下降在窄方向上反复震荡。这一现象的定量描述由条件数给出，收敛速率中包含条件数因子，条件数越大收敛越慢。数据特征的尺度差异、变量之间的强相关都会造成高条件数，处理方式包括特征标准化、白化变换与使用二阶信息。3.3 节给出条件数与收敛速率的定量关系。

噪声与步长

随机优化的梯度估计带有方差，噪声使迭代点在最优点附近持续游走。步长必须与噪声水平匹配：过大则震荡，过小则进展缓慢。处理方式包括步长衰减（如 $1/t$ 或 $1/\sqrt{t}$ 的衰减率）、自适应方法（按梯度平方的滑动平均调整每个坐标的步长）、以及方差缩减技术（用控制变量降低估计方差）。3.4 节讨论这些方法。

规模与数值精度

大规模问题受内存与计算两方面的限制。海森矩阵无法存储，正逆运算无法承受，只能使用一阶方法或低秩近似；数据量过大时单次遍历代价高昂，只能使用小批量。数值上还要注意运算的稳定性：指数函数可能溢出，对数和的计算需要专门的技巧（如 log-sum-exp），梯度可能因量纲差异跨越多个数量级。

import numpy as np

# 条件数对梯度下降的影响：同一个二次函数，条件数不同则收敛速度差别很大
def gradient_descent_quadratic(kappa, steps=200, lr=0.1):
    """最小化 f(x) = 0.5 * (x1^2 + kappa * x2^2)，最优解在原点"""
    L = kappa                     # 最大曲率
    x = np.array([1.0, 1.0])
    for _ in range(steps):
        g = np.array([x[0], kappa * x[1]])
        x = x - lr * g / L        # 用 L 归一化步长，便于比较
    return x

for kappa in [1, 10, 100, 1000]:
    x_final = gradient_descent_quadratic(kappa)
    print(f"条件数 {kappa:5d}：迭代 200 步后 |x| = {np.linalg.norm(x_final):.3e}")
# 条件数从 1 增到 1000，同样的迭代次数下残差从接近 0 增到 0.7 以上

3.1.7 本节小结

先分类，再选算法

本节建立了优化问题的描述语言：决策变量、目标函数与约束构成问题的三要素，可行域是约束确定的取值集合，标准形式统一为最小化。最优解分为全局与局部两类，存在性需要紧性与连续性条件，最优解不唯一的情况会带来结果对初值与扰动的依赖。问题按四个维度分类：凸性、约束形式、光滑性与信息完整程度，每一类对应一组算法。凸性是核心维度，它带来局部即全局、条件由必要变充分、强对偶成立与收敛速率可表达四项收益，使算法具备全局保证。机器学习中的训练、超参数搜索与决策是三类不同的优化，损失函数与正则项的性质决定了可用的算法家族。困难主要来自非凸性、病态条件数、梯度噪声与规模限制，后续各节围绕这四条逐一展开。

接下来先补上判断凸性与光滑性的工具。3.2 节讨论凸集与凸函数，给出判定条件与保凸运算，引入共轭函数与次梯度，并以二次上界与下界的形式给出光滑性与强凸性的定量刻画。这三组工具是后面所有收敛性分析的公共基础。

练习题

第 1 题 概念推导

设 $f:{\text{R}}^n\to \text{R}$ 是凸函数，$\mathcal{X}$ 是非空凸集。证明 $f$ 在 $\mathcal{X}$ 上的任一局部最优解都是全局最优解；并举例说明目标函数非凸时该结论不成立。

参考答案

证明：设 ${\mathbf{x}}^{\ast }$ 是局部最优解，即存在 $\delta >0$ 使 $f({\mathbf{x}}^{\ast })\le f(\mathbf{x})$ 对所有 $\mathbf{x}\in \mathcal{X}$ 且 $\parallel \mathbf{x}-{\mathbf{x}}^{\ast }\parallel \le \delta$ 成立。反设存在 $\mathbf{y}\in \mathcal{X}$ 使 $f(\mathbf{y})<f({\mathbf{x}}^{\ast })$。

取 $\mathbf{z}={\mathbf{x}}^{\ast }+t(\mathbf{y}-{\mathbf{x}}^{\ast })$，其中 $t\in (0,1]$ 且足够小使 $\parallel \mathbf{z}-{\mathbf{x}}^{\ast }\parallel \le \delta$。$\mathcal{X}$ 是凸集，故 $\mathbf{z}\in \mathcal{X}$；由局部最优性，$f({\mathbf{x}}^{\ast })\le f(\mathbf{z})$。

另一方面，由 $f$ 的凸性，

$$f(\mathbf{z})=f((1-t){\mathbf{x}}^{\ast }+t\mathbf{y})\le (1-t)f({\mathbf{x}}^{\ast })+tf(\mathbf{y})<(1-t)f({\mathbf{x}}^{\ast })+tf({\mathbf{x}}^{\ast })=f({\mathbf{x}}^{\ast })$$

最后一步用到 $f(\mathbf{y})<f({\mathbf{x}}^{\ast })$。这与 $f({\mathbf{x}}^{\ast })\le f(\mathbf{z})$ 矛盾，故不存在这样的 $\mathbf{y}$，${\mathbf{x}}^{\ast }$ 是全局最优解。

非凸情形：取 $f(x)=\sin (3x)+0.3x^2-0.5x$。该函数有多个局部极小，$x=-1.4$ 附近与 $x=1.6$ 附近各有一个，函数值不同。从两者的邻域内分别出发做梯度下降，会分别收敛到各自的局部极小，其中的较大者不是全局最优。这说明局部最优性不能推出全局最优性。

第 2 题 计算推理

某数据集的样本量 $n={10}^5$，特征数 $p={10}^3$。使用梯度下降训练逻辑回归，每一次迭代需要遍历全部数据计算梯度，计算量为 $O(np)$。请估算一次梯度计算的浮点运算次数；若改为小批量大小为 $64$ 的随机梯度下降，单次迭代的计算量是多少？要达到相同的梯度精度，随机方法需要多少次迭代？据此说明随机方法的优势条件。

参考答案

全批量梯度：一次计算需要 $n\times p={10}^5\times {10}^3={10}^8$ 次乘加运算，量级为 ${10}^8$，即一亿次浮点运算。若迭代 $1000$ 次达到收敛，总量级为 ${10}^{11}$。

小批量梯度：小批量大小为 $64$ 时，单次迭代的计算量为 $64\times {10}^3=6.4\times {10}^4$，比全批量小约 $1560$ 倍。这样一次迭代可以做 $1560$ 次，每步的方差较大但整体进展快。

迭代次数：随机梯度的估计方差随批量增大而下降，与小批量大小成反比。使用大小为 $B$ 的批量时，梯度估计的方差约为全批量的 $1/B$ 倍，为达到相同的梯度精度，需要的迭代次数大约增加 $\sqrt{B}$ 倍（方差按 $1/\sqrt{B}$ 的量级反映在步长与迭代数上）。在本例中，用 $64$ 的批量达到同样的梯度精度，需要的迭代次数大约是全批量的 $\sqrt{64/{10}^5}$ 分之一。

优势条件：随机方法在每步计算量远小于全批量、而所需迭代次数增长得比较缓慢时占优。数据量越大、数据冗余越强（样本之间高度相似导致梯度方向一致），随机方法的优势越明显。反之，数据量很小、或目标函数对梯度的精度要求很高（如需要高精度解的病态问题）时，全批量方法更合适。这一取舍是深度学习实践中批量大小选择的核心依据。

第 3 题 代码验证

构造一个含多个局部极小的非凸函数，用多起点梯度下降求解，记录不同初值收敛到的解与目标值；再对同一个问题改用凸的目标函数（例如把其中一个局部极小所在区域以外的部分截断），验证从任意初值都收敛到同一个最优值。

参考答案

import numpy as np

def f(x):
    return np.sin(3 * x) + 0.3 * x ** 2 - 0.5 * x

def grad_f(x):
    return 3 * np.cos(3 * x) + 0.6 * x - 0.5

def gradient_descent(x0, lr=0.15, steps=500):
    x = x0
    for _ in range(steps):
        x = x - lr * grad_f(x)
    return x

print("非凸函数的多起点求解：")
seen = {}
for x0 in [-3.5, -2.0, -0.5, 0.5, 1.5, 3.0]:
    x_star = gradient_descent(x0)
    seen.setdefault(round(x_star, 3), []).append(x0)
    print(f"  初值 {x0:+.1f} → 解 {x_star:+.4f}，f = {f(x_star):+.4f}")
print(f"共收敛到 {len(seen)} 个不同的解")

# 凸版本：只保留一个凹陷区域，构造单峰函数
def g(x):
    return 0.5 * (x - 1.0) ** 2

def grad_g(x):
    return x - 1.0

print("\n凸函数的收敛结果：")
for x0 in [-3.5, -2.0, 0.5, 3.0, 10.0]:
    x = x0
    for _ in range(500):
        x = x - 0.5 * grad_g(x)
    print(f"  初值 {x0:+.1f} → 解 {x:+.6f}")
# 所有初值都收敛到同一个最优点 x = 1

非凸情形下不同的初值落入不同的吸引域，得到不同的解与目标值，其中只有一个对应全局最优。凸情形下所有初值收敛到同一点，验证了局部最优即全局最优这一性质。多起点策略是应对非凸问题的常用手段，代价是计算量成倍增加，且在维度很高时随机初值很难覆盖全部吸引域。

第 4 题 综合应用

某团队要在给定预算下分配三类渠道的广告投入，目标是最大化总转化量。已知转化量随投入增加但边际递减，各渠道有最低投入要求，且某一渠道的投入不得超过总预算的 $40\mathrm{\%}$。请把该问题写成标准优化形式，判断它属于哪一类问题，并说明应选用哪个算法家族，以及需要检查哪些性质才能确认算法适用。

参考答案

标准形式：设三个渠道的投入为 $x_1,x_2,x_3$（单位：万元），预算为 $B$，各渠道的转化函数为 $c_i(x_i)$（递增、边际递减，即凹函数）。

$$\begin{array}{rl}\underset{\mathbf{x}}{max}& \sum _{i=1}^3{c}_i(x_i)\\ \text{s.t.}& x_1+x_2+x_3\le B\\ & x_i\ge l_i,i=1,2,3\\ & x_2\le 0.4B\end{array}$$

转化为标准最小化形式时对目标取负号，得到凸目标加线性约束。

问题类别：目标函数是凹函数之和（取负号后为凸函数之和，仍为凸），约束全部为线性，因此是凸优化问题，具体属于线性约束的凸问题。若 $c_i$ 是可微的凹函数，问题是光滑的；若转化函数以分段线性方式给出，则是非光滑的凸问题。

算法选择：连续变量、凸目标、线性约束的规模很小（三维），可以直接用内点法或投影梯度法求解。若目标光滑，用内点法可以在少量迭代内得到高精度解；若目标分段线性，可以化为线性规划用单纯形法求解。维度更高（例如渠道数上千）时，投影梯度或近端梯度更合适。

需要检查的性质：其一，目标函数的凹性是否成立，边际递减这一假设需要从历史数据中验证，若不成立则问题非凸，全局最优无法保证。其二，约束是否相容，最低投入之和若超过预算则可行域为空，此时问题无解而不是算法失败。其三，约束是否互相矛盾，例如某渠道的最低投入已超过预算的 $40\mathrm{\%}$ 上限。其四，转化函数是否存在饱和区域，若某个渠道的转化量在高投入后不再增长，最优解会落在饱和点附近，此时对参数估计误差很敏感，需要做敏感性分析。其五，是否需要考虑整数约束（投入必须为整数万元），若需要则问题变为整数规划，算法家族完全不同。

常见错误

错误 1 · 把局部最优解当作全局最优解

原因：多数算法（梯度下降、随机梯度、拟牛顿）只保证收敛到驻点或局部最优。在非凸问题上，算法输出解的质量依赖初值与迭代路径，直接把它当作全局最优并在报告中不加限定，会给出误导性结论。

解决：先判断问题的凸性，凸问题可以直接声称全局最优。非凸问题采用多起点、随机重启或全局搜索策略，报告时说明初值策略与多次运行的结果分布，并把最优值与其上下界一并给出。

错误 2 · 忽略约束可行性直接套用无约束算法

原因：无约束算法在迭代过程中会离开可行域，得到的点可能违反约束而目标函数值看似更优。把这种点当作可行解输出，会得到不可实施的方案。可行域为空时算法可能仍在收敛，实际是问题无解。

解决：求解前检查可行域是否非空，并在代码中用约束违反量做校验。使用无约束算法处理有约束问题时，加入投影步骤或罚项，并检查最终解的约束违反量在容差范围内。

错误 3 · 用固定的步长训练含噪声的目标

原因：随机梯度带有方差，固定步长下迭代点在最优解附近持续震荡，误差不会随迭代增加而下降。这一现象在训练后期表现为损失值在某个水平上下波动，若据此判断收敛会误认为算法已经完成。

解决：使用步长衰减策略（如随迭代次数递减）或自适应方法，并监控梯度的滑动平均平方以判断震荡程度。训练深度模型时观察验证集指标而非训练损失的瞬时值，用早停与学习率调度控制过程。

错误 4 · 把病态条件数误判为算法失效

原因：目标函数的条件数很大时（特征量纲差异大、变量强相关），梯度下降的收敛速度极慢，窄方向上的震荡使迭代数看似没有下限。把这一现象归因于算法错误而更换算法，往往只是把问题转移到另一个同样受条件数影响的算法上。

解决：先做尺度处理，把特征标准化或白化，观察条件数是否下降。若条件数仍然很大，改用对条件数依赖较弱的方法（动量、加速梯度、二阶方法），或在目标中加入正则项来改善曲率。诊断手段是计算海森矩阵（或其在若干方向上的投影）的条件数，而不是只观察损失曲线。