原文地址為：數值優化（Numerical Optimization）學習系列-懲罰和增廣拉格朗日方法（Augmented Lagrangian Methods）
概述
求解帶約束的最優化問題，一類很重要的方法就是將約束新增到目標函式中，從而轉換為一系列子問題進行求解，最終逼近最優解。關鍵問題是如何將約束進行轉換。本節主要介紹
1. 二次懲罰方法
2. 非平滑懲罰方法
3. 增廣拉格朗日方法
二次懲罰方法
動機
帶約束問題如果轉換為目標函式加上一個對約束的懲罰項，則問題轉換為一個無約束問題。
轉換後的問題可以通過懲罰項的係數進行控制，一個比較常見的懲罰函式就是二次懲罰。
等式約束的最優化問題
等式約束問題可以表示為
min f(x)s.t ci(x)=0,i∈E
新增一個二次懲罰項，則有
Q(x;μ)=f(x) μ2∑i∈Ec2i(x)
其中
μ
是懲罰引數，直觀上只要增加懲罰引數的值就可以逼近原始問題的最優解。
在實際中，對於某個懲罰引數
μ
只要幾步無約束最優化問題，不需要尋找最優解。
一般化約束最優化問題
一般化約束最優化問題表示為
minf(x)s.tci(x)=0 i∈E ci(x)≥0 i∈I
新增懲罰項係數結果為
Q(x;μ)=f(x) μ2∑i∈Ec2i(x) μ2∑i∈I([ci(x)]−)2
其中
ci(x)−
表示當該值大於0時，結果為0，否則為
−ci(x)
二次懲罰項通用框架
1.引數
μ
的選擇可以根據無約束問題的優化難度進行確定，如果很容易優化則可以
μk 1=μk
，否則可以選擇
μk 1=μk
2. 定理：如果轉換後的問題
Q(x;μk)
每一步都計算最優解，並且當
μk→∞
時能夠接近原始問題的最優解。
非平滑懲罰函式
有些懲罰函式是精確的，即懲罰項引數
μ
達到一定值時轉換後的問題的最優解就是原始問題的最優解，其中l1懲罰項就是精確的，表示如下
ϕ1(x;μ)=f(x) μ∑i∈E|ci(x)| μ∑i∈E|ci(x)|−
通用求解框架
增廣拉格朗日方法
動機
增廣拉格朗日方法在拉格朗日方法的基礎上新增了二次懲罰項，從而使得轉換後的問題能夠更容易求解，不至於因條件數變大不好求。則轉換後的問題為
L(x,λ;μ)=f(x)−∑i∈Eλici(x) μ2∑i∈Eci(x)2
在第K步迭代過程中，固定懲罰項引數
μ
和
λk
，此時優化x，根據最優化條件有
∇xL=∇f(x)−∑i∈E(λki−μkci(x))∇ci(x)=0
對比最優性條件，應該有
∇f(x∗)=0;λ∗=λki−μkci(x)
，從而很自然的可以將
λk 1=λki−μkci(x)
等式約束通用框架
實際應用
在實際中，增廣拉格朗日方法可以很有效的處理邊界約束和線性約束最優化問題。
總結
瞭解通過將約束轉換為懲罰項新增到目標函式上的方法，瞭解增廣拉格朗日方法的動機。
轉載請註明本文地址：數值優化（Numerical Optimization）學習系列-懲罰和增廣拉格朗日方法（Augmented Lagrangian Methods）