PAGE1

PAGE1

12.对偶理论与KKT条件

12.1对偶理论概述

对偶理论是优化问题中的一个重要概念，它通过构造一个与原问题相关的对偶问题，来提供原问题的解决方案。对偶问题通常比原问题更容易求解，并且可以提供关于原问题的重要信息，如最优解的边界条件、最优值的下界等。

原问题与对偶问题

假设有一个标准的最小化优化问题，形式如下：

min

其中，x∈Rd是决策变量，fx是目标函数，

构造对偶问题的第一步是定义拉格朗日函数：

L

其中，λ=λ1,

对偶函数定义为：

g

对偶问题可以表述为：

max

弱对偶性和强对偶性

弱对偶性是指对偶问题的最优值总是小于或等于原问题的最优