统计机器学习-拉格朗日对偶性

作者: 又双叒叕苟了一天 | 来源:发表于2020-06-16 18:10 被阅读0次

统计机器学习-拉格朗日对偶性
拉格朗日对偶性
拉格朗日对偶性
机器学习——拉格朗日对偶
Lagrange duality拉格朗日对偶性
拉格朗日算子--Apple的学习笔记
机器人动力学方程（二）：拉格朗日法
穷也有好处（拉格朗日数学家的道路）
小蓝本复习（6）拉格朗日对偶性
如何分摊秘密（七）

将有原始问题转化成对偶问题，通过求解对偶问题解决原始问题。

原始问题

假设 $f(x)$ ， $c_i(x)$ ， $h_j(x)$ 是定义在 $\textbf R^n$ 上的连续可微函数，考虑约束最优化问题
$\min_{x\in \textbf R^n}f(x)\\\tag1$

$\mathrm{s.t.}\ \ c_i(x)\leq0,\ \ i=1,2,\cdots,k\\\tag2$

$h_j(x)=0,\ \ j=1,2,\cdots,l\tag3$

称此约束最优化问题为原始最优化问题或原始问题。

如果只是极小化(1)是比较容易的，但是加上约束就不太好处理，于是首先引入广义拉格朗日函数
$L(x,\alpha,\beta)=f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)\tag4$
$\alpha_i$ 和 $\beta_j$ 是拉格朗日乘子，规定 $\alpha_i\geq0$ 。定义函数
$\theta_P(x)=\max_{\alpha,\beta:\alpha_i\geq0}L(x,\alpha,\beta)\\ =\max_{\alpha,\beta:\alpha_i\geq0}\bigg (f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)\bigg )\tag5$
这是一个关于 $x$ 的函数。首先把 $x$ 看做一个常量，再此基础上确定使(4)最大的 $\alpha_i$ 和 $\beta_j$ ，然后带入(5)就成为了一个关于 $x$ 的函数。

如果满足了约束，很容易得到 $\theta_P(x)=f(x)$ 。因为第二项中 $\alpha_i\geq0$ ，且条件 $c_i(x)\leq0$ ，所以乘积 $\alpha_ic_i(x)\leq0$ ，取最大则等于0，第三项满足条件时为0，所以 $\theta_P(x)=f(x)$ 。

如果不满足条件，则会得到
$\theta_P(x)=\max_{\alpha,\beta:\alpha_i\geq0}\bigg (f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)\bigg )=+\infty\tag6$
因为如果 $c_i(x)\gt0$ ，则可以使 $\alpha_i=+\infty$ 。同理，如果 $h_j(x)\neq0$ ，也可以找到 $\beta_j$ 使 $\beta_jh_j(x)=+\infty$ 。

所以(5)可以改写成
$\theta_P(x)=\begin{cases}f(x),\ x满足原始问题约束\\ +\infty,\ 其他 \end{cases}\tag7$
于是原始问题就等于极小化问题
$\min_{x}\theta_P(x)=\min_x\max_{\alpha,\beta:\alpha_i\geq0}L(x,\alpha,\beta)\tag8$
称为广义拉格朗日函数的极大极小问题。定义原始问题的最优值
$p^*=\min_x\theta_P(x)\tag9$

对偶问题

定义
$\theta_D(\alpha,\beta)=\min_xL(x,\alpha,\beta)\tag{10}$
类似的，这是一个关于 $\alpha$ 和 $\beta$ 的函数。首先把 $\alpha$ 和 $\beta$ 看做一个常量，再此基础上确定使(10)最大的 $x$ ，然后带入(10)就成为了一个关于 $\alpha$ 和 $\beta$ 的函数。

对公式(10)极大化，即
$\max_{\alpha,\beta:\alpha_i\geq0}\theta_D(\alpha,\beta)=\max_{\alpha,\beta:\alpha_i\geq0}\min_xL(x,\alpha,\beta)\\ =\max_{\alpha,\beta:\alpha_i\geq0}\min_x\bigg (f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)\bigg )\tag{11}$
称为广义拉格朗日函数的极大极小问题。(11)等价于约束最优化问题
$\max_{\alpha,\beta}\theta_D(\alpha,\beta)=\max_{\alpha,\beta}\min_xL(x,\alpha,\beta)\tag{12}$

$\mathrm{s.t.}\ \ \alpha_i\geq0,\ i=1,2,\cdots,k\tag{13}$

定义对偶问题的最优值
$d^*=\max_{\alpha,\beta:\alpha_i\geq0}\theta_D(\alpha,\beta)\tag{14}$

原始问题和对偶问题的关系

定理1

若原始问题和对偶问题都有最优值，则
$d^*\leq p^*\tag{15}$
证明略。即当原始问题和对偶问题都有最优值时，原始问题的最优值大于等于对偶问题的最优值。

推论1

