机器学习是一个"获取数据 > 选择模型 > 优化问题(调整参数)"的过程,因此优化问题也是非常重要的一环,一般我们会选择一个凸函数来进行优化,因为这种函数性质较好,而且一般来说单纯的优化问题并不复杂,复杂的是在优化的同时需要考虑一些限制条件。因此今天主要来看看凸优化问题。

凸集合和凸函数

这里需要重点了解凸集合与凸函数之间的关系。首先先说一下凸集合,对于下面两个集合,集合A是凸集合,集合B不是凸集合。

image-20180817111442934

凸集合的定义:如果一个集合Ω\Omega中任何两个点之间的线段上任何一个点还是属于Ω\Omega,那么Ω\Omega就是一个凸集合。

凸函数的定义:如果一个函数ff定义域Ω\Omega是凸集,而且对于任何两点以及两点之前线段上任意一个点都有

(1.1)f(λx1+(1λ)x2)λf(x1)+(1λ)f(x2)x1,x2Ω,λ(0,1)f(\lambda x_1 + (1 - \lambda) x_2) \le \lambda f(x_1) + (1 - \lambda) f(x_2) \qquad \forall x_1, x_2 \in \Omega, \lambda \in (0, 1) \tag{1.1}

这个翻译成人话就是对于任意在SS的边界取两个点连成的直线上的任意一点是否还在SS中,下图就是一个凸函数。需要注意的是凸函数的局部极值一定是全局极值,由于具有这样良好的性质,优化问题就转换为如何将复杂函数转换为凸函数。

image-20180817113655331

函数的上镜圆定义:假设ff是一个定义在Ω\Omega上的函数,区域{(x,y)yf(x),xΩ}\{(x, y) | y \ge f(x), \forall x \in \Omega\}就是ff的上镜圆。对应到上图就是区域SS

凸函数和凸集合的关系就显而易见了:一个函数是凸函数当且仅当ff的上镜圆是凸集合。

凸组合

定义:对于任意nn个点{xi}i=1n\{x_i\}^n_{i=1}以及权重系数{wi}i=1n\{w_i\}^n_{i=1},若权重系数非负wi0w_i \ge 0而且i=1nwi=1\sum^{n}_{i=1}w_i = 1,则线性组合s=i=1nwixis = \sum^n_{i=1}w_ix_i为一个凸组合。

集合的凸包

集合的凸包是nn个点{xi}i=1n\{x_i\}^n_{i=1}的全部凸组合就构成了{xi}i=1n\{x_i\}^n_{i=1}的凸包,如下图右边加上蓝色区域的就是原来集合的凸包。

image-20180817130139443

琴生不等式(Jensen)

定义:如果f:ΩRf : \Omega \to \mathbb{R}是一个凸函数,则对于任意{xiΩ}i=1n\{x_i \in \Omega\}^n_{i=1}以及凸组合i=1nwixi\sum^{n}_{i=1} w_i x_i都有

(4.1)i=1nwif(xi)f(i=1nwixi)\sum^n_{i=1}w_if(x_i) \ge f(\sum^n_{i=1}w_ix_i) \tag{4.1}

其中i=1nwif(xi)\sum^n_{i=1}w_if(x_i)是函数值的凸组合,一定是在函数的上镜圆中,而f(i=1nwixi)f(\sum^n_{i=1}w_ix_i)是函数的一个点,因此上面的不等式在凸函数的时候就成立了。

优化问题

约束条件一般分为等式约束和不等式约束两种:

  • 等式约束,表示为g(x)=0g(\boldsymbol{x}) = 0
  • 不等式约束,表示为g(x)0g(\boldsymbol{x}) \le 0

假设xRn\boldsymbol{x} \in \mathbb{R}^n,对于hi(x)=0h_i(x) = 0来说,就是一个(n1)(n-1)维的曲面,类比到二维空间,就是一个一维的直线,那么对于fi(x)0f_i(x) \le 0可以理解为nn维空间的子集,还是类比到二维空间,如下图所示。

image-20180820113216381

最优解特点分析

