type
status
date
slug
summary
tags
category
icon
password
凸优化复习期间做的总纲和简要个人理解
注：部分图快写的公式简述已经通过latex重写（2024年3月7日）
前置知识：
范数的定义：非负的、正定的、齐次性、满足三角不等式
柯西施瓦格不等式：两个向量的内积小于等于它们的范数之积
Young不等式：
📝 复习重点
仿射集合，凸集合；保凸运算
仿射集合是集合内部所有点的仿射组合都在集合内部的集合。（任两点的直线都在集合内）
凸集合是集合内部所有点的凸组合都在集合内部的集合。（任意两点的线段都在集合内）
超平面是关于x的非平凡线性方差的解空间，是一个仿射集合。
一个超平面把划分成两个半空间，并且半空间包含它的边界的超平面，半空间是凸的，但不是仿射的。
常见凸集：多面体（例：超平面、半空间、线段、射线、子空间、单纯形）、凸锥、Euclid球和椭球、范数球和范数锥、对称半正定矩阵集合（半正定锥）
保凸运算：交集、仿射函数（例：伸缩和平移）、透视函数（用n+1维向量的最后一维t做规范化，使得分量为1并舍弃之）、线性分式函数（先n→m+1仿射，再m+1→m透视）
锥，正常锥（广义不等式）
当集合C中任一向量x的非负倍数都在集合C中（这条向量对应的延伸出的射线都在集合C中），称它是锥或者非负齐次。
凸锥：是锥且是凸的。
集合C是凸锥的充要条件是它包含其元素的所有锥组合。
正常锥：1、凸2、尖（不包含直线）3、实（有非空内部）4、闭
广义不等式：A、B两个东西的差A-B属于对应这个广义不等式的正常锥，则A在对应的广义不等式中大于B。严格的广义不等式需要满足的是属于对应正常锥的相对内部
广义不等式的性质：1、对加法保序、2具有传递性、3、对非负数乘是保序的4、是自反的5、是反对称的6、对于极限运算是保序的
对偶锥
分离超平面定理、支持超平面定理
分离超平面定理：两个交集为空的凸集可以被一个超平面分开。
支持超平面定理：一个凸集边界上任意一点一定有经过它的支撑超平面。
凸函数(条件，操作)
凸函数定义域是凸集，定义域中任意两点之间线段上的一点的值小于这两点值的加权平均。
凸函数的条件：
一阶条件：若f可微，则函数为凸函数的充要条件为dom(f)为凸集，同时对于任意x，y属于dom(f)有f(y)≥，严格凸则去除等号。
二阶条件：对于开集dom(f)中的任意一点，它的Hession矩阵或者二阶导数广义不等式大于等于0
常见凸函数：
:指数函数、幂函数(（a≤0或a≥1）)、绝对值幂函数()(p≥1)、负熵(xlogx)
:范数、最大值函数、二次-线性分式函数、指数和的对数、几何平均
常见凹函数：
:幂函数（0≤a≤1）、对数函数
:对数行列式(logdetx)
其他概念：下水平集和上境图，Jensen不等
保凸运算：非负加权求和、复合仿射映射、逐点最大和逐点上确界（上境图的交集→凸集的交集得到）、复合(f=hog)（f’’(x)=h’’(g(x))g’(x)^2+h(g(x))g’’(x)）（h凸且非减、g凸，则f凸；h凸且非增、g凹，则f凸；h是凹函数且非减、g凹,f凹；h是凹函数且非增、g凸，f凹），透视函数（g(x,t)=tf(x/t)）。
共轭函数
无论f是否是凸函数，f*都是凸函数，因为它是一系列y的凸函数的逐点上确界。
Fenchel不等式（可微时是Young不等式）：f(x)+
当f是闭and凸函数有：凸函数的共轭函数的共轭函数为原函数
独立凸函数的和的共轭函数是各个凸函数的共轭函数的和
拟凸/拟凸函数
拟凸函数是定义域和所有下水平集是凸集的函数，又称单峰函数，凸函数也是拟凸函数，拟凸函数不一定是凸函数。
用二分法来求解拟凸优化（凸可行性问题求解）
等价性问题
可以简单从一个问题的解获得另一个问题的解，并且反之亦然的两个问题，我们一般主动构建等价问题来求解一些问题。
构建方法：变量变换、目标函数和约束函数的变换、松弛变量、消除等式约束、消除线性等式约束、引入等式约束、优化部分变量、上境图问题形式、隐式和显式约束
凸优化(性质)
目标函数、不等式约束函数都是凸函数，等式约束函数都是仿射函数的优化问题。
性质：局部最优解就是全局最优解；
对偶问题
拉格朗日函数：
拉格朗日对偶函数：无论如何都是凹函数，构成了最优值的下界
拉格朗日对偶问题：从拉格朗日函数能得到的最好下界是什么？可以表述为在不等式优化的系数向量广义大于0的情况下，对g(\lamda,v)优化求最大值问题。
弱对偶性：拉格朗日对偶问题的最优值≤
强对偶性（需要条件）：=
一个强对偶性成立的约束条件是Slater条件：存在一点严格可行（使得不等式约束都是小于的，等号不成立）（弱化版：仿射的不等式约束不需要严格成立）
KKT最优条件
1、可行条件
2、互补松弛条件
3、偏导为0条件
证明思路：
范数逼近、最小范数问题、正则化逼近
范数逼近：最小化||Ax-b||的无约束优化问题。
最小范数问题：在Ax=b的等式约束下，最小化||x||，可以转换成范数逼近问题。（按我的理解就是在满足一系列等式约束条件下，最小化x的范数）
双准则式：寻找向量x使其较小，同时使得残差Ax-b小，也就是以||Ax-b||，||x||为双目标的（凸）向量优化问题
正则化逼近：求解双准则问题的一个常见标量化方法，有多种形式
一个形式是：极小化目标函数的加权和
另一个常用方法是：极小化加权范数平方和
投影
dist（x0,c）=inf{||x0-x|| | xC}其中的极小总是可达的
称C中每一个最接近x0的点（到x0的距离为x0到集合C的距离），为x0在C上的投影
若C是凸且闭的而范数严格凸（比如Euclid范数），那么对于任意x0，它在C上的投影是唯一的。
上述结论的逆命题成立：如果对于每个x0，在C中有唯一的Euclid投影，那么C是闭且凸的。
强凸性和光滑性
强凸性：函数对应的二阶梯度大于一个正常量m乘单位向量I,也就是它的梯度不会趋近于0或者等于0，变化趋势更强烈，后面的下降方法中讨论的都是具有强凸性的函数。
光滑性：在书上没有找到对应的定义，只有令函数光滑而避免噪声的方法。后补,
（知乎上截了定义来看）
下降方法
对无约束问题采用的迭代算法求解
通用下降方法：
给定初始点x属于目标函数定义域，重复进行：
1、确定下降方向，
2、直线搜素。选择步长t>0
3、修改。x:=x+t
直到满足停止准则
精准直线搜索：沿着对应射线确定该射线上的最优解
回溯直线搜索：非精确直线搜素，只需f有足够的减少
给定f在x处的下降方向（三角形）x，参数属于（0，0.5），属于（0，1）
t:=1
如果f(z+)>f(x)+t，令t:= t。
梯度下降法
最速下降法：通过选择到方向导数最小的方向，也就是所用范数的单位球中在负梯度方向上投影最长的方向
Newton方法：以Newton步径为下降方向的方法，Newtonb步径为
梯度下降法
梯度下降法是以负梯度为搜索方向，给定初始点x属于可行集，
重复进行：
1、：=-
检验停止准则是否满足
2、直线搜索。通过精准或回溯直线搜索方法确定步长t
3、修改。x:=x+t
直到满足停止准则
📎 参考文章
- 《凸优化》中文版 清华大学出版社
- 作者:Cu.Li.Zn.
- 链接:culizn.cn/article/d2925c00-174e-4438-8e4e-94d0a8641591
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。