凸优化

📚 内容概要

一门全面的研究生级别课程与教材，涵盖凸优化的理论、应用及数值算法。重点在于识别并构建工程与科学领域中的凸问题。

掌握凸优化的数学基础与实用算法，应用于工程与数据科学。

作者： 斯蒂芬·博伊德（Stephen Boyd），利文·万登贝赫（Lieven Vandenberghe）

致谢： 本工作部分得到美国国家科学基金会（NSF）资助，并得益于斯坦福大学和加州大学洛杉矶分校的学生与同事们的贡献，特别感谢阿卡迪·涅米罗夫斯基（Arkadi Nemirovski）和基申·巴赫蒂（Kishan Baheti）。

🎯 学习目标

1. 定义数学优化问题的组成部分，包括目标函数、约束条件和变量。
2. 根据其数学特性区分最小二乘问题、线性规划问题和凸优化问题。
3. 比较局部与全局优化策略，并评估每种方法相关的计算复杂度。
4. 使用形式化组合符号定义并区分仿射集、凸集和锥。
5. 识别并表示标准凸集，如欧几里得球、椭球、多面体以及半正定锥。
6. 应用保持凸性的运算（如交集、仿射变换和透视函数），以验证集合性质。
7. 识别并应用保持凸性的运算，包括仿射函数的逐点上确界和向量复合规则。
8. 推导各类函数的拉格朗日共轭，并应用杨不等式（Young's inequality）。
9. 使用次水平集及一阶/二阶可微条件刻画拟凸性。
10. 建模与转换：通过松弛变量和约束消去法，将原始优化问题转化为标准凸形式。

🔹 第1课：数学优化导论

概述： 本课介绍数学优化的基本概念，从一般问题表述逐步过渡到可解的具体类别，如最小二乘法和线性规划。强调凸优化与非凸优化之间的关键区别，详述凸方法如何成为效率的可靠“分水岭”，并为解决更复杂的非线性问题提供重要工具。

学习成果：

• 定义数学优化问题的组成部分，包括目标函数、约束条件和变量。
• 根据数学特性区分最小二乘问题、线性规划问题和凸优化问题。
• 比较局部与全局优化策略，并评估每种方法相关的计算复杂度。

🔹 第2课：凸集理论

概述： 本课探讨优化的几何基础，从基本的线性结构过渡到凸集与锥的复杂性质。涵盖仿射集与凸集的数学定义，研究多面体、半正定锥等特定几何结构，并详细说明允许研究人员在高维空间中表征和操作凸集的操作与定理。

学习成果：

• 使用形式化组合符号定义并区分仿射集、凸集和锥。
• 识别并表示标准凸集，如欧几里得球、椭球、多面体以及半正定锥。
• 应用保持凸性的运算（如交集、仿射变换和透视函数），以验证集合性质。

🔹 第3课：凸函数及其性质

概述： 本课深入探讨保持凸性的高级运算，如逐点上确界和特定复合规则，并引入拉格朗日共轭函数。将凸性概念扩展至拟凸函数与对数凹函数，同时考察广义不等式下的凸性以及矩阵特有性质（如舒尔补）。这些概念构成了识别与建模复杂优化问题的数学基础。

学习成果：

• 识别并应用保持凸性的运算，包括仿射函数的逐点上确界和向量复合规则。
• 推导各类函数的拉格朗日共轭，并应用杨不等式。
• 使用次水平集及一阶/二阶可微条件刻画拟凸性。

🔹 第4课：凸优化问题的建模

概述： 本课涵盖凸优化问题的形式结构与转化，从标准形式、最优性条件到具体问题类别，如线性规划（LP）、二次规划（QP）和半定规划（SDP）。学生将学习如何识别全局最优性，使用二分法求解拟凸问题，并应用标量化方法处理多准则向量优化。

学习成果：

• 建模与转换：通过松弛变量和约束消去法，将原始优化问题转化为标准凸形式。
• 分析最优性：应用基于梯度的最优性准则，判断某点是否为全局最优。
• 分类与求解：区分LP、QP、SOCP、GP和SDP，并应用专门方法（如二分法）求解拟凸函数。

🔹 第5课：拉格朗日对偶性与KKT条件