首先先说g(x)=0g(\boldsymbol{x}) = 0即等式约束条件,我们观察一下图3中的红色虚线(可行解空间)和蓝色虚线(目标函数的等值线),发现这个被约束的最优解恰好在二者相切的位置,这并不是个偶然。

推论1:在等式约束条件下优化问题的最优解x\boldsymbol{x}^\star,原始目标函数f(x)f(\boldsymbol{x})的梯度向量f(x)\nabla f(\boldsymbol{x}^\star)必然与约束条件g(x)=0g(\boldsymbol{x}) = 0的切线方向垂直。

推论2:函数f(x)f(\boldsymbol{x})的梯度方向也必然与函数自身等值线切线方向垂直。

推论3:函数f(x)f(\boldsymbol{x})与函数g(x)g(\boldsymbol{x})的等值线在最优解点x\boldsymbol{x}^\star处相切,即两者在x\boldsymbol{x}^\star点的梯度方向相同或相反。

根据上面的三条推论我们可以写成公式5.1

(5.1)f(x)+λg(x)=0\nabla f(\boldsymbol{x}^\star) + \lambda\nabla g(\boldsymbol{x}^\star) = 0 \tag{5.1}

变量λ\lambda用来描述两个梯度矢量的长度比例,但是这样还是无法获得x\boldsymbol{x}^\star的解,还需要加入一点限制条件

(5.2)g(x)=0g(\boldsymbol{x}^\star) = 0 \tag{5.2}

公式5.1公式5.2放在一起就能找到最优点了。

构造拉格朗日函数

对于上面的有条件优化问题,我们希望转换到一个无条件的公式中去优化。根据上面的优化问题对应的拉格朗日量可以写为

\begin{align} L(\boldsymbol{x}, \lambda) = f(\boldsymbol{x}) + \lambda g(\boldsymbol{x}) \tag{5.3} \end{align}

我们将公式5.4分别对x\boldsymbol{x}v\boldsymbol{v}求导令其结果等于0可以很容易的计算出公式5.1公式5.2,这就说明新构造的拉格朗日目标函数的优化问题完全等价于原来的等式约束条件下的优化问题,当然这是在约束条件为等式的条件下成立的。

KTT条件

对于不等式约束条件g(x)0g(\boldsymbol{x}) \le 0的情况,对应着两种情况,如下图4:

  • 最优解在边界上,相当于约束条件就是g(x)=0g(\boldsymbol{x}) = 0,在这种情况下目标函数f(x)f(\boldsymbol{x})的最优解在可行域的外部,因为一旦目标函数的最优解在可行域的内部必定不符合这个规定,就会变成下图右半部分区域。同时函数f(x)f(\boldsymbol{x})在最优解x\boldsymbol{x}^\star附近的变化趋势是“在可行解区域内侧较大而在区域外侧较小”,与之对应的是函数g(x)g(\boldsymbol{x})在可行域内小于0,在可行域外大于0,所以f(x)f(\boldsymbol{x})g(x)g(\boldsymbol{x})梯度方向相反,根据公式5.1可以推断出λ>0\lambda \gt 0
  • 如果在区域内,则相当于约束条件没有起作用,因此公式5.3中的拉格朗日函数中的参数λ=0\lambda = 0
image-20180820133650411

如果整合这两种情况,就可以获得

