本文共 4717 字，大约阅读时间需要 15 分钟。

本文简单总结一些相关概念，具体证明以后再补充； 

1. 拉格朗日乘子法 

2. 罚函数法：外罚函数与内罚函数法 

3. 广义乘子法

1. 拉格朗日乘子法

1.1 无约束问题

无约束问题，定义为 minf(x)minf(x)， 对于凸函数而言，直接利用费马定理，f′(x)=0f′(x)=0，获得最优解；

1.2 等式约束问题

等式约束定义如下： 

现在利用拉格朗日乘子法，合并式子： 

对 x,ax,a 分别求偏导： 

发现第二个式子刚好是其约束条件；

为什么？ 

现在，我们在平面内投影函数，画出f(x)f(x)的等高线，以及g(x)=0g(x)=0的边界线；如图示： 

蓝色虚线代表了f(x,y)f(x,y)的等高线；红色代表g(x,y)=c=0g(x,y)=c=0; 

 

回顾： 

1. 方向导数是各个方向上的导数 

2. 偏导数连续才有梯度存在 

3. 梯度的方向是方向导数中取到最大值的方向，梯度的值是方向导数的最大值(垂直方向) 

假设f(x)f(x)的最小值在圆心处，即梯度方向向外；g(x,y)g(x,y)的梯度方向向下； 

那么满足条件的值一定是两个函数相切处；如果相交，那么一定还存在一个等高线与红线相切，而且更小；在切点处，两个函数的梯度共线，即f′(x)=−ag′(x),a<0f′(x)=−ag′(x),a<0；做简单的变换后：f′(x)+ag′(x)=0f′(x)+ag′(x)=0，这就是第一个等式啦，同时还需要满足第二个式子；

1.3 不等式约束问题（KTT条件）

不等式约束问题： 

引入拉格朗日函数：(KTT 条件) 

这样就将不等式约束变成了等式约束，偏导等于零即可求得最优参数； 

对偶变换后有：
因为 h(x)<0h(x)<0 ，所以只有当 bh(x)=0bh(x)=0 时， L(x,a,b)L(x,a,b) 才能取得最大值；否则不满足条件；所以KTT条件是 minf(x)minf(x) 的必要条件；

补充：SVM 满足KTT条件:在边界上的点，有h(x)=0h(x)=0；非边界处，令b=0;

1.4 拉格朗日乘子法问题

当 目标函数的Hess矩阵不正定时（特征值不全为正，或者行列式不为正，那么此时的偏导为0处，并不能确定是否是极值点），所以无法求解；

例子： 

求解

