【知识总结】 对偶

Lagrange 对偶函数

• 标准形式优化问题
  • • 最优值设为
• 问题的Lagrange函数
  • • 称为对应约束的Lagrange乘子，称为对偶变量或问题的Lagrange乘子向量
• Lagrange对偶函数
  • • 若关于无下界，则对偶函数值取
    • 优化该函数是容易的，因为这是一个凹函数，且没有约束条件
• 最优值的下界
  • 设是原问题的可行点，则对偶函数构成了原问题最优值的下界
    • 对有
    • 注：后面的强对偶性成立条件可以理解为要求上述不等号都取等
• 对偶范数
• Lagrange对偶函数和共轭函数
  • 共轭函数为
  • 设优化问题形式为
  • 对偶函数为

Lagrange对偶问题

• 标准形式对偶问题
  • • 极大化的目标函数是凹函数，约束集合是凸集，所以Lagrange对偶问题是凸优化问题
  • 该对偶问题的任务是寻找原问题最优值的最紧下界
    • 设对偶问题最优值是
• 弱对偶性
• 最优对偶间隙 -
• 强对偶性
  • 凸问题通常有强对偶性
• 规范约束准则
  • 保证凸问题的强对偶性的条件
    • 比如Slater条件
  • Slater条件
    • 存在，使得
    • 当满足Slater条件，凸问题的强对偶性成立
  • 改进的Slaster条件
    • 存在，使得
    • 当满足改进的Slater条件，且是仿射的，凸问题的强对偶性成立

KKT最优性条件

• KKT最优性条件
  • 非凸问题的KKT条件
    • 对于目标函数和约束函数可微的任意优化问题，如果强对偶性成立，则任意一对原、对偶问题最优解满足KKT条件
    • 设分别是原问题和对偶问题的某对最优解，对偶间隙是零
  • 凸问题的KKT条件
    • 当原问题是凸问题，满足KKT条件的点是原、对偶最优解（强对偶性、对偶间隙为零）
    • 设是凸函数，是仿射函数，是任意满足KKT条件的点

等价问题的对偶问题

• 对一个问题进行等价变形，可能得到非常不同的对偶问题
• 常见变形
  • 引入新的变量或等式约束
  • 用目标函数的增函数代替原目标函数
  • 将显式约束隐式表达，比如将其并入目标函数的定义域

广义不等式推广

• 一般形式
  • 其中是正常锥
• Lagrange乘子向量
  • 对于每个广义不等式引入Lagrange乘子向量
• Lagrange函数
• Lagrange对偶函数
• 最优值下界
  • 若，则
    • 是的对偶锥
• 对偶问题
  • 最优值一般记为
• 弱对偶性
• 强对偶性
  • 凸问题在合适的约束准则下满足强对偶性，此处不继续展开