\begin{align} \left \{ \begin{array}{lr} g(\boldsymbol{x}) \le 0 \quad (1) \\ \lambda \ge 0 \ \ \ \ \ \ \ \ \ (2) \\ \lambda g(\boldsymbol{x}) = 0 \ \ (3) \end{array} \right . \tag{5.4} \end{align}

公式5.4(1)(1)是约束本身,在第一种情况下λ>0,g(x)=0\lambda \gt 0, g(\boldsymbol{x}) = 0,在第二种情况下λ=0,g(x)<0\lambda = 0, g(\boldsymbol{x}) \lt 0,因此就有了(2)(2)(3)(3)这两种情况。公式5.4就是KTT条件。KTT条件是对最优解的约束,而原始问题中的约束是对可行解的约束。

拉格朗日对偶

之前我们解决有约束的优化问题是通过拉格朗日方程将目标函数与约束条件融合进了一个函数中,从而将有约束的优化问题变换为了无约束的优化问题。我们仍然秉承这一思路去解决不等式约束条件下的优化问题,那么如何针对不等式约束条件下的优化问题构建拉格朗日函数呢?

因为我们要求解的是最小化问题,所以一个直观的想法是如果我能够构造一个函数,使得该函数在可行解区域内与原目标函数完全一致,而在可行解区域外的数值非常大,甚至是无穷大,那么这个没有约束条件的新目标函数的优化问题就与原来有约束条件的原始目标函数的优化是等价的问题。

我们最终的目标就是:

  1. 有约束的原始目标函数优化问题
  2. 新构造的拉格朗日目标函数优化问题
  3. 拉格朗日对偶函数的优化问题

这三个问题具有完全相同的最优解,在数学上第三个目标是最好解决的。

原始目标函数(有约束条件)

为了接下来的讨论,更具有一般性,我们把等式约束条件也放进来,进而有约束的原始目标函数优化问题重新给出统一的描述:

\begin{align} & \mathop{\min}_{\boldsymbol{x}} \quad f(\boldsymbol{x}) \\ & \begin{array}{lr} \mathrm{s.t.} & h_i(\boldsymbol{x}) = 0 \quad i = 1, \dots, m \\ & g_i(\boldsymbol{x}) \le 0 \quad i = 1, \dots, n \end{array} \tag{5.5} \end{align}

公式5.5表示mm个等式约束条件和nn个不等式约束条件下的目标函数f(x)f(\boldsymbol{x})的优化问题。

构造拉格朗日目标函数的优化函数(没有约束条件)

接下来我们构造一个基于广义拉格朗日函数的新目标函数,记为

\begin{align} \theta_P(\boldsymbol{x}) &= \max_{\boldsymbol{\alpha}, \boldsymbol{\beta}; \beta_j \ge 0} \ L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \tag{5.6} \\ &= \max_{\boldsymbol{\alpha}, \boldsymbol{\beta}; \beta_j \ge 0} \ f(\boldsymbol{x}) + \sum^m_{i=1}\alpha_ih_i(\boldsymbol{x}) + \sum^n_{j=1}\beta_jg_j(\boldsymbol{x}) \tag{5.7} \\ &= f(\boldsymbol{x}) + \max_{\boldsymbol{\alpha}, \boldsymbol{\beta}; \beta_j \ge 0} \left [ \sum^m_{i=1} \alpha_ih_i(\boldsymbol{x}) + \sum^n_{j=1}\beta_jg_j(\boldsymbol{x}) \right ] \tag{5.8} \end{align}

这里α=[α1α2αm]T, β=[β1β2βn]T\boldsymbol{\alpha} = \begin{bmatrix} \alpha_1 & \alpha_2 & \cdots & \alpha_m \end{bmatrix}^T , \ \boldsymbol{\beta} = \begin{bmatrix} \beta_1 & \beta_2 & \cdots & \beta_n\end{bmatrix}^T,是我们在构造新目标函数时加入的系数变量,同时也是公式5.6需要最大化的自变量,就如公式5.8展现的那样,在公式中要最大化后面的那一部分是因为θP(x)\theta_P(\boldsymbol{x})为一定值的时候,使得f(x)f(\boldsymbol{x})的值最小。

按照我们之前说的,函数在可行解区域内与原目标函数完全一致,而在可行解区域外的数值非常大,我们使用Φ\Phi表示可行域,那么数学符号可以表示为

(5.9)θP(x)={f(x)xΦ+xΦ\theta_P(\boldsymbol{x}) = \left \{ \begin{array}{lr} f(\boldsymbol{x}) \quad \boldsymbol{x} \in \Phi \\ +\infty \quad \boldsymbol{x} \notin \Phi \end{array} \right. \tag{5.9}

那么这就意味着在可行区域内θP(x)=f(x)\theta_P(\boldsymbol{x}) = f(\boldsymbol{x}),因此后面的maxα,β;βj0[i=1mαihi(x)+j=1nβjgj(x)]=0\max_{\boldsymbol{\alpha}, \boldsymbol{\beta}; \beta_j \ge 0} \left [ \sum^m_{i=1} \alpha_ih_i(\boldsymbol{x}) + \sum^n_{j=1}\beta_jg_j(\boldsymbol{x}) \right ] = 0,而不在可行区域时,maxα,β;βj0[i=1mαihi(x)+j=1nβjgj(x)]=+\max_{\boldsymbol{\alpha}, \boldsymbol{\beta}; \beta_j \ge 0} \left [ \sum^m_{i=1} \alpha_ih_i(\boldsymbol{x}) + \sum^n_{j=1}\beta_jg_j(\boldsymbol{x}) \right ] = + \infty,如果满足这个那么我们就满足了上述要求。

最终优化的问题就变成了

\begin{align} \min_\boldsymbol{x} \ \theta_P(\boldsymbol{x}) \tag{5.9} \end{align}

这个问题的解就等价于公式5.5,即在有约束的条件下最小化f(x)f(\boldsymbol{x})的问题。

对偶问题

尽管公式5.9描述的无约束优化问题看起来很美好,但一旦你尝试着手处理这个问题,就避不开α\boldsymbol{\alpha}β\boldsymbol{\beta}的问题,也就没有办法使用\begin{align} \frac{\partial \theta_P(\boldsymbol{x})}{\partial \boldsymbol{x}} \end{align}求解最优解了。

我们先将公式5.9展开

\begin{align} \min_\boldsymbol{x} \ \theta_P(\boldsymbol{x}) = \min_\boldsymbol{x} \max_{\boldsymbol{\alpha}, \boldsymbol{\beta}; \beta_j \ge 0} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \end{align} \tag{5.10}

我们再构造另一个函数,然后给出另外一个优化问题的描述

\begin{align} \max_{\boldsymbol{\alpha}, \boldsymbol{\beta}; \beta_j \ge 0} \ \theta_D(\boldsymbol{\alpha}, \boldsymbol{\beta}) = \max_{\boldsymbol{\alpha}, \boldsymbol{\beta}; \beta_j \ge 0} \min_\boldsymbol{x} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \end{align} \tag{5.11}

我们就把公式5.11看做公式5.10的对偶问题,如果我们能想办法证明公式5.10公式5.11存在相同的解x,α,β\boldsymbol{x}^\star, \boldsymbol{\alpha}^\star, \boldsymbol{\beta}^\star,那么我们就可以选择一个叫简单的公式进行求解。

我们把对偶问题最大值点称为(α,β)(\boldsymbol{\alpha}^\star, \boldsymbol{\beta}^\star),对应的最大值记为dd^\star公式5.5的最大值记为pp^\star,则:

  • 弱对偶性满足dpd^\star \le p^\star,这是必定满足的,可以参见公式5.7i=1mαihi(x)\sum^m_{i=1}\alpha_ih_i(\boldsymbol{x})恒等于0,而j=1nβjgj(x)\sum^n_{j=1}\beta_jg_j(\boldsymbol{x})恒小于等于0,因此弱对偶性是一定满足的。
  • 强对偶性满足d=pd^\star = p^\star,在满足KTT条件下,j=1nβjgj(x)\sum^n_{j=1}\beta_jg_j(\boldsymbol{x})恒等于0,因此SVM是满足强对偶性的。

因此最终的大公式为

\left \{ \begin{array}{lr} \nabla_\boldsymbol{x}(\boldsymbol{x}^\star, \boldsymbol{\alpha}^\star, \boldsymbol{\beta}^\star) = 0 \\ g_i(\boldsymbol{x}^\star) \le 0 \quad i = 1,\dots, m \\ \beta^\star_j \ge 0 \quad j = 1,\dots, m \\ \beta^\star_j g_i(\boldsymbol{x}^\star) = 0 \quad j = 1,\dots,m\\ h_j(\boldsymbol{x}^\star) = 0 \quad j =1, \dots, n \\ \end{array} \tag{5.12} \right .

致谢

到这里凸函数的优化基本告一段落,以后有新发现也会继续补充……再次感谢知乎@耳东陈老师的教程,把如此复杂的问题解释的如此通俗易懂,感谢!

REFERENCES

  1. 零基础学SVM—Support Vector Machine(一)