不等式為何需要不同的罰項
等式殘差應趨近零;不等式殘差則只需變成非正:嚴格負值代表容許的鬆弛量。把整個殘差平方,會把鬆弛也當成錯誤,因而可能改變最優化問題。在 gi(x)≤0 的慣例下,不等式乘子也必須保持非負。若照抄等式更新而不維持符號限制,便可能破壞對偶問題作為下界的意義。
正部增廣拉格朗日(Lagrange)函數尊重這兩個區別。其乘子更新是到非負正交象限的 Euclidean 投影。我們會推導公式,證明精確最小化實現了受約束對偶問題上的近端步,並在有限維、光滑凸模型中建立收斂。定理包括取到及約束規範假設,並非對任意非凸問題或近似內層求解法的斷言。
模型與基本假設
考慮
p∗=min{f(x):x∈Rn, gi(x)≤0, i=1,…,m},q(z)=xinf{f(x)+zTg(x)},z∈R+m.
假設 f,g1,…,gm 都是 Rn 上有限值、連續可微的凸函數;有限的原問題最小值取到;且存在嚴格可行點 xs,使所有 gi(xs)<0。分離、次梯度與強對偶單元中已證的 Slater 定理於是提供至少一個取到的對偶最大點 z∗,滿足 q(z∗)=p∗。等價地,下述收斂證明也可直接從原問題與對偶問題均取到且零間隙開始;嚴格可行性只是保證這些事實的一條充分途徑。它不被用來斷言內層最小點存在。
固定 c>0,取 λ0≥0,並額外假設下文每個實際使用的內層問題都取到最小值。例如,若 f 具強制性,這便自動成立:增廣目標不小於 f(x)−∥λk∥2/(2c),且連續,所以其次水平集有界,最小值亦取到。只有在討論原問題點的聚點及到解集的距離時,才會另外假設所選原問題最小點形成有界序列。
定義 11.2.1
(正部增廣拉格朗日函數與精確外層迭代)
對向量 v,以 [v]+ 表示逐分量的 max(vi,0)。對 c>0 及 λ≥0,定義
Φc(u,λ)=2c∥[λ+cu]+∥2−∥λ∥2,Lc(x,λ)=f(x)+Φc(g(x),λ).一次精確外層迭代任選
xk+1∈xargminLc(x,λk),λk+1=[λk+cg(xk+1)]+.
定理不要求固定參數 c 增至無窮。但每次迭代仍須有精確而且取到的最小點;計算方便不能替代這個假設。
從最大化推導正部公式
固定 u,λ,對 z 配方:
zTu−2c1∥z−λ∥2=−2c1∥z−(λ+cu)∥2+λTu+2c∥u∥2.
在 z≥0 上,唯一最大點是 z=[λ+cu]+,即 λ+cu 到非負正交象限的投影。逐座標代入可得
Φc(u,λ)=z≥0max{zTu−2c1∥z−λ∥2}.
確切而言,若 λi+cui>0,該座標的貢獻是 λiui+cui2/2;否則最大值是 −λi2/(2c)。兩個值及其一階導數在 λi+cui=0 處吻合。因此 Φc 對 u 連續可微,梯度為 [λ+cu]+;它亦為凸函數,且對 u 的每個座標非遞減。另一種看法是,上述最大化把 Lc(⋅,λ) 寫成凸函數 f+zTg 減去常數後的逐點上確界。因此 Lc 為凸,其梯度是
∇xLc(x,λ)=∇f(x)+i=1∑m[λi+cgi(x)]+∇gi(x).
在精確內層最小點,此梯度為零。以投影更新定義 z=λ+,便令 x 成為普通凸拉格朗日函數 f+zTg 的駐點,所以它也是該函數的全局最小點。特別是
q(z)=f(x)+zTg(x)>−∞.
這是由原問題最小化通往對偶函數的橋樑。只計算投影而沒有最小化內層目標,並不能建立這個等式。
概念視角結構
投影就是符號約束的最優性條件
對 z=[λ+cg(x)]+ 和任何 w≥0,Euclidean 投影給出
(λ+cg(x)−z)T(w−z)≤0,g(x)T(w−z)≤c1(z−λ)T(w−z).這個不等式取代了精確罰函數與增廣拉格朗日單元中等式約束方法的殘差恆等式。若 zi>0,更新滿足 zi−λi=cgi(x)。若 zi=0,約束可以嚴格鬆弛,上述等式未必成立。但投影不等式在兩種情況都有效,並提供收斂證明所需的符號。
精確的近端對偶恆等式
定理 11.2.2
(精確內層求解給出唯一近端對偶步)
在上述凸且可微的假設下,設 x 最小化 Lc(⋅,λ),其中 c>0、λ≥0。則 z=[λ+cg(x)]+ 是
q(w)−2c1∥w−λ∥2在 w≥0 上的唯一最大點。因此,所有精確原問題最小點的選擇,都產生同一個下一乘子,即使其原問題座標可以不同。
對任何 w≥0,q 的定義及精確駐點條件給出
q(w)≤f(x)+wTg(x)=q(z)+g(x)T(w−z)≤q(z)+c1(z−λ)T(w−z).減去 ∥w−λ∥2/(2c) 並展開平方,得到更強的上界
q(w)−2c∥w−λ∥2≤q(z)−2c∥z−λ∥2−2c∥w−z∥2.所以 z 最大化近端式,其他點除非等於 z,否則值必嚴格較小。若 q(w)=−∞,不等式直接成立。這裏沒有未經證明地交換下確界與最大值;證明是構造一對原問題點與對偶點,然後直接驗證其全局不等式。
精確收斂及適用範圍
定理 11.2.3
(固定參數的不等式增廣拉格朗日法收斂)
在基本假設及精確、取到的內層最小化下,λk 收斂至一個對偶最大點,[g(xk+1)]+→0,且 f(xk+1)→p∗。每個 i 亦有 λk+1,igi(xk+1)→0。所選原問題點序列的每個聚點都是原問題最優點。若此序列有界,便有聚點,且它到原問題解集的距離趨近零。若解集只有一點,則有界的原問題點序列收斂至該點。
證明分兩部分:先處理乘子,再由乘子讀出原問題的結論。
對偶迭代點的距離不等式
令 z=λk+1、λ=λk、d=z−λ。在配方前的不等式取 w=z∗,並用 q(z∗)=p∗,便得
c[p∗−q(z)]≤dT(z∗−z).平方距離恆等式於是給出
∥z−z∗∥2≤∥λ−z∗∥2−∥d∥2−2c[p∗−q(z)].增量的範數平方非負,對偶間隙則由弱對偶保證非負。到任何對偶最優點的距離非遞增,故乘子有界。從 k=0 至 T−1 求和,得到
k=0∑T−1∥λk+1−λk∥2≤∥λ0−z∗∥2,k=0∑T−1[p∗−q(λk+1)]≤2c∥λ0−z∗∥2.因此 d→0,對偶間隙亦趨近零。有限維中,有界乘子序列有收斂子序列。對偶函數是連續仿射函數族的下確界,故上半連續。因此它在該子序列極限的值至少為 p∗;再由弱對偶,該極限為對偶最優點。把這個特定極限取作 z∗,同一距離不等式仍成立。這些距離非遞增,且有子序列趨近零,故整個乘子序列收斂至該極限。
恢復可行性、互補性與目標值
整個向量 g(x) 未必趨近零。相反,若 gi(x)>0,當前非負乘子令 zi=λi+cgi(x)>0,所以
0≤[gi(x)]+≤∣di∣/c.這便證明正部違約量消失。此外,當 zi>0 時,cgi(x)=di;當 zi=0 時,下列兩個乘積均為零。因此每個座標都滿足精確恆等式
zigi(x)=zidi/c.由乘子有界和 d→0,得到逐分量的漸近互補性及 zTg(x)→0。再由 f(x)=q(z)−zTg(x),便得目標收斂。這個證明不需要嘗試控制負的鬆弛量 gi(x) 本身。
若某原問題子序列收斂至 xˉ,連續性給出 g(xˉ)≤0 和 f(xˉ)=p∗。在有界假設下,若到閉解集的距離不趨近零,便有一個子序列與解集保持至少某 ε>0 的距離;但它有進一步子序列收斂至最優點,造成矛盾。唯一性遂迫使原問題點收斂。若沒有有界性,這些緊緻性步驟並不能憑空產生聚點。
證明透視
精確性、符號約束與緊緻性分別用在哪裏
精確內層駐點條件把 q(λk+1) 識別為所選原問題點的拉格朗日值,從而建立近端及距離不等式。符號約束只透過投影不等式進入;它是不等式而非等式約束情形的等式,但方向仍然正確,給出 c[p∗−q(z)]≤dT(z∗−z)。其後對偶部分全靠距離不等式:距離單調令乘子有界,伸縮求和迫使 d→0 及對偶間隙趨近零。所有原問題結論都經由兩個座標恆等式 [gi]+≤∣di∣/c 及 zigi=zidi/c 從 d→0 讀出,所以從不需要控制負的鬆弛量。有限維緊緻性先用於有界乘子,以取得最優極限;只有原問題點也有界時,才另外用於這些點。目標有極限、違約量消失,不能控制沿著不改變兩者的方向任意移動。
透視的最後一句並非技術細節,一個帶平坦方向的例子便可說明。
令 f(x,y)=x2/2、g(x,y)=−1。每處都嚴格可行,原問題解是所有 (0,y)。從 λ0=0 開始。乘子為零時 [λ0+cg]+=0,所以增廣目標是 x2/2,與 y 無關,每個 (0,y) 都是精確內層最小點。第 k 步選 (0,k)。投影乘子保持 [0−c]+=0,目標等於最優值 0,亦沒有違約,但原問題點序列無界,沒有聚點。這符合定理,因為其原問題結論以有界性為條件;它亦說明為何須另外列出這個條件。
算例與失效檢查
最小化 f(x)=(x−1)2/2,受 g(x)=x≤0 約束。解為 x∗=0、p∗=1/2,最優乘子為一。內層駐點條件是 x−1+z=0,而 z=[λ+cx]+。對 λ≥0、c>0,相容分支為
x+=1+c1−λ,λ+=z=1+cλ+c>0.所以 λ+−1=(λ−1)/(1+c)。當 c=2、λ0=0,首兩對是 (x1,λ1)=(1/3,2/3) 及 (x2,λ2)=(1/9,8/9)。早期內層解不可行,但違約量趨近零,目標趨近 1/2。因乘子會變動,有限且固定的 c 已足夠。
最小化 (x+1)2/2,受 x≤0 約束,取 c=1、λ0=3。內層駐點式是 x+1+[λ+x]+=0。首步在正分支給出 x1=−2、λ1=1;因 3−2=1>0,分支相容。第二步給出 x2=−1、λ2=0,恰在分支交界。其後保持 (x,λ)=(−1,0)。殘差 g(x)=−1 保持嚴格為負,正是應有情況:最優點的約束不活躍。由於其乘子為零,互補性成立。
反例模式
把鬆弛平方會解成另一個問題
在不活躍約束的例子中,若於 λ=0、c=1 改用等式形式的二次罰函數,便在 x=−1/2 最小化 (x+1)2/2+x2/2,而非得到原問題最優點 −1。若還採用無符號限制的等式乘子更新,便有 x+=−(1+λ)/2、λ+=(λ−1)/2。從零開始會得到 λk→−1,是不合法的不等式乘子;同時 xk→0,是目標值為 1/2 的等式約束解。原不等式最優值卻為零。正部公式及投影同時修復這兩個錯誤。
不能直接刪掉嚴格可行性,卻仍保留定理中對偶取到的前提。考慮最小化 x,受 x2≤0 約束。原問題值零取到,但當 z>0,q(z)=xinf(x+zx2)=−1/(4z),而 q(0)=−∞。對偶上確界為零,卻不在任何有限乘子取到。距離論證沒有可作基準的 z∗。這是其假設不成立,而非與定理矛盾。
誠實的內層停止準則
對建議的內層點 x,計算 z=[λ+cg(x)]+。可計算的駐點殘差是
e=∇f(x)+i∑zi∇gi(x)=∇xLc(x,λ).
精確證明使用了 e=0。兩個誘人的停止規則都不能提供它。
單靠原問題違約量及乘子變化不能推出 e=0。在不活躍約束純量例子中,取 λ=0,反覆選 x=0,便永遠有零違約量及零乘子變化,但目標為 1/2 而非零,且 e=1。
即使固定的小正梯度容許值,也不保證漸近精確最優化。對任何 0<ε<1,反覆選 x=−1+ε/2 且 λ=0。該點嚴格可行,投影後的下一乘子為零;內層梯度為 ε/2,低於容許值 ε。但固定目標差仍為 ε2/8>0。由這個停止規則宣稱精確收斂是錯的。
若有額外資訊,可得到有效的內層誤差證書。若已知 Lc(⋅,λ) 是 μ-強凸,μ>0,其精確最小點為 xc,則支撐二次不等式給出
Lc(x,λ)−Lc(xc,λ)≤2μ∥e∥2.
證法是以下式從下方界住 Lc(y,λ):Lc(x,λ)+eT(y−x)+μ∥y−x∥2/2,再對 y 最小化右邊。這是內層目標誤差證書,並不證明有任意誤差的外層方法收斂。完整的非精確定理必須指定誤差怎樣下降或累積,以及它怎樣擾動對偶不等式;這不在此處所證精確方法的範圍內。
練習
快速檢查
(對 c=2、λ=(1,3)T、u=(−1,1)T,直接及利用最大化公式計算 z=[λ+cu]+ 和 Φc(u,λ)。)
解答
λ+cu=(−1,5)T,所以 z=(0,5)T。正部公式給出 (25−10)/4=15/4。最大化式中,zTu=5,且 ∥z−λ∥2=(0−1)2+(5−3)2=5,故值為 5−5/4=15/4;逐座標投影證明這就是最大值。
快速檢查
(在活躍約束純量例子,取 c=1、λ0=2。求 x1,λ1,x2,λ2,並檢查可行內層點也可以有正乘子。)
解答
x1=−1/2、λ1=3/2,再有 x2=−1/4、λ2=5/4。兩個原問題點都嚴格滿足不等式,乘子卻為正。互補鬆弛性是極限最優點的條件,不是每個中途內層解都要滿足的要求。實際上,λ1x1=−3/4=λ1(λ1−λ0)/c。
快速檢查
(若 D=∥λ0−z∗∥,利用距離不等式界住首 T 個原問題點中最小的正部違約量平方。這是否末次迭代速率?)
把增量平方和與 [gi]+≤∣di∣/c 結合。
解答
可求和性給出 k=0∑T−1∥λk+1−λk∥2≤D2。由 ∥[g(xk+1)]+∥2≤∥λk+1−λk∥2/c2,最小的違約量平方至多 D2/(c2T)。這是最佳迭代上界。證明已建立整個違約量序列收斂,但這個平均論證不建立 1/T 的末次迭代上界。
快速檢查
(若一個 2-強凸的內層目標,其梯度殘差範數至多 0.01,可得甚麼目標誤差上界?固定這個上界是否證明外層精確收斂?)
解答
差至多 0.012/(2⋅2)=0.000025。這界住一次內層求解的目標誤差。純量反例表明,反覆使用固定容許值不建立外層精確收斂;非精確外層定理需要明確額外誤差條件。
快速檢查
(在不活躍約束純量例子中取 c=1,由 λ0=1/2 出發。求 x1 及 λ1。)
解答
內層駐點式為 x+1+[21+x]+=0。正分支給出 x=−3/4,但此時 21+x=−1/4<0,分支不相容。零分支給出 x+1=0,故 x1=−1,且確有 21−1<0;因此 λ1=[21−1]+=0。一步精確迭代便到達最優對 (−1,0):只要 λ0−1≤0,零分支便相容,所以在這個不活躍約束上,任何 λ0≤1 的起始乘子都會在一步內被捨去。