您的位置: 首页  >  文章  >  凸优化概括总结

凸优化概括总结

分类: 文章 • 2024-04-18 16:42:39

相关概念

仿射集（Affine set）：

通过集合C中任意两个不同点的直线仍然在集合C内，则称集合C为仿射集。

比如：

  • 直线、平面、超平面

类似于线性变换 。
n维空间的n-1维仿射集为n-1维超平面。

仿射包（Affine hull）：

包含集合C的最小仿射集。

比如：

  • 直线的仿射包是它自己。
  • 球不是仿射集。

仿射维数：

仿射包的维数。

比如：

  • 三角形的仿射维数为2；
  • 线段的仿射维数为1；
  • 球的仿射维数为3。

仿射——单连通，不能有洞（带洞的是复连通）

内点：

对于集合C中的某个点x，以x为中心做半径为r的球B（r>0，且足够小），若球B完全落在C的内部（即B是C的子集），则x为C的内点。

集合C的仿射包A的内点y，如果y位于C中，则称y为集合c的相对内点relint。（对于集合C中的某个点y，以y为中心做半径为r的球B（r>0，且足够小），若球B和A的交集完全落在C的内部（即B∩A是C的子集），则y为C的相对内点。）
边界 相对边界

凸集（convex set）：

集合C内任意两点间的线段均在集合C内，则称集合C为凸集。

  • 所有的三角形都是凸的。
  • 任何一个仿射集都是凸集。

凸优化概括总结
以上两种写法其实是一致的。

凸包（convex hull）：

集合C的所有点的凸组合形成的集合，叫做集合C的凸包。

集合C的凸包是能够包含C的最小的凸集。
例题：给定n个离散点，求凸包；给定一个多边形，求凸包。

锥（cones）：

凸优化概括总结
射线是一个锥，n个射线的组合也是锥。
n阶半正定方阵的集合为凸锥。

超平面：

{x|aTx=b}

半空间：

{x|aTx<b} {x|aTx>b}
（法向量的方向是>0的，如3x+5y-z+6=0，法向量（3，5，-1），该向量指的方向大于零）

欧式球：

B(xc,r)={x|||x−xc||2≤r}={x|(x−xc)T(x−xc)≤r2}

椭球：

E={x|(x−xc)TP(x−xc)≤r2}，P为对称正定矩阵

范数

范数球

范数锥

多面体：

有限个半空间和超平面的交集。

  • 仿射集、射线、线段、半空间都是多面体。
  • 多面体是凸集，所以凸集的交集是凸集。
  • 有界的多面体称作多胞形（polytope）

保凸运算

集合交运算 仿射变换 f(x)=Ax+b,A∈Rm×n,b∈Rm，伸缩、平移、投影
两个集合的和、笛卡尔积（直积）、部分和（分配率）为凸集。
透视变换：透视函数对向量进行伸缩（规范化），使得最后一维的分量为1并舍弃之。 P:Rn+1→Rn,P(z,t)=z/t

直观意义：小孔成像

投射变换

投射变换（线性分式函数）：透视函数和仿射函数的复合。

凸优化概括总结

分割与支撑超平面

分割超平面：设C和D为两不相交的凸集，则存在超平面P，P可以将C和D分离。

构造：两个集合间元素的最短距离为两个集合的距离，做集合C和集合D最短线段的垂直平分线。
“若两个凸集C和D的分割超平面存在，C和D不
相交”为假命题。
若两个凸集至少有一个是开集，那
么当且仅当存在分割超平面，它们不相交。

支撑超平面

凸优化概括总结

凸函数

定义：

若函数f的定义域dom f 为凸集，且满足∀x,y∈domf,0≤r≤1, 有f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)

直观：

  • 割线位于函数那条曲线的上方。
  • 若f一阶可微，函数图像位于切线图像上方，则为凸函数。

进一步的思考：

  • 对于凸函数，其一阶Taylor近似本质上是该函数的全局下估计。
  • 反之，如果一个函数的一阶Taylor近似总是起全局下估计，则该函数是凸函数。
  • 该不等式说明从一个函数的局部信息，可以得到一定程度的全局信息。
  • 若f二阶可微，则函数f为凸函数当且仅当dom为凸集，且二阶导数大于零（若f是一元函数，则二阶导大于等于0；若f是多元函数，则二阶导Hessian矩阵半正定）。

凸函数举例：

  • 指数函数、幂函数（a>=1或a<=0）、负对数函数、负熵函数（xlogx）、范数函数等······
  • 直线既凸且凹。

上境图（epigraph ）

凸优化概括总结
一个函数是凸函数，当且仅当其上境图是凸集。

亚图（hypograph）

hypof=(x,t)|t≤f(x)

一个函数是凹函数，当且仅当其亚图是凸集。

Jensen不等式

f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)

（两个变量和k个变量的形式表达意义一样）
若k个变量变为连续，即积分，如p(x)为一个概率密度函数。
得到重要结论如下：
凸优化概括总结
应用

  • EM推导用到这个
  • KL散度（Kullback–Leibler divergence，相对熵），可证明D(q||p)>=0
  • 变分思想：用简单的分布q去近似复杂的分布p，，用D来评估近似程度。

函数保凸：

  • 凸函数的非负加权和
  • 凸函数与仿射函数的复合
  • 凸函数的逐点最大值、逐点上确界f(x)=max(f1(x),...fn(x),f(x)=supy∈Ag(x,y)（分别是离散情况和连续情况，y是某一维度）

一系列函数逐点上确界函数对应着这些函数上境图的交集。

共轭函数

不论凸凹函数的共轭函数都是凸函数。

Fenchel不等式

凸优化

一般优化问题的基本形式和相关概念：

凸优化概括总结
凸优化概括总结
某个集合X 的子集 E 的下确界(英语：infimum 或infima，记为inf E )是小于或等于的E 所有其他元素的最大元素，其不一定在E內。
x在某一个z定点的周围满足上述性质，则为局部最优。

凸优化问题

f0(x)、fi(x)为凸函数，hj(x)为仿射函数。

凸优化问题的重要性质：

  • 凸优化问题的可行域为凸集。
  • 凸优化问题的局部最优解即为全局最优解。

对固定的x，Lagrange函数L(x,λ,v)为关于λ和v的仿射函数。
凸优化概括总结
（对仿射函数求下确界，是凹的）

KKT条件

若要对偶函数的最大值即为原问题的最小值，需要满足KKT条件：
凸优化概括总结

相关推荐