AI-统计学习(10)-拉格朗日对偶性-求极值必备

       我们经常要做的就是求解极值，最大或者最小。为了数学方便，引入的是拉格朗日乘子和对偶性。在求解极值的其实就是关注d*（最优值） C（约束）  p*（最优概率）。如果不想看推导，可直接看总结的红字即可。

 

   1.拉格朗日对偶性及其推导

    2.定理

        2.1定理1  d* C  p*关系

        2.2定理2  d*= p* 等号成立的条件（凸集、凸优化问题）

        2.3定理3 著名的KKT条件（5个）x*,a*,b*满足5个条件

                  X*就是原问题的最优解。

                 a*,b*就是对偶问题的最优解

 

---

1.拉格朗日对偶性及其推导

1.1 原始问题

     Minf(x)

   

1.2加入了拉格朗日函数

1.3根据拉格朗日函数定义了原始问题的对偶性

  简而言之 Minmax=maxmin

 

1.4推导过程

  1.4.1原始问题 函数表达式和约束（不等式约束和等式约束）

  1.4.2 拉格朗日函数

  1.4.3 代入拉格朗日函数

       取约束条件最大化

       取fx最小化

       约束条件最优于是值最优

  1.4.3名词 目标函数、优化变量、可行域、最优值、最优解、约束条件

      目标函数：f(x)

      优化变量：x

      可行域：等式、不等式的交集

     

     最优值：x*

   最优解：P*

   约束条件：C

   求解目标：

1.5结论：

根据拉格朗日函数定义了原始问题的对偶问题(关于a、b求目标函数的极大值)。

原始问题相当于Min max拉格朗日函数

对偶问题相当于max min拉格朗日函数

2.定理

2.1定理1 d* C  p*关系

   原始问题：

   对偶问题：

  求最优值的关系：

   过程：

        a最优值描述 没对x做任何约束

  b 取最小时，等式变换

  c ab取最小时，去掉后等式变换

     d 得最优概率 P*

总结：1.d*<=p*对偶问题的最优值提供了原问题的极小值的下界

      2.原始问题求极小值,极小值最小不能小过d*

      3. C d*

        P*    对偶问题与原始问题的关系

       d*<=p*,我们关心的是=成立 即 d*=p*

 

2.2定理2  d*= p* 等号成立的条件

  2.2.1成立的条件两个

      原问题是凸优化问题

      原问题满足slater条件

 

  2.2.2凸集 凸优化问题

     a)凸集是神马

    

 

     b)凸优化问题是神马

         

C)凸函数是神马

         

2.2.3 slater

      

总结：何时d*= p* 就是什么时候可以用过对偶问题求解原问题的解。

实现的充分条件是 凸集、凸优化、凸函数、slater

不是充要条件。左边可以推出右边，但是右边成立，左边不一定成立。

 

2.3定理3 著名的KKT条件（5个）

   2.3.1 5个条件

   2.3.2 求解过程

2.3.3总结：

   找x*,a*,b*满足5个条件

   那么X*就是原问题的最优解

   a*,b*就是对偶问题最优解。