凸优化理论学习

2021年9月7日 2点热度 0条评论 来源: 诚朴求食

在机器学习和深度学习的工作中,最后一步都是对损失函数的极值计算,而这个极值如果我们能够找到全局极值也就是最小值,这是最好的情况;否则我们就必须想办法把原来的问题进行转化或者尝试其他的方法。这其中用到的方法就是凸优化理论。

下面我将对我学习的凸优化理论进行一些整理,知识点可能比较杂碎,但句句是关键和我们所必须了解的。

衡量一个问题难易的程度不在于其是否线性,而在于是凸问题还是非凸问题。

一阶导数有时候用g(x)表示,海森矩阵用H(X)表示(g表示gradient,H表Hessian)。

问题针对无约束优化问题和有约束优化问题两种。

无约束优化问题

海森矩阵的性质:海森矩阵是对称矩阵,可以衡量二次型的正负,也就特征值是大于0还是小于0。

无约束优化直接分析法的局限(直接求导)
1、可能这个函数就不可导
2、函数可以求导,但是变量很多,求不出导数为0的x
3、就算求出了解,但是这个解可能是个集合

然后使用无约束优化迭代法
1、选择一个初始点;
2、决定搜索方向,使函数下降(核心);
3、决定步长;
4、如果小于容错值,停止迭代;否则继续迭代

三种常用的方法:
第一种:梯度下降法,沿负梯度方向,只使用了一阶导数:搜索比较慢,等值线上显示为Z型走法,轨迹是相互正交的。
第二种:牛顿法。在一阶导数的基础上考虑了二阶导数,性能会更好一点。涉及到了海森矩阵求逆,可能不可逆,比如半正定或者半负定,要做适当修正。等值线上走的是直的。
第三种:拟牛顿法。使用梯度信息去生成对于海森逆矩阵的连续低秩估计。收敛速度比牛顿法相当,但是计算复杂度低很多。

一般约束优化问题

定义:约束条件有等式,也有不等式。找到最优解至少要碰到一个边界,不然约束条件都没作用。

在此我们引入KKT条件,目的是为了思考如何把约束优化转换为无约束优化,它是一个一阶必要条件。

KKT只是一个必要条件,但是工程中就这么算。在函数是凸函数的时候,只要是局部最小解,就是全局最小解。凸函数和非凸函数是一个分水岭。当问题转换为凸问题后,一切都变得很简单。

下面我们给出凸集的定义:
凸集的定义:随便拉两个点,线段在这个图形内。超平面是一个凸集,半空间也是凸集(超平面的一边),多面体,凸集的交集是凸集、欧式球、椭球,p范数都是凸集。



KKT条件在凸优化问题上是充要条件。所以谁能把一个问题转换为凸问题这就是牛逼的地方。解一个原始问题,就等于在解另一个镜像问题,如果另一个问题是凸问题,则这两个问题之间的gap为0,也就是说解一样。

在对一个问题进行求解的时候,我们需要对初始点进行一个初始化。这个初始化的点的选择,我们可以先假设这个问题是凸问题,求出他的解,然后再当成原始问题的初始解。

约束条件中,不等式条件要求是凸函数,等式条件要求是线性函数

    原文作者:诚朴求食
    原文地址: https://blog.csdn.net/fengchi863/article/details/80224624
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。