凸优化知识总结

重新搞一个电子版的凸优化知识总结，凸优化在支持向量机中的应用待补充。

有一个没展开的是二次规划以及半正定性的讨论

另外就是跳过了Slater条件和KKT条件的证明

补充阅读书籍《凸优化》

基础知识

凸函数

定义

一个函数 $f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ 被称为凸函数，如果

  • $\mathbf{dom}(f)(f$ 的定义域 $)$ 是凸集
  • 对于任何 $\mathbf{x}, \mathbf{y} \in \operatorname{dom}(f)$ 和 $0 \leq \theta \leq 1,$ 有

$$
f(\theta \mathbf{x}+(1-\theta) \mathbf{y}) \leq \theta f(\mathbf{x})+(1-\theta) f(\mathbf{y})
$$

仿射集

如果一个集合 $C \in \mathbb{R}^{n}$ 是仿射的，则 C 中两点间的直线也在 C 中

$$
\mathbf{x}=\theta \mathbf{x_{1}}+(1-\theta) \mathbf{x_{2}} \in C , \theta \in \mathbb{R}
$$

凸集

一个集合 $C \in \mathbb{R}^{n}$ 是凸的，则对于任意的 $\mathbf{x}, \mathbf{y} \in C,$ 有 $\theta \mathbf{x}+(1-\theta) \mathbf{y} \in C \quad 0 \leq \theta \leq 1$

常见的凸集：

  • $\mathbb{R}^n$

  • $\mathbb{R}_{+}^{n}$

  • 超平面

  • 半空间

  • 多面体：有限个半空间的交集

  • $-\log x \ on \ x>0$

  • $x\log x \ on \ x\geq0$

  • $f(\mathbf{x})=\mathbf{x}^{T} \mathbf{P} \mathbf{x}+2 \mathbf{q}^{T} \mathbf{x}+\mathbf{r}$ ， $\mathbf{P}\geq \mathbf{0}$

  • $n\geq 1$的范数球

凸集性质

  • 凸集的交集是凸集

凸函数充要条件

  • 一阶充要条件

    $f\left(\mathbf{x_{1}}\right) \geq f(\mathbf{x})+\nabla^{T} f(\mathbf{x})\left(\mathbf{x_{1}}-\mathbf{x}\right)$对于所有的$x_1$,$x$均成立

  • 二阶充要条件

    若函数$f$二阶可导，则函数为凸函数iff Hessian矩阵
    $$
    \mathbf{H}(\mathbf{x}) \succeq \mathbf{0}
    $$

保凸运算

  1. 若$f$为凸函数，则$f(\mathbf{Ax+b})$为凸函数

  2. 若$g$凸、$h$凸，$h$非递减，则$h(g(x))$为凸函数

  3. $f_1,f_2,..,f_m$为凸函数，$w_1,w_2,..,w_m \geq 0$ 则$\sum_{i=1}^m{w_if_i}$为凸函数

  4. $f_1,f_2,..,f_m$为凸函数，则有

优化问题

无约束最值问题

$$\min f(\mathbf{x}) \quad \mathbf{x} \in \mathbb{R}^{n}$$

有约束最值问题

这里等式约束和不等式约束同时出现

$$\begin{array}{cl}
\operatorname{minimize} & f_{0}(\mathbf{x}) \
\text { subject to } & f_{i}(\mathbf{x}) \leq 0 \text { for } i=1,2, \cdots, m \
& h_{i}(\mathbf{x})=0 \text { for } i=1,2, \cdots, p
\end{array}$$

凸优化问题

对于凸优化问题，要求$f$是凸函数，$h$是仿射函数（可行域是凸集，目标函数是凸函数）

解法是将带约束的优化问题利用拉格朗日乘数法转化为无约束优化问题

  • 线性规划
  • 二次规划
  • QCQP

（这部分内容不考虑$f$函数和$h$函数是否为凸函数或是仿射函数）

拉格朗日乘数法

$$
L(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{v})=f_{0}(\mathbf{x})+\sum_{i=1}^{m} \lambda_{i} f_{i}(\mathbf{x})+\sum_{i=1}^{p} v_{i} h_{i}(\mathbf{x})
\
s.t. \ \ \ \ \ \lambda \geq 0
$$

主问题如下
$$
\hat{p}=\min_{\mathbf{x}}\left(\max_{\boldsymbol{\lambda\geq 0}, \boldsymbol{v}} L(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{v})\right)
$$
拆解来看，是先最大化两个带约束函数的式子；若满足约束，这部分最大是0，若不满足约束，这部分为＋∞，后面无论怎么优化目标函数主问题的解都是正无穷；当满足约束条件时，主问题的最优解就是原问题的最优解，记主问题的最优解也就是目标函数的最优解为$\hat{p}$。

