最近看文章，学到stackelberge game的时候，突然发现需要使用convex optimization的方法，之前一直看看就过去了，这次决定，稍微认真一点。

一、凸优化相关概念

凸优化：

如果一个最优化问题的可行域是凸集，并且目标函数是凸函数，则该问题为凸优化问题。下面一一接受，凸集，凸函数。

凸集：

欧式空间中，对于集合中的任意两点的连线，连线上任意一点都在集合中，我们就说这个集合是凸集。
几何意义：

凸函数：

定义在$\mathbb{R}^n \rightarrow \mathbb{R}$Rn→R上的函数f是凸函数，如果它的定义域$\mathbb{D}(f)$D(f)是一个凸集且对任意的$x,y\in \mathbb{D}$x,y∈D和$0\leq \theta \leq 1,f(\theta x +(1-\theta y)) \leq \theta f(x) + (1-\theta)f(y)$0≤θ≤1,f(θx+(1−θy))≤θf(x)+(1−θ)f(y)恒成立。
几何意义：

充要条件：如果f(x)在开凸集S上具有二阶连续偏导数，且f(x)的海塞矩阵（二阶偏导的矩阵）在S上处处半正定，则f(x)为S上的凸函数。对于其与正定矩阵，其判定的方法，我没有细学，请参考here

凸优化问题的优势

1、凸优化问题的局部最优解就是全局最优解
2、很多非凸问题都可以被等价转化为凸优化问题或者被近似为凸优化问题。
3、凸优化问题的研究较为成熟，当一个具体被归为一个凸优化问题，基本可以确定该问题是可被求解的

凸优化问题的求解

直接考虑一个比较复杂的约束优化形式，一般使用拉格朗日函数+KKT条件求解。注意目标函数是凸函数，定义域是凸集。
如果是浅度学习，只是掌握这个tool的话到这里已经可以了，记着(3)(4)三个条件比较特殊，使用时稍微注意。后面主要介绍为什么会有（4）这个互补松弛条件自己用的比较多所以只认真学了为啥有（4）

如果我们优化$f(x)$f(x) with $g(x)\leq 0$g(x)≤0，考虑拉格朗日橙子：
$F=f(x)+\lambda g(x)$F=f(x)+λg(x)

此时只有两种情况
（1）可行解在$g(x)\leq 0$g(x)≤0，范围内，那么相当于并没有不等式的约束，因为你不约束我们的解依然在这里，此时可以令$\lambda=0$λ=0，去除约束。（左图，蓝线为等高线）
（2）可行解在并不在$g(x)\leq 0$g(x)≤0区域内，那么加上约束的话，可行解会落在在边界上，那么此时$g(x)=0$g(x)=0。

也就是说无论是哪种情况，要么$\lambda=0$λ=0，要么$g(x)=0$g(x)=0，因此会有对所有不等式约束的松弛条件(4)：$\lambda g(x)=0$λg(x)=0。