塘沽二中心小学机器学习知识点总结-拉格朗⽇乘⼦法
（LagrangeMultiplierMethod）详解
⼀直对拉格朗⽇乘⼦法不是理解的不是很透彻，今天决定要push⼀下⾃⼰，彻底的理解拉格朗⽇乘⼦法，希望对⼤家有所帮助。
接下来，我将从⼀下⼏个⽅⾯循序渐进的介绍拉格朗⽇乘⼦法：
⽬录
1 拉格朗⽇乘⼦法的基本定义和思想
拉格朗⽇乘⼦法是⼀种优化算法，主要⽤于解决带约束条件下的优化问题。其基本思想就是通过引⼊拉格朗⽇乘⼦，将含有n个变量、k个约束条件的约束优化问题转化为含有（n+k）个变量的⽆约束优化问题。 标准形式的带约束的优化问题可以⽤如下公式表⽰:
公式（1.1）
在公式（1.1）中，是⾃变量，。该问题的定义域是⾮空集合为, 其中 表⽰满⾜约束的⾃变量的集合。
为满⾜约束条件的当前问题的最优解，为最优解对应的最优值。在当前问题中为最优极⼩值。
1.2 拉格朗⽇乘⼦法的定义
拉格朗⽇乘⼦法的基本思想就是将公式（1.1）中带有约束的最优化求解问题，转换为没有约束的优化问题。它的具体实现如公式（1.2）：
公式（1.2）
其中，是拉格朗⽇函数，就是拉格朗⽇乗⼦，且满⾜。成为primal变量，为dual变量（对偶变 量）。
1.3 KKT（Karush-Kuhn-Tucker）条件
本节将详细介绍为什么拉格朗⽇乘⼦法可以将带约束的优化问题转换成⽆约束的优化问题，引出KKT条件的定义并介绍它的含义和作⽤。
1.3.1 为什么拉格朗⽇乘⼦法可以将带约束的优化问题转换成⽆约束的优化问题?
谁欠谁的幸福 作者
带约束的优化问题可以分为：等式约束的优化问题和不等式约束的优化问题。接下来，我们将从这两⽅⾯进⾏分析。
1. 等式约束的优化问题。
等式约束的优化问题定义为：假定为维向量，欲寻的某个取值 ，使⽬标函数最⼩，且满⾜。
可⽤以下数学公式表⽰：
从⼏何⾓度来看，该问题的⽬标是在由⽅程确定的维度曲⾯上寻能够使⽬标函数最⼩化的点。
如图(a)所⽰，假设⾃变量包括两个维度。我们不难得出如下结论：
1. 对于约束曲⾯上的任⼀点，该点的梯度正交于约束曲⾯
2. 对于最优点，⽬标函数在最优点的梯度也正交于约束曲⾯
由此可知，在最优点，梯度和必然⽅向相同或者相反。即：存在，使得：
其中对应了拉格朗⽇函数中的拉格朗⽇乘⼦。
在该问题中，构造的对应的拉个朗⽇⽅程应为：。
不难发现，拉格朗⽇⽅程的对于的偏导数 设置为0则等价于公式（1.4）；同时，若将拉格朗⽇对求得的偏导设置为0，则得到对应的约束条件。
于是，可以证明：拉格朗⽇乘⼦法可以将原始的带等式约束的优化问题转化为对拉格朗⽇函数的⽆约束优化问题。
(a) 带等式约束的优化问题 (b) 带不等式约束的优化问题
马家老鸡铺2. 不等式约束的优化问题
现在我们考虑带不等式约束的优化问题。带不等式约束的优化问题可以写成：
在该种情况下，最优点的位置只有两种可能：要么存在于约束边界的区域内；要么存在于约束边界上。接下来我们分开分析⼀下这两种情况。石大科技
- 最优点在约束边界区域内
在这种情况下，约束不起作⽤。我们可以直接通过条件求得最优点。
等价于令后，再对拉格朗⽇函数求导
- 最优点在约束边界上
这种情况类似于等式约束的优化问题。
但需要注意的是，和必须反向，即存在，使得
。
在整合这两种可能，⽆论是还是，最优解都必须满⾜：。
swi.t
综上可知，拉格朗⽇乘⼦法可以将 带不等式约束的优化问题，转化成在约束条件（公式（1.6））下对求最⼩化的优化问题。
拉格朗⽇函数
同理，上述做法可以推⼴到多个约束的情况，即对于1.1节中描述的原始问题，⾸先我们可以利⽤拉格朗⽇乘⼦法构造拉格朗⽇⽅程及其对应的KKT条件：
求解1.1节介绍的原始问题等价于求解在满⾜KKT条件下的拉格朗⽇函数的最优化的问题。
⾄此，我们已经证明了拉格朗⽇乘⼦法的有效性，它确实可以将原始带约束的优化问题转化为求解满⾜KKT条件下的拉格朗⽇函数的最优化问题。
1.3.2 KKT条件的定义及作⽤？
从上⼀节的推倒过程我们可知，拉格朗⽇乘⼦法可以将带不等式约束的优化问题 ，转化成在KKT条件下对拉格朗⽇函数
求最⼩化的优化问题。
这句话的含义是，当KKT条件被满⾜时，对拉格朗⽇函数的最优化问题才 等价于 原始问题。换句话说，KKT条件是拉格朗⽇取得可
⾏解的必要条件。只有满⾜KKT条件，才能求出原始问题的最优解。
2 对偶理论
因为⼀个优化问题 可以从两个⾓度进⾏考察：即：主问题（primal问题）和对偶问题（dual问题）。本节中，我们将⾸先介绍原始
问题、对偶问题及其定关系；然后介绍在带约束的优化问题中对偶函数的定义，以及在拉格朗⽇乘⼦法中原始问题的对偶问题是什么、以及
对其对偶问题和原始问题的关系的推倒。
2.1 原始问题、对偶问题的定义和它们之间的关系
对偶问题：每⼀个线性规划问题都伴随有另⼀个线性规划问题，称为对偶问题。
原始问题（主问题）：原来的线性规划问题则称为原始线性规划问题，简称原始问题。
对偶问题与原始问题之间存在着下列关系：
① ⽬标函数对原始问题是极⼤化，对对偶问题则是极⼩化。
② 原始问题⽬标函数中的收益系数是对偶问题约束不等式中的右端常数，⽽原始问题约束不等式中的右端常数则是对偶问题中
⽬标函数的收益系数。
③ 原始问题和对偶问题的约束不等式的符号⽅向相反。
④ 原始问题约束不等式系数矩阵转置后即为对偶问题的约束不等式的系数矩阵。
⑤ 原始问题的约束⽅程数对应于对偶问题的变量数，⽽原始问题的变量数对应于对偶问题的约束⽅程数。
⑥对偶问题的对偶问题是原始问题，这⼀性质被称为原始和对偶问题的对称性。
值得注意的是，如果我们能够获得原始问题或者对偶问题的中的任意⼀个问题的最优解，那么就相当于已经得到另外的问题的最优解。
2.2 拉格朗⽇乘⼦法中的对偶
2.2.1 对偶函数、原始问题、对偶问题以及⼀些基本结论
本节我们先给出对偶函数的定义；然后再介绍拉格朗⽇乘⼦法中的原始问题，对偶问题分别是什么。
对偶函数
拉格朗⽇函数的对偶函数的定义：拉格朗⽇函数关于取得的最⼩值。可表⽰为：
拉格朗⽇乘⼦法中的原始问题、对偶问题分别是什么
原始问题：1.1节给出的带约束的最优化问题
对偶问题：原始问题的对偶问题等于 拉格朗⽇函数的对偶函数的最优值，即：
⼀些基本结论
结论1：对偶函数 构成了原始问题（即公式（1.1））的最优值的下界，即:
结论2：若对偶问题和原始问题均有最优解，设对偶问题的最优解对应的最优值为 ，即：
其中，的定义为公式（2.2）中给出，它是对偶函数的最优极⼤值。
2.2.2 对偶问题与原始问题的关系的推倒
接下来我们看⼀下为什么该结论成⽴：
结论1证明：
⾸先，在拉格朗⽇函数中，对于任意可⾏点，由于，并且 ，，因此有：
公式（2.5）因⽽，根据上述不等式，我们可以推出：
因此，对任意可⾏点均有：
故⽽，可以推出公式（2.3）对于的不等式 成⽴，即：对偶函数是原始问题的最优值的下界。
结论2证明：
从结论1中可知，对偶函数构成了原始问题的最优值的下界，即: 。
故⽽，对偶函数的全部可能取解，都⼩于等于原始问题的最优解。
sony cr33所以，对偶函数的最优值，也⼀定⼩于原始问题的最优解。
在⽬前研究的问题当中，对偶函数具有极⼤值，那么可以推出结论2：
⾄此，拉格朗⽇乘⼦法、对偶问题以及对偶问题和原始问题的关系介绍完毕。
3 拉格朗⽇乘⼦法实例
后记：
⾃参加完⼀个会议之后，⾃觉与⼤⽜们差距甚远。往事不可追，后悔之前的荒废时间和不求甚解已经是徒劳。但求以后，以这篇⽂章为起点，要求⾃⼰不论⼯作亦或是求学都能踏踏实实，全⼒以赴。⼗年后再回⾸不会再有虚度光阴之感。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议