凸优化

课程简介

凸优化是数学优化的重要分支，主要研究凸集上的凸函数优化问题。在机器学习、信号处理、控制理论等领域有广泛应用。

学习内容

凸集与凸函数

• 凸集的定义与性质
• 凸函数的定义与判定
• 凸函数的性质

凸优化问题

• 线性规划
• 二次规划
• 半定规划
• 锥规划

优化算法

• 梯度下降法
• 牛顿法
• 内点法
• 对偶方法

学习笔记

第一章：凸集

1.1 凸集的定义

定义：集合 $C\subseteq {\mathbb{R}}^n$ 是凸集，当且仅当对于任意 $x_1,x_2\in C$ 和任意 $\theta \in [0,1]$，有：

$$\theta x_1+(1-\theta )x_2\in C$$

几何意义：连接集合中任意两点的线段都在集合内。

1.2 凸集的例子

1. 超平面：$\{x|a^{T}x=b\}$
2. 半空间：$\{x|a^{T}x\le b\}$
3. 多面体：有限个半空间的交集
4. 椭球：$\{x|(x-x_c{)}^T{P}^{-1}(x-x_c)\le 1\}$

第二章：凸函数

2.1 凸函数的定义

定义：函数 $f:{\mathbb{R}}^n\to \mathbb{R}$ 是凸函数，当且仅当对于任意 $x_1,x_2\in \text{dom }f$ 和任意 $\theta \in [0,1]$，有：

$$f(\theta x_1+(1-\theta )x_2)\le \theta f(x_1)+(1-\theta )f(x_2)$$

2.2 凸函数的判定

一阶条件：如果 $f$ 可微，则 $f$ 是凸函数当且仅当：

$$f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^T(y-x)$$

二阶条件：如果 $f$ 二阶可微，则 $f$ 是凸函数当且仅当：

$${\mathrm{\nabla }}^{2}f(x)⪰0$$

实践练习

• [ ] 证明常见函数的凸性
• [ ] 实现梯度下降算法
• [ ] 解决凸优化问题实例

参考资料

• 教材：《Convex Optimization》- Boyd & Vandenberghe
• 在线课程：Stanford CS229 Machine Learning
• 软件工具：CVXPY, CVX

---

最后更新：2024年9月9日