凸优化课程

优化问题

定义:从一个可行解中找到一个最好的元素。通常来说优化问题都可以写成如下的形式：

最小化目标函数： $min f_l(x)$

m个约束函数： $st: f_i(x)<=b_i ( i=1...m)$

$x = [x1...xn]^T$

凸规划与非凸规划

凸规划满足:

凸规划都是相对容易解决的，非凸规划比较难解决。

仿射集

一个集合c是仿射集，若x1，x2在集合c中，则x1与x2的连线也在集合c中

仿射组合: $θ_1(x_1)+θ_2(x_2)+...θ_k(x_k) ∈ c$ ,且 $θ_1(x_1)+θ_2(x_2)+...θ_k(x_k) = 1$

仿射包：任何集合c，构造尽可能小的仿射集

凸集

组合

正定与半正定

半正定：就是特征值>=0,但是通常来说特征值太难求。我们可以通过假如X属于R，对于任意X，都要满足 $X*A*X^T > 0$ ，则说明A具有半正定。

证明对称半正定矩阵一定是凸锥或者凸集

正定:

仿射函数

仿射函数即由由1阶多项式构成的函数，一般形式为 f (x) = A x + b，这里，A 是一个 m×k 矩阵，x 是一个 k 向量,b是一个m向量，实际上反映了一种从 k 维到 m 维的空间映射关系。设f是一个矢性（值）函数，若它可以表示为f(x1,x2,…,xn)=A1x1+A2x2+…+Anxn+b，其中Ai可以是标量，也可以是矩阵，则称f是仿射函数。

23-24

广义凸问题

狭义凸问题

目标函数是凸函数，不等式约束是凸函数， $a_i^TX = b_i$ 是一个仿射函数

重要性质凸问题：局部最优 = 全局最优

首先定义局部最优解: 当 $x$ 是可行的(亦即位于可行域内), 而且存在 $(R > 0)$ , 使得对于所有 $(\parallel x-z \parallel_2 \leq R)$ 的位于可行点 $(z)$ ,使得 $(f(x) \leq f(z))$ .

证明过程如下：

令 $x$ 是一个局部最优解, 但不是全局最优解, 所以存在一个可行的点 $y$ 使得 $f(x) > f(y)$ .根据局部最优解的定义, 没有一个可行点 $z$ 满足 $\parallel x-z \parallel_2 \leq R, f(z) < f(x)$ . 但是, 我们可以构造一个组合 $z$

z=\theta y + (1-\theta)x, \theta=\frac{R}{2\parallel x-y \parallel_2}

其中 $\theta$ 是一个定值，这是一种特殊的取法，由于 $\parallel x-y \parallel_2 > R$ ,因为 $y$ 肯定在局部范围外，所以 $\theta=\frac{R}{2\parallel x-y \parallel_2}$ 的取值范围为 0 ~ 1/2。所以z是一个凸组合。因为z是凸组合，所以 $z$ 也一定是可行的。

由于是凸问题，所以可得： $f(z) = { \theta y + (1-\theta)x }, f(z) \leq (1-θ)f(x) + θf(y)$

由于 $\theta=\frac{R}{2\parallel x-y \parallel_2}$ ，所以 $\parallel x-z \parallel_2= {\theta \parallel x-y \parallel_2 = \frac{R}{2} }$ , 可得 $f(y) < f(x) <= f(z)$ 。

因为 $f(y) < f(x) <= f(z)$ ，显然 $(1-θ)f(x) + θf(y) < f(z)$

$f(z) \leq (1-θ)f(x) + θf(y) < f(z)$ , 假设不成立，所以(x) 是全局最优解.

对偶问题

任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应，反之亦然，如果我们把其中一个叫原问题，则另一个就叫做它的对偶问题，并称这一对互相联系的两个问题为一对对偶问题。

“三凸”

首先，我们还是要看下，什么是凸优化？抛开凸优化中的种种理论和算法不谈，纯粹的看优化模型，凸优化就是：1、在最小化（最大化）的要求下，2、目标函数是一个凸函数（凹函数），3、同时约束条件所形成的可行域集合是一个凸集。以上三个条件都必须满足。而世间万物千变万化，随便抽一个函数或集合它都可能不是凸的。