概述： 本课深入探讨拉格朗日对偶性的基本理论，从拉格朗日对偶函数的定义出发，推导对偶问题的构造。涵盖原问题与对偶问题最优值之间的关键差距，以及这些关系的几何与博弈论解释；同时介绍刻画最优解的卡拉什-库恩-塔克（KKT）条件。最后，课程延伸至灵敏度分析与影子价格。

学习成果：

• 推导拉格朗日对偶函数，并为各类优化问题构造对偶问题。
• 利用弱对偶性、强对偶性及斯莱特约束资格（Slater's constraint qualification）评估原问题与对偶问题之间的关系。
• 应用KKT最优性条件求解并验证凸与非凸问题的最优解。

🔹 第6课：逼近、拟合与正则化

概述： 本课探讨线性方程组解的逼近与函数拟合的数学基础及实际应用。涵盖基于范数的逼近方法，包括惩罚函数与正则化技术，用于管理异常值与稀疏性；还介绍处理数据不确定性的鲁棒优化技术。此外，详细讨论在特定约束（如凸性、单调性）下进行函数拟合的方法。

学习成果：

• 建模并求解范数逼近问题，解释最小二乘法、切比雪夫逼近与L1方法之间的几何与统计差异。
• 设计并实现正则化逼近模型，以在残差误差、解的大小与稀疏性之间取得平衡。
• 构建鲁棒逼近框架，以应对数据矩阵中的不确定性。

🔹 第7课：统计估计与推断

概述： 本课探索统计推断与凸优化的交叉领域。聚焦于将估计问题——包括最大似然估计、非参数分布估计和最优检测器设计——建模为凸规划问题。学生将学习如何利用优化方法寻找参数并设计具有信息量的实验。

学习成果：

• 将最大似然估计（MLE）与逻辑回归问题建模为凸优化任务并求解。
• 使用线性规划（LP）设计最优检测器，并解释接收者操作特征曲线（ROC）。
• 应用非参数估计技术，包括最大熵方法与KL散度最小化。

🔹 第8课：几何问题与分类

概述： 本课探讨凸优化在几何问题中的应用，包括点在集合上的投影、集合间距离的计算以及集合中心的刻画。进一步将这些几何原理拓展至实际任务，如线性与非线性分类、最优设施选址及利用几何规划进行平面布局设计。

学习成果：

• 使用KKT条件与对偶表示，建模并求解凸集间的投影与距离问题。
• 通过极值体积椭球近似复杂凸集，并确定其效率因子。
• 计算多种集合中心，并将其应用于鲁棒判别与分类。

🔹 第9课：无约束最小化算法

概述： 本课涵盖凸函数无约束最小化的理论基础与算法实现。详细阐述从一阶梯度下降法到二阶牛顿法的各类下降方法。重点聚焦收敛性分析，特别是强凸性以及自协调性的仿射不变理论。

学习成果：

• 定义强凸性，并利用其含义为次优性与到最优解的距离提供上界。
• 在欧几里得、二次与L1范数下比较并对比梯度下降法与最速下降法。
• 计算牛顿步与牛顿减值，解释为何牛顿法具有仿射不变性。

🔹 第10课：等式约束最小化

概述： 本课探讨求解带线性等式约束的凸优化问题的方法。重点在于牛顿步的推导与实现，比较可行与不可行初始点方法，并在原-对偶框架内解释这些步骤。特别强调通过KKT系统块消元实现高效的数值实现。

学习成果：

• 计算并解释等式约束问题的牛顿步与牛顿减值。
• 展示带等式约束的牛顿法与约束消除方法之间的等价性。
• 实现不可行初始牛顿法，并解释其原-对偶残差减小特性。

🔹 第11课：内点法

概述： 本课介绍内点法，通过将不等式约束问题转化为一系列等式约束问题，并应用牛顿法求解。核心内容涉及对数障碍函数，沿中心路径追踪最优解，以及利用原-对偶框架提升效率与鲁棒性。

学习成果：

• 定义并构造对数障碍函数，刻画中心路径及其关联的对偶点。
• 实现障碍法，包括中心化步与外迭代之间的权衡。
• 建模并求解第一阶段可行性问题，以找到严格可行的初始点。