拉格朗日对偶性
拉格朗日对偶性 - Lagrange Duality
目录
- 原始问题
- 对偶问题
- 原始问题与对偶问题的关系
1. 原始问题
假设$ f(x),c_i(x),h_j(x) $是定义在$R^n$上的连续可微函数,考虑约束最优化问题
称此约束最优化问题为原始最优化问题或原始问题。
引入广义拉格朗日函数
这里,$x=(x^{(1)}, x^{(2)}, …, x^{(n)})^T \in R^n, \alpha_i, \beta_j$是拉格朗日乘子,$ \alpha_i \geq 0 $, [不要求$ \beta_j \geq 0 $,详细可以看这里]。 考虑$x$的函数:
这里下标$P$表示原始问题。
当有约束条件不满足时,可以调整该约束条件的拉格朗日乘子,可以使得$ \theta_P(x)=+\infty $,只有当所有的约束条件全都满足时,则可知$\theta_P(x) = f(x)$。 所以,
所以,如果考虑极小化问题
该问题与原始最优化问题$式(1) \sim 式(3)$等价,即它们具有相同解。问题$ \mathop{\min}_x \theta_P(x) = \mathop{\min_x\max_{\alpha, \beta: \alpha_i \geq 0}} L(x, \alpha, \beta) $ 称为广义拉格朗日函数的极小极大问题,这样,原始最优化问题表示为广义拉格朗日函数的极小极大问题。
定义原始问题的最优值:
称为原始问题的值。
2. 对偶问题
定义
再考虑极大化
问题$ \mathop{\max}_{\alpha,\beta:\alpha_i \geq 0} \mathop{\min_x} L(x,\alpha, \beta) $称为广义拉格朗日函数的极大极小问题。
可以将广义拉格朗日函数的极大极小问题表示为约束最优化问题:
称为原始问题的对偶问题。
定义对偶问题的最优解:
称为对偶问题的值。
3. 原始问题与对偶问题的关系
3.1 定理 1
若原始问题和对偶问题都有最优值,则
3.2 定理 2
考虑原始问题$式(1) \sim 式(3)$和对偶问题$式(11) \sim 式(12)$, 假设函数$f(x)$和$c_i(x)$是凸函数,$h_j(x)$是仿射函数[最高次数为1的多项式函数,常数项为零的仿射函数称为线性函数]; 并且假设不等式约束$c_i(x)$是严格可行的,即存在$x$,对所有$i$有$c_i(x)<0$, 则存在$ x^{\ast}, \alpha^{\ast}, \beta^{\ast} $,使$x^{\ast}$是原始问题的解,$ \alpha^{\ast}, \beta^{\ast} $是对偶问题的解,并且
3.3 定理 3
对原始问题$式(1) \sim 式(3)$和对偶问题$式(11) \sim 式(12)$, 假设函数$f(x)$和$c_i(x)$是凸函数,$h_j(x)$是仿射函数,并且假设不等式约束$c_i(x)$是严格可行的,则$ x^{\ast} 和 \alpha^{\ast}, \beta^{\ast} $分别是原始问题和对偶问题的解的充分必要条件是$ x^{\ast}, \alpha^{\ast}, \beta^{\ast} $满足下面的$ Karush-Kuhn-Tucker(KKT) $条件:
特别指出,$ 式(17) $称为$KKT$的对偶互补条件,由此条件可知:若$ \alpha^{\ast} > 0 $,则$ c_i(x^{\ast})=0 $。
参考
李航 - 《统计学习方法》