不等式约束下的对偶问题

对偶问题

  • 原问题

[egin{align} min_{x in cal D} f(x) end{align} ]

其中 ({cal D} = {x in X: g_i(x) leq 0, i = 1,2,cdots, m})​. 一般的,这里(X = mathbb{R}^n)​.

  • (lambda = (lambda_1, cdots, lambda_m)), 并令

[L(x) := max_{lambda geq 0} Big ( f(x) + sum_i lambda_i g_i(x) Big) riangleq max_{lambda geq 0} L(x, lambda) ]

  • 注意下面性质

    • (x otin cal D)时, (L(x) = +infty); 当 (x in cal D)​ 时, (L(x) = f(x)).
    • (L(x))取到最小值时, 我们有 (lambda_i g_i(x) = 0, forall i)​.
  • 根据上面第一条性质,原问题等价于

[min_{x in cal D} f(x) iff min_{xin X} L(x) = min_{xin X} max_{lambda geq 0} L(x, lambda) ]

  • 交换 (min)(max), 得到对偶问题

[max_{lambda geq 0}min_{xin X} L(x, lambda) riangleq max_{lambda geq 0} F(lambda) ]

  • 根据定义,容易证明弱对偶性不等式

    • (max_{lambda geq 0}min_{xin X} L(x, lambda) leq min_{xin X} max_{lambda geq 0} L(x, lambda)), 即 (max_{lambda geq 0} F(lambda) leq min_{x in cal D} f(x))
    • 在给定一些比较弱的条件下, 上述等号都成立,比如目标函数连续。
  • 注意到 (min_{xin X} L(x, lambda)) 对变量(x) 是无约束, 可以直接对拉格朗日函数(L(x, lambda))关于(x)求导, 所以一般的问题会得到简化。

  • 举例: 取(X = {x: x in {0,1}^{I imes J}, x e_J = e_I}), (f)是线性函数, 则对偶的问题(min_{x in X} L(x,lambda))有闭合解。在分配问题上非常有用。 听报告了解到一个dual decomposition 算法, 适用于(F(lambda)) 可以split成几个独立问题的和,即(F(lambda) = sum_j F_j(lambda)),每个子问题只用部分(i)指标, 这里 (I)远大于 (J)

  • KKT条件

[egin{align} & abla_x L(x, lambda) = 0 \ & lambda_i g_i(x) = 0, forall i \ & g_i(x) leq 0, forall i \ & lambda_i geq 0, forall i\ end{align} ]


--- 她说, 她是仙,她不是神
原文地址:https://www.cnblogs.com/bregman/p/15205661.html