• 首页
  • ML/DL
  • 视觉相关
  • 数据结构与算法
  • Python
  • Java
  • WEB开发
  • 不知道分到哪里
Pteromyini的小站
没错Pteromyini就是树树的网名
  1. 首页
  2. ML/DL
  3. 正文

(邹博ML)凸优化

2020年03月03日 24点热度 2人点赞 0条评论

目录

  • 凸集的基本概念
  • 凸函数的基本概念
  • 凸优化的一般提法

凸集基本概念

思考两个不能式

两个正数的算术平均数大于等于几何平均数

截屏2020-03-03下午2.14.42

给定可逆对称阵Q,对于任意向量x,y,有:

截屏2020-03-03下午2.15.32

思考凸集和凸函数

在机器学习中,我们把形如

截屏2020-03-03下午2.16.26截屏2020-03-03下午2.16.45

这样的图形的都称为凸函数。

  • $y=x^2$是凸函数,函数图像上位于$y=x^2$的区域构成凸集。
    • 凸函数图像的上方区域,一定是凸集;
    • 一个函数图像的上方区域为凸集,则该函数是凸函数。

直线的向量表达

已知二维平面上的两定点A(5,1),B(2,3)尝试给出经过带你AB的直线方程:

截屏2020-03-03下午2.20.42

写成向量形式:

截屏2020-03-03下午2.21.11

其中:截屏2020-03-03下午2.21.26

几何体的向量表达

已知二维平面上的两个定点截屏2020-03-03下午2.38.54,则:

截屏2020-03-03下午2.39.28

推广到高维:

截屏2020-03-03下午2.40.05

仿射集(Affine set)

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

截屏2020-03-03下午2.42.37

仿射集的例子:直线、平面、超平面

超平面:$Ax=b$

f(x)=0表示定义域在$R^n$的超曲面:令$f(x)=Ax-b$,则$f(x)=0$表示截距为b的超平面。

n维空间的n-1维仿射集为n-1维超平面

凸集

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

注意和仿射集区分

截屏2020-03-03下午2.53.36

仿射集是凸集的一种特殊形式,仿射集一定是凸集。

k个点的版本:

截屏2020-03-03下午2.55.46

截屏2020-03-03下午2.56.13

凸包

集合C的所有点的凸组合所形成的集合,叫做集合C的凸包:

截屏2020-03-03下午2.57.24

集合C的凸包是能够包含C的最小凸集。

截屏2020-03-03下午2.58.17

超平面和半空间

超平面:hyperplane

$${x|a^Tx=b}$$

半空间:halfspace

$${x|a^Tx\le b}$$ $${x|a^Tx\ge b}$$

截屏2020-03-03下午3.04.26

欧式球和椭球

欧式球

截屏2020-03-03下午3.05.24

椭球

截屏2020-03-03下午3.05.51

范数球和范数锥(欧式空间推广)

截屏2020-03-03下午3.16.34

$R^3$空间中的二阶锥

截屏2020-03-03下午3.19.54

多面体

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

截屏2020-03-03下午3.20.52

仿射集(如超平面、直线)、射线、线段、半空间都是多面体

多面体是凸集

此外,有界的多面体有时称作多胞体(Polytope)

截屏2020-03-03下午3.22.39

保持凸性运算

  • 集合交运算
  • 仿射变换
  • 透视变换
  • 投射变换(线性分式变换)

集合交运算:半空间的交

截屏2020-03-03下午3.28.07

仿射变换

截屏2020-03-03下午3.28.31

透视变换

截屏2020-03-03下午3.31.38

投射函数(线性分式函数)

截屏2020-03-03下午3.32.29

分割超平面

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

截屏2020-03-03下午3.44.48

截屏2020-03-03下午3.45.24

分割超平面的构造:

截屏2020-03-03下午3.45.50

支撑超平面

设集合C,x0是C边界上的点,若存在$a\not=0$。满足对任意$x\in C$,都有截屏2020-03-03下午3.48.41成立,则称超平面截屏2020-03-03下午3.49.23为集合C在点x0处的支撑超平面。

凸集边界上任意一点,均存在支撑超平面。

反之,若一个闭的非中空集合,在边界上任意一点存在支撑超平面,则该集合为凸集。

凸函数

若函数f的定义域domf为凸集,且满足:

截屏2020-03-03下午3.53.35

一阶可微

若f一阶可微,则函数f为凸函数,当且仅当f的定义域domf为凸集,且:

截屏2020-03-03下午3.55.34

分析截屏2020-03-03下午3.55.57

对于凸函数,其一阶Taylor近似本质上是该函数的全局下估计。

反之如果一个函数的一阶Taylor近似总是其全局下估计,则该函数是凸函数

该不等式说明从一个函数的局部信息,可以得到一定车程度的全局信息。

二阶可微

若函数f二阶可微,则函数f为凸函数当且进档dom为凸集,且:

截屏2020-03-03下午3.58.40

若f为一元函数,上式表示二阶导大于等于0

若f是多元函数,上式表示二阶导Hessian矩阵半正定。

凸函数举例:

截屏2020-03-03下午4.00.33

上镜图

函数f的图像定义为:截屏2020-03-03下午4.05.48

函数f的上镜图(epigraph)定义为

截屏2020-03-03下午4.06.30

Jensen不等式:若f是凸函数

基本Jensen不等式

截屏2020-03-03下午4.31.59

若:

截屏2020-03-03下午4.32.21

则:

截屏2020-03-03下午4.32.45

若:

截屏2020-03-03下午4.33.07

则:

截屏2020-03-03下午4.33.26

Jensen不等式是几乎所有不等式的基础

保持函数凸性的算子

截屏2020-03-03下午4.35.48

凸函数的逐点最大值

若$f_1,f_2$均为凸函数,定义函数$f$:

截屏2020-03-03下午4.37.43

则函数$f$为凸函数。

证明:

截屏2020-03-03下午4.38.13

第二个不等号的表达:

截屏2020-03-03下午4.38.48

第二个不等好的形式化表达:

截屏2020-03-03下午4.39.16

共轭函数

原函数截屏2020-03-03下午4.39.46,共轭函数定义:

截屏2020-03-03下午4.40.09

显然,定义式的右端是关于y的仿射函数,他们逐点求上确界,得到的函数f*(y)一定是凸函数。

理解:

截屏2020-03-03下午4.41.39

例:

求共轭函数截屏2020-03-03下午4.42.09

截屏2020-03-03下午4.42.30

Fenchel不等式

根据共轭函数定义:

截屏2020-03-03下午4.43.25

易得:

截屏2020-03-03下午4.43.48

应用:

截屏2020-03-03下午4.44.11

凸优化

凸优化问题的基本形式:

截屏2020-03-03下午4.44.57

  • 优化变量:$x \in R^n$

  • 不等式约束:$f_i(x)\le0$

  • 等式约束:$h_j(x)=0$

  • 无约束优化:$m=p=0$

  • 优化问题的域:

    截屏2020-03-03下午4.50.31

  • 可行点(解)(feasible)

    截屏2020-03-03下午4.51.22

  • 可行域(可解集)

    所有可行点的集合。

  • 最优化值

    截屏2020-03-03下午4.52.11

  • 最优化解

    截屏2020-03-03下午4.52.31

对于

截屏2020-03-03下午4.44.57

其中

$f_i(x)$为凸函数,$h_j(x)$为仿射函数

凸优化问题的重要性质:

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

对偶问题

一般优化问题的Lagrange乘子法

Lagrange函数:截屏2020-03-03下午5.01.00

对于固定的x,Lagrange函数$L(x,\lambda,v)$是关于$\lambda$和v的仿射函数。

Lagrange对偶函数

Langrange对偶函数:

截屏2020-03-03下午5.05.08

若没有下确界,定义:

截屏2020-03-03下午5.06.41

根据定义,显然有:对截屏2020-03-03下午5.07.21,若原优化问题有最优值P*,则:

截屏2020-03-03下午5.08.01

进一步:Lagrange函数对偶函数为凹函数。

截屏2020-03-03下午5.08.57

鞍点解释

截屏2020-03-03下午5.09.59

截屏2020-03-03下午5.10.19

鞍点:最优点

截屏2020-03-03下午5.10.55

强对偶条件

若要对偶函数的最大值即为原问题的最小值,需要满足的条件:

截屏2020-03-03下午5.13.06

Karush-Kuhn-Tucker(KKT)条件

截屏2020-03-03下午5.15.03

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2020年03月03日

Pteromyini

树树虽然是个小辣鸡,但是树树想变强~~

打赏 点赞
< 上一篇
下一篇 >

树树虽然是个小辣鸡,但是树树想变强~~

文章目录
  • 1 目录
  • 2 凸集基本概念
    • 2.1 思考两个不能式
    • 2.2 思考凸集和凸函数
    • 2.3 直线的向量表达
    • 2.4 几何体的向量表达
    • 2.5 仿射集(Affine set)
    • 2.6 凸集
    • 2.7 凸包
    • 2.8 超平面和半空间
    • 2.9 欧式球和椭球
    • 2.10 范数球和范数锥(欧式空间推广)
    • 2.11 $R^3$空间中的二阶锥
    • 2.12 多面体
    • 2.13 保持凸性运算
    • 2.14 分割超平面
    • 2.15 支撑超平面
  • 3 凸函数
    • 3.1 一阶可微
    • 3.2 二阶可微
    • 3.3 上镜图
    • 3.4 Jensen不等式:若f是凸函数
    • 3.5 保持函数凸性的算子
    • 3.6 凸函数的逐点最大值
    • 3.7 共轭函数
    • 3.8 Fenchel不等式
  • 4 凸优化
    • 4.1 凸优化问题的基本形式:
    • 4.2 对偶问题
    • 4.3 Lagrange对偶函数
    • 4.4 鞍点解释
    • 4.5 强对偶条件
    • 4.6 Karush-Kuhn-Tucker(KKT)条件
最新 热点 随机
最新 热点 随机
将博客搬至CSDN Dijkstra 最短路算法 windows安装TeX Live 2019及TeXstudio iwrite复制攻略 爬取纽约时报特定关键词新闻并计数 简单写个logictic回归 植树节快到了-那就种棵决策树吧 简简单单做个房价预测 (ML邹博)回归
将博客搬至CSDN
(Github搬砖)动手学深度学习(TF2.0版)-2.3 自动求梯度 (Py练习)数组元素调换 (Github搬砖)动手学深度学习(TF2.0版)-5.2 填充和步幅 Dijkstra 最短路算法 (Github搬砖)动手学深度学习(TF2.0版)-4.5 读取和存储 (Github搬砖)动手学深度学习(TF2.0版)-3.16 实战Kaggle比赛:房价预测 (Py练习)日期格式转换 简简单单做个房价预测 (Github搬砖)动手学深度学习(TF2.0版)-3.14 正向传播、反向传播和计算图
友情链接

博客园博客

远处有泽细细说




标签聚合
贪心CV ty-深度学习 ty-WEB开发 微机原理 ty-未分类 py爬虫 ty-Python ty-数据结构与算法

COPYRIGHT © 2020 .Pteromyini ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

鲁ICP备19000938号-2

鲁公网安备 37160202000443号