凸集定义：在欧式空间中，对于任意两点的连线上的任意点都在该集合中，我们就可以判定该集合为突凸集。

凸函数几何定义：函数上任意两点的连线在两点中点的上方

半正定矩阵的定义：特征值大于等于0的实对称矩阵实对称矩阵：

如果有n阶矩阵A，其矩阵的元素都为实数，且矩阵A的转置等于其本身(aij=aji)(i,j为元素的脚标)，而且该矩阵对应的特征值全部为实数，则称A为实对称矩阵。

半正定矩阵：特征值大于等于0的矩阵。

凸函数的充要条件：对于一元函数来说，其一阶导数等大于等于0，对于多元函数来说，其Hessian Matrix（黑塞矩阵）为半正定矩阵。黑塞矩阵：

我来表露下个人浅显的理解。半正定与正定矩阵同意用半正定矩阵来事例：首先半正定矩阵定义为: 其中X 是向量，M 是变换矩阵我们换一个思路看这个问题，矩阵变换中，代表对向量 X进行变换，我们假设变换后的向量为Y，记做。于是半正定矩阵可以写成：这个是不是很熟悉呢？他是两个向量的内积。同时我们也有公式：||X||, ||Y||代表向量 X,Y的长度，是他们之间的夹角。于是半正定矩阵意味着, 这下明白了么？正定、半正定矩阵的直觉代表一个向量经过它的变化后的向量与其本身的夹角小于等于90度。

凸二次规划

有一篇好文章：www.cnblogs.com/xinchen1111…

可能要在满足一定约束条件的情况下最小化目标函数，比如有一个等式约束：

\begin{align*}
min\quad f(x)\\
s.t.\quad h(x) = 0
\end{align*}

解决这个的时候问题不能先用上面的方法求出 f(x) 的极值点，然后留下满足方程 h(x)=0 的。因为这个问题的解可能根本不是 minf(x) 的解，它们是没有关系的。那么还是要从问题本身去找线索：

如图，其中的圆圈是指目标函数 f(x，y) 投影在平面上的等值线，表示在同一个圆圈上，黑线是约束条件 h(x)=0 的函数图像。所以等值线与函数图像相交的点其实就是所有满足约束的点。那么极值点只有可能在等值线与函数图像相切的地方取到，因为如果在相交的地方取到，那么沿着 h(x) 的图像往前走或者往后走，一定还有其它的等值线与它相交，也就是 f(x,y) 的值还能变大和变小，所以交点不是极值点，只有相切的时候才有可能是极值点(不可能同时变大和变小了)。在相切的地方 h(x) 的梯度和 f(x,y) 的梯度应该是在同一条直线上的。（这一点可以这么想，在切点处两个函数的梯度都与切平面垂直，所以在一条直线上）

所以满足条件的极值点一定满足：∇f(x,y)=λ∇h(x,y) ( λ=0 是允许的，表示 f(x,y) 本身的极值点刚好在切点上)，然后和原来的等式方程 h(x,y)=0 联立，然后只要解出这个方程组，就可以得到问题的解析解了。当然也存在解不出来的情况，就需要用罚函数法之类的方法求数值解了。

为了方便和好记，就把原来的优化问题写成 f(x,y)+λh(x,y) 的形式，然后分别对 λ,x,y 求偏导，并且令偏导为 0 就行了，和之前得到的方程组是一样的。这种方法叫拉格朗日乘数法。

如果有多个等式约束怎么办呢，如下图：

这里的平面和球面分别代表了两个约束 h1(x) 和 h2(x)，那么这个问题的可行域就是它们相交的那个圆。这里蓝色箭头表示平面的梯度，黑色箭头表示球面的梯度，那么相交的圆的梯度就是它们的线性组合（只是直观上的~），所以在极值点的地方目标函数的梯度和约束的梯度的线性组合在一条直线上。所以就满足：

