Lagrange 对偶

Langrangian Duality

拉格朗日对偶

  • 考虑优化问题:找到$f(x)$满足约束的最好下界

  • 考虑方程组

    • 方程组无解:$v$是优化问题的一个下界

    • 方程组有解:则可以推出

      • 显然,取$g_1 + g_2 = 0, g_1(x) > 0$是反例,不能 推出原方程有解
    • 由以上方程组有解逆否命题:方程组无解充分条件如下

  • 由此方法推出的最好下界,即拉格朗日对偶问题

说明

  • 拉格朗日对偶对实数域上的优化问题都存在,对目标函数、 约束函数都没有要求

  • 强对偶定理:$v^{} = z^{}$,需要$f,g$满足特定条件才成立

    • 线性规划
    • 半正定规划
    • 凸优化
    • 即需要给约束条件加以限制,使得 是上述方程组有解的冲要条件
  • 弱对偶定理:$v^{} \leq z^{}$,永远成立(以上即可证)

    • 通过弱对偶定理,可以得到原问题的一个下界
    • 对求解原问题有帮助,比如:分支界限法中快速求下界
  • 对偶问题相关算法往往原问题算法在实际应用中往往更加有效

    • dual-simplex
    • primal-dual interior point method
    • augmented Lagrangian Method

原始问题

约束最优化问题

Generalized Lagrange Function

  • 引入Generalized Lagrange Function

    • $x=(x_1, x_2, \cdots, x_n) \in R^n$
    • $\alpha_i \geq 0, \beta_j$:拉格朗日乘子
  • 考虑关于x的函数

    • $P$:primal,原始问题
    • 若x满足原始问题的两组约束条件,则$\theta_P(x)=f(x)$

    • 若x违反等式约束j,取$\beta_j \rightarrow \infty$, 则有$\theta_P(x) \rightarrow \infty$

    • 若x违反不等式约束i,取$\alpha_i \rightarrow \infty$ ,则有$\theta_P(x) \rightarrow \infty$

    则有

  • 则极小化问题,称为广义拉格朗日函数的极小极大问题

    与原始最优化问题等价,两问题最优值相同,记为

对偶问题

  • 定义

  • 再考虑极大化$\theta_D(\alpha, \beta)$,得到广义拉格朗日 函数的极大极小问题,即

    表示为约束最优化问题如下

    称为原始问题的对偶问题,其最优值定义记为

原始、对偶问题关系

定理1

  • 若原始问题、对偶问题都有最优值,则
  • $\forall x, \alpha, \beta$有

  • 而原始、对偶问题均有最优值,所以得证

  • 设$x^{}$、$\alpha^{}, \beta^{}$分别是原始问题、对偶 问题的可行解,且$d^{} = p^{*}$,则其分别是原始问题、 对偶问题的最优解
Author

UBeaRLy

Posted on

2019-06-27

Updated on

2019-06-27

Licensed under

Comments