拉格朗日对偶性

构造一个对偶问题，其中$D$为函数$L$的定义域（此处不考虑$f$函数和$h$函数是否为凸函数或是仿射函数）
$$
\max_{\lambda \geq 0 , \mathbf{v}} \min_{\mathbf{x}\in D} L(\mathbf{x,\lambda,v})
$$
记对偶问题的最优解为$d^{*}$

首先考察$g( \mathbf{\lambda,v})= \min_{\mathbf{x}\in D} f_{0}(\mathbf{x})+\sum_{i=1}^{m} \lambda_{i} f_{i}(\mathbf{x})+\sum_{i=1}^{p} v_{i} h_{i}(\mathbf{x})$的凸性，对于每一个$x$，这都是一个关于$ \lambda,v$的仿射函数（既凸又凹），根据保凸运算有，关于$x$的g函数的逐点下确界是凹函数。

探究$g$函数的不等关系，若$\mathbf{\tilde{x}}$为可行域中任一点
$$
g(\mathbf{\lambda},v) = \min_{\mathbf{x}\in D} L(\mathbf{x,\lambda,v}) \leq L(\mathbf{\tilde{x},\lambda,v})
$$
又因为可行域中$\sum_{i=1}^{m} \lambda_{i} f_{i}(\mathbf{\tilde{x}})+\sum_{i=1}^{p} v_{i} h_{i}(\mathbf{\tilde{x}}) \leq 0$
$$
L(\mathbf{\tilde{x},\lambda,v})=f_{0}(\mathbf{\tilde{x}})+\sum_{i=1}^{m} \lambda_{i} f_{i}(\mathbf{\tilde{x}})+\sum_{i=1}^{p} v_{i} h_{i}(\mathbf{\tilde{x}}) \leq f_{0}(\mathbf{\tilde{x}})
$$
所以有
$$
g(\mathbf{\lambda},v) \leq f_{0}(\mathbf{x^{*}}) = \hat{p}
$$
注意:这里逐点下确界函数$g(\mathbf{\lambda},v)$的$x$只是在定义域中，而并不一定在可行域中。

涉及到一个问题，$\min_{x\in D} L(\mathbf{x,\lambda,v})$是关于$\lambda,\mathbf{v}$的一个函数，结果为$f_{0}(\mathbf{x^{‘}})+\sum_{i=1}^{m} \lambda_{i} f_{i}(\mathbf{x^{‘}})$，并且这里的$f_i(x^{‘}) \leq 0$

接下来需要探究主问题的最优解与对偶问题的最优解的关系：

利用前面两个结论

  1. 对于任意$\lambda \geq 0,\mathbf{v}$满足$g(\mathbf{\lambda},v) \leq f_{0}(\mathbf{\hat{x}}) = \hat{p}$
  2. 对偶问题最优解$\hat d$时的$\hat \lambda,\mathbf{\hat v}$

因此有结论（这被叫做弱对偶条件）。需要注意，这个结论与$f_0$函数是否为凸函数无关；并且$d^*$对应的$x$也不一定在可行域中。
$$
\hat d \leq \hat p
$$

继续观察对偶问题，对偶问题可以写为关于$\lambda,\mathbf{v}$的优化问题
$$
\max g(\lambda,\mathbf{v})
\
s.t. \lambda \geq 0
$$
可以很简单地观察出，对偶问题为在凸集的可行域中最大化一个凹函数，仍然是一个凸优化问题

（以下部分暂不加证明）

Slater条件

上面推导出一个结论：对偶问题的最优解总是小于等于原问题的最优解（$\hat d \leq \hat p$），Slater条件想探究不等式取等号（强对偶）的充分条件。

直接给条件：

  1. 原问题是一个凸优化问题
  2. 存在内点$\mathbf{x}$，使得$f_i(\mathbf{x})<0$对于$i=1,2,..,m$均成立（Slater条件）

并且此时两个问题的最优值点重合（都位于可行域中）
$$
\hat p=\hat d=L(\mathbf{\hat x,\hat \lambda,\hat v})
$$

KTT条件

目前想探究凸优化问题且满足Slater条件的前提下$\mathbf{\hat x,\hat \lambda, \hat v}$为原问题、对偶问题的最优解的充要条件

KKT条件如下