{

minf=2x2+y2−2xys.t.x+y=1{minf=2x2+y2−2xys.t.x+y=1

我们定义

L(x,y,λ)=f−λg(x)=2x2+y2−2xy−λ(x+y−1)L(x,y,λ)=f−λg(x)=2x2+y2−2xy−λ(x+y−1) 

求偏导可得：

⎧⎩⎨⎪⎪⎪⎪∂L∂x=4x−2y−λ=0∂L∂y=2y−2x−λ=0∂L∂λ=x−y−1=0{∂L∂x=4x−2y−λ=0∂L∂y=2y−2x−λ=0∂L∂λ=x−y−1=0

我们可以计算原目标函数的Hess矩阵：

A=⎡⎣⎢∂2L∂x2∂2L∂y∂x∂2L∂x∂y∂2L∂y2⎤⎦⎥=[4−2−22]A=[∂2L∂x2∂2L∂x∂y∂2L∂y∂x∂2L∂y2]=[4−2−22]正定矩阵； 

再看一个目标函数，方程稍作修改： 

{

minf=2x2+y2+3xys.t.x+y=1{minf=2x2+y2+3xys.t.x+y=1

直接求偏导，发现方程无解； 

再看其Hess矩阵：

B=[4332]B=[4332]非正定矩阵； 

也就是说，在梯度为零处，我们无法判断是否是极值；

---

2. 罚函数法

2.1 定义

罚函数法：根据约束条件的特点，构造出惩罚函数，然后加入到目标函数中，将其转化为无约束问题；新目标函数的解与原始目标函数解一致；

2.1.1 等式约束的罚函数法：

我们引入一个增广目标函数： 

这里： σσ 是惩罚因子，取很大的正数， F(x,σ)F(x,σ) 是罚函数， σP(x)σP(x) 是惩罚项； 
惩罚项的性质： 
1. 当xx为可行解时，P(x)=0P(x)=0，惩罚项为0；  
2.当xx不在可行域内，此时σP(x)σP(x)会很大，那么求得minF(x,σ)minF(x,σ)必然有minf(x)minf(x)与minx,σ[σP(x)]minx,σ[σP(x)]同时成立；所以，当σσ充分大时，增广目标函数的最优值接近于原始问题的最优值；（σ→∞σ→∞，若原问题有解（F<∞F<∞），则会有g=0g=0）

例如： 

minf(x)=(x1+x2)2s.t.g(x)=x1+x2=cminf(x)=(x1+x2)2s.t.g(x)=x1+x2=c

构造罚函数为：

minL(x,σ)=minf(x)+σ||g(x)||22minL(x,σ)=minf(x)+σ||g(x)||22

σσ设置的值较大；第一部分优化解，第二部分使得解在可行域内； 

如果x不在可行域内，需要我们大步迭代；

2.1.2 不等式约束的罚函数法：

此时我们构造惩罚项； 
（1） P(x)=∑[min(0,hi(x))]2P(x)=∑[min(0,hi(x))]2 ，可以简单分析出：当 hi(x)>=0hi(x)>=0 时 P(x)=0P(x)=0 ，满足条件；当不在可行域内时，我们需要加大惩罚； 
（2） P(x)=∑αih2iP(x)=∑αihi2 ,其中 αi={

0,hi>=01,hi<0αi={0,hi>=01,hi<0

2.1.3 一般形式的罚函数法： 

那么罚函数为：

特别注意：惩罚因子是充分大的数，拉格朗日乘子是一个确定的参数，意义不一样；(当惩罚因子过大时，在求解极小值的过程中，Hess矩阵变成病态矩阵？)

2.2 外罚函数法

对不在可行域内，加大惩罚；上文介绍的就是外罚函数法； 

2.3 内罚函数法

又称障碍函数法，内点法）；在可行域内筑起高墙，迫使值在可行域内，目标函数无法穿越；（只适用于不等式约束） 

障碍函数一般取：（1）倒数 （2）对数 

障碍因子为很小的正数 

当xx趋于边界时，那么障碍函数趋于无穷；初始点在可行域内部； 

在可行域内时，障碍函数值很小，增广目标函数与原始目标函数等价了；

---

3. 广义乘子法

3.1 等式约束广义乘子法：

广义乘子法是 拉格朗日乘子法与罚函数法 的结合； 

在罚函数的基础上增加了乘子项，首先在 σσ 足够大的基础上，获得 ϕϕ 的极小值，然后在调整 λλ 获得原问题的最优解； 
迭代公式如下 ： 
梯度等于零： ∇xϕ(xk,λk,σk)=0∇xϕ(xk,λk,σk)=0 ,即
令 λk+1=σkg(xk)+λkλk+1=σkg(xk)+λk ，则导出拉格朗日乘子法的一阶必要条件； 

计算方法： 
(1)初始值设置： x,λ,σx,λ,σ  
(2)计算梯度为0，获得当前最优值 xkxk ，然后判断是否终止； 
(3)是否调整惩罚因子，获得 σk+1σk+1  
(4)计算 λk+1=σkg(xk)+λkλk+1=σkg(xk)+λk

3.2 不等式约束广义乘子法：

思想是：引入松弛变量，化不等式问题为等式约束； 

那么原始问题转化成： 

首先计算关于 ββ 的极小值；因为 β>=0β>=0 ，上式是关于 ββ 的二次函数，开口向上，对称轴是 h+λσh+λσ ，
这样做的目的是：保证增广目标函数最优解近似于原始问题最优解； 
分析：当 σh+λ>=0σh+λ>=0 时， β=h+λσβ=h+λσ ，则
当 σh+λ<0σh+λ<0 时， β=0β=0 ，则
梯度为零计算最优解，发现刚好满足朗格朗日乘子法的必要条件；

3.3 一般约束广义乘子法：

混合等式不等式约束法，计算即可。

https://blog.csdn.net/lmm6895071/article/details/78329045?locationNum=7&fps=1