凸优化与凸优化问题识别

层级：B｜按需

1. 识别结构比选择算法更先

如果问题是凸的，你可以获得全局最优保证、使用成熟求解器并通过原—对偶间隙检验；如果不是凸的，就应避免声称同样保证。凸优化识别依靠目标、约束和函数组合规则。

2. 标准凸优化

\begin{aligned} \min_xquad&f_0(x)\\ \text{s.t.}quad&f_i(x)\le0, i=1,\ldots,m,\\ &Ax=b, \end{aligned}

其中 $f_0,f_i$ 都凸，等式约束仿射。可行域是凸集，目标凸。

为什么等式必须仿射？一般凸函数等式 $f(x)=0$ 的零水平集不一定凸。例如 $x^2=1$ 可行点为 $\{-1,1\}$ 。

3. 凸性检查流程

明确变量与定义域；
将问题写成标准最小化形式；
检查可行域是否凸；
检查目标在该域上凸；
用已知原子与组合规则，必要时检查 Hessian；
注意等价变换是否保持凸性和定义域。

4. 常见凸原子

仿射 $a^Tx+b$ ；
范数 $\|Ax+b\|$ ；
平方范数 $\|Ax-b\|_2^2$ ；
$e^x$ ；
$-\log x$ （ $x>0$ ）；
LogSumExp；
最大值 $\max_i(a_i^Tx+b_i)$ ；
hinge $\max(0,1-yw^Tx)$ ；
logistic loss $\log(1+e^{-yz})$ ；
PSD 二次型 $x^TAx$ 。

5. 组合规则

凸函数的非负加权和凸；
凸函数与仿射映射复合凸；
凸函数的逐点最大凸；
若外函数凸且非递减、内函数凸，复合凸；
若外函数凸且非递增、内函数凹，复合凸；
部分最小化在适当联合凸条件下保持凸性。

不能仅凭“凸函数套凸函数”就断言凸。例如 $f(x)=x^2$ 凸，但与凸 $g(x)=x^2-1$ 复合的某些变体要检查外函数在内层值域的单调性。

6. 机器学习例子

线性回归

\|Xw-y\|_2^2

是仿射映射后的平方范数，凸。

Logistic 回归

\sum_i\log(1+e^{-y_iw^Tx_i})

每项凸，和凸；加 L1/L2 正则仍凸。

线性 SVM

\frac\lambda2\|w\|^2 +\frac1n\sum_i\max(0,1-y_iw^Tx_i)

凸但 hinge 在折点不可微。

k-means

联合优化簇分配与中心非凸，容易局部最优；固定分配时中心子问题凸，固定中心时分配可逐点最优。

神经网络

对所有层参数联合通常非凸；固定前层表示，仅优化最后一层 logistic/平方目标可能凸。

7. 严格凸与强凸

严格凸使最优解至多一个；强凸还提供二次增长：

f(y)\ge f(x)+\nabla f(x)^T(y-x) +\frac\mu2\|y-x\|^2.

线性回归 $X^TX$ 不满秩时只凸不严格；加入 $\lambda\|w\|^2$ 常使其强凸并得到唯一解。

8. 非光滑凸优化

L1 与 hinge 凸但不可微。可用：

次梯度法；
坐标下降；
近端梯度；
ADMM；
bundle method；
通用凸求解器。

不可微不等于难到无解，反而凸性仍提供全局结构。

9. Disciplined Convex Programming

CVX/CVXPY 等系统让用户用已知原子与组合规则建模，自动验证凸性并转换为锥规划。若系统拒绝一个数学上可能凸的表达式，可能是写法不符合 DCP 规则，需要改成可识别等价形式；不要关闭检查后盲目求解。

10. 求解器与最优性证书

根据问题结构选择：

光滑无约束：梯度/Newton/L-BFGS；
非光滑复合：近端与坐标方法；
二次规划：专用 QP；
线性规划：simplex/内点法；
锥规划：内点或一阶锥求解器；
超大规模有限和：随机/增量方法。

求解器状态 optimal_inaccurate、不可行证书和容差需要阅读，不能只取返回数组。

11. 凸不代表自动容易

变量可能数十亿、条件数极差、约束投影昂贵、数据分布式，凸问题仍可计算困难。凸性提供结构和全局保证，不消除规模与数值工程。

易错点

目标凸但可行域非凸，整体不是凸优化。
凸等式约束一般不允许，等式应仿射。
严格凸与强凸不同。
不可微凸函数仍可全局优化。
联合非凸问题可能对每个变量块分别凸，不能因此称整体凸。

常见问答

Q1：加正则化一定让问题凸吗？

若原目标非凸，加一个凸项通常仍非凸；凸项只能改善某些曲率，除非强到抵消所有负曲率且可证明。

Q2：深度学习最后一层为何常容易优化？

固定表示后，最后一层对参数是线性/仿射，配平方或交叉熵形成凸问题。

Q3：凸问题有多个最优解吗？

可以。最优解集合是凸的；严格凸才保证至多一个。

练习

判断 $x^2$ 在约束 $x\in[-1,2]$ 的问题是否凸。
约束 $x^2=1$ 是否形成凸可行域？
为什么 L1 正则 logistic 回归仍凸？
k-means 固定簇分配后中心最优是什么？
目标强凸带来哪些额外性质？

答案与提示

是，目标和可行域均凸。
否，可行集两点连线不都可行。
logistic loss 与 L1 均凸，非负和保持凸。
每个簇样本均值。
唯一最优、二次增长、通常更快且可定量的收敛。