線性子空間只是約束的一種。可行向量也可能必須具有非負座標,或位於超平面的某一側。此時從最近點出發的殘差一般不與所有可行方向正交:有些方向不允許移動。正確的替代條件是一個不等式,它還引出了約束最小化的迭代方法。
定義 4.2.1
(凸集及其投影)
全文令 為實 Hilbert 空間。若 且 時都有 ,則稱 為凸集。當 非空、閉且凸時,其投影 表示 中離 最近的唯一點;其存在性與唯一性正是下面定理的一部分。
最近點與一個不等式
定理 4.2.2
(到閉凸集的投影)
設 非空、閉且凸。對每個 ,存在唯一 滿足 。 是這個最近點當且僅當
證明
(極小化序列與單側導數)
令 ,選取 使 。由凸性,,故它到 的距離至少為 。平行四邊形恆等式給出
右側趨於零,因此 是 Cauchy 序列。完備性給出極限 ,閉性保證 ;由範數連續性,其距離為 。
對 ,當 時線段上的點 可行。在 取得最小值得
除以 並令 ,得到 (1)。反之,(1) 蘊含
所以 最近,且任何不同的 不可能同樣近。特別地,第一段找到的最近點就是滿足 (1) 的唯一點。
證明透視
為甚麼兩個假設都重要
證明分為存在性和刻畫兩半,兩者以不同方式使用假設。存在性只用一次凸性:中點 屬於 ,所以其距離至少為 ;平行四邊形恆等式於是把兩點都接近最優轉化為兩點彼此接近。 的完備性給出極限, 的閉性使極限仍然可行。刻畫部分第二次使用凸性,但方式不同:整條線段 留在 中,卻只限於 。這種單側性是關鍵一步,也是一階條件是不等式而非等式的原因:除以 保持符號,而負的 不可用。反方向得以完成,是因為 的展開式恰好含有 (1) 所控制的項,餘下的 直接給出唯一性,無須另行論證。
若 是閉線性子空間,對每個 和 都有 。在 (1) 中分別取 與 ,得到 ,於是恢復熟悉的正交投影。其餘兩個假設確實不可缺少,實數軸上的兩個子集就能說明。
反例模式
缺少閉性或缺少凸性
斷言:每個非空凸集,或每個非空閉集,對每個 都恰有一個最近點。在 中,凸集 滿足 ,但沒有 使 ,所以沒有離 最近的點。閉但非凸的集合 有 ,所以 有兩個最近點。定理兩個假設都需要:閉性保證存在,凸性保證唯一(以及 Cauchy 論證)。
常見錯誤
(把不等式換成正交條件)
對一般閉凸集,殘差 不一定與 正交。取 、,則 ,而 在 時為負,並非零。只有當每個可行方向都可以反向時(例如子空間),才有正交性;在凸集的邊界點上只能用不等式 (1)。
例題 4.2.3
(到閉單位球的投影)
令 。若 ,則 。否則令 ,於是 ,且 ,其中 。對 ,Cauchy–Schwarz 給出 ,因此
由 (1),。在邊界情形 ,兩個公式都給出 。
投影的穩定性
命題 4.2.4
(投影的堅定非擴張性)
對非空閉凸集 及所有 ,
特別地,。
證明
(把兩個變分不等式相加)
令 、。在 處以 應用 (1),得 ;在 處以 應用 (1),得 。兩式相加,
整理即得 (2)。Cauchy–Schwarz 不等式把 (2) 的右邊控制為 ; 時約去 ,得 , 時此估計顯然成立。
因而輸入的微小改變不會放大投影之間的距離。此不等式強於連續性,但並不聲稱嚴格壓縮。
例題 4.2.5
(到半空間的投影)
固定非零 和 ,令 。若 ,則 。否則令 、。則 ,所以 位於邊界上,且對每個 ,
由 (1) 得 。例如在 中, 到 的投影使用 、、,結果為 。
約束二次問題與迭代
令 有界、自伴,並假設存在常數 ,使得
對固定的 ,在非空閉凸集 上最小化 。
定理 4.2.6
(約束二次最小化)
在上述假設下, 在 上有唯一最小點 ,它由變分不等式刻畫:
對 及任意 ,投影迭代 滿足 ,其中 。
證明
(不動點解出變分不等式的壓縮映射)
若 ,一切顯然。否則定義 。由 (2)(特別是非擴張性)及自伴性,
當 非零時,Cauchy–Schwarz 不等式給出 ,所以 ,且 。步長條件使它嚴格小於一,因而 屬於 。完備空間 上的壓縮映射定理給出唯一不動點 ,且迭代滿足 。對點 應用 (1),方程 表示對所有 有 ;由於 ,這恰為 (3)。
對任意 ,令 ,利用自伴性得
因此 是唯一最小點。反過來,若 在 上最小化 ,對於 , 在 處的單側導數為 且非負,於是得到 (3)。
常見錯誤
(壓縮來自梯度步,而非投影)
投影本身不是壓縮映射:對 及輸入 和 ,兩者的投影都是自身,。證明中的因子 來自 ,用到了強制常數 。 的非擴張性只保證投影不會抵銷這個收益。
對 的估計只是充分條件,並非斷言更大的步長一定失敗;但步長必須有某種限制。
反例模式
步長過長
斷言:投影迭代對每個步長 都收斂。取 、(閉且凸)、、,於是 ,。迭代為 。取 得 ;從 出發,迭代在 之間交替,永不收斂。取 ,絕對值每步加倍。對每個初值都收斂恰好當 ,即 ,在此例中它正好與保證範圍 相同。
例題 4.2.7
(有限步內到達起作用的約束)
取 、、、,於是 。無約束駐點解 ,即 ,它不可行。此處 滿足 (3),因為對每個 都有 。由 ,保證範圍是 ;取 。則 ,所以
從 出發得到 、、,之後迭代停在 。約束在解處起作用,正是投影阻止了迭代沿梯度走向 。
練習
快速檢查
(求 並驗證 (1)。)
離負數最近的非負數是一個邊界點。
解答 · 答案
投影為 。對每個 ,,所以 (1) 成立。
快速檢查
(若 閉且凸,證明 。這是否意味著 線性?)
中的點到自身的距離為零。
解答 · 答案
已屬於 ,故它在 中的唯一最近點是它自己。投影未必線性:對 ,。
快速檢查
(在 上最小化 ,並驗證 (3)。)
把 寫成 的形式。
解答 · 答案
此處 、。候選點為 :對 ,,所以 (3) 成立。最小值為 。
快速檢查
(對 ,說明非擴張估計對兩個不同輸入可以取等號。)
選取本身已經可行的輸入。
解答 · 答案
對 、,兩者的投影都是自身,所以 。