本文共 7686 字，大约阅读时间需要 25 分钟。

前言

最优化问题的求解方法在机器学习算法中是经常被用到的。下面是一个最优化问题的一个简单概述：

求解$f(x)$最小值时的$x^{\ast }$，即： $$\underset{x}{\min }f(x)$$ 无约束时，可通过求导的方式解决。事实情况中会涉及不同约束条件($\text{s.t.}$)，即存在等式约束和不等式约束。如下：

• 等式约束：$h_i(x)=0,i=1,2,3,\dots ,m$
• 不等式约束：$g_j(x)\le 0,j=1,2,3,\dots ,n$
• 同时存在等式约束和不等式约束:KKT(Karush-Kuhn-Tucker)条件

对于上面的问题该如何求解呢？

1 拉格朗日乘子法

通过拉格朗日函数将约束问题转化为无约束问题，在无约束问题中就方便求解了，这里主要是将等式约束转换为拉格朗日函数。则有：

目标函数为$f(x)$，约束条件为： $$h_k(x),k=1,2,3,\dots ,l$$ 对该优化问题建模就有： $$\min f(x)\text{s.t.}{h}_k(x)=0$$ 这时需要构建拉格朗日函数，将约束的问题转换为无约束的优化问题。 在上图中可以看出，只有相切的时候，才有可能是极值点，在相切的地方$h(x)$的梯度和$f(x)$的梯度应该在同一条直线上，即在极值点有： $$\nabla f(x)=\lambda \nabla h(x)$$ 根据上述分析，可将将原始优化问题表示为： $$L(x,\lambda )=f(x)+\sum _{k=1}^l{\lambda }_k{h}_k(x)$$ $L(x,\lambda )$即拉格朗日函数，${\lambda }_k$是拉格朗日乘子。拉格朗日函数对$x$求偏导的结果为0时，即为最优解。

2 KKT条件

通过KKT条件将不等式约束转换为拉格朗日函数。优化问题中经常包含等式约束和不等式约束。对问题建模问题建模如下：

