梯度步後保持可行
無約束梯度步可能離開可行集。投影梯度法將該步投回集合,並可在適當假設下給出定量目標界。
令 非空、閉且凸。令 凸且可微,其梯度對某個 為 -Lipschitz。假設最小點 存在。
定義 8.1.1
(歐氏投影與投影梯度法)
對 ,投影 是 中在歐氏範數下唯一最接近 的點。對 和固定步長 ,投影梯度法令
閉性和凸性確保最近點存在且唯一;約束是最優化問題的一部分,並非事後補充。
投影與三點估計
投影由一條不等式而非公式刻畫。
引理 8.1.2
(投影的變分不等式)
設 、。則 當且僅當對每個 都有 。
證明
(沿可行線段求導)
設 ,。當 時線段 可行;其到 的距離平方在零點的右導數 不能為負。反過來,若不等式成立,則對每個 ,展開 ,可知 是最近點。
特別地,對可微凸函數 ,可行點 在 上最小,當且僅當對所有 有 。取 ,這正是變分不等式,所以最優性等價於對任意 ,
此條件容許邊界處 。
定理 8.1.3
(一次投影步)
對 、 及每個 ,
證明
(三條不等式與一條極化恆等式)
令 、。光滑性不等式及 給出 。凸性給出 。兩式之和至多為 。把投影不等式用於點 、投影 和可行點 :
最後利用 。最後的平方項與光滑性項抵消。
證明透視
步長條件用在哪裏
證明結合三條不等式,每個假設恰好用一次。光滑性給出 在 的上界模型;凸性透過在 的線性化比較 與 ;投影不等式是集合 唯一出場之處,它之所以適用,是因為比較點 可行。關鍵一步是極化恆等式:它把投影產生的內積化為到 的平方距離之差,再減去額外一項 。這額外一項抵銷光滑性罰項,而罰項不超過 恰好在 時成立; 就用在這裏。若步長更長,右邊會剩下正的餘項 。所得右邊是相鄰距離之差,正因如此下一個證明才能伸縮相消。
有限迭代保證
定理 8.1.4
(目標差距)
對每個整數 ,
證明
(單調性與伸縮相消)
在單步不等式取 得 。取 ,從 加到 ,平方距離相消。由於函數值不增,和中每個目標差距至少為最後的差距;因為 在 上最小,每個差距均非負。除以 即得。
定理限制最後一次迭代的目標差距。它假設最小點達到且投影精確。
常見錯誤
(把收斂率讀成多於目標界的結論)
定理沒有給出到唯一解距離的相同速率、捨入下的停止規則或不精確投影的保證。它計數的亦是迭代次數,而非實際運行時間:投影成本可能主導每次迭代。
例題 8.1.5
(邊界上的最小點)
取 、、、。因 ,步長符合條件。未投影步為 ,故 ;下一個未投影步為 ,投影後仍為 。這是受約束最小點,即使 ,因為能使 下降的方向不可行。
常見錯誤
(以為解處梯度必為零)
邊界上的受約束最小點不一定是 的駐點,上例的 便是如此。正確的判別是不動點條件 ,即對每個可行 有 。以 為停止準則,在這裏永遠不會停止。
在方盒上,投影逐個座標進行,各座標可在不同時間到達邊界。
例題 8.1.6
(投影到方盒)
取 及 ,故 、。用 及 。投影到方盒就是把每個座標截到 。
- ,故 。
- ,故 。
- ,未投影點為 ,故 。
點 是受約束最小點,;該處 ,所以第一個座標由邊界擋住,第二個座標則是無約束駐點。核對定理:,界為 ,而實際差距為 及 。
假設的作用
反例模式
閉的可行集未必包含最小點
在 上, 凸且梯度全局 Lipschitz,因為 ;但其下確界為零,沒有任何有限 達到。故 的閉性及凸性不能推出 存在。另外,非凸集合可能有多個最近點: 時,兩點都是原點的投影。
步長條件是充分條件,並非聲稱所有更大步長都失敗。
例題 8.1.7
(長於 1/L 的步長)
令 、、,則 且 。取 ,迭代為 ,而 不斷增大。取同樣違反 的 ,迭代為 ,收斂到最小點 。定理只是沒有涵蓋這類步長;對此二次函數,收斂恰好在 時成立。
習題
快速檢查
(在邊界例子中求 ,並解釋為何非零導數不違反受約束最優性。)
解答 · 答案
兩者都是 。右端點的可行方向不能指向更大的 ,而目標在該方向下降。
快速檢查
(若 、、,目標差距界是多少?)
解答 · 答案
至多 。
快速檢查
(為何把 的存在列為假設?)
解答 · 答案
光滑凸 softplus 例子在閉集 上有有限下確界,但沒有最小點。
快速檢查
(為何 的凸性對唯一的歐氏投影重要?)
解答 · 答案
加上非空及閉性,凸性給出唯一最近點; 展示沒有凸性時唯一性可能失敗。
延伸閱讀
MIT 開放式課程:投影梯度與鏡像下降 討論投影方法。