拉格朗日函數為什麼要先最大化？

求解帶條件的最優化問題，可使用拉格朗日乘數法轉化為無條件約束優化。對於原函數

$egin{alignat}{3} &min_{x} &f(x) quad \ &s.t. &h_{i}(x)=0 quad &i=1,2,3,...,m \ &&g_{j}(x)leq0 quad &j=1,2,3,...,n \ end{alignat}\ ag{1}$

引入拉格朗日乘子，定義拉格朗日函數：

$L(x, alpha,eta) = f(x)+sum_{i=1}^{m}{alpha_{i}h_{i}(x)}+sum_{j=1}^{n}{eta_{j}g_{j}(x)} ag{2}$

對公式(2)先最大化再最小化，即

$min_{x} left[ max_{alpha,eta;eta_{j}geq0} L(x,alpha,eta) ight] = min_{x} left{ f(x) + max_{alpha,eta;eta_{j}geq0} left[ sum_{i=1}^{m}{alpha_{i}h_{i}(x)}+sum_{j=1}^{n}{eta_{j}g_{j}(x)} ight] ight}\ ag{3}$

在滿足KKT條件的情況下，公式(1)和公式(3)是等價的。

暫且拋開KKT條件的具體細節。很明顯，如果是非零常數，那麼這兩個式子是不可能相等的。現在把這兩組乘子看成自變數，然後調節之使最大化。對於公式(3)，我們將分成兩部分分析：

1. 可行解區域內，此時公式(1)的約束條件都得到滿足。因為 $h_{i}(x)=0$ , 所以不管如何變化，必然有 $alpha_{i}h_{i}(x)=0$ 。 $g_{j}(x)leq0$ ，且限定了 $eta_{j}geq0$ ，則 $eta_{j}g_{j}(x)$ 最大值為0。綜上，在可行解區域內

$max_{alpha,eta;eta_{j}geq0} L(x,alpha,eta) = f(x) + max_{alpha,eta;eta_{j}geq0} left[ sum_{i=1}^{m}{alpha_{i}h_{i}(x)}+sum_{j=1}^{n}{eta_{j}g_{j}(x)} ight] = f(x) ag{4}$

2. 可行解區域外，此時公式(1)的約束條件未滿足。若 $h_{i}(x) e0$ ，則最大化後 $alpha_{i}h_{i}(x) ightarrow+infty$ 。若 $g_{j}(x)>0$ ，則最大化後 $eta_{j}g_{j}(x) ightarrow+infty$ 。所以在可行解區域外

$max_{alpha,eta;eta_{j}geq0} L(x,alpha,eta)=+infty ag{5}$

綜合上面兩個論域，在可行解區域內最小化，等於 $max_{alpha,eta;eta_{j}geq0} L(x,alpha,eta)$ 的最小化，而在可行解區域外， $max_{alpha,eta;eta_{j}geq0} L(x,alpha,eta)$ 無極值。這樣當我們嘗試最小化 $max_{alpha,eta;eta_{j}geq0} L(x,alpha,eta)$ 時也就相當於求解公式(1)了。