\nabla f(x) = \lambda \sum_{i=1}^{2}\mu_{i}\nabla h_i(x)=\sum_{i=1}^{2}\lambda_{i}\nabla h_i(x)\\
h_1(x)=0\\
h_2(x)=0

大于2个约束的情况也一样。为了好记，将原来的约束的问题写成 L(x,λ)=f(x)+∑ni−1λi∇hi(x)的形式，然后对 x、λ 求偏导，然后让它们为 0。结果像上面一样直接列方程组是一样的。这个可以看做是一种简记，或者是对偶问题，这个函数叫做拉格朗日函数。

再进一步，如果问题中既有等式约束，又有不等式约束怎么办呢？对于：

\begin{align*}
min \quad f(x)\\
& s.t. \quad h(x) = 0\\
&\quad \quad \quad g(x) \leq 0
\end{align*}

当然也同样约定不等式是 ≤，如果是 ≥ 只要取反就行了。对于这个问题先不看等式约束，对于不等式约束和目标函数的图：

阴影部分就是可行域，也就是说可行域从原来的一条线变成了一块区域。那么能取到极值点的地方可能有两种情况：还是在 h(x) 和等值线相切的地方 f(x) 的极值点本身就在可行域里面。

因为如果不是相切，那么同样的，对任意一个在可行域中的点，如果在它附近往里走或者往外走，f(x) 一般都会变大或者变小，所以绝大部分点都不会是极值点。除非这个点刚好在交界处，且和等值线相切；或者这个点在可行域内部，但是本身就是 f(x) 的极值点。如下图（维基百科上的图~）：

对于第一种情况，不等式约束就变成等式约束了，对f(x)+λh(x)+μg(x) 用拉格朗日乘子法：

\nabla f(x)+\lambda \nabla h(x)+\mu \nabla g(x) = 0\\
h(x)=0\\
g(x)=0\\
\mu \geq 0

这里需要解释一下，为什么不是 μ≠0 而是 μ≥0。后面的约束比前面的更强。看“不等式约束”那个图，我们已经知道了问题中的可行域是在 g(x)≤0 一侧，而 g(x) 的梯度是指向大于 0 的一侧，也就是不是可行域的一侧。而求的问题是极小值，所以 f(x) 在交点处的梯度是指向可行域的一侧，也就是说两个梯度一定是相反的。所以也就可以确定这里的系数一定是大于 0 的。而等式约束由于不知道 h(x) 的梯度方向，所以对它没有约束，那么为什么 μ 还能等于 0 呢，因为极值点可能刚好在 g(x) 上。

对于第二种情况，不等式约束就相当于没有，对 f(x)+λh(x) 用拉格朗日乘子法：

\nabla f(x)+\lambda \nabla h(x)= 0\\
h(x)=0\\
g(x) \leq 0

最好把两种情况用同一组方程表示出来。对比一下两个问题，不同的是第一种情况中有 μ≥0 且 g(x)=0, 第二种情况 μ=0 且 g(x)≤0 。综合两种情况，可以写成 μg(x)=0 且 μ≥0 且 g(x)≤0：

\nabla f(x)+\lambda \nabla h(x)+\mu \nabla g(x) = 0\\
\mu g(x) = 0\\
\mu \geq 0 \\
h(x)=0\\
g(x) \leq 0

这个就是 KKT 条件。它的含义是这个优化问题的极值点一定满足这组方程组。（不是极值点也可能会满足，但是不会存在某个极值点不满足的情况）它也是原来的优化问题取得极值的必要条件，解出来了极值点之后还是要代入验证的。但是因为约束比较多，情况比较复杂，KKT 条件并不是对于任何情况都是满足的。要满足 KKT 条件需要有一些规范性条件（Regularity conditions），就是要求约束条件的质量不能太差，常见的比如：

1.LCQ：如果 h(x) 和 g(x) 都是形如 Ax+b 的仿射函数，那么极值一定满足 KKT 条件。

2.LICQ：起作用的 g(x) 函数（即 g(x) 相当于等式约束的情况）和 h(x) 函数在极值点处的梯度要线性无关，那么极值一定满足 KKT 条件。

