71-理论方法-对偶算法

知识点：对偶算法

知识点概述

对偶算法是一类通过求解对偶问题来解决原始优化问题的算法。当对偶问题比原始问题结构更简单、更容易求解时，这种方法尤其有效。

详细解释

• 动机:
  • 原始问题中的约束可能很复杂，但在对偶问题中它们可能被简化或消除。
  • 对偶问题总是凸的，即使原始问题非凸。
  • 问题的结构可能在对偶域中变得可分，从而适合分布式计算。
• 对偶上升法 (Dual Ascent):
  • 思想: 对对偶问题使用梯度上升法。
  • 算法:
    1. $x_{k+1}=\arg {\min }_{x}L(x,{\lambda }_k)$ (x-minimization step)
    2. ${\lambda }_{k+1}={\lambda }_k+{\alpha }_k\nabla g({\lambda }_k)$ (dual update step) 其中对偶函数的梯度 $\nabla g(\lambda )$ 就是原始约束的违反度。
  • 缺点: 需要能高效地求解x-minimization子问题，这并不总是可行。
• 对偶分解 (Dual Decomposition): 如果拉格朗日函数可以分解为多个关于不同变量块的和，那么x-minimization步骤就可以并行地对每个块进行，这使得算法可以分布式执行。
• 原始-对偶混合梯度 (Primal-Dual Hybrid Gradient, PDHG): 一类更现代的算法，同时对原始变量和对偶变量进行迭代，通常具有更好的收敛性和更广泛的适用性。

学习要点

• 理解通过求解对偶问题来解决原始问题的核心思想。
• 掌握对偶上升法的基本迭代步骤。
• 了解对偶分解如何实现分布式优化。

实践应用

• 广泛应用于网络流、资源分配等大规模分布式优化问题。
• 是ADMM等更高级算法的基础。

关联知识点

• 前置知识: 53-理论方法-对偶理论, 57-理论方法-梯度下降法
• 后续知识: 72-理论方法-交替方向乘子法
• 相关知识: 65-理论方法-增广拉格朗日函数法