cs_notes

Convex Optimization I

https://www.youtube.com/playlist?list=PL8WsPW41L6l7rviIGvIkY0-jn-tM3YSNi

2. Lecture 2 Convex Sets

定义

集合S称为凸集(convex set)如果对任意S中的两个点x和y,线段[x,y]全在S内。

特性

1. 凸集的任意以下点组成的集合也是凸集:
   • 两个点的线段
   • 有限多个点的凸包
2. 凸集内部的任意点与界点之间的线段都在凸集内
3. 凸集与其它凸集的交集还是凸集
4. 凸集与其它凸集的并集还是凸集
5. 凸集内任意两个点都有唯一连线全在凸集内

例子

1. 球 - 任意二点的连线在球面上
2. 四面体 - 任意二点的连线在四面体内部
3. 射影空间中的负定集 - 负定二次型定义的集合

识别凸集

1. 直观画图判断一个集合是否是凸集
2. 用集合的性质推导
3. 计算集合的交集、并集等操作,查看是否还是凸集
4. 对集合求楔形包围,如果等于原集合则是凸集

3. Lecture 3 Convex functions

定义

函数f:Rn→R是一个凸函数,如果对任意x,y∈Rn以及λ∈[0,1],都满足:

f(λx+(1-λ)y) ≤ λf(x)+(1-λ)f(y)

也就是说,函数在任意两个点之间的secant线(‖切线‖)总在函数图面以上。

特性

1. 一个凸函数的等高线一定是凸的
2. 凸函数在其定义域内任意点的切线的斜率不大于通过任意两点的secant线的斜率
3. 凸函数局部最小值一定是全局最小值

例子

1. 二次型 - ax^2 + bx + c ,当a≥0时是凸函数

2. 绝对值函数 -

   x

3. 指数函数 - e^x
4. 对数函数 - ln(x)当x>0时
5. 幂函数 - x^n 当n≥1时

识别凸函数

1. 计算二阶导数试图找出函数的定性
2. 画出函数图形观察是否满足凸性定义
3. 对数函数确认定义域是否正确
4. 将函数写成二次型形式判断系数是否满足需求

4. Lecture 4 Convex optimization problems

定义

凸优化问题是指在某个凸集S上找到一个凸函数f(x)的全局最小值。

即:

min f(x)

s.t. x∈S

其中S是凸集,f(x)是凸函数。

特性

1. 凸优化问题一定存在唯一的全局最小值。

2. 本地最小值一定是全局最小值。

3. Karush-Kuhn-Tucker条件是必要充分条件来判断一个点是否是解。

例子

1. 线性规划:对象函数和约束函数都是线性的。

2. 二次规划:对象函数是二次的,但约束函数可以是线性的或二次的。

3. 支持向量机:描述间隔最大化问题。

4. 最优控制:描述动态系统在给定期间的最优路径问题。

解法

1. 利用KKT条件构建对偶问题。

2. 应用算法:梯度下降法,牛顿法,内点法等。

3. 针对特定问题设计更高效的定製算法。

4. 将非凸问题分解或近似为一系列子凸优化问题求解。

5. Lecture 5 Duality

对偶问题的定义

对一个凸优化问题min f(x),s.t. g(x)≤0,其对偶问题定义为:

max q(y)

where q(y) = inf_{x} [f(x) + y^T g(x)]

这里y是拉格朗日乘子。

拉格朗日对偶性质

1. 如果原问题可行,对偶问题的解存在。

2. 如果原问题和对偶问题都有内点,原问题和对偶问题的最优值相等。

3. 拉格朗日乘子的选择使得原问题的KKT条件等价于对偶问题的KKT条件。

线性规划的对偶问题

对于max c^Tx, s.t. Ax ≤ b的线性规划问题:

其对偶问题是min b^Ty, s.t. A^Ty ≥ c

对偶理论的应用

1. 构造比原问题更容易解决的对偶问题

2. 应用对偶性质检验原问题特性,如可行性和有界性

3. 采用对偶间隔概念设计支持向量机模型

4. 证明优

6. Lecture 6 Approximation and fitting

逼近

逼近问题是找到一个简单函数来近似描述复杂函数或数据的曲线。

最小二乘法

找到使残差平方和最小的逼近函数。常用线性、多项式逼近。

正则化

添加正则项控制函数复杂程度,避免过拟合。如LASSO、Ridge回归。

多项式混合法

使用正交多项式基作为逼近函数空间。

拟合

拟合问题是根据已知离散样本点建立连续描述函数。

样条函数

通过各点附近的多项式重构全局函数,保持连续性和光滑性。

RBF基函数

使用径向基函数(RBF)作为本地插值函数,全局插值函数为RBF的线性组合。

B样条

使用Bernstein多项式 basic函数定义样条切片,保证全局函数光滑连续。

评估

用未见数据测试逼近效果,根据RMSE、R-square等度量指标评价模型优劣。

7. Lecture 7 Statistical estimation

统计估计

根据样本数据估计整体分布或参数。

点估计

用样本统计量(平均值、中位数等)作为参数估计值。

• 平均值估计波动最小,但需要样本大小足够大。

• 中位数估计不容易被差值点影响,比较稳定。

区间估计

根据样本和置信度给出参数的可能范围。

• 普通区间:参数落在该区间的概率是1-α。

• 最细区间:保证包含真参数的可能性最大。

最大似然估计

选择使样本机率最大的模型参数作为估计值。对多参数分布起作用。

贝叶斯估计

利用先验分布与似然函数给出后验分布,其分位数作为估计值及区间。

性能评价

• 偏差:估计值期望与真值差异。

• 方差:估计值与其期望间差异。

• 误差:估计值与真值间差异。

要求偏差小,方差小作为一个好的统计估计。

9. Lecture 9 Numerical linear algebra background

线性代数基础

• 向量空间及其基本操作
• 矩阵及其性质:秩、逆矩阵、特征值等
• 线性系统Ax=b求解

数值线性代数

• 矩阵分解:LU、QR、Schur、SVD等
• 迭代法求解线性系统:Jacobi、Gauss-Seidel、Conjugate Gradient等
• 非线性问题线性化:牛顿法

误差分析

• 截断误差:小数点后几位数的选择
• 进位误差:加减乘除产生的误差累加
• 几何级数收敛:迭代法与条件数的关系
• 误差层叠:多步计算导致的误差扩大

软件库

• BLAS:基本线性代数操作
• LAPACK:线性问题求解器
• ARPACK:源迭代法求特征值
• PETSc:并行迭代求解器

数值稳定性

• 微分的数值求导
• 矩阵分解的数值稳定性
• 预处理技术提高迭代收敛

10. Lecture 10 Unconstrained minimization

方法分类

1. 一阶方法:利用函数梯度信息,如梯度下降法

2. 二阶方法:利用函数值和梯度的一阶和二阶导数,如牛顿法、BFGS法

3. etc.

梯度下降法

• 利用负梯度方向作为搜索方向
• 带线搜索来选取步长,保证每个迭代都使函数下降
• 收敛速度受函数曲率影响

牛顿法

• 使用海森矩阵的逆作为搜索方向
• 每步求解一个二次型,收敛速度快但计算代价高
• 必须确保海森矩阵非奇异

BFGS法

• 逼近海森矩阵的逆,免去直接计算
• 具有良好的收敛速度而较低计算成本
• 仅需要函数值和梯度

适用性

• 对自变量数量小于1000的问题使用二阶方法
• 自变量多时使用一阶方法,通过加速技巧提升效率

工具箱

• Numpy/Scipy提供的优化函数接口
• TensorFlow可自动求导的离散优化

11. Lecture 11 Equality constrained minimization

定义和分类

等式限制优化问题是在满足某些等式约束的条件下求解凸函数的最小值。

白金汉模拟转换

将等式约束引入对象函数,构建相当于无约束的问题。

动态规划法

将整个问题分解成子问题依次求解,利用子问题解更新全局解。

寻找拉格朗日乘子

构建拉格朗日函数,利用KKT条件求原问题与对偶问题的联合解。

滤波器法

迭代算法在每步保留等式约束,求解次优化子问题得到解的一部分。

扰动法

在每步允许小幅度违反等式约束,迭代收敛时满足等式约束。

牛顿法与增量法

利用等式结构约束信息,求解等式约束生根子空间内的牛顿方程。

适用范围

线性等式约束问题可直接求解,非线性问题常用迭代法收敛到解处。

12. Lecture 12 Interior point methods

定义

内点方法是一类求解凸优化问题的迭代算法,它在每一步迭代都保持在可行区域内部运行。

原理

1. 将非等式约束引入拉格朗日函数形成优化障碍函数

2. 每步搜索障碍函数的内点极小点

3. 通过中心路径方法,保证迭代点呈指数型收敛至边界

特征

1. 每步都避免直接考虑约束可满,收敛速度快

2. 需要解决密集矩阵系统方程

3. 适用于中小规模线性和混合整数设计问题

算法类型

1. 常用的有内点法、向边界点法等

2. 路径跟踪法控制迭代过程

3. 每步可使用LU分解或 condoms 清晰法等解方程组

应用

1. 运筹优化问题如交通、生产调度等

2. 结构优化与机械 Detail 设计

3. 图像处理与模式识别中的凸优化问题

4. 混合整数非线性程序