3.Slater 条件：如果优化问题是个凸优化问题，且至少存在一个点满足 h(x)=0 和 g(x)=0，极值一定满足 KKT 条件。并且满足强对偶性质（下面会讲）。

这里的 Slater 条件比较重要，因为它可以推导出强对偶性质（下面会讲到，它比 KKT 条件还好）。它需要原问题是凸优化问题。所谓凸优化就是这个优化问题的优化函数是凸函数，并且可行域是凸集。可行域数凸集就要求其中的 h(x)≤0 的条件中 h(x) 必须也是凸函数，而 g(x)≤0 中的 g(x) 必须是 Ax+b 形式的，也就是仿射函数（比如二维的情况，可行域就在 g(x) 这条曲线上，那么 g(x) 必须得是直线才能满足凸集的定义）。

其它条件还有很多，可以看维基百科。

如果有多组等式约束 gi(x)=0(i=1,..,n), 和不等式约束 hi(x)≠0(i=1,..,n)也是一样，只要做个线性组合就行了：

\nabla f(x)+\sum_{i=1}^{n}\lambda_i \nabla h_i(x)+\sum_{i=1}^{n}\mu_i \nabla g_i(x) = 0\\
\mu_i g(x)_i = 0\\
\mu_i \geq 0\\
h_i(x)=0\\
g_i(x) \leq 0\\
i = 1,2,...,n

问题到这里就大致解决了，KKT 条件虽然从理论上给出了极值的必要条件，但是一般实际解的时候直接方程也是很困难的（特别是约束很多的时候），一般也会采用罚函数法等数值方法。

为了更好的解决这个优化问题，数学家还找到了它的对偶问题。找一个优化问题的对偶问题的一般因为是对偶问题比原问题更好解决，并且对偶问题的解和原问题是一样的。上面的拉格朗日函数也可以看做原问题的对偶问题。

为了去掉问题中的约束，可以把它们作为惩罚项加到目标函数中 minxf(x)+Mh(x)+Ng(x) 其中 M, N 是两个很大的正数，在数值解法中可以直接这样做，这个就是罚函数法的思路。不过在理论推导时这样做是不严谨的，除非 M, N 为无穷大。所以就把原问题改写 L(x,μ,λ)=minxmaxμ,λf(x)+λh(x)+μg(x) 。这个式子可以这么理解，现在外层给定任意一个 x0 值，然后内层在给定的 x0 下优化那个函数，让它最小。然后外层选能够让内层得到的值最大的一个 x0，得到的函数表达式就是：

L(x,\mu,\lambda)=
\left\{\begin{matrix}
f(x) & (x \quad满足约束)\\
\infty & (x \quad不满足约束)\\
\end{matrix}\right.

所以外层选的那个 x0 一定满足约束，否则，内层的 max 的时候会让 μ 或者 λ 为无穷大。外层不会选那些能让内层得到无穷大的 x 值。这样改写就和原来的带约束形式完全一致了，但是形式不同。这样可以利用 maxminf(x)≤minmax(f(x)) 这个公式（这个很好理解，minf(x)≤minmaxf(x), 然后就有这个公式了），得到原问题的最小值的一个下界，就是:

min_{x}max_{\mu,\lambda}f(x) + \lambda h(x) + \mu g(x) \geq max_{\mu,\lambda}min_{x}f(x) + \lambda h(x) + \mu g(x)

前面的就是原函数，后面的是它的一个下界。那么为什么要这样做呢? 是因为后面的一定是一个凸规划(理论上证明了的)，比较好解决。但是这个只是一个下界，它们之间还是有一定的差距。这个差距叫对偶误差（duality gap）。对偶误差如果为 0 其实是一个非常好的性质，表示可以直接求解后面的问题得到原问题的解，这种性质叫强对偶性质，否则就只是弱对偶。

强对偶性质非常好，但是要求也很苛刻，比 KKT 条件要苛刻。如果问题满足强对偶一定也满足 KKT 条件，反之不一定。对于这类优化问题，KKT 条件、强对偶、规范性条件之间的关系是：

对于强对偶推出 KKT 可以参看这篇博客。

机器学习中的凸优化理论