约束优化问题|机器学习推导系列（六）

作者: 酷酷的群 | 来源:发表于2020-08-01 16:18 被阅读0次

一、简介

约束优化问题的原问题（Primal Problem）的一般形式如下：

$\left\{\begin{matrix} \underset{x}{min}\; f(x),x\in \mathbb{R}^{p}\\ s.t.\; m_{i}(x)\leq 0,i=1,2,\cdots ,M\\ s.t.\; n_{j}(x)=0,j=1,2,\cdots ,N \end{matrix}\right.$

求解约束优化问题需要用到拉格朗日乘子法，定义拉格朗日函数：

$L(x,\lambda ,\eta )=f(x)+\sum_{i=1}^{M}\lambda _{i}m_{i}(x)+\sum_{j=1}^{N}\eta _{j}n_{j}(x)\\ \lambda ,\eta 分别是M维、N维向量$

然后原问题可以转化为以下优化问题，这两个优化问题具有同样的解：

$\left\{\begin{matrix} \underset{x}{min}\; \underset{\lambda ,\eta }{max}\; L(x,\lambda ,\eta )\\ s.t.\; \lambda _{i}\geq 0 \end{matrix}\right.$

可以说明一下为什么上述约束优化问题可以求得原问题的最优解：

$以不等式约束为例\\ \left\{\begin{matrix} 如果x违反了约束m_{i}(x)\leq 0，即m_{i}(x)>0,由于\lambda _{i}\geq 0，\underset{\lambda }{max}\; L=\infty \\ 如果x符合约束m_{i}(x)\leq 0,由于\lambda _{i}\geq 0，\underset{\lambda }{max}\; L\neq \infty （此时\lambda _{i}=0） \end{matrix}\right.\\ 因此\underset{x}{min}\; \underset{\lambda }{max}\; L=\underset{x}{min}\left \{\underset{x符合约束}{\underbrace{\underset{\lambda }{max}\; L}},\underset{x不符合约束}{\underbrace{\infty }}\right \}$

也就是说虽然拉格朗日函数对 $x$ 没有约束，但是在求解过程中会过滤掉不符合原问题 $x$ 的约束的 $x$ 。

二、对偶关系证明

原问题的对偶问题为

$\left\{\begin{matrix} \underset{\lambda ,\eta }{max}\; \underset{x}{min}\;L(x,\lambda ,\eta )\\ s.t.\; \lambda _{i}\geq 0 \end{matrix}\right.$

可以看到原问题是关于 $x$ 的函数，对偶问题是关于 $\lambda ,\eta$ 的函数。有如下定理：

$\underset{\lambda ,\eta }{max}\; \underset{x}{min}\;L(x,\lambda ,\eta )\leq \underset{x}{min}\;\underset{\lambda ,\eta }{max}\;L(x,\lambda ,\eta )$

这个关系可以简单地得到证明：

$\underset{A(\lambda ,\eta )}{\underbrace{\underset{x}{min}\;L(x,\lambda ,\eta )}}\leq L(x,\lambda ,\eta )\leq \underset{B(x)}{ \underbrace{\underset{\lambda ,\eta }{max}L(x,\lambda ,\eta )}}\\ \Rightarrow A(\lambda ,\eta )\leq B(x)\\ \Rightarrow A(\lambda ,\eta )\leq min\; B(x)\\ \Rightarrow max\; A(\lambda ,\eta )\leq min\; B(x)\\ \Rightarrow \underset{\lambda ,\eta }{max}\;\underset{x}{min}\;L(x,\lambda ,\eta )\leq L(x,\lambda ,\eta )\leq \underset{x}{min}\;\underset{\lambda ,\eta }{max}\; L(x,\lambda ,\eta )$

三、对偶性的几何解释

$\left\{\begin{matrix} \underset{x}{min}\; f(x),x\in \mathbb{R}^{p}\\ s.t.\; m(x)\leq 0 \end{matrix}\right.\\ 其定义域D为dom\; f\cap dom\; m$

对于上述约束优化问题，可以写出它的拉格朗日函数：

$L(x,\lambda )=f(x)+\lambda m(x),\lambda \geq 0$

然后表示出原问题和对偶问题的最优解 $p^*$ 和 $d^*$ ：

$p^{*}=min\; f(x)\\ d^{*}=\underset{\lambda }{max}\; \underset{x}{min}\; L(x,\lambda )$

接着定义集合G：

$G=\left \{(m(x),f(x))|x\in D\right \}\\ =\left \{(u,t)|x\in D\right \}$

集合G在二维坐标系下表示的空间假设为下图：

因此 $p^*$ 可以表示为：

$inf\left \{t|(u,t)\in G,u\leq 0\right \}$

$p^*$ 在图中可以表示为：

同样地 $d^*$ 也可以用 $u$ 和 $t$ 来表示：

$d^{*}=\underset{\lambda }{max}\; \underset{x}{min}\; L(x,\lambda )\\ =\underset{\lambda }{max}\; \underset{g(\lambda)}{\underbrace{\underset{x}{min}\;(t+\lambda u)}}\\ =\underset{\lambda }{max}\;g(\lambda)\\ g(\lambda)=inf\left \{t+\lambda u|(u,t)\in G\right \}$

$t+\lambda u=b$ 表示以 $-\lambda$ 为斜率，以 $b$ 为截距的直线，而 $g(\lambda)$ 即为与区域 $G$ 相切最小截距的直线 $t+\lambda u=b的b$ 。如下图所示：

g(λ)

结合上图来看，而 $d^*$ 也就可以认为是调整斜率 $-\lambda$ 使得直线 $t+\lambda u=b$ 截距 $b$ 最大时的 $b$ 的值。可以想象无论直线怎么变动，所取得的极值 $d^*$ 都不可能比 $p^*$ 大，这也就解释了为什么对偶问题最优解总是小于等于原问题最优解。

如果 $p^*>d^*$ 则为弱对偶关系；如果 $p^*=d^*$ 则为强对偶关系。

在某些特殊情况下可以使得强对偶关系成立，在图中表示如下：

强对偶关系

如果一个约束优化问题是凸优化问题且同时满足Slater条件，那么可以使得 $d^*=p^*$ ：

$凸优化+Slater条件\Rightarrow d^*=p^*$

但是 $d^*=p^*$ 并不能推出该约束优化问题是凸优化问题且同时满足Slater条件，这是因为Slater条件是 $d^*=p^*$ 的充分不必要条件，还有其他的条件可以使得约束优化问题满足 $d^*=p^*$ 。

四、Slater条件

Slater条件指的是 $\exists \hat{x}\in relint\; D$ 使得 $\forall i=1,2,\cdots ,M\; m_{i}(\hat{x})<0$ 。

$relint\; D$ 指的是定义域除去边界的部分。

有以下两点说明：
①对于大多数凸优化问题，Slater条件是成立的；
②放松的Slater条件：M个 $m_{i}(x)$ 中的仿射函数可以不用验证。因为在定义域内寻找一个满足所有 $m_{i}(x)<0$ 的点是比较困难的，因此放松的Slater条件会减少一些复杂度。

五、KKT条件

对于原问题：

$\left\{\begin{matrix} \underset{x}{min}\; f(x),x\in \mathbb{R}^{p}\\ s.t.\; m_{i}(x)\leq 0,i=1,2,\cdots ,M\\ s.t.\; n_{j}(x)=0,j=1,2,\cdots ,N \end{matrix}\right.$

以及其对偶问题：

$\left\{\begin{matrix} \underset{\lambda ,\eta }{max}\; \underset{x}{min}\;L(x,\lambda ,\eta )\\ s.t.\; \lambda _{i}\geq 0 \end{matrix}\right.$

如果原问题和对偶问题满足强对偶关系，则原问题和对偶问题具有相同的最优解，另外它们还天然地满足KKT条件（Karush-Kuhn-Tucker条件）。假设原问题最优解 $p^{*}$ 对应 $x^{*}$ ，对偶问题最优解 $d^{*}$ 对应 $\lambda ^{*}$ 和 $\eta ^{*}$ ，则KKT条件为：

$\left\{\begin{matrix} 可行条件：\left\{\begin{matrix} m_{i}(x^{*})\leq 0\\ n_{j}(x^{*})=0\\ \lambda ^{*}\geq 0 \end{matrix}\right.\\ 互补松弛：\lambda _{i}m_{i}=0,对\forall i=1,2,\cdots ,M成立\\ 梯度为0：\left.\begin{matrix} \frac{\partial L(x,\lambda ^{*},\eta ^{*})}{\partial x} \end{matrix}\right|_{x=x^{*}}=0 \end{matrix}\right.$

可以进行以下证明：

$d^{*}=\underset{\lambda ,\eta }{max}\; g(\lambda ,\eta )\\ = g(\lambda ^{*},\eta ^{*})\\ =\underset{x}{min}\; L(x,\lambda ^{*},\eta ^{*})\\ \leq L(x^{*},\lambda ^{*},\eta ^{*})\\ =f(x^{*})+\sum_{i=1}^{M}\lambda _{i}^{*}m_{i}(x^{*})+\underset{=0}{\underbrace{\sum_{j=1}^{N}\eta _{j}^{*}n_{j}(x^{*})}}\\ =f(x^{*})+\underset{\leq 0}{\underbrace{\sum_{i=1}^{M}\lambda _{i}^{*}m_{i}(x^{*})}}\\ \leq f(x^{*})\\ =p^{*}\\ 因为d^{*}=p^{*},所以上式中两个\leq 都必须取等号。\\ 首先\underset{x}{min}\; L(x,\lambda ^{*},\eta ^{*})=L(x^{*},\lambda ^{*},\eta ^{*}),则可以得出：\\ \left.\begin{matrix} \frac{\partial L(x,\lambda ^{*},\eta ^{*})}{\partial x} \end{matrix}\right|_{x=x^{*}}=0\\ 然后f(x^{*})+\sum_{i=1}^{M}\lambda _{i}^{*}m_{i}(x^{*})=f(x^{*})，则可以得出：\\ \sum_{i=1}^{M}\lambda _{i}^{*}m_{i}(x^{*})=0，由于\lambda _{i}^{*}m_{i}(x^{*})\leq 0，要使得\sum_{i=1}^{M}\lambda _{i}^{*}m_{i}(x^{*})=0，则必有\lambda _{i}^{*}m_{i}(x^{*})=0$

约束优化问题|机器学习推导系列（六）

一、简介

二、对偶关系证明

三、对偶性的几何解释

四、Slater条件

五、KKT条件

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

人工智能