设 $x^*$ 和 $\alpha^*$ ， $\beta^*$ 分别是原始问题(1)-(3)和对偶问题(12)-(13)的可行解，并且 $d^*= p^*$ ，则 $x^*$ 和 $\alpha^*$ ， $\beta^*$ 分别是原始问题和对偶问题的最优解。

证明略。即两者都是最优解时， $d^*= p^*$ 。

于是存在某些条件下可以用解对偶问题代替解原始问题，且 $d^*= p^*$

定理2

对于原始问题(1)-(3)和对偶问题(12)-(13)。假设函数 $f(x)$ 和 $c_i(x)$ 是凸函数， $h_j(x)$ 是仿射函数；并且假设不等式约束 $c_i(x)$ 是严格可行的，即存在 $x$ ，对所有 $i$ 有 $c_i(x)\lt0$ ，则存在 $x^*$ ， $\alpha^*$ ， $\beta^*$ ，使 $x^*$ 是原始问题的解， $\alpha^*$ ， $\beta^*$ 是对偶问题的解，并且
$d^*= p^*=L(x^*,\alpha^*,\beta^*)\tag{16}$

定理3

对于原始问题(1)-(3)和对偶问题(12)-(13)。假设函数 $f(x)$ 和 $c_i(x)$ 是凸函数， $h_j(x)$ 是仿射函数；并且假设不等式约束 $c_i(x)$ 是严格可行的，则 $x^*$ 和 $\alpha^*$ ， $\beta^*$ 分别是原始问题和对偶问题的解充分必要条件是 $x^*$ ， $\alpha^*$ ， $\beta^*$ 满足Karush Kuhn Tucker(KKT)条件：
$\nabla_xL(x^*,\alpha^*,\beta^*)=0\tag{17}$

$\alpha_i^*c_i(x^*)=0,\ \ i=1,2,\cdots,k\tag{18}$

$c_i(x^*)\leq0,\ \ i=1,2,\cdots,k\tag{19}$

$\alpha_i^*\geq0,\ \ i=1,2,\cdots,k\tag{20}$

$h_j(x^*)=0,\ \ j=1,2,\cdots,k\tag{21}$

(20)称为KKT的对偶互补条件，由此条件可知，若 $\alpha_i^*\gt0$ ，则 $c_i(x^*)=0$ 。

PS：

凸函数：类似满足条件
$\frac{f(x_1)+f(x_2)}{2}\geq f(\frac{x_1+x_2}{2})$
的函数，二阶导数大于等于0或海塞矩阵正定。

仿射函数：最高次数为1的函数，例如 $f(x)=Ax+b$ 。

统计机器学习-拉格朗日对偶性
将有原始问题转化成对偶问题，通过求解对偶问题解决原始问题。原始问题假设，，是定义在上的连续可微函数，考虑约束最...
拉格朗日对偶性
在约束最优化问题中，拉格朗日对偶性将原始问题转换为对偶问题，通过解对偶问题而得到原始问题的解。该方法在统计学习方法...
拉格朗日对偶性
原始问题与对偶问题原始问题：求，s.t.拉格朗日函数设如果与不满足前面的条件约束，则上式就会变成正无穷然后再考虑最...
机器学习——拉格朗日对偶
拉格朗日对偶与凸优化、拉格朗日乘子、KKT条件有着密切的联系，KKT条件可以通过朗格朗日对偶推到得到。 ...
Lagrange duality拉格朗日对偶性
Welcome To My Blog在约束最优化问题(Constrained Optimization)中,常常利...
拉格朗日算子--Apple的学习笔记
在看深度学习资料，居然也有拉格朗日算子，再仔细学习下他的推导。那个landa的引入关键点依据是：拉格朗日算子极值...
机器人动力学方程（二）：拉格朗日法
1、拉格朗日法拉格朗日法是一种基于能量的动力学方法，从拉格朗日函数L（系统动能和势能的差值）出发来建立机器人动力...
穷也有好处（拉格朗日数学家的道路）
约瑟夫·拉格朗日（Joseph-Louis Lagrange，1736~1813) 1736年1月25日，拉格朗日...
小蓝本复习（6）拉格朗日对偶性
本文大多数文字源于李航老师的《统计学习》，仅用于本人复习，侵权删。作者：月牙眼的楼下小黑联系： zhang...
如何分摊秘密（七）
十、拉格朗日插值法本节介绍拉格朗日插值法，学过的读者请略过。从数值分析的角度来看，拉格朗日插值法常被描述成是用...

统计机器学习-拉格朗日对偶性

原始问题

对偶问题

原始问题和对偶问题的关系

定理1

推论1

定理2

定理3

相关文章

统计机器学习-拉格朗日对偶性

拉格朗日对偶性

拉格朗日对偶性

机器学习——拉格朗日对偶

Lagrange duality拉格朗日对偶性

拉格朗日算子--Apple的学习笔记

机器人动力学方程（二）：拉格朗日法

穷也有好处（拉格朗日数学家的道路）

小蓝本复习（6）拉格朗日对偶性

如何分摊秘密（七）

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读