机器学习笔记之最优化理论与方法(五)凸优化问题(上)

引言

本节将介绍凸优化问题，主要介绍凸优化问题的基本定义、凸优化与非凸优化问题的区分。

凸优化问题的基本定义

关于最优化问题$\mathcal{P}$描述如下：
$$\mathcal{P}\Rightarrow \{\begin{array}{l}\min f(x_1,x_2,\cdots ,x_n)\\ \text{s.t. }\{\begin{array}{l}{\mathcal{G}}_i(x_1,x_2,\cdots ,x_n)\le 0i=1,2,\cdots ,m\\ {\mathcal{H}}_j(x_1,x_2,\cdots ,x_n)=0j=1,2,\cdots ,l\end{array}\end{array}$$
同时记最优化问题的可行域$\mathcal{S}$为：
从可行域中采样出的$x\in \mathcal{S}$也被称作可行解。
S = { x ∈ R n ∣ G i ( x ) ≤ 0 , i = 1 , 2 , ⋯ , m ; H j ( x ) = 0 , j = 1 , 2 , ⋯ , l } \mathcal S = \{x \in \mathbb R^n \mid \mathcal G_i(x) \leq 0,i=1,2,\cdots,m;\mathcal H_j(x) = 0,j=1,2,\cdots,l\} S={x∈Rn∣Gi​(x)≤0,i=1,2,⋯,m;Hj​(x)=0,j=1,2,⋯,l}
什么情况下，最优化问题$\mathcal{P}$被称作凸优化问题$?$针对上述描述，需要满足如下三个条件：

• 目标函数$f(x)$是关于决策变量$x$的凸函数；
• $m$个不等式约束函数${\mathcal{G}}_i(x),i=1,2,\cdots ,m$均是关于决策变量$x$的凸函数；
• $l$个等式约束函数${\mathcal{H}}_j(x),j=1,2,\cdots ,l$均是关于决策变量$x$的线性函数。

观察不等式约束函数${\mathcal{G}}_i(x)$，为什么要强调它们是凸函数$?$，首先，观察不等式约束的描述：
$${\mathcal{G}}_i(x)\le 0i=1,2,\cdots ,m$$
这种描述明显是：关于函数${\mathcal{G}}_i(x)$在水平值$a=0$处的水平集${\mathcal{L}}_{i;0}$：
关于水平集的概念，详见凸函数：定义与基本性质。
L i ; 0 = { x ∣ G i ( x ) ≤ 0 , x ∈ R n ; i = 1 , 2 , ⋯ , m } \mathcal L_{i;0} = \{x \mid \mathcal G_i(x) \leq 0,x \in \mathbb R^n;i=1,2,\cdots,m\} Li;0​={x∣Gi​(x)≤0,x∈Rn;i=1,2,⋯,m}
根据水平集的定义：如果${\mathcal{G}}_i(x),i=1,2,\cdots ,m$是凸函数，那么其对应的水平集${\mathcal{L}}_{i;0},i=1,2,\cdots ,m$必然是凸集。而$m$个不等式约束对应的结果是$m$个水平集的交集，而该交集必然也是凸集。
关于凸集的交集也是凸集同样见上述链接几种保持函数凸性的运算。

同样，观察等式约束函数${\mathcal{H}}_j(x),j=1,2,\cdots ,l$，如果它们是线性函数：
$${\mathcal{H}}_j(x):{\mathcal{A}}_j^{T}x+b_j=0j=1,2,\cdots ,l$$
而线性函数同样是凸函数，因而等式约束函数描述的集合同样也是凸集。从而在上述两类约束条件下的可行域$\mathcal{S}$也必然是凸集。根据凸集的简单认识中介绍的：凸优化问题与凸集合凸函数的关系中的两个条件：

• 目标函数$f(x)$是一个凸函数；
• $x$的可行域$\mathcal{S}\Rightarrow x\in \mathcal{S}$是一个凸集；

满足条件的最优化问题才属于凸优化问题。

相反，如果目标函数$\bar{f}(x)$描述为：$\max \bar{f}(x)$，想要将其转化为凸优化问题，我们需要判定：$\bar{f}(x)$是否为凹函数。如果$\bar{f}(x)$是凹函数，可以将其转化为相应凸函数的优化问题：
关于凹函数,同样见凸函数：定义与基本性质。
$$\max \bar{f}(x)\iff \min -\bar{f}(x)$$

凸优化定义：示例

观察：下面的最优化问题是否为凸优化问题$?$
$$\{\begin{array}{l}\min f(x)=x_1^2+x_2^2\\ \text{s.t. }\{\begin{array}{l}\begin{array}{rl}\mathcal{G}(x)& =\frac{x_1}{1+x_2^2}\le 0\\ \mathcal{H}(x)& =(x_1+x_2{)}^2=0\end{array}\end{array}\end{array}$$

• 首先，观察到该最优化问题是最小化问题，并且目标函数$f(x)=x_1^2+x_2^2$是凸函数；
  该函数对应决策变量$x$的$\text{Hessian Matrix}\Rightarrow {\nabla }^{2}f(x)$是固定结果：$\left(\begin{array}{c}20\\ 02\end{array}\right)$，它是一个正定矩阵(凸函数的二阶条件)。
• 观察不等式约束$\begin{array}{r}\mathcal{G}(x)=\frac{x_1}{1+x_2^2}\end{array}$，从表面上看：它并不是一个凸函数。但我们可以推出如下表达：
  由于分母$1+x_2^2>0$恒成立，因此只需要观察分子的符号即可。
  $$\mathcal{G}(x)=\frac{x_1}{1+x_2^2}\le 0\iff x_1\le 0\Rightarrow \bar{\mathcal{G}}(x)=x_1$$
  而$\bar{\mathcal{G}}(x)=x_1$是线性函数，自然也是凸函数；
• 观察等式约束$\mathcal{H}(x)=(x_1+x_2{)}^2=0$，很明显它不是线性函数。但我们同样可以推出如下表达：
  $$\mathcal{H}=(x_1+x_2{)}^2=0\iff x_1+x_2=0\Rightarrow \bar{\mathcal{H}}(x)=x_1+x_2$$
  而$\bar{\mathcal{H}}(x)$是线性函数。综上，该示例描述的最优化问题是凸优化问题。
  关于约束条件，可能并不是上来直接用，能够化简的部分需要进行化简。

凸优化与非凸优化问题的区分

在凸集的简单认识中，介绍了凸优化相关的两个优秀性质：

局部最优解即全局最优解

关于局部最优解$\bar{x}$的定义表示为：
$$f(\bar{x})\le f(x)\forall \in \mathcal{S}\cap {\mathcal{N}}_{ϵ}(\bar{x})$$
其中${\mathcal{N}}_{ϵ}(\bar{x})$表示包含$\bar{x}$的小的邻域范围。也就是说：仅在较小的邻域范围$\mathcal{S}\cap {\mathcal{N}}_{ϵ}(\bar{x})$内，某可行解$\bar{x}$的目标函数值$\le$所有目标函数值，称可行解$\bar{x}$为局部最优解；
相反，关于全局最优解$x^{\ast }$的定义表示为：
$$f(x^{\ast })\le f(x)\forall x\in \mathcal{S}$$
也就是说：在整个可行域$\mathcal{S}$范围内，某可行解$x^{\ast }$的目标函数值$\le$所有目标函数值。称可行解$x^{\ast }$为全局最优解。

回到凸优化问题上：如果在$\mathcal{S}$中找到某一个局部最优解，那么该解一定也是全局最优解。

(反证法)证明：

• 假设找到某个解$\bar{x}$是局部最优解，但不是全局最优解，可以推出：必然存在某个解$x^{\ast }\in \mathcal{S}$，有：
  如果不存在，这个局部解就是全局解~
  $$f(x^{\ast })<f(\bar{x})$$
• 从$\bar{x}$开始，沿着$x^{\ast }-\bar{x}$方向前进一个小的步长，得到一个新的点：$\bar{x}+\lambda \cdot (x^{\ast }-\bar{x}),\lambda \in (0,1)$，它的目标函数结果：$f[\bar{x}+\lambda \cdot (x^{\ast }-\bar{x})]$可表示为：
  可以将$\bar{x}+\lambda \cdot (x^{\ast }-\bar{x})=(1-\lambda )\cdot \bar{x}+\lambda \cdot x^{\ast }$重新组合，可看作点$\bar{x},x^{\ast }$的凸组合。
  将上面的$f(x^{\ast })<f(\bar{x})$代入。
  $$\begin{array}{rl}f[\lambda \cdot x^{\ast }+(1-\lambda )\cdot \bar{x}]& \le \lambda \cdot f(x^{\ast })+(1-\lambda )\cdot f(\bar{x})\\ & <\lambda \cdot f(\bar{x})+(1-\lambda )\cdot f(\bar{x})\\ & =f(\bar{x})\end{array}$$
• 可以发现：无论$\lambda$如何取值，$f[\bar{x}+\lambda \cdot (x^{\ast }-\bar{x})]<f(\bar{x})$恒成立。如果$\lambda \Rightarrow 0$，小到$\bar{x}+\lambda \cdot (x^{\ast }-\bar{x})$位于局部最优解邻域${\mathcal{N}}_{ϵ}(\bar{x})$内，会出现矛盾：$\bar{x}$是该邻域内的最优解，但存在另一个解$\bar{x}+\lambda \cdot (x^{\ast }-\bar{x})$，其函数值小于$f(\bar{x})$，这意味着：$\bar{x}$不是该邻域内的最优解。至此，得证：如过$\bar{x}$是局部最优解，那么它一定是全局最优解。

凸优化问题的最优性条件

什么样的解是凸优化问题的最优解$?$关于最优解有如下充要条件：
$$x^{\ast }\in \mathcal{S}\text{ is Optimal }\iff [\nabla f(x^{\ast }){]}^T(x-x^{\ast })\ge 0\forall x\in \mathcal{S}$$
为什么满足该充要条件就一定是最优解$?$证明如下：
充分性：已知某解$x^{\ast }$满足$[\nabla f(x^{\ast }){]}^T(x-x^{\ast })\ge 0,\forall x\in \mathcal{S}$。

• 观察$f(x)$与$f(x^{\ast })+[\nabla f(x^{\ast }){]}^T(x-x^{\ast }),\forall x\in \mathcal{S}$两者之间的大小关系。必然有：

  • 其中不等式右侧描述：过$[x^{\ast },f(x^{\ast })]$点并与凸函数$f(\cdot )$相切的直线。根据凸函数的定义,函数图像必然全部在切线上方。
  • 又根据上述条件，必然有:$f(x^{\ast })+[\nabla f(x^{\ast }){]}^T(x-x^{\ast })\ge f(x^{\ast })$。

  $$f(x)\ge f(x^{\ast })+[\nabla f(x^{\ast }){]}^T(x-x^{\ast })\ge f(x^{\ast })$$

• 总上，对于$x\in \mathcal{S}$，都有上述式子$f(x)\ge f(x^{\ast })$成立，因而$x^{\ast }$是全局最优解。

必要性：已知某解$x^{\ast }$是全局最优解。(反证法)证明：

• 假设$\exists \bar{x}\in \mathcal{S}$，使得：$[\nabla f(x^{\ast }){]}^T(\bar{x}-x^{\ast })<0$；
• 基于上述假设，以$x^{\ast }$为起始，向$\bar{x}$方向移动一个较小距离$\lambda \cdot (\bar{x}-x^{\ast }),\lambda \in (0,1)$，观察函数值从$f(x^{\ast })$到$f[x^{\ast }+\lambda \cdot (\bar{x}-x^{\ast })]$的变化情况。这里使用泰勒公式对$f[x^{\ast }+\lambda \cdot (\bar{x}-x^{\ast })]$在$x^{\ast }$处进行展开：
  其中$\mathcal{O}(\cdot )$表示高阶无穷小。
  $$f[x^{\ast }+\lambda \cdot (\bar{x}-x^{\ast })]=f(x^{\ast })+\frac{1}{1!}\cdot \lambda [\nabla f(x^{\ast }){]}^T(\bar{x}-x^{\ast })+\mathcal{O}(\lambda ||\bar{x}-x^{\ast }||)\lambda \in (0,1)$$
  整理得：
  $$\frac{f[x^{\ast }+\lambda \cdot (\bar{x}-x^{\ast })]-f(x^{\ast })}{\lambda }=[\nabla f(x^{\ast }){]}^T(\bar{x}-x^{\ast })+\frac{\mathcal{O}(\lambda \cdot ||\bar{x}-x^{\ast }||)}{\lambda }$$
  当$\lambda \Rightarrow 0$时，等式右侧的符号由$[\nabla f(x^{\ast }){]}^T(\bar{x}-x^{\ast })$控制：$<0$；等式左侧自然也$<0$：
  关于高阶无穷小:$\begin{array}{r}\frac{\mathcal{O}(\lambda \cdot ||\bar{x}-x^{\ast }||)}{\lambda }\end{array}$在$\lambda \Rightarrow 0$时，分子趋于$0$的速度更快。因而$\begin{array}{r}\underset{\lambda \Rightarrow 0}{\lim }\frac{\mathcal{O}(\lambda \cdot ||\bar{x}-x^{\ast }||)}{\lambda }=0\end{array}$。
  $$\underset{\lambda \Rightarrow 0}{\lim }\frac{f[x^{\ast }+\lambda \cdot (\bar{x}-x^{\ast })]-f(x^{\ast })}{\lambda }<0\Rightarrow \underset{\lambda \Rightarrow 0}{\lim }f[x^{\ast }+\lambda \cdot (\bar{x}-x^{\ast })]-f(x^{\ast })<0$$
  这意味着：存在一点$x^{\ast }+\lambda \cdot (\bar{x}-x^{\ast })$，其函数值$f[x^{\ast }+\lambda \cdot (\bar{x}-x^{\ast })]<f(x^{\ast })$。也就是说：$x^{\ast }$不是全局最优解。这与条件相矛盾，证毕。

关于凸优化问题最优性条件的几何解释

对上述最优性条件变换成如下形式：
$$x^{\ast }\in \mathcal{S}\text{ is Optimal }\iff -[\nabla f(x^{\ast }){]}^T{x}^{\ast }\ge -[\nabla f(x^{\ast }){]}^{T}x\forall x\in \mathcal{S}$$
根据凸集的支撑超平面定理，如果$-[\nabla f(x^{\ast })]\ne 0$，则可以找到以$x^{\ast }$为边界点，并垂直于向量$-[\nabla f(x^{\ast })]$的超平面，使该超平面支撑凸集$\mathcal{S}$。而$-[\nabla f(x^{\ast })]$作为负梯度方向，必然有：$\forall x\in \mathcal{S},\text{ s.t. }-[\nabla f(x^{\ast })](x-x^{\ast })\le 0$。对应图像表示如下：

• 其中支撑超平面定理是凸集的自身性质。
• 也就是说：向量$-[\nabla f(x^{\ast })]$与向量$x-x^{\ast }$之间的夹角$\ge 90^{。}$恒成立。
  

个人深度思考：上述最优性条件成立建立在$-[\nabla f(x^{\ast })]\ne 0$的情况下，如果$-[\nabla f(x^{\ast })]=0$时，有：$\forall x\in \mathcal{S},[\nabla f(x^{\ast }){]}^T(x-x^{\ast })\ge 0$恒成立。也就是说：在凸集中的任意一点，都可以满足该条件。在迭代寻找最优解的过程中，如果$-[\nabla f(x^{\ast })]=0$，可能会选择错误的方向。

什么时候会出现这种情况：梯度消失的时候。也就是说：如果出现梯度消失的情况下，在迭代寻找最优解的过程中，可能会选择错误的方向。最终找到的最优解可能并不是凸集的某个边界点，而是某个内点。
当然，如果选择的点是内点并且目标函数结果又返回至较大的情况，此时的梯度又存在了，会继续重新收敛至最优解。这里只是描述出现的这种反弹现象。

几种特殊凸问题的最优性条件

无约束凸优化

无约束凸优化问题：在目标函数$f(\cdot )$是凸函数的条件下，$x\in {\mathbb{R}}^n$，关于$\min f(x)$的最优性条件表示如下：
$$x^{\ast }\text{ is Optimal }\iff \nabla f(x^{\ast })=0$$
如果将该问题带入凸优化问题最优性条件中，可以得到：
$$x^{\ast }\text{ is Optimal }\iff [\nabla f(x^{\ast }){]}^T(x-x^{\ast })\ge 0,\forall x\in {\mathbb{R}}^n\iff \nabla f(x^{\ast })=0$$
可以理解为：$\forall x\in {\mathbb{R}}^n$构成的向量$x-x^{\ast }$均满足$[\nabla f(x^{\ast }){]}^T(x-x^{\ast })\ge 0$，那只有一种情况：$\nabla f(x)$是零向量。
这里需要与上面描述的梯度消失的情况区分一下。上述的最优性条件必须满足可行域$\mathcal{S}$是凸集。如果在$\mathcal{S}$是凸集情况下，$\nabla f(x^{\ast })=0$会导致无法找到$x^{\ast }$位置下关于凸集$\mathcal{S}$的支撑超平面;相反，在无约束凸优化问题中，对可行域$\mathcal{S}$没有约束。

等式约束凸优化

等式约束的凸优化问题：在目标函数$f(\cdot )$是凸函数的条件下，关于 min ⁡ { f ( x ) ∣ A x = b } \min \{f(x) \mid \mathcal A x = b\} min{f(x)∣Ax=b}的最优性条件表示如下：
关于凸优化问题的等式约束函数是线性函数。
$$x^{\ast }\text{ is Optimal }\iff \exists \mu ,\text{ s.t. }\nabla f(x^{\ast })+{\mathcal{A}}^T\mu =0,\mathcal{A}{x}^{\ast }=0$$
证明：
如果$x^{\ast }$是全局最优解，必然有：
$$x^{\ast }\text{ is Optimal }\iff [\nabla f(x^{\ast }){]}^T(x-x^{\ast })\ge 0\forall x:\mathcal{A}x=b,\mathcal{A}{x}^{\ast }=b$$
根据$\mathcal{A}x=\mathcal{A}{x}^{\ast }=b$，因而有：$\mathcal{A}(x-x^{\ast })=b-b=0$。记向量$d=x-x^{\ast }$，从而有：
$$x^{\ast }\text{ is Optimal }\iff [\nabla f(x^{\ast }){]}^{T}d\ge 0\forall d:\mathcal{A}d=0$$
很明显，$\mathcal{A}d=0$是一个齐次线性方程组，可以将$d$描述为：$\mathcal{A}x=0$解集中的一个解。即：$d\in \mathcal{N}(\mathcal{A})$：
其中$\mathcal{N}(\mathcal{A})$表示系数矩阵$\mathcal{A}$的零空间。
$$x^{\ast }\text{ is Optimal }\iff [\nabla f(x^{\ast }){]}^{T}d\ge 0\forall d\in \mathcal{N}(\mathcal{A})$$
发现这样一个现象：如果$d\in \mathcal{N}(\mathcal{A})$那么$-d\in \mathcal{N}(\mathcal{A})\Rightarrow -\mathcal{A}d=0$，将$d,-d$都带入上式中：
$$\{\begin{array}{l}[\nabla f(x^{\ast }){]}^{T}d\ge 0\\ [\nabla f(x^{\ast }){]}^T(-d)\ge 0\Rightarrow [\nabla f(x^{\ast }){]}^{T}d\le 0\end{array}$$
也就是说：关于$[\nabla f(x^{\ast }){]}^{T}d$在可行域$d\in \mathcal{N}(\mathcal{A})$中只能取等：
$$x^{\ast }\text{ is Optimal }\iff [\nabla f(x^{\ast }){]}^{T}d=0\forall d\in \mathcal{N}(\mathcal{A})$$
这意味着：向量$\nabla f(x^{\ast })$与$\mathcal{N}(\mathcal{A})$中的任意解向量$d$均是垂直关系，即向量$\nabla f(x^{\ast })$与$\mathcal{N}(\mathcal{A})$垂直：
$$x^{\ast }\text{ is Optimal }\iff \nabla f(x^{\ast })\in \mathcal{N}(\mathcal{A}{)}^{\perp }$$
对应图像表示如下：
其中$[\nabla f(x^{\ast }){]}^{T}d=\Vert \nabla f(x^{\ast })\Vert \cdot \Vert d\Vert \cdot \cos \theta =0\to \cos \theta =0$

因而$\nabla f(x^{\ast })$必然能够表达为系数矩阵$\mathcal{A}$行向量的线性组合。对应数学符号表示为：
这实际上就是$\text{KKT}$条件在等式约束凸问题的具体化。后续有机会介绍~
$$x^{\ast }\text{ is Optimal }\iff \nabla f(x^{\ast })+{\mathcal{A}}^T\mu =0$$

非负约束凸优化

基于非负约束的凸优化问题：在目标函数$f(\cdot )$是凸函数的条件下，关于 min ⁡ { f ( x ) ∣ x ≥ 0 } \min\{f(x) \mid x \geq 0\} min{f(x)∣x≥0}的最优性条件表示如下：
$$x^{\ast }\text{ is Optimal }\iff \nabla f(x^{\ast }{)}_i\cdot x_i^{\ast }=0x^{\ast }\ge 0;\nabla f(x^{\ast })\ge 0$$
证明：依然根据凸优化问题的最优性条件，有：
其中$x^{\ast }$作为可行域内的最优解，必然也满足：$x^{\ast }\ge 0$
$$x^{\ast }\text{ is Optimal }\iff [\nabla f(x^{\ast }){]}^T(x-x^{\ast })\ge 0\forall x\ge 0;x^{\ast }\ge 0$$
将上式展开，整理有：
$$x^{\ast }\text{ is Optimal }\iff [\nabla f(x^{\ast }){]}^{T}x\ge [\nabla f(x^{\ast }){]}^T{x}^{\ast }\forall x\ge 0;x^{\ast }\ge 0$$
观察上式：$\forall x\ge 0$，并满足：$[\nabla f(x^{\ast }){]}^{T}x\ge [\nabla f(x^{\ast }){]}^T{x}^{\ast }$，必然有：

• 解释：如果$\nabla f(x^{\ast })$中存在某一个/若干个分量$<0$,在执行线性运算$[\nabla f(x^{\ast }){]}^{T}x$时，由于$x$可在$x\ge 0$范围内任意取值，假设$x$中对应上述$\nabla f(x^{\ast })$分量$<0$的分量位置是$+\infty$,那么$[\nabla f(x^{\ast }){]}^{T}x$的结果必然是$-\infty$。这是可能发生的结果。但该结果可能不满足$[\nabla f(x^{\ast }){]}^{T}x\ge [\nabla f(x^{\ast }){]}^T{x}^{\ast }$。因此：$\nabla f(x^{\ast })\ge 0$必须成立。
• 当$x=0$时，必然也满足：$[\nabla f(x^{\ast }){]}^T{x}^{\ast }\le [\nabla f(x^{\ast })]\cdot 0=0$
  $$x^{\ast }\text{ is Optimal }\iff \{\begin{array}{l}\nabla f(x^{\ast })\ge 0;x^{\ast }\ge 0\\ [\nabla f(x^{\ast }){]}^T{x}^{\ast }\le 0\end{array}$$

继续观察上式：在$\nabla f(x^{\ast }),x^{\ast }\ge 0$情况下，$[\nabla f(x^{\ast }){]}^T{x}^{\ast }\le 0$。因此只有一种情况：
$$x^{\ast }\text{ is Optimal }\iff \{\begin{array}{l}\nabla f(x^{\ast })\ge 0;x^{\ast }\ge 0\\ [\nabla f(x^{\ast }){]}^T{x}^{\ast }=0\end{array}$$
这意味着：线性运算$[\nabla f(x^{\ast }){]}^{T}x$过程执行加法运算的每一个分量$\nabla f(x^{\ast }{)}_i\cdot x_i(i=1,2,\cdots ,n)$均为$0$。
相反，如果存在某分量乘积结果 ∇ f ( x ∗ ) k ⋅ x k ∗ > 0 ( k ∈ { 1 , 2 , ⋯ , n } ) \nabla f(x^*)_k \cdot x_k^*> 0(k \in \{1,2,\cdots,n\}) ∇f(x∗)k​⋅xk∗​>0(k∈{1,2,⋯,n})最终的$[\nabla f(x^{\ast }){]}^{T}x$结果必然$>0$，不满足上述条件。

证毕。

$\text{Reference}$：
最优化理论与方法-第四讲-凸优化问题