拉格朗日对偶性

2020-06-16 本文已影响0人 LuckilyHaveYou

原始问题与对偶问题
- 原始问题：
  求 $\underset{x\in R^n}{min}f(x)$ ，
  s.t. $c_i(x)\leq 0,i=1,2,..k$
  $h_j(x)=0,j=1,2..l$
  拉格朗日函数
  $L(x,\alpha,\beta)=f(x)+\sum_i^k\alpha_ic_i(x)+\sum_j^l\beta_jh_j(x)$
  设 $\theta_P(x)=\underset{\alpha,\beta:\alpha\geq0}{max}L(x,\alpha,\beta)$
  如果 $c_i(x)$ 与 $h_i(x)$ 不满足前面的条件约束，则上式就会变成正无穷
  $\theta_P(x)=\begin{cases} f(x) & \\ +Inf \end{cases}$
  然后再考虑最小化问题 $\underset{x}{min}\theta_P(x)$
  则上式与f(x)极小化是等价的。这个就是极小极大问题
- 对偶问题:
  - $\theta_D(\alpha,\beta)=\underset{x}{min}L(x,\alpha,\beta)$
    然后再考虑极大
    $\underset{\alpha,\beta}{max}\theta_D(\alpha,\beta)$
    这个就是极大极小问题
- 原始问题与对偶问题的关系
  定理1：如果两个问题都有最优值，对偶问题会小于等于原始问题
  推论：如果可以找到 $x^*,\alpha^*,\beta^*$ 是原始与对偶问题的最优解，且两者相等，则分别是原始问题与对偶问题的最优解。这样理解，因为原始问题会大于等于对偶问题，则在取等号时取到了最小值，则是最优解，反过来一样，对偶问题是找最大值。
  定理2：如果f(x)与c(x)是凸函数，h(x)是仿射函数，并且c(x)是严格可行的（存在x，使得对于所有的i有c(x)<0），则推论中的解是存在的。
  定理3:求最优解的充分必要条件是 $x^*,\alpha^*,\beta^*$ 满足KKT条件
  $\begin{aligned} \nabla_xL(x^*,\alpha^*,\beta^*)=0 \\ \alpha_i^*c_i(x^*)=0 \\ c_i(x^*)\leq0 \\ \alpha_i^*\geq0 \\ h_j(x^*)=0 \end{aligned}$

去github

拉格朗日对偶性

猜你喜欢

热点阅读