罰函數法和拉格朗日乘子法的區別？

01-04

我的理解是，拉格朗日乘子法的求解是解析的，而求解罰函數是不斷迭代的數值方法，不知道這樣的理解對不對？

半夜醒來，然後失眠了，答個題

Penalty methods和Multiplier Methods的形式緊密相關，甚至可以互相解釋，所以要清晰而精確地論述二者的本質差異並不容易。

先理清一些誤解吧。解析與不解析無非就是個符號而已，只要是唯一確定並且可以計算就夠了，不要強迫症地認為"x=log(2)"是解析解，"x是x^3-x-100=0的最大根"就不是解析解。我看到評論中的說法，懲罰函數法適用於不等式約束，拉式乘子法適用於等式約束。這樣的描述就很尷尬。通常書本上確實喜歡這麼舉例，但這並不意味著懲罰函數法不可以用於等式約束，拉式乘子法不可以用於不等式約束。因為很顯然我們可以把等式約束寫成兩個不等式約束，而把類似於g(x)&<=0的不等式約束寫成max(g(x),0)=0這樣的等式約束，所以等式約束問題和不等式約束問題在形式上總可以互相等價轉換。

正是這樣的等價轉換使得二者形式高度相關。懲罰函數是一個約束違背的度量(measure of constraint violation),使得當約束滿足時取零，約束違背時取非零。作為一種度量，我們通常要求它非負和單調遞增。舉個例子，只需要考慮最簡單的一維約束y&<=0,有很多常用的懲罰函數，比如G(y)=0 if y&<=0, infinity else，和 G(y)= max(y,0)^p。簡單起見，考慮如下只有一個約束的優化問題: min{F(x): g(x)&<=0}。應用上述函數可以得到如下等價變換min{F(x): G[g(x)]=0}。對於這個等價問題，我們寫出懲罰函數形式L(x,r)=F(x)+rG[g(x)]，然而這正是拉格朗日函數，所以說懲罰函數法與拉式乘子法形式緊密相關。當然如果拉式乘子法用於原問題，得到的是L(x,r)=F(x)+rg(x)，這個時候效果就不一樣了，如果我們放鬆對懲罰函數非負的要求，形式上拉式乘子法就可以解釋為linear penalty method。

個人認為，區分懲罰函數法與拉式乘子法不是上述形式，而是二者對於參數r的意義的理解以及由此導致的求解思路不同。在懲罰函數里，r是作為一個固定的參數來對待的，求解L(x,r)時一直保持不變(當然實際中為了提高求解效率，會使用path-following或SUMT，目的還是求解最終那個懲罰常數對應的問題)。對於懲罰函數法，大多數的理論結果類似於，當r趨於無窮時，L(x,r)的解趨於原問題的解。而在拉式乘子法中，r是作為對偶變數出現的，求解過程中是要不斷更新的，而且更多的是會考慮Lagrange Duality。Duality Theory是拉式乘子法的最核心的理論支撐。即便是比較path-following懲罰法和乘子法，關於參數r的更新方法也是不同的，懲罰法中r通常是自適應地按照固定倍率不斷增大，因而對於所有的問題案例，r序列都是相同且給定的，而在乘子法中r是一步梯度更新，更新過程中r可能增大也可能減小，對於不同的問題案例，更新得到的r序列是不同的。

為了更進一步說明二者之間的聯繫和差異，我們考慮凸優化問題，假設F(x)和g(x)都是光滑的凸函數，並且存在x0滿足Slater condition即g(x0) &< 0。考慮攝動問題V(u)=min{F(x): g(x)&<=u}，這個問題至關重要。首先，Lagrange Duality可以根據函數V(u)的性質來構建，具體結論是，對於凸優化問題，如果V(u)在u=0處下半連續，那麼strong duality 成立。此時，拉式乘子法可以正常使用。其次，有意思的是，對於懲罰函數法有如下exact penalty theory : 當r &> sup{ [V(0)-V(u)]/u : u&>0 }時，f(x)=F(x)+rG[g(x)]的解一定是V(0)的解，這裡G(y)= max(y,0)。第三，比較無約束凸優化問題min f(x)的最優性條件與約束問題min{F(x): g(x)&<=0}的KKT條件，可以進一步發現兩個方法內在的相通性: 乘子法是尋找變數x和r使得F"(x)+rg"(x)=0，而懲罰法是尋找變數x使得F"(x)+h(x)=0，這裡h(x)是非光滑凸函數rG[g(x)]的一個次梯度subgradient。

總結來看，懲罰法是pure primal method, 乘子法是primal-dual method。從發展歷史來看，懲罰法是上個世紀60年代的成果和主流方法，很快在70年代就被兩者的結合體ALM: Augmented Lagrangian methods 取代了，並進一步演化出了ADMM: Alternating direction method of multipliers。在凸優化問題中，這些演進有時候並不僅僅是既有思路的簡單結合，甚至會有更深刻的理論結果。比如，通常大家會把ADMM當作是Augmented Lagrangian問題的alternating optimization求解方法而已，然而，可以構造出一些特殊問題使得標準的ALM會發散，而ADMM依然可以求得最優解。所以，形式相似雖然很有啟發意義，更重要的是研究弄清背後的機理和理論基礎。

萌新回答一下這個問題，求指導。

我認為這是兩個層面的問題。考慮Lasso，

$egin{equation}label{key} min f(x)+eta|Ax|_1 end{equation}$

寫成標準形式就是

$egin{equation}label{key} min f(x)+eta|y|_1+lambda(Ax-y)+frac{ ho}{2}|Ax-y|^2_2 end{equation}$

lambda=0 是 penalty method， rho=0 是 Lagrange Multiplier method。

當然也可以同時不為0，那就是ALM/ADMM.

在Lipschitz 假設下，

$egin{equation}label{key} f(x)=f(x_0)+ abla f(x_0)(x-x_0)+frac{L}{2}|x-x_0|^2_2 end{equation}$

代入式子，相當於優化

$egin{equation}label{key} min abla f(x_0)(x-x_0)+frac{L}{2}|x-x_0|^2_2+lambda(Ax-y)+frac{ ho}{2}|Ax-y|^2_2 end{equation}$

，這個時候我們既可以直接針對每一步更新寫出閉式解（在實際應用中不會有人使用這種方法，因為求逆的代價太大。）

$egin{equation}label{key} x^+ =( ho A^TA+L)^{-1}(Lx- abla f+ ho A^T y^+-A^Tlambda) end{equation}$

也可以使用數值方法求解這個問題（線性化，注意到那個eta了吧）

$frac{ ho}{2}|Ax-y-frac{lambda}{ ho}|^2_2= ho (Ax-y)+lambda+frac{ hoeta}{2}|x-x_0|^2_2$

$egin{equation}label{key} x^+ = x - frac{1}{L+ hoeta}( abla f + ( ho(Ax-y^+)+lambda)) end{equation}$

看了 @周君豹大佬的答案很有啟發，補充兩句。罰函數法求解的時候，rho 可以不斷增大，最後當rho跑到足夠大的時候就類似障礙函數，變成硬約束了。而乘子法的lambda在這裡是對偶變數，每一步都需要求解更新。當然如果在ADMM當中我們既會讓rho增大，也會維護lambda。

拉格朗日乘子法是用來求最優解的方法，損失函數是你要最優化的東西。拉格朗日乘子法對應於梯度下降法。