44-核心概念-复合优化问题

知识点：复合优化问题

知识点概述

复合优化问题是一类特殊结构的优化问题，其目标函数可以写成一个光滑函数和一个（可能非光滑的）凸函数的和。这种结构在现代信号处理和机器学习中非常普遍，并且可以被高效的近似点梯度算法求解。

详细解释

• 模型: ${\min }_{x}f(x)+g(x)$ 其中 $f(x)$ 是一个光滑的凸函数（梯度利普希茨连续），$g(x)$ 是一个凸函数，但可能非光滑。
• 特点: 问题的难点在于 $g(x)$ 的非光滑性，使得传统的梯度下降法无法直接应用。但 $g(x)$ 通常具有简单的结构，其“邻近算子”（Proximal Operator）容易计算。
• 例子:
  • LASSO: ${\min }_x\frac{1}{2}\Vert Ax-b{\Vert }_2^2+\lambda \Vert x{\Vert }_1$。这里 $f(x)=\frac{1}{2}\Vert Ax-b{\Vert }_2^2$ 是光滑的，$g(x)=\lambda \Vert x{\Vert }_1$ 是非光滑的。
  • 稀疏逻辑回归: 最小化逻辑回归损失（光滑）加上 ${\ell }_1$ 正则项（非光滑）。
  • 矩阵补全: ${\min }_X\frac{1}{2}\Vert {\mathcal{P}}_{\Omega }(X)-M{\Vert }_F^2+\lambda \Vert X{\Vert }_{\ast }$。这里数据保真项是光滑的，核范数是（在矩阵空间中）非光滑的。

学习要点

• 掌握复合优化的“光滑+非光滑”结构。
• 能够识别一个问题是否属于复合优化模型。
• 知道这类问题的存在使得我们可以将许多带复杂正则项的问题纳入一个统一的框架。
• 了解近似点梯度法是求解这类问题的关键算法。

实践应用

• 几乎所有带 ${\ell }_1$ 范数、核范数、全变差等非光滑正则项的机器学习和图像处理问题都可以看作是复合优化问题。

关联知识点

• 前置知识: 24-核心概念-凸函数, 28-核心概念-次梯度
• 后续知识: 67-理论方法-近似点梯度法, 68-理论方法-Nesterov加速算法
• 相关知识: 3-应用案例-稀疏优化, 39-应用案例-全变差模型