$$\begin{gathered} \min f(x) \\ \text{s.t.}{h}_k(x)=0,k=1,2,\cdots ,l \\ {g}_j(x)\le 0,j=1,2,,\cdots ,n \end{gathered}$$ 对于等式约束，可以引入拉格朗日乘子进行转换。对于不等式约束使用KKT条件构造拉格朗日乘子，构造结果如下： $$L(x,\lambda ,\mu )=f(x)+\sum _{k=1}^l{\lambda }_k{h}_k(x)+\sum _{j=1}^n{\mu }_j{g}_j(x)$$ 其中，${\lambda }_k$是为等式约束引入的拉格朗日乘子，${\mu }_j$是为不等式约束引入的松弛变量，也叫KKT乘子，需要注意的是KKT乘子是大于0的。这样就将有约束的优化问题转换为无约束问题的优化了，通过求导即可求出极值点。 其中，求出的极值点$x^{\ast }$满足KKT条件： $$\{\begin{array}{rl}\nabla f\left(x^{\ast }\right)+\sum _k{\lambda }_k\nabla h_k\left(x^{\ast }\right)+\sum _j{\mu }_j\nabla g_j\left(x^{\ast }\right)& =0\\ {\mu }_j& \ge 0\\ {\mu }_j{g}_j\left(x^{\ast }\right)& =0\\ g_j\left(x^{\ast }\right)& \le 0\end{array}$$ 注： $f(x)$、$g(x)$结尾凸函数

3 对偶问题

有时候原优化问题很难求解，为了解决问题，可将原优化问题进行等效转化，然后再求解。原优化问题：

$$\begin{gathered} \min f(x) \\ \text{s.t.}{h}_k(x)=0,k=1,2,\cdots ,l \\ {g}_j(x)\le 0,j=1,2,,\cdots ,n \end{gathered}$$ 其对应的拉格朗日函数： $$L(x,\lambda ,\mu )=f(x)+\sum _{i=1}^m{\alpha }_i{h}_i(x)+\sum _{j=1}^n{\beta }_j{g}_j(x)$$ 对上式先最大化再最小化： $$\underset{x}{\min }\left[\underset{\alpha ,\beta ;{\beta }_j\ge 0}{\max }L(x,\alpha ,\beta )\right]=\underset{x}{\min }\left\{f(x)+\underset{\alpha ,\beta ;{\beta }_j\ge 0}{\max }\left[\sum _{i=1}^m{\alpha }_i{h}_i(x)+\sum _{j=1}^n{\beta }_j{g}_j(x)\right]\right\}$$ 在满足KKT条件的情况下，该式和原优化问题式等价的。下面来看看如何证明。

证明：

将上式分为两部分：

1. 可行解区域内，原优化问题的约束条件都得到满足。因为$h_i(x)=0$，所以不管$\alpha$如何变化，必然有$\alpha h_i(x)=0$。$g_j(x)\le 0$，且限定了${\beta }_j>0$，则${\beta }_j{g}_i(x)$最大值为0。综上，在可行解区域内：
   $$\underset{\alpha ,\beta ;{\beta }_j\ge 0}{\max }L(x,\alpha ,\beta )=f(x)+\underset{\alpha ,\beta ;{\beta }_j\ge 0}{\max }\left[\sum _{i=1}^m{\alpha }_i{h}_i(x)+\sum _{j=1}^n{\beta }_j{g}_j(x)\right]=f(x)$$
2. 可行解区域外，此时原优化问题的约束条件未满足。若$h_i(x)\ne 0$，则最大化后为$+\infty$。若$g_j(x)>0$，则最大化后也为$+\infty$。所以在可行解区域外：
   $$\underset{\alpha ,\beta ;{\beta }_j\ge 0}{\max }L(x,\alpha ,\beta )=+\infty$$

综上两个论域，$f(x)$在可行域内最小化，等于$\underset{\alpha ,\beta ;{\beta }_j\ge 0}{\max }L(x,\alpha ,\beta )$的最小化，而在可行域外，$\underset{\alpha ,\beta ;{\beta }_j\ge 0}{\max }L(x,\alpha ,\beta )$无极值。这样当尝试对其进行最小化时，也就相当于原优化问题了。

接着构建对偶问题

有如下定义：

$${\theta }_p(x)=\underset{\alpha ,\beta ;{\beta }_i\ge 0}{\max }\mathcal{L}(x,\alpha ,\beta )$$ 则最小化primal(原始)问题与原问题有同样的解： $$\underset{x}{\min }{\theta }_{\mathrm{p}}(x)=\underset{x}{\min }\underset{\alpha ,\beta ;{\beta }_i\ge 0}{\max }\mathcal{L}(x,\alpha ,\beta )$$ 定义dual(对偶)优化问题如下： $$\underset{\alpha ,\beta ;{\beta }_i\ge 0}{\max }{\theta }_{\mathcal{D}}(\alpha ,\beta )=\underset{\alpha ,\beta ;{\beta }_i\ge 0}{\max }\underset{x}{\min }\mathcal{L}(x,\alpha ,\beta )$$ 注： ${\theta }_p$是针对$\alpha$、$\beta$的优化，${\theta }_D$是针对$w$的优化。

根据上面的内容再做进一步定义：

$p^{\ast }=\underset{x}{\min }{\theta }_p(x)$为primal最小化问题的值，

$d^{\ast }=\underset{\alpha ,\beta ;{\beta }_i\ge 0}{\max }{\theta }_D(\alpha ,\beta )$为Dual问题的值，

他们之间满足：

$$d^{\ast }=\underset{\alpha ,\beta ;{\beta }_i\ge 0}{\max }\underset{x}{\min }\mathcal{L}(x,\alpha ,\beta )\le \underset{x}{\min }\underset{\alpha ,\beta ;{\beta }_i\ge 0}{\max }\mathcal{L}(x,\alpha ,\beta )=p^{\ast }$$ 只有在KKT条件成立时，才有$d^{\ast }=p^{\ast }$，此时，就可以通过Dual问题来求解primal问题。 对偶问题证明： $$d^{\ast }=\underset{\alpha ,\beta ;{\beta }_i\ge 0}{\max }\underset{x}{\min }\mathcal{L}(x,\alpha ,\beta )\le \underset{x}{\min }\underset{\alpha ,\beta ;{\beta }_i\ge 0}{\max }\mathcal{L}(x,\alpha ,\beta )=p^{\ast }$$

对任意$(x,\alpha ,\beta )$，如下不等式一定成立：

$${\theta }_{\mathcal{D}}(\alpha ,\beta )=\underset{x}{\min }\mathcal{L}(x,\alpha ,\beta )\le \mathcal{L}(x,\alpha ,\beta )\le \underset{\alpha ,\beta ;{\beta }_i\ge 0}{\max }\mathcal{L}(x,\alpha ,\beta )={\theta }_{\mathrm{p}}(x)$$ 即： $${\theta }_{\mathcal{D}}(\alpha ,\beta )\le {\theta }_{\mathrm{p}}(x)$$ 所以： $$\underset{\alpha ,\beta ;{\beta }_i\ge 0}{\max }{\theta }_{\mathcal{D}}(\alpha ,\beta )\le \underset{x}{\min }{\theta }_p(x)$$ 即可得到： $$d^{\ast }=\underset{\alpha ,\beta ;{\beta }_i\ge 0}{\max }\underset{x}{\min }\mathcal{L}(x,\alpha ,\beta )\le \underset{x}{\min }\underset{\alpha ,\beta ;{\beta }_i\ge 0}{\max }\mathcal{L}(x,\alpha ,\beta )=p^{\ast }$$

总结

上面一些内容也是从网络习得，也存在一些不严谨的地方，如有错误还请批评指正。

转载地址：http://cmlxf.baihongyu.com/