凸优化 I
这门课学什么
课程教你识别和求解凸优化问题：凸集与凸函数、LP、QP、SOCP、SDP、对偶理论和内点法，并讲信号处理、统计和控制中的应用。教材是 Boyd 与 Vandenberghe 的《凸优化》。
内容摘要
这门课教你识别凸优化问题，把实际问题写成凸问题，并用现成工具求解。2008 年版共 19 讲，配套教材是 Boyd 和 Vandenberghe 合著的《Convex Optimization》。讲师 Stephen Boyd 讲课直接，常用一句玩笑点出概念的实际用处。
课程分 3 部分。理论部分（第 1–9 讲）讲凸集、凸函数和标准问题类，包括 LP、QP、SOCP、SDP 和几何规划。这部分的终点是对偶理论、KKT 条件和灵敏度分析。应用部分（第 10–14 讲）讲逼近与拟合、统计估计、几何问题和分类，最后补充数值线性代数。算法部分（第 15–19 讲）讲梯度下降、牛顿法、等式约束问题和内点法。
阅读作业按教材章节推进。课程有 8 次作业，题目主要来自教材习题。部分题目要用 MATLAB 和 CVX 建模工具实际求解。站上还有期末样卷和期末试题。
学完后，你能判断一个问题是不是凸问题。你也能把信号处理、统计、控制和金融中的问题写成标准形式，并理解求解器内部的内点法。很多学校把这门课当作优化、机器学习和控制方向的基础课。
为什么值得学
《凸优化》是该领域的标准教材，作者官网可免费下载。这门课就是教材的配套讲授。
课程信息
- 学校
- 斯坦福（Stanford）
- 课程号
- EE364A
- 讲师
- Stephen Boyd
- 学期
- 2008 (SEE)
- 平台
- Stanford Engineering Everywhere
- 费用
- 免费
- 难度
- 高级
- 学时
- 19 讲
- 先修
- 需要扎实的线性代数，建议先学 EE263。
- 材料
- 视频、讲义、作业、考试、教材、代码
- 许可证
- CC BY-NC-SA 4.0（SEE 站声明）
课程大纲 · 共 19 节
大纲依据：SEE 2008 版讲次列表（19 讲，按每讲 Topics 概括）（查看原始页面 ↗）
- 1凸优化导论Introduction to Convex Optimization
举例说明优化问题，讲最小二乘和线性规划。说明凸优化为什么重要，以及课程目标。
- 2凸集Convex Sets
讲凸集、凸锥、多面体和半正定锥。讲保持凸性的运算、广义不等式和支撑超平面定理。本讲由客座讲师 Jacob Mattingley 主讲。
- 3凸函数Convex Functions
讲凸函数的定义、一阶和二阶条件、上图和下水平集。讲 Jensen 不等式和保持凸性的运算。
- 4共轭函数、拟凸函数与对数凹函数Conjugate, Quasiconvex and Log-Concave Functions
讲透视函数和共轭函数。讲拟凸函数、对数凹函数和对数凸函数的性质。
- 5凸优化问题Convex Optimization Problems
讲最优点、可行性问题和凸问题的标准形式。证明局部最优就是全局最优，并讲等价变换和拟凸优化。
- 6线性规划、二次规划、二阶锥规划与几何规划LP, QP, SOCP and Geometric Programming
介绍线性分式规划、QP、QCQP、SOCP 和鲁棒线性规划。用悬臂梁设计的例子讲几何规划。
- 7半定规划与向量优化Semidefinite Programming and Vector Optimization
讲 SDP，以及 LP 和 SOCP 怎样写成 SDP。讲帕累托最优、多目标优化和投资组合的风险收益权衡。
- 8对偶Duality
讲拉格朗日函数和对偶函数。讲弱对偶、强对偶、Slater 条件和互补松弛。
- 9KKT 条件与灵敏度分析KKT Conditions and Sensitivity Analysis
讲 KKT 条件，以及扰动和灵敏度分析。讲问题改写对对偶问题的影响。
- 10逼近与拟合Approximation and Fitting
进入应用部分。讲范数逼近、罚函数逼近、正则化、信号重构和鲁棒逼近。
- 11统计估计Statistical Estimation
讲最大似然估计、逻辑回归和假设检验。讲试验设计和 D-最优设计。
- 12几何问题Geometric Problems
讲最小外接椭球、最大内接椭球和解析中心。开始讲线性判别。
- 13分类；数值线性代数基础Classification; Numerical Linear Algebra Background
讲鲁棒线性判别和支持向量分类器。转入数值线性代数：矩阵结构与算法复杂度。
- 14矩阵分解Matrix Factorizations
讲 LU、Cholesky 和 LDLT 分解及其稀疏版本。讲带结构的方程组，以及结构矩阵加低秩项的解法。
- 15无约束最小化Unconstrained Minimization
进入算法部分。讲强凸性、梯度下降、最速下降和牛顿法的收敛分析。
- 16自和谐性；等式约束最小化Self-Concordance; Equality-Constrained Minimization
讲自和谐函数下牛顿法的收敛分析。开始讲等式约束问题的牛顿法。
- 17不可行起点牛顿法；内点法Infeasible-Start Newton Method; Interior-Point Methods
讲不可行起点的牛顿步和 KKT 系统的解法。引入内点法和对数障碍函数。
- 18障碍法The Barrier Method
讲中心路径、对偶点和力场解释。讲障碍法、收敛分析和第一阶段（Phase I）方法。
- 19内点法复杂度；课程总结Interior-Point Complexity; Course Conclusion
用自和谐性分析牛顿迭代的总次数，并推广到广义不等式。总结课程和后续方向。