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$ 称为一对对偶优化问题.