Note: The lecture from cxt.

对偶问题基础

  1. 为什么要构造原问题的对偶问题？

    • 非凸问题NP-hard：对偶问题便于计算分析；
    • 对偶问题解与原问题解的关联；
    • 对偶将一系列约束优化转化成更少的约束优化甚至无约束优化；
    • 对偶提供一些新的解法；

  2. 如何构造对偶

    • 拉格朗日对偶
    • Fenchel对偶

  3. 对偶问题与原问题的关系

  4. 对偶

    • 对偶不仅适用于连续优化，整数规划等也适用对偶理论；

    • 鲁棒优化、锥优化很需要对偶分析

拉格朗日对偶

  1. 拉格朗日函数 L(x,λ,μ)x∈X=f(x)+∑imλigi(x)+∑ilμihi(x), λi≥0L(x,\lambda,\mu)_{x\in X}=f(x)+\sum_i^m \lambda_i g_i(x)+\sum_i^l \mu_i h_i(x),\ \lambda_i\geq 0

    • 将原问题的约束条件转化通过乘子合并为一个新的目标函数，减少约束，只剩x∈Xx\in X；
    • 对拉格朗日函数关于x∈Xx\in X求最小值，要比原问题带有多个约束要简单，并且给一组(λ,μ)(\lambda,\mu)的值，就可以得到关于xx的最小值，最小值是关于(λ,μ)(\lambda,\mu)的函数；

  2. 对偶函数 d(λ,μ)=min L(x,λ,μ)x∈X, ∀λ,μ,λ≥0d(\lambda,\mu)=min\ L(x,\lambda,\mu)_{x\in X},\ \forall\lambda,\mu,\lambda\geq0

    • d(λ,μ)=min L(x,λ,μ)x∈X≤min L(x,λ,μ)x∈S≤min f(x)x∈Sd(\lambda,\mu)=min\ L(x,\lambda,\mu)_{x\in X}\leq min\ L(x,\lambda,\mu)_{x\in S}\leq min\ f(x)_{x\in S} 其中SS为原问题的可行域（不仅是x∈Xx\in X还有约束条件）

      • 上式第一个不等号因为在一个可行域大的集合（S⊆XS\subseteq X）里肯定能取到更小的值；
      • 上式第二个不等式因为在可行域SS里，两个乘子项部分是≤0\leq0的；

    • 结论：∀λ,μ,λ≥0\forall\lambda,\mu,\lambda\geq0，d(λ,μ)≤V(p)d(\lambda,\mu)\leq V(p)，V(p)V(p)是原问题最优值，对偶问题是原问题最优值的下界，通过不同的λ,μ\lambda,\mu可以算出不同的下界；

  3. 拉格朗日对偶问题：在d(λ,μ)d(\lambda,\mu)许多个下界中找出最大下界

    max d(λ,μ)=maxλ≥0, μ∈Rnminx∈XL(x,λ,μ)max\ d(\lambda,\mu)=max_{\lambda\geq 0,\ \mu\in R^n}min_{x\in X}L(x,\lambda,\mu)

    • 如果先对λ,μ\lambda,\mu先求最大，再对xx求最小呢？：还原成原问题

    • 原问题可以看成拉格朗日函数先对乘子求最大，然后对变量求最小，即min maxmin\ max的问题

    • 对偶问题可以看成拉格朗日函数先对变量求最小，然后对乘子求最大，即max minmax\ min的问题