1.1. 优化中的对偶问题

优化中的对偶问题 ( Dual Problem )

Fenchel’s duality theorem

Wolfe dual problem

1.1.1. 约束优化的对偶问题

设有原优化问题

(1.7)\[P: {\rm max}\ f({\bm x}) = {\bm c}^T {\bm x} \\ {\rm s.t.} \left\{\begin{array}{r}{{\bm A}{\bm x}\leq {\bm b}} \\ {{\bm x} \geq {\bm 0}}\end{array}\right. \]

其对偶优化问题为

(1.8)\[D: {\rm min}\ g({\bm y}) = {\bm b}^T {\bm y} \\ {\rm s.t.} \left\{\begin{array}{r}{{\bm A}^T{\bm y}\geq {\bm c}^T} \\ {{\bm y} \geq {\bm 0}\ }\end{array}\right. \]

上述问题 \(P\) 和 \(D\) 称为一对对偶优化问题.