支持斜率為甚麼引出另一種算法
梯度描述可微函數唯一的切平面。在折角處,支持平面可能不止一個,每個都給出有效的全局下界。這種選擇很有用:我們可以直接最小化絕對值、仿射損失的最大值,以及這些項的和,毋須先把折角平滑化。不過,收斂論證也要改變。負次梯度未必是下降方向,因此不能直接沿用光滑函數的下降引理。
我們先建立假設可以逐一檢查的運算規則。在運算部分,所有函數都在整個 上取有限值且為凸函數。這個限制排除了定義域邊界的困難;它比一般凸分析定理所需的條件更強。我們會在這個設定下證明和法則,然後展示去掉限制後可能出現的失敗。討論算法時,約束另由非空閉凸集 表示,而目標函數仍在整個空間上取有限值。
幾何方面需要歐氏投影,以及上一篇關於分離與強對偶的筆記所用的有限維分離定理:兩個不相交的非空開凸集可由一個非零線性泛函分離;開凸集與集外一點之間存在非零的弱分離泛函。以下正是使用這兩種分離結果。
次梯度是下界,並非任選的導數
對有限凸函數 ,定義
「對每個 」這個量詞十分重要。只在幾個測試點支撐圖像,並不足以證明某向量是次梯度。集合 是閉凸集,因為對變量 而言,上式的每一個不等式都定義一個閉半空間。
兩個直接推論有助理解定義。首先, 當且僅當 是全局無約束最小點。其次,若 在 可微,則 :把支持不等式用於 ,除以正數 並令 趨於零,再以 重複,便迫使支持斜率等於梯度。凸性則保證梯度本身滿足支持不等式。
有限值情況下為甚麼存在支持斜率
引理 5.2.1
(有限凸函數連續且處處有次梯度)
設 為凸函數。則 連續,而且對每個 , 非空。
證明
(局部上界與支持超平面)
使用開集分離前,需要先知道連續性。以下是一個基本論證。固定 ,取立方體 ,其中 。令 為 在有限個頂點上的最大值。立方體內每一點都是頂點的凸組合,所以整個立方體上都有 ,特別是 。
當 時,令 及 。凸性給出 。對 也有相同上界。再用 ,得到
所以 在每個 連續。這是以固定中心 為準的局部估計,並沒有假設全局 Lipschitz 常數。
現在嚴格上圖集 是開凸集,而 不在其中。分離定理及從 趨近該點的極限,給出非零向量對 ,使
令 向上增加,可知 。若 ,則不等式對每個 成立,迫使 ,矛盾。因此 。令 下降至 ,便得 。排除 的一步,確實用到了函數在整個空間取有限值。
附明確條件的運算規則
定理 5.2.2
(有限凸函數的和法則)
設 都是有限凸函數。對每個 ,
右方為 Minkowski 和 。
若 ,則 。若 ,則
把兩個支持不等式相加,便證明和法則由右至左的包含關係。正比例及仿射項法則則可直接把定義不等式除以正數或減去仿射項,從兩個方向證明。和法則反方向的包含關係需要額外論證;只把不等式相加並不能得到它。
證明
(分離兩個開集以拆分斜率)
取 。對 ,記 及 。考慮
這是兩個非空開凸集。次梯度不等式給出 ,所以它們不相交。兩者的閉包都含 。因此可用非零 把分離不等式寫成
由於兩個閉包都含原點,共同的分離閾值必為零。 含向上的鉛直射線,迫使 。若 ,第一個不等式對所有 成立,因為每個 上方都有 中的點;於是 ,與分離泛函非零矛盾。將係數正規化為 。
分別取極限至兩個圖像邊界,得到
所以 且 。這就證明了缺少的包含關係,從而得到等式。
證明透視
困難的包含關係為何需要分離
把支持不等式相加,只能得到 。反方向的包含要把和的一個支持平面拆成兩部分,而不等式 並沒有說明如何拆分。證明把問題轉成幾何: 位於 圖像上方, 位於 圖像下方,而 的次梯度不等式正好等價於兩者不相交。在整個 上取有限值這個假設用了兩次:它令 與 連續,使兩個集合都是開集,從而可用開集分離;它又保證每個 上方都有 的點,迫使 。取 後,分離斜率 是分給 的部分, 則是分給 的部分。下面的反例顯示,當某個函數只在半直線上有限時,這樣的拆分未必存在。
反覆使用便得到有限多項的和法則。係數為零時應直接處理:常數零函數的次微分為 。乘以負數一般不保留凸性。
有限個仿射函數之最大值的精確公式
設
命題 5.2.3
(仿射函數最大值的次微分)
設 及 如上,則對每個 ,
證明
(活躍部分與投影)
每個活躍仿射函數都是全局下界,並在 與 相接。因此它的斜率是次梯度;次梯度的凸組合仍是次梯度。
反過來,假設 不在活躍斜率的凸包 內。該凸包非空、緊緻且凸。令 及 。投影不等式給出每個活躍斜率都滿足 ,而 。因此 。非活躍仿射函數在 有正的差距,而且函數數目有限,所以對所有充分小的 ,它們在 的值都不超過 。某個達到斜率 的活躍函數恰好取此值,因此 ,與 的支持不等式矛盾。故每個次梯度都在所述凸包內。
概念視角幾何
折角同時保留多個活躍線性模型
對 ,零點的活躍斜率為 及 ,其凸包是 。離開零點,只有一個仿射函數活躍。折角處的區間並不表示普通導數可以隨意選取;它記錄的是所有全局支持直線。
若有限凸函數 對歐氏範數滿足全局 -Lipschitz 條件,則每個 都有 。事實上,在 同時使用支持及 Lipschitz 不等式,可得對每個單位向量 及 都有 。當 時,取 即可。若有限個仿射函數的斜率皆有 ,其最大值便有此性質;凸包公式也直接給出次梯度界。
例題 5.2.4
(三條直線最大值的次梯度)
求 的 及全局最小值。
在零點,首兩個仿射函數活躍,斜率分別為 及 ;第三個函數的值為 。因此 ,包含零。最小值為 。直接看, 時第一個仿射函數至少為一, 時第二個至少為一。當 時,相應的界為嚴格不等式,所以零是唯一最小點。
去掉定義域假設後會怎樣
反例模式
不加條件的廣義值和法則是錯的
允許以 把點排除在函數的定義域之外。在定義域內的點,沿用相同的支持不等式來定義次微分;函數值為 的地方,不等式自動成立。在 上定義
這兩個函數都是真、下半連續的凸函數;這裏「真」指從不取 ,且至少在一點取有限值。在零點,若 ,則對每個 都須有 ,即 。當 下降至零,沒有有限 能滿足此條件,所以 是空集。另一方面,,而 ,故 。但兩個個別次微分的和是空集。
正確做法是使用附有實際假設的和定理。本節在整個 取有限值的定理,是一個充分版本。這裏並未證明一般以定義域相對內部為條件的法則。
投影次梯度步驟
設 非空、閉且凸,而 為有限凸函數。選擇 、正步長 ,以及任意 ,並令
在這些假設下投影唯一存在。次梯度的選取是算法的一部分:在折角處,不同的合法選擇可以產生不同的下一個迭代點。我們假設 在 上存在最小點 ,並記 。單靠 閉並不能保證最小點存在。
為取得定量界,假設實際選取的向量滿足 ,其中 已知。全局 -Lipschitz 連續是一個充分條件,但證明只用到所選向量的界。再選已知 ,使 。這些界需要就具體問題證明,並非算法自動提供的數值。
定理 5.2.5
(最佳迭代點與平均點的保證)
對每個整數 ,令
則 ,而 與 都不超過
特別是,若預先固定迭代預算 ,並在該次運行全程取常步長 ,則兩個誤差都不超過 。
證明
(投影、展開與相消求和)
設 及 。投影不等式 給出
令 及 。展開平方,再使用次梯度不等式,得到
移項後從 加至 ,中間的距離平方互相抵消。捨去最後非負的距離平方,便有
最小的誤差不超過這些誤差的加權平均。另一方面, 的凸性保證 可行,而 的凸性給出 。所以所求兩個誤差各自滿足同一個上界。對指定的常步長, 且 ,得到 。
證明透視
目標值未必下降,改為消去相鄰距離項
次梯度步未必令 下降,所以證明從不直接追蹤 ,而是追蹤到固定最小點的距離平方。投影到凸集 不會增加到任何可行點的距離,所以約束不帶來代價。關鍵一步是在 的次梯度不等式中取 :它把交叉項 換成目標差距 。唯一的代價是誤差項 ,這就是界中把 與 比較的原因。求和使中間的距離項互相抵消,而最後的距離非負,論證便告完成。最後再用一次凸性: 的凸性使 可行, 的凸性則以 的加權平均限制 。
常見錯誤
(保證並非關於最後一個迭代點)
定理計算的是 ;不能把其中最佳目標值換成 。它也沒有比較平均點與最佳迭代點的目標值:兩者都有可能較小。這是目標值精確度的界,並非到某個指定最小點的距離界。
若任意固定 ,相同論證給出 。令 趨於無窮後仍留下正的上界,因此此估計不能證明固定非零步長下的精確收斂。在按預算調整的界中,改變 也會改變該次運行所用步長。若 ,則 已是 的全局最小點,算法可以停止,毋須計算收斂速率。
例題 5.2.6
(到歐氏球的投影)
證明到歐氏球 的投影公式,其中 。為甚麼不能改為把每個座標獨立截斷至 ?
若 ,投影就是 。否則,對每個可行 ,反三角不等式給出 ,而 取等。由投影的唯一性,。逐座標截值則是投影到長方盒:在二維會把 留在原位,但該點範數為 ,位於球外。
在兩個折角處作完整計算
例題 5.2.7
(合法步驟可以離開精確最小點)
在 上最小化 。和法則與正比例法則給出: 時斜率為 , 時為 , 時為 。在折角處,
當 時,;當 時,;當 時,。由此可見唯一最小點是 ,最小值為 。所有次梯度的範數都不超過 。
取 ,從 出發,作以下合法選擇。區間投影就是把數值截斷至區間內;本表的試探點都已在區間內,所以投影不改變它們。
| 所選 | |||
|---|---|---|---|
每行都由 得出。從精確最小點走到 的一步使目標值上升。若在最小點選零次梯度,則會留在原位。這兩個選擇都是合法的次梯度。
另作一次預算為 的運行,同樣從 出發,利用已知界 及 ,應取 。定理保證在指定的首 100 個計值點中,最佳點與平均點的誤差都不超過 。這是最壞情況保證;上表用的是另一個步長。
反例模式
負次梯度未必指向下降方向
「若非零 ,則沿 走充分短的一步會使 下降」是錯的。對 ,在 選 。每個 都給出 。即使是精確最小點,也可以有非零次梯度。
次梯度提供未來函數值的下界,並不提供沿其負方向的上界。因此證明利用距離控制累積的目標誤差,而不假設逐步下降。最優性判別是零次梯度存在,並非所有次梯度都為零。
練習及完整解答
快速檢查
(求 在 的次微分。 是否存在無約束最小點?)
逐個座標處理,再加上仿射梯度。
解答 · 答案
在 , 的支持斜率在第一座標形成 , 的支持斜率在第二座標形成 。加上仿射梯度 ,得 ,不含零。這只能排除該點為最小點。為判斷整個問題,固定 ,令 趨於 :。所以不存在無約束最小點。
快速檢查
(設 且 ,直接證明 。)
用一個仿射部分在 的值去估計它在 的值。
解答 · 答案
對每個 ,。對 取最大值,得到 。交換 、 便得反方向的不等式。
快速檢查
(假設投影次梯度定理適用,且 、。選擇迭代預算與常步長,使目標誤差保證不超過 。準確指出保證適用於哪些輸出。)
由 解出 。
解答 · 答案
只須 ,因此可選 及 。保證適用於 及 。它沒有聲稱最後更新點 也滿足同一界;具體問題仍須符合距離與次梯度的假設。