机器学习之凸优化原理推导及相关知识总结

左手的ㄟ右手 2022-05-14 03:08 229阅读 0赞

### 文章目录 ###

*  目录
 *   *  1、了解凸集和仿射集的基本概念。
     *  2、知道几何体的向量表达。
     *  3、了解超平面和半空间的概念。
     *  4、了解分割超平面和支撑超平面的含义。
     *  5、知道jensen不等式。
     *  6、掌握知识：凸函数。
     *  7、掌握凸优化

# 目录 #

## 1、了解凸集和仿射集的基本概念。 ##

凸集：在凸集内部的两个点之间的线段仍在图形内，则称这个图形为凸集。  
仿射集：通过集合中任意两个不同点的直线仍然在这个集合内则称为这个集合的仿射集。  
仿射集说的是直线，凸集说的是线段。  
![这里写图片描述][70]  
![这里写图片描述][70 1]

## 2、知道几何体的向量表达。 ##

两个θ+（1-θ）=1代表的是两个点之间的关系是直线关系，如果不等于1则代表是其他的非线性的关系。  
![这里写图片描述][70 2]  
![这里写图片描述][70 3]

## 3、了解超平面和半空间的概念。 ##

超平面：如下图所示，将线性方程转化为矩阵的形式，然后（2,3）可以用向量a（已知点的向量）表示，（x,y）可以用向量x来表示，常数可以用b来表示。即若在2维空间中表示则超平面是一条直线，若a为N维向量（即在N维空间中表示），则式子可表示为一个N维空间中的超平面方程。  
半空间：如下图所示的2x+3y=1这条直线的一半即代表半空间，表示形式如下图所示  
![这里写图片描述][70 4]  
![这里写图片描述][70 5]  
2维空间中超平面是一条直线，3维中是一个平面。。。半空间就是超平面的一半的空间称为半空间。

## 4、了解分割超平面和支撑超平面的含义。 ##

分隔超平面：将两个超平面分割的平面称为分割超平面。即两个凸集内部的两个点d和c的连线的最短距离的垂直平分线即为这两个凸集的分割超平面。  
![这里写图片描述][70 6]  
支撑超平面：对于一个图形，通过它的任意边上画切线，如果图形在切线的一边则证明该图形是凸集组成的图形。若不是则证明该图形非凸集。可以把这个切线称为支撑超平面。  
如果一个集合任何一个点都存在支撑超平面则这个集合是凸集。  
![这里写图片描述][70 7]

## 5、知道jensen不等式。 ##

jenson不等式可以转化为f(E(x))<=E(f(x))，无论x是连续的或者是离散的。

## 6、掌握知识：凸函数。 ##

数学含义：凸函数定义式可以理解为一个函数，它的割线总是在函数的上方，则可称该函数是凸函数，如下图所示。  
![这里写图片描述][70 8]

## 7、掌握凸优化 ##

凸优化：基本形式如下所示，即任何问题都可以转化为求f0(x)的最小值，而对于f0(x)存在两个限制条件 Fi(x)（代表的是若干个不等式约束条件）与Hj(x)（代表的是若干个等式约束条件）。  
![这里写图片描述][70 9]  
对于最终的最优化值我们不关心，而是关心对应的x的值  
**最优值的公式数学含义：在什么样的条件下求对应的F0（x）的下确界**  
![这里写图片描述][70 10]  
由对应的限制条件可得lagrange函数中的Hj(x)为0。  
对偶函数通过梯度来求极大值。  
![这里写图片描述][70 11]  
![这里写图片描述][70 12]

将Lagrange函数转化为求它的对偶函数，而Lagrange对偶函数为凹函数，则凹函数的最大值也就对应原函数的最小值。  
![这里写图片描述][70 13]  
我们求得是最小值。通过下面的推导也就转化为求对偶函数。  
由于Hj(x)=0所以原式转化为g(λ)。  
PS：下图中的h(x)改为f(x)，h(x)=0了，已经被舍掉了。  
![这里写图片描述][70 14]  
\*\*整体的过程：\*\*优化问题，优化的形式是固定，即问题可以转化为一个表达式F（x）外加两个限制条件的表达式。即任何问题都可以转化为求f0(x)的最小值，而对于f0(x)存在两个限制条件 Fi(x)与Hj(x)。  
将凸优化问题转化为Lagrange函数，再将Lagrange函数转化为求它的对偶函数，而Lagrange对偶函数为凹函数，则凹函数的最大值也就对应原函数的最小值，即可得凸优化问题的解。

[70]: /images/20220514/81e1c9ab9950459cbe3fb618ea9d5544.png
[70 1]: /images/20220514/2f0f0b606b7c497995977b9ebe264f27.png
[70 2]: /images/20220514/7f0274c47e314ffbaa25457f69fb18b4.png
[70 3]: /images/20220514/d363974a678c42faae6cae09ac7175c7.png
[70 4]: /images/20220514/04d6ae11497e4f7b8c9553283e46ed34.png
[70 5]: /images/20220514/29d048eac0e6415c89c9dcacb4781eb1.png
[70 6]: /images/20220514/fb6123d4d3cd4df68dd3db7982d625db.png
[70 7]: /images/20220514/893aec1e628c48d89323494649d83954.png
[70 8]: /images/20220514/3cacaa40a5254809af3a1356064af7ac.png
[70 9]: /images/20220514/cfd41ccb79a849608a1cae1a4e30c762.png
[70 10]: /images/20220514/3c768ef877cc4c3596149e5139c41fb8.png
[70 11]: /images/20220514/b8eb745ecad549f1b990f37c013c0b66.png
[70 12]: /images/20220514/4d64dad4826e4a5b8d2f6bddfe4f40db.png
[70 13]: /images/20220514/d82da00105a5487da82bfa78d6450d60.png
[70 14]: /images/20220514/b530d0639e954807ba4b32214e37a4b3.png