動機
處理約束可以直接拒絕不可行點,但這不是唯一方法。罰函數對違反約束收費,容許無約束求解器探索不可行點。二次罰函數的參數愈大,違反的代價愈高,但有限參數仍可能留下非零殘差。非光滑的精確罰函數則可在有限參數下重現受約束解,只要罰係數大於某個最優乘子的大小。
增廣拉格朗日(Lagrange)函數結合乘子和二次罰項。乘子更新並非任意修正:在凸等式約束問題中,它是對偶目標的近端步。本節推導此恆等式,並在子問題精確求解且取得最小值的假設下證明收斂。實際計算常用近似解,但以下證明不會暗中涵蓋未指定的誤差或停止容差。
定義
考慮等式約束問題
p ∗ = inf { f ( x ) : x ∈ R n , A x = b } , p_* = \inf\{f(x):x\in\mathbb R^n,\ Ax=b\}, p ∗ = inf { f ( x ) : x ∈ R n , A x = b } ,
其中 f : R n → R f:\mathbb R^n\to\mathbb R f : R n → R 凸且連續可微,A ∈ R m × n A\in\mathbb R^{m\times n} A ∈ R m × n 。寫 r ( x ) = A x − b r(x)=Ax-b r ( x ) = A x − b ,拉格朗日對偶函數為
q ( λ ) = inf x [ f ( x ) + λ T r ( x ) ] , λ ∈ R m . q(\lambda)=\inf_x[f(x)+\lambda^Tr(x)],\qquad \lambda\in\mathbb R^m. q ( λ ) = x inf [ f ( x ) + λ T r ( x )] , λ ∈ R m .
主要結果均假設存在原問題最小點 x ∗ x_* x ∗ 和對偶最大點 λ ∗ \lambda_* λ ∗ ,它們有共同有限值 p ∗ = q ( λ ∗ ) p_*=q(\lambda_*) p ∗ = q ( λ ∗ ) 。因此對偶間隙為零。弱對偶 q ( λ ) ≤ p ∗ q(\lambda)\le p_* q ( λ ) ≤ p ∗ 一般均成立。這些都是明確假設;單有凸性不能保證取得最優值。
定義 11.1.1
(增廣拉格朗日函數、精確罰函數與乘子法)
對 c > 0 c\gt0 c > 0 及 ρ > 0 \rho\gt0 ρ > 0 ,定義增廣拉格朗日函數及精確罰目標
L c ( x , λ ) = f ( x ) + λ T r ( x ) + c 2 ∥ r ( x ) ∥ 2 2 , P ρ ( x ) = f ( x ) + ρ ∥ r ( x ) ∥ 1 . L_c(x,\lambda)=f(x)+\lambda^Tr(x)+\frac c2\|r(x)\|_2^2,
\qquad P_\rho(x)=f(x)+\rho\|r(x)\|_1. L c ( x , λ ) = f ( x ) + λ T r ( x ) + 2 c ∥ r ( x ) ∥ 2 2 , P ρ ( x ) = f ( x ) + ρ ∥ r ( x ) ∥ 1 . 給定 λ k \lambda_k λ k ,精確乘子法 選取 L c ( ⋅ , λ k ) L_c(\cdot,\lambda_k) L c ( ⋅ , λ k ) 的全局最小點 x k + 1 x_{k+1} x k + 1 ,再令
λ k + 1 = λ k + c r ( x k + 1 ) . \lambda_{k+1}=\lambda_k+c\,r(x_{k+1}). λ k + 1 = λ k + c r ( x k + 1 ) .
寫 r k + 1 : = r ( x k + 1 ) r_{k+1}:=r(x_{k+1}) r k + 1 := r ( x k + 1 ) 。我們假設每個此類子問題均取得最小值,不要求最小點唯一。公式使用所選最小點的殘差及固定 c c c ,不要求 c → ∞ c\to\infty c → ∞ 。次序重要:先用舊乘子最小化,再計算殘差及更新乘子。若顛倒次序或使用不同殘差,便得到不同迭代,必須重新建立下文的駐點恆等式。
定理/命題
在上述原、對偶取得及零間隙假設下,若 ρ > ∥ λ ∗ ∥ ∞ \rho>\|\lambda_*\|_\infty ρ > ∥ λ ∗ ∥ ∞ ,則 P ρ P_\rho P ρ 的每個全局最小點均為原問題可行且最優;每個原問題最小點亦最小化 P ρ P_\rho P ρ 。當兩常數相等時,可能出現不可行的罰函數最小點。
在相同假設下,若每個增廣子問題精確求解並取得最小點,則乘子法滿足 λ k → λ ˉ \lambda_k\to\bar\lambda λ k → λ ˉ ,其中 λ ˉ \bar\lambda λ ˉ 是某個對偶最優點;r ( x k ) → 0 r(x_k)\to0 r ( x k ) → 0 且 f ( x k ) → p ∗ f(x_k)\to p_* f ( x k ) → p ∗ 。原序列的每個聚點均可行且原問題最優。當最小點不唯一時,定理不斷言原序列有界或收斂。
證明思路
絕對值罰項為何可以精確
對偶最優性表示每個 x x x 都滿足 f ( x ) + λ ∗ T r ( x ) ≥ q ( λ ∗ ) = p ∗ f(x)+\lambda_*^Tr(x)\ge q(\lambda_*)=p_* f ( x ) + λ ∗ T r ( x ) ≥ q ( λ ∗ ) = p ∗ 。由 Hölder 不等式,
P ρ ( x ) ≥ p ∗ + ρ ∥ r ( x ) ∥ 1 − λ ∗ T r ( x ) ≥ p ∗ + ( ρ − ∥ λ ∗ ∥ ∞ ) ∥ r ( x ) ∥ 1 . P_\rho(x)\ge p_*+\rho\|r(x)\|_1-\lambda_*^Tr(x)
\ge p_*+(\rho-\|\lambda_*\|_\infty)\|r(x)\|_1. P ρ ( x ) ≥ p ∗ + ρ ∥ r ( x ) ∥ 1 − λ ∗ T r ( x ) ≥ p ∗ + ( ρ − ∥ λ ∗ ∥ ∞ ) ∥ r ( x ) ∥ 1 . 原問題最小點的殘差為零,且 P ρ = p ∗ P_\rho=p_* P ρ = p ∗ 。若係數嚴格為正,每個不可行點的罰值嚴格大於 p ∗ p_* p ∗ ,所以罰函數最小點均可行且最優。已假設的原問題最小點本身也證明罰函數最小點存在。這是關於精確目標的全局結論;罰函數的局部最小點可能需要另行分析,近似的數值最小點亦然。
至於增廣拉格朗日定理,證明先辨認乘子更新,然後只研究乘子。
乘子更新是對偶近端步
在精確子問題最小點,可微性與凸性給出
0 = ∇ f ( x k + 1 ) + A T [ λ k + c r ( x k + 1 ) ] = ∇ f ( x k + 1 ) + A T λ k + 1 . 0=\nabla f(x_{k+1})+A^T[\lambda_k+c r(x_{k+1})]
=\nabla f(x_{k+1})+A^T\lambda_{k+1}. 0 = ∇ f ( x k + 1 ) + A T [ λ k + cr ( x k + 1 )] = ∇ f ( x k + 1 ) + A T λ k + 1 . 所以 x k + 1 x_{k+1} x k + 1 全局最小化乘子 λ k + 1 \lambda_{k+1} λ k + 1 下的普通拉格朗日函數,且 q ( λ k + 1 ) = f ( x k + 1 ) + λ k + 1 T r k + 1 q(\lambda_{k+1})=f(x_{k+1})+\lambda_{k+1}^Tr_{k+1} q ( λ k + 1 ) = f ( x k + 1 ) + λ k + 1 T r k + 1 。對任意 μ \mu μ ,在同一點評估下確界,得超梯度不等式
q ( μ ) ≤ q ( λ k + 1 ) + ( μ − λ k + 1 ) T r k + 1 . q(\mu)\le q(\lambda_{k+1})+(\mu-\lambda_{k+1})^Tr_{k+1}. q ( μ ) ≤ q ( λ k + 1 ) + ( μ − λ k + 1 ) T r k + 1 . 由 r k + 1 = ( λ k + 1 − λ k ) / c r_{k+1}=(\lambda_{k+1}-\lambda_k)/c r k + 1 = ( λ k + 1 − λ k ) / c ,配方可見 λ k + 1 \lambda_{k+1} λ k + 1 唯一最大化
q ( μ ) − 1 2 c ∥ μ − λ k ∥ 2 . q(\mu)-\frac1{2c}\|\mu-\lambda_k\|^2. q ( μ ) − 2 c 1 ∥ μ − λ k ∥ 2 . 具體地,超梯度不等式把任意 μ \mu μ 的值減去 λ k + 1 \lambda_{k+1} λ k + 1 的值,以上界 − ∥ μ − λ k + 1 ∥ 2 / ( 2 c ) -\|\mu-\lambda_{k+1}\|^2/(2c) − ∥ μ − λ k + 1 ∥ 2 / ( 2 c ) 控制。為看清抵消,令 d = μ − λ k + 1 d=\mu-\lambda_{k+1} d = μ − λ k + 1 、v = λ k + 1 − λ k v=\lambda_{k+1}-\lambda_k v = λ k + 1 − λ k 。超梯度項貢獻 d T v / c d^Tv/c d T v / c ,而展開二次罰項貢獻 − [ 2 d T v + ∥ d ∥ 2 ] / ( 2 c ) -[2d^Tv+\|d\|^2]/(2c) − [ 2 d T v + ∥ d ∥ 2 ] / ( 2 c ) ,交叉項相消。這直接證明近端解釋;即使原子問題有多個最小點,下一個乘子仍唯一。
Fejér 不等式及收斂
在超梯度不等式取 μ = λ ∗ \mu=\lambda_* μ = λ ∗ ,並使用 q ( λ ∗ ) = p ∗ q(\lambda_*)=p_* q ( λ ∗ ) = p ∗ 。展開距離平方得
∥ λ k − λ ∗ ∥ 2 − ∥ λ k + 1 − λ ∗ ∥ 2 ≥ ∥ λ k + 1 − λ k ∥ 2 + 2 c [ p ∗ − q ( λ k + 1 ) ] . \|\lambda_k-\lambda_*\|^2-\|\lambda_{k+1}-\lambda_*\|^2
\ge\|\lambda_{k+1}-\lambda_k\|^2
+2c[p_*-q(\lambda_{k+1})]. ∥ λ k − λ ∗ ∥ 2 − ∥ λ k + 1 − λ ∗ ∥ 2 ≥ ∥ λ k + 1 − λ k ∥ 2 + 2 c [ p ∗ − q ( λ k + 1 )] . 由弱對偶,右邊兩項非負。求和顯示乘子序列有界、乘子增量的平方和有限,而且非負對偶間隙之和有限。因此 λ k + 1 − λ k → 0 \lambda_{k+1}-\lambda_k\to0 λ k + 1 − λ k → 0 ,從而 r k + 1 → 0 r_{k+1}\to0 r k + 1 → 0 ,並有 q ( λ k + 1 ) → p ∗ q(\lambda_{k+1})\to p_* q ( λ k + 1 ) → p ∗ 。
有限維有界序列存在收斂子列。對偶函數是連續仿射函數對 λ \lambda λ 取下確界,故上半連續。子列極限因而對偶最優:其值至少是極限上確界 p ∗ p_* p ∗ ,而弱對偶又給出至多 p ∗ p_* p ∗ 。對這個極限重用距離不等式,距離不遞增,而某子列距離趨零,所以整列都收斂至該對偶最優點。
最後,f ( x k + 1 ) = q ( λ k + 1 ) − λ k + 1 T r k + 1 → p ∗ f(x_{k+1})=q(\lambda_{k+1})-\lambda_{k+1}^Tr_{k+1}\to p_* f ( x k + 1 ) = q ( λ k + 1 ) − λ k + 1 T r k + 1 → p ∗ ,因為乘子有界而殘差趨零。若原變量有收斂子列,由 r r r 及 f f f 的連續性,其極限可行且值為 p ∗ p_* p ∗ 。此證明不保證原變量存在聚點;沒有有界或強制性假設時可能沒有聚點。
證明透視
一個恆等式,之後只看乘子 證明的關鍵是一個恆等式。內層問題在舊乘子 λ k \lambda_k λ k 處的精確駐點條件,被改寫為普通拉格朗日函數在新乘子 λ k + 1 \lambda_{k+1} λ k + 1 處的駐點條件;精確性及「先最小化、後更新」的次序正是在這裏用到。凸性只用一次:把該駐點提升為全局最小點,從而得到以 r k + 1 r_{k+1} r k + 1 為超梯度的超梯度不等式。更新規則把 r k + 1 r_{k+1} r k + 1 轉成增量 ( λ k + 1 − λ k ) / c (\lambda_{k+1}-\lambda_k)/c ( λ k + 1 − λ k ) / c ,代入 λ ∗ \lambda_* λ ∗ 便得 Fejér 單調性;零間隙假設 q ( λ ∗ ) = p ∗ q(\lambda_*)=p_* q ( λ ∗ ) = p ∗ 令間隙項非負。此後論證只涉及乘子:有界性、增量可求和因而殘差趨零,以及以緊緻性和上半連續性辨認極限。原變量的資訊只在最後經 f ( x k + 1 ) = q ( λ k + 1 ) − λ k + 1 T r k + 1 f(x_{k+1})=q(\lambda_{k+1})-\lambda_{k+1}^Tr_{k+1} f ( x k + 1 ) = q ( λ k + 1 ) − λ k + 1 T r k + 1 回來。沒有任何一步界住原變量,所以定理不斷言它們收斂。
近似解會改變甚麼
精確駐點方程是通往超梯度與近端恆等式的橋樑。若子問題只做到固定目標容差,未必滿足該方程,證明不能直接略去誤差。可在指定可求和誤差及合適殘差條件下分析近似近端步,但正確條件依賴誤差如何量度。本節只證精確方法,不斷言固定或未指定的內層容差也收斂。
乘子如何改變二次罰法
概念視角 結構
乘子的作用 由 q q q 的定義及零間隙假設 q ( λ ∗ ) = p ∗ q(\lambda_*)=p_* q ( λ ∗ ) = p ∗ ,每個 x x x 均滿足以下增廣目標不等式:
L c ( x , λ ∗ ) ≥ p ∗ + c 2 ∥ r ( x ) ∥ 2 . L_c(x,\lambda_*)\ge p_*+\frac c2\|r(x)\|^2. L c ( x , λ ∗ ) ≥ p ∗ + 2 c ∥ r ( x ) ∥ 2 . 原問題最優點取等號。因此即使固定有限 c > 0 c>0 c > 0 ,L c ( ⋅ , λ ∗ ) L_c(\cdot,\lambda_*) L c ( ⋅ , λ ∗ ) 的每個最小點都可行且原問題最優。此結論假設已知道正確乘子;迭代的目的則是在不知道它時趨近對偶最優點,上面的證明明確說明沿途可得到甚麼結論。
純量例子令分別更清楚。乘子為零時,內層解是不可行的純罰點 1 / ( 1 + c ) 1/(1+c) 1/ ( 1 + c ) ;乘子為一時,相同固定 c c c 的子問題在零最小化。改變來自線性乘子項抵消了目標函數違反等式的一階動機,而不是有限二次項本身突然變得精確。
增大罰係數與數值條件數
增大 c c c 可減少純罰法的違反量,但也可能令內層最小化在不同方向的曲率差距加大。考慮 f ( x 1 , x 2 ) = 1 2 ( x 1 2 + x 2 2 ) f(x_1,x_2)=\tfrac12(x_1^2+x_2^2) f ( x 1 , x 2 ) = 2 1 ( x 1 2 + x 2 2 ) ,約束 x 1 = 1 x_1=1 x 1 = 1 。其二次罰函數 Hessian 為 diag ( 1 + c , 1 ) \operatorname{diag}(1+c,1) diag ( 1 + c , 1 ) ,譜條件數為 1 + c 1+c 1 + c 。對條件數敏感的求解器在 c c c 增大時可能需要更多工作。乘子法提供另一取捨:可固定 c c c 並更新線性項,但仍需按所用收斂定理的要求求解每個子問題。
約束縮放會改變數值參數。以可逆 D D D 把 A x − b = 0 Ax-b=0 A x − b = 0 換成 D ( A x − b ) = 0 D(Ax-b)=0 D ( A x − b ) = 0 ,可行集不變,但歐氏二次罰項變成 ∥ D ( A x − b ) ∥ 2 \|D(Ax-b)\|^2 ∥ D ( A x − b ) ∥ 2 ,對不同殘差方向賦予不同權重。乘子亦相應轉換:若 λ ~ \widetilde\lambda λ 乘縮放後殘差,原乘子為 D T λ ~ D^T\widetilde\lambda D T λ 。因此應連同約束的正規化方式解讀罰閾值與條件數。
可計算的檢查及其限制
更新式給出 ∥ r ( x k + 1 ) ∥ = ∥ λ k + 1 − λ k ∥ / c \|r(x_{k+1})\|=\|\lambda_{k+1}-\lambda_k\|/c ∥ r ( x k + 1 ) ∥ = ∥ λ k + 1 − λ k ∥/ c ,所以乘子改變直接量度等式違反。單有小殘差卻不能證明近似最優:可行點的目標值可以任意大。精確內層駐點方程提供第二個檢查:∇ f ( x k + 1 ) + A T λ k + 1 = 0 \nabla f(x_{k+1})+A^T\lambda_{k+1}=0 ∇ f ( x k + 1 ) + A T λ k + 1 = 0 。在定理假設下,這些性質伴隨目標值收斂;對近似實作,兩類誤差的大小及累積效果仍需另行分析。
距離不等式提供的定量資訊
Fejér 不等式亦給出有限迭代界。令 D = ∥ λ 0 − λ ∗ ∥ D=\|\lambda_0-\lambda_*\| D = ∥ λ 0 − λ ∗ ∥ ,把前 T T T 個不等式相加並丟掉最後的非負距離平方,得到
∑ k = 0 T − 1 ∥ λ k + 1 − λ k ∥ 2 ≤ D 2 , ∑ k = 0 T − 1 [ p ∗ − q ( λ k + 1 ) ] ≤ D 2 2 c . \sum_{k=0}^{T-1}\|\lambda_{k+1}-\lambda_k\|^2\le D^2,
\qquad
\sum_{k=0}^{T-1}[p_*-q(\lambda_{k+1})]\le\frac{D^2}{2c}. k = 0 ∑ T − 1 ∥ λ k + 1 − λ k ∥ 2 ≤ D 2 , k = 0 ∑ T − 1 [ p ∗ − q ( λ k + 1 )] ≤ 2 c D 2 .
所以前 T T T 個殘差中至少有一個的範數平方不超過 D 2 / ( c 2 T ) D^2/(c^2T) D 2 / ( c 2 T ) ,也至少有一個對偶間隙不超過 D 2 / ( 2 c T ) D^2/(2cT) D 2 / ( 2 c T ) ;兩者未必出現在同一步。這些計算建立各列表的最佳迭代界,並未建立最後迭代的速率。定理中較強的極限結論依上文的可求和性和有限維緊緻性得到。
近端推導亦解釋為何下一個乘子不依賴所選的精確原最小點:每個選擇給出的候選乘子都滿足相同的近端目標全局二次上界。兩個不同候選都必須是其唯一最大點,矛盾。原變量卻仍可沿零空間方向不同,下面關於精確子問題極小點的練習展示了這一點。
例題詳解
在 x = 0 x=0 x = 0 下最小化 f ( x ) = − x f(x)=-x f ( x ) = − x 。唯一原可行點的值為零,λ ∗ = 1 \lambda_*=1 λ ∗ = 1 時 q ( λ ∗ ) = 0 q(\lambda_*)=0 q ( λ ∗ ) = 0 ,其他乘子時為 − ∞ -\infty − ∞ 。若 ρ > 1 \rho>1 ρ > 1 ,− x + ρ ∣ x ∣ -x+\rho|x| − x + ρ ∣ x ∣ 在每個非零點均為正,唯一最小點是零。若 ρ = 1 \rho=1 ρ = 1 ,每個 x ≥ 0 x\ge0 x ≥ 0 的目標值都是零,故有不可行最小點。定理中的嚴格不等式不可省。
在 x = 0 x=0 x = 0 下最小化 f ( x ) = 1 2 ( x − 1 ) 2 f(x)=\tfrac12(x-1)^2 f ( x ) = 2 1 ( x − 1 ) 2 。二次罰函數 1 2 ( x − 1 ) 2 + c 2 x 2 \tfrac12(x-1)^2+\tfrac c2x^2 2 1 ( x − 1 ) 2 + 2 c x 2 的最小點為 x = 1 / ( 1 + c ) x=1/(1+c) x = 1/ ( 1 + c ) ,對每個有限 c > 0 c>0 c > 0 均非零。增大 c c c 會縮小違反量,卻不會在有限參數下達到精確可行;原問題乘子為 λ ∗ = 1 \lambda_*=1 λ ∗ = 1 。
對相同的 f f f 及 x = 0 x=0 x = 0 ,最小化 L c ( x , λ k ) L_c(x,\lambda_k) L c ( x , λ k ) 得 x k + 1 = ( 1 − λ k ) / ( 1 + c ) x_{k+1}=(1-\lambda_k)/(1+c) x k + 1 = ( 1 − λ k ) / ( 1 + c ) 、λ k + 1 = ( λ k + c ) / ( 1 + c ) \lambda_{k+1}=(\lambda_k+c)/(1+c) λ k + 1 = ( λ k + c ) / ( 1 + c ) 。所以 λ k + 1 − 1 = ( λ k − 1 ) / ( 1 + c ) \lambda_{k+1}-1=(\lambda_k-1)/(1+c) λ k + 1 − 1 = ( λ k − 1 ) / ( 1 + c ) 。對每個 c > 0 c>0 c > 0 ,乘子幾何地收斂至一,殘差趨零。與純二次罰法不同,固定 c c c 的乘子迭代可趨向精確可行。
常見錯誤
最優乘子給出罰係數的充分閾值;任意乘子不能套用相同證明,而閾值取等號時可能有不可行最小點,第一個例題已說明這點。
反例模式
由乘子估計定出的罰閾值 聲稱:乘子法一旦給出估計 λ k \lambda_k λ k ,任何 ρ > ∥ λ k ∥ ∞ \rho\gt\|\lambda_k\|_\infty ρ > ∥ λ k ∥ ∞ 都令 ℓ 1 \ell_1 ℓ 1 罰函數精確。取純量問題 f ( x ) = 1 2 ( x − 1 ) 2 f(x)=\tfrac12(x-1)^2 f ( x ) = 2 1 ( x − 1 ) 2 、x = 0 x=0 x = 0 ,並取 c = 2 c=2 c = 2 、λ 0 = 0 \lambda_0=0 λ 0 = 0 ,於是 λ 1 = 2 / 3 \lambda_1=2/3 λ 1 = 2/3 ;再取 ρ = 0.8 > λ 1 \rho=0.8\gt\lambda_1 ρ = 0.8 > λ 1 。對 x > 0 x\gt0 x > 0 ,罰函數 P ρ ( x ) = 1 2 ( x − 1 ) 2 + 0.8 ∣ x ∣ P_\rho(x)=\tfrac12(x-1)^2+0.8|x| P ρ ( x ) = 2 1 ( x − 1 ) 2 + 0.8∣ x ∣ 的導數為 x − 0.2 x-0.2 x − 0.2 ,在 x = 0.2 x=0.2 x = 0.2 為零,此處 P ρ = 0.32 + 0.16 = 0.48 < 0.5 = P ρ ( 0 ) P_\rho=0.32+0.16=0.48\lt0.5=P_\rho(0) P ρ = 0.32 + 0.16 = 0.48 < 0.5 = P ρ ( 0 ) 。所以罰函數最小點不可行。修正後的敍述使用最優乘子:此處 λ ∗ = 1 \lambda_*=1 λ ∗ = 1 ;當 ρ > 1 \rho\gt1 ρ > 1 ,在 x > 0 x\gt0 x > 0 上斜率 x − 1 + ρ > 0 x-1+\rho\gt0 x − 1 + ρ > 0 ,在 x < 0 x\lt0 x < 0 上斜率 x − 1 − ρ < 0 x-1-\rho\lt0 x − 1 − ρ < 0 ,故零是唯一最小點。
另外兩個錯誤關乎收斂定理,而非罰函數。
所述更新要求增廣子問題取得最小值,收斂證明使用精確最小化,而非單單「殘差夠小」。可行點的目標值可以任意大;把殘差與最優性連起來的是第二個檢查 ∇ f ( x k + 1 ) + A T λ k + 1 = 0 \nabla f(x_{k+1})+A^T\lambda_{k+1}=0 ∇ f ( x k + 1 ) + A T λ k + 1 = 0 。
對偶收斂及可行性本身不保證不唯一或無界的原序列收斂。若 A A A 有非平凡零空間,而 f f f 在其上不變,精確內層最小點便可沿它漂移,下面關於精確子問題極小點的練習正展示這點。
總結
弱對偶把最優乘子轉成精確 ℓ 1 \ell_1 ℓ 1 罰函數界;單獨二次罰項一般不精確。在凸等式情況,精確增廣拉格朗日最小化產生對偶近端步;距離不等式給出乘子收斂、可行性和目標值收斂。假設包括原與對偶取得、零間隙、以及內層精確且取得最小值。
練習
快速檢查
(對 f ( x ) = − x f(x)=-x f ( x ) = − x 及約束 x = 0 x=0 x = 0 ,分別描述 ρ = 1 \rho=1 ρ = 1 和 ρ > 1 \rho\gt1 ρ > 1 時 P ρ P_\rho P ρ 的所有最小點。)
比較 − x + ρ ∣ x ∣ -x+\rho|x| − x + ρ ∣ x ∣ 在零兩側的斜率。
解答 · 答案 ρ = 1 \rho=1 ρ = 1 時,− x + ∣ x ∣ -x+|x| − x + ∣ x ∣ 在 [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) 為零,在 x < 0 x\lt0 x < 0 為正,所以所有 x ≥ 0 x\ge0 x ≥ 0 均最小。ρ > 1 \rho\gt1 ρ > 1 時,離開零的兩側目標值均為正,故零是唯一最小點。
快速檢查
(對 f ( x ) = 1 2 ( x − 1 ) 2 f(x)=\tfrac12(x-1)^2 f ( x ) = 2 1 ( x − 1 ) 2 、x = 0 x=0 x = 0 、c = 2 c=2 c = 2 ,由 λ 0 = 0 \lambda_0=0 λ 0 = 0 出發,求 x 1 , λ 1 , x 2 , λ 2 x_1,\lambda_1,x_2,\lambda_2 x 1 , λ 1 , x 2 , λ 2 。)
解答 · 答案 由遞推得 x 1 = 1 / 3 x_1=1/3 x 1 = 1/3 、λ 1 = 2 / 3 \lambda_1=2/3 λ 1 = 2/3 、x 2 = 1 / 9 x_2=1/9 x 2 = 1/9 、λ 2 = 8 / 9 \lambda_2=8/9 λ 2 = 8/9 。每次先用目前乘子作內層最小化,再加上 2 x k + 1 2x_{k+1} 2 x k + 1 更新乘子。
快速檢查
(為何在此算法中,∥ λ k + 1 − λ k ∥ 2 \|\lambda_{k+1}-\lambda_k\|^2 ∥ λ k + 1 − λ k ∥ 2 可求和可推出可行性,卻未必推出原變量收斂?)
解答 更新式給 r ( x k + 1 ) = ( λ k + 1 − λ k ) / c r(x_{k+1})=(\lambda_{k+1}-\lambda_k)/c r ( x k + 1 ) = ( λ k + 1 − λ k ) / c ,故增量趨零令殘差趨零。但它只控制 A x − b Ax-b A x − b ,不控制 A A A 的零空間中的移動;不唯一的內層最小點可沿該空間移動。
快速檢查
(設 f ( x 1 , x 2 ) = 1 2 x 1 2 f(x_1,x_2)=\tfrac12x_1^2 f ( x 1 , x 2 ) = 2 1 x 1 2 ,約束 x 1 = 0 x_1=0 x 1 = 0 。解釋為何即使殘差及目標值收斂,仍可選取無界的精確子問題最小點序列。)
解答 增廣目標只依賴 x 1 x_1 x 1 ,故可選任何最小化的第一座標,並令 x 2 , k = k x_{2,k}=k x 2 , k = k 。若 λ 0 = 0 \lambda_0=0 λ 0 = 0 ,精確最小化的第一座標、所有殘差及目標值均為零,但原序列無界。