机器学习笔记_数学基础_7-凸优化理论

2021-12-23 机器学习

优化问题
minf0(x)
subjecttofi(x)≤bi,i=1,?,m
x=(x1,?,xn)称为优化变量
f0 称为目标函数
fi 称为约束函数

最小二乘问题 (无约束条件；目标函数是若干平和)
minf0(x)=||Ax?b||22=∑ki=1(aTi?bi)2
线性规划：目标函数 f0 和约束函数 f1,?,fn 均是线性函数
凸优化：目标函数 f0 和约束函数 f1,?,fn 均是凸函数
1. 线性凸优化
2. 非线性凸优化
  a. 等式约束
  b. 无约束
  c. 不等式约束
二次规划(QP) ：目标函数 f0 是凸且二次型；约束函数是仿射函数时(线性函数) => 二次规划
min(12)xTPx+qTx+r
subjecttoGx?h; Ax=b

=>二次规划等结余在多面体上极小化一个凸二次函数

二次约束二次规划(QCQP): 目标函数和约束函数均是（凸）二次型

凸优化的基本理论

凸集->凸函数->凸优化
仿射集：集合C内的任意两点的直线，仍在凸集=>仿射集(直线，平面，超平面)
仿射包；内点；相对内点
凸集：集合C内的任意两点的线段，仍在集合
锥；锥包（过原点的射线，射线族，角）
超平面： {x|aTx=b}
半平面： {x|aTx≤b}
多面体（仿射集，射线，线段，半空间）=> 多面体是凸集

保凸运算
1. 集合的交运算
2. 仿射函数(类比线性运算)
3. 透视函数（单位向量化，舍弃最后一个等于1的向量）
4. 投射函数( 线性分段函数)
分割超平面：定义集合C和集合D最短线段的垂直平分线
支持超平面: 集合C的边界上的点的切线(面)

凸函数基本问题

f(θx+(1?θ)y)≤θf(x)+(1?θ)f(y)
1. f 一阶可微；f(y)≤f(x)+▽f(x)T(y?x) ; 一阶Taylor 展开为其下估计
2. f 二阶可微:▽f(x)2 : （1） f是一元函数，上式大于0; (2)f多元函数，上式二阶Hessian半正定；
上境图：一个函数是凸函数，当且仅当其上境图是凸集
Jensen不等式：
f(θ1x1+?+θkxk)≤θ1f(x1)+?+θkf(xk)
<=>f(Ex)≤E(f(x))
保凸运算
1. 凸函数的非负加权: f(x)=ω1f1(x)+?+ωnfn(x)
2. 仿射函数:g(x)=f(Ax+b)
3. 凸函数逐点最大值，逐点上确界
f(x)=max(f1(x),?,fn(x)); f(x)=supy∈Ag(x,y)
=>建立凸函数的方法： 将其表示为一族仿射函数的逐点上确界

共轭函数
f?(y)=supx∈domf(yTx?f(x))
右侧是关于y的仿射函数，对仿射函数逐点求上确界，则得到的函数f?(y) 是凸函数

凸优化

minf0(x)
S.t.fi(x)≤0,i=1,...,m; hj(x)=0,j=1,...p
可行点（解）；可行域；最优化值；最优化解
凸优化的局部最优=全局最优

对偶问题

minf0(x)
S.t.fi(x)≤0,i=1,...,m; hj(x)=0,j=1,...p
Lagrange函数
L(x,λ,ν)=f0(x)+∑i=1mλifi(x)+∑j=1pνjhj(x)
固定x，则Lagrange函数是关于 λ 和 ν 的仿射函数
Lagrange函数的对偶函数
g(λ,ν)=infx∈D(f0(x)+∑i=1mλifi(x)+∑j=1pvihi(x))
【机器学习笔记_数学基础_7-凸优化理论】在可行域逐点求下确界，得到的Lagrange函数的对偶函数是凹函数；
g(λ,ν)≤p?=> 对偶函数小于等于最优值

机器学习笔记_数学基础_7-凸优化理论

文章图片

机器学习笔记_数学基础_7-凸优化理论

文章图片

推荐阅读

上一篇：使用Google Earth Engine制作作物时间序列变化曲线

下一篇：试解leetcode算法题--求解方程