OPT 01・決策建模與凸集合
先備知識:ML 01A・學習所需的線性代數、ML 01C・數值計算與梯度檢查
導覽:本頁與本系列: 導覽:本頁與本系列
本頁內容
最佳化
你將學到
- 把決策轉成變數、目標、限制與固定資料。
- 區分可行、最佳、不可行、無界與未達到下確界的問題。
- 理解仿射集合、凸組合、凸包與錐。
- 辨認半空間、多面體、範數球、橢球與半正定錐。
- 使用保留凸性的運算、投影與分離超平面。
- 檢查數值解對模型與實際應用各自提供什麼證據。
先看全貌
影像復原系統選擇輸出像素,排程系統選擇資源分配,擬合程序選擇係數。三者都有許多可選答案、比較答案好壞的方式,以及允許答案的規則。最佳化把這三個要素寫清楚。
本軌以 Stephen Boyd 與 Lieven Vandenberghe 的《Convex Optimization》[1] 為主軸,學習辨認、建立與求解具有全域保證的問題。前幾章建立集合、函數、標準問題與對偶;應用連到擬合、統計估計與幾何設計;最後討論數值演算法與現代延伸。
比喻有其限制:口味不一定是凸函數,材料也可能只能整包購買。第一個能力是辨認實際決策的哪些部分適合凸模型、哪些不適合。合理建模,比對錯誤方程式使用快速求解器更重要。
凸最佳化也能出現在非凸學習流程中,例如在固定特徵上擬合線性分類器、計算受限預測、擬合校準曲線,或替困難問題建立下界。但它不會讓任意神經網路訓練自動變成凸問題。保證只屬於實際求解的那個數學模型。
從一句話到最佳化模型
白話版。 先決定可以改什麼、已知什麼、什麼答案比較好,以及必須遵守哪些規則,再選演算法。
一般純量最佳化可寫成
是含 個決策變數的向量; 是要最小化的純量目標; 是 個不等式限制函數; 是 個等式限制函數。固定量測與設計參數出現在函數中,但除非模型明確指定,否則不是決策變數。
例如兩種作業的資源用量為 ,容量限制可以是 ,且 。若固定目標配置為 , 偏好接近目標。這些數字定義合成模型,不是產線量測。
單位也是模型的一部分。把金錢成本與影像重建誤差相加,需要權重慣例。換算尺度的係數應有可解釋含意,並經過檢查。影像從零到 255 改成零到一,其他項不變時,正則化的相對強度也可能改變。
建立簡短的建模紀錄:每個變數的意義與單位、固定輸入的來源、每個限制的理由,以及目標的解釋。這能避免把方便的公式誤認成唯一合理的任務描述。
限制與懲罰代表不同承諾
硬限制表示答案不被允許;懲罰表示某種偏差不理想,但可以換取其他好處。即使某次答案相似,兩者的含意仍不同。
例如強制 ,所有可行影像都非負;對負值加平方懲罰,仍可能容許少量負值,以換取較好的資料項。增加懲罰係數不自動等於精確限制,有限精度下尤其如此。
預算限制設定明確上限,成本懲罰則表示與係數有關的偏好。係數選擇是應用決策,凸性不會替你決定。對偶章會推導乘子如何描述放寬硬限制的敏感度。
算例:容量限制下的目標配置
目標配置未必符合現有容量。最佳化找最近的容許配置,而不是把每個座標減少相同數量。
取合成目標 ,在 與 下最小化 。目標消耗九單位容量,因此不可行。最佳解的容量邊界為作用中限制,其法向量為 ,所以最短修正沿著 :
其中 是候選配置、 是修正尺度、 是容量限制的法向量。代入可得 ,而且兩座標都為正,所以非負限制不會改變這個投影。
為什麼它是最近的點?對任何可行 ,都有 。展開目標差:
其中 是任意可行競爭點,其餘符號如上定義。兩項都非負,因此候選點為全域最小解,目標值為 。這個計算在使用求解器前,就連起變數、作用中規則、修正方向與最佳值 [1]。
可行性與最佳值
白話版。 被允許的答案不一定是最佳答案。有時沒有任何答案符合規則,有時目標喜歡的是越跑越遠的選擇。
是同時滿足所有限制與函數定義域的可行集合。集合中的點稱為可行點。最佳值為
是所有可達目標值的最大下界。最佳解 是達到 的可行點。下確界存在,不代表存在達到它的點。
要區分四種情況:可行且達到有限最佳值;可行集合為空;目標向負無限延伸;有限下確界卻沒有點達到。
例如最小化 且要求 ,最佳值為零,但零不允許。最小化 且 ,問題向下無界。同時要求 與 ,則不可行。求解器都可能沒有回傳有限最佳解,但原因完全不同。
非空緊緻可行集合上的連續目標會達到最小值。閉而無界的集合,若目標在無限遠成長得足夠,也可能存在最小值。解是否存在,是開始執行演算法前就屬於模型的問題。
數值狀態是有限精度計算的證據
求解器通常把限制殘差、最佳條件或原始—對偶 gap 與容忍值比較。成功狀態不表示實數意義下精確可行,更不保證量測、目標與應用限制都正確。
若應用必須真正守住安全上限,需說明數值容忍值如何對應該上限。 與 數學等價,但未正規化殘差的尺度不同。
記錄殘差單位、尺度與容忍值。不同目標定義的數值不要直接比較。若停止原因是迭代上限,就如實報告;不能把點幾乎不動當成最佳性的證明。
仿射集合與凸集合
白話版。 仿射集合包含任意兩點之間的整條直線;凸集合只需要包含它們之間的線段。
對 :
為端點向量, 為組合,純量 控制直線位置。允許所有實數 ,得到整條線;限制 ,得到線段。
包含所有仿射組合的集合是仿射集合;包含所有非負且係數總和一的凸組合,則是凸集合。所以仿射集合必為凸,但圓盤是凸而不是仿射。
有限多點的凸組合:
是 個端點, 是權重,組合是加權平均。非負很重要;外插可以離開凸集合。
凸性本身不要求平滑邊界、有界或閉。開球是凸,無界直線也是凸,單點也是凸。空集合慣例上也算凸,因為沒有違反定義的端點。

反例能否證,取樣不能證明
要否證凸性,只需找到集合內兩點,使其中點或線段上其他點落在集合外。圓環可用相反端點平均成中心。
要證明凸性,使用定義或保留規則。隨機測很多點對能揭露實作錯誤,卻不能保證所有端點都成立。很小的非凸缺口可能完全沒有被抽到。
這與數值梯度檢查相似:它們是實作診斷,而數學證明處理全稱敘述。兩者用途不同,應標示清楚。
程式碼:凸組合與非凸反例
以下自成一體,驗證特定點。圓盤凸性的證明來自三角不等式,不是只有 assertion。
程式碼 · Python · 12 行
import numpy as np
u = np.array([0.8, 0.1])
v = np.array([-0.2, 0.7])
theta = np.linspace(0, 1, 101)
segment = theta[:, None] * u + (1 - theta[:, None]) * v
assert np.linalg.norm(segment, axis=1).max() <= 1 + 1e-12
ring_u, ring_v = np.array([1.0, 0.0]), np.array([-1.0, 0.0])
midpoint = (ring_u + ring_v) / 2
assert not (0.5 <= np.linalg.norm(midpoint) <= 1.2)
print("disk sampled-segment maximum norm:", np.linalg.norm(segment, axis=1).max())
print("ring midpoint:", midpoint, "norm:", np.linalg.norm(midpoint))凸包與鬆弛
白話版。 凸包填入原有選擇的所有加權平均。它能簡化離散決策,但新加入的點未必真的可執行。
是原集合, 是有限組合中的點數; 是包含 的最小凸集合。
若必須在三個配置中選一個,凸包也容許混合。若混合代表時間分配,可能是實際可操作的選擇;若必須買一台不可分割的機器,分數配置只是鬆弛,不是原問題可行答案。
最小化問題擴大可行集合,不會提高最佳值,所以凸鬆弛可給離散問題下界。把鬆弛解變成真實離散選擇,還需額外步驟;捨入可能違反限制或傷害目標。
不可把鬆弛問題的精確最佳解說成原問題的精確最佳解。原可行集、鬆弛集合、下界與實際達成目標應分開。應用章會再討論。
常用凸集合詞彙
白話版。 多數有用模型由幾種可重用幾何形狀組成。學會辨認後,陌生方程式也比較容易理解。
超平面、半空間與多面體
是點, 是法向量, 是純量偏移。超平面是仿射;閉半空間包含邊界與其中一側。
多面體是有限個半空間與超平面的交集,常寫 。 放係數, 放界限,不等式逐座標比較。多面體可有界、無界、低維或空。
盒狀集合只限制各座標上下界;機率單純形再加入非負與總和一。這說明機率向量與有界像素常適合凸限制。
範數球與橢球
是中心, 是半徑, 是範數。三角不等式給出凸性。二範數球是圓形,無限範數球是盒,一範數球帶有角點。
把單位二範數球映射成橢球, 是輔助座標, 是中心。 可逆時可用正定形狀矩陣寫二次描述; 奇異時得到低維影像,仍然凸。
錐與矩陣不等式
凸錐對非負組合封閉:
是錐, 是其中的點, 是非負純量;權重不需要總和一。非負 orthant 是例子。
二階錐包含 的 ,其中 是純量, 是向量,可表達許多範數限制。
半正定錐包含滿足下式的對稱矩陣:
對稱, 是任意測試向量。記為 ,不等於每個矩陣元素非負。共變異數矩陣自然落在此錐中。
廣義不等式用錐定義順序: 表示 。Orthant 對應逐座標順序,對稱矩陣則對應半正定順序,必須說明使用哪個錐。
保留凸性的運算
白話版。 已知一個集合凸後,可以透過特定運算得到另一個凸集合。這些規則比一直畫圖更可靠。
凸集合的交集仍凸:兩端點的線段會同時留在每個集合內。因此加入更多凸限制很直接。
仿射映射與仿射逆像保留凸性。 凸時, 與 都凸; 是固定矩陣與向量。一般非線性轉換沒有此保證。
Cartesian product 與集合和保留凸性。取部分座標的投影是仿射映射,因此消去輔助變數後仍凸。這是 extended formulation 的基礎:增加變數反而可能更容易描述。
聯集通常不凸,兩個分離的球就示範失敗。限制敘述中的「且」改成「或」,即使每個分支都凸,也可能根本改變問題。
矩陣變數也一樣。 半正定時, 下的 半正定,對每個向量檢查二次型即可。
兩個可重用的短證明
凸性證明通常追蹤一條線段如何通過集合構造。假設 ,且 都凸。對 ,混合點 同時屬於兩集合,因此屬於交集。任意多個凸集合的交集也可用相同推理。
對仿射映射,令 、,其中 。兩映射點的混合為
其中 是凸集合、 是固定轉換資料、 是映射後的點。中括號內的點屬於 ,所以混合點也在映射集合內。這就是消去輔助座標仍保留凸可行集合的原因 [1,第 2.3 節]。
聯集的對應證明會失敗,因為兩端點可能來自不同集合。例如 、,但中點零不屬於任何一個區間。兩區間各自凸,聯集卻不凸。對建模而言,同時滿足凸規則保留凸性;二選一規則則可能破壞它。
投影與分離超平面
白話版。 投影找離任意點最近的允許點。從投影指向原點的方向,也能描述可行集合位於邊界哪一側。
非空閉凸集合 的二範數投影為
是查詢點, 是可行候選, 是唯一最小點。平方二範數的嚴格凸性確保唯一;其他距離或非凸集合未必如此。
令 :
是投影, 遍歷所有可行點。從 朝任意可行 移動一小步,平方距離不能下降,就得到此條件。
若 ,,它定義通過 的超平面,使可行集合與 分處兩側,給出具體分離構造。
更一般的分離定理比較不相交凸集合 [1,第 2.5 節]。沒有附加假設時,分離未必有正 margin;閉性、緊緻性與集合距離都影響嚴格分離。

程式碼:盒與球的投影
盒投影逐座標裁切;球投影只對外部點縮放。[1,第 8.1 節] 討論這些幾何應用。
程式碼 · Python · 15 行
import numpy as np
y = np.array([2.0, -1.5])
lower, upper = np.array([0.0, -1.0]), np.array([1.0, 1.0])
box_projection = np.clip(y, lower, upper)
radius = 1.0
ball_projection = y * min(1.0, radius / np.linalg.norm(y))
rng = np.random.default_rng(2)
points = rng.normal(size=(1000, 2))
points /= np.maximum(1.0, np.linalg.norm(points, axis=1))[:, None]
inequality = (points - ball_projection) @ (y - ball_projection)
assert inequality.max() <= 1e-12
assert np.all(box_projection >= lower) and np.all(box_projection <= upper)
print("box projection:", box_projection)
print("ball projection:", ball_projection)取樣只展示投影不等式,不能替代所有可行點的證明。複雜集合的投影本身可能需要最佳化,所以「投影梯度」不代表投影便宜。
推導投影檢查條件
投影不等式來自檢查每個可行方向,而不是畫一條看起來合理的切線。令 ,任取 。凸性使 在 時可行。因為 最小化平方距離,其單側方向導數必須非負:
其中 是查詢點、 是其投影、 是可行比較點、 是線段參數。這便得到前面的分離不等式。它也充分:把 處距離展開,就得到 處距離,加上一個非負內積與 。
唯一性也很直接。若不同的 都最小化平方距離,可行中點的值會嚴格更小。封閉性則確保存在:最小化序列留在有界的距離次水平集合內,因此有收斂子序列,而極限仍在 。非空、封閉與凸性各自扮演明確角色 [1]。
內部、相對內部與隱藏等式
白話版。 集合可能在自己的平面內有活動空間,卻在完整周圍空間沒有內部。
機率向量座標總和一,位於超平面,完整向量空間中的內部是空。但座標嚴格正的點,仍可位於此超平面中的相對內部。
仿射包是包含 的最小仿射集合;相對內部是在仿射包中量測的內部。這與可行性條件和對偶有關,不能要求完整維度內部而排除有用的等式模型。
不等式也可能隱藏等式:同時要求 與 ,就強制等號。辨認它能改善解釋與數值處理。
嚴格可行不是「算出很小違反」。它要求相關不等式嚴格成立,同時滿足等式。對偶與內點章會說明何時需要此條件。
凸問題需要集合與函數都合適
白話版。 允許選擇是凸,只完成一半;目標形狀與等式也必須符合條件。
凸最小化使用凸目標、凸不等式函數與仿射等式 [1]。下一章定義凸函數並推導辨認規則。
凸可行集合本身不夠:在盒上最小化有多個谷地的函數仍非凸。凸目標加不連通離散限制,也非凸。
整體問題凸時,每個局部最小點都是全域最小點。但解未必唯一,線性目標可能在整個面上相同。可行集合上的嚴格凸性,可在存在最小值時保證唯一。
全域性與唯一性不保證所有尺度都容易。巨大密集問題可能超過記憶體,病態問題的緊容忍值可能難求。凸性提供結構優勢,但計算量與實作仍重要。
為什麼局部最小解必須是全域最小解
凸性把較好的遠處答案連到目前點,排除局部陷阱。假設 是凸可行集合 上凸函數 的局部最小解,但某個可行 有 。對任意 ,定義 ,則
其中 是可行線段點、 是混合權重。任意小的正 都能讓該點任意靠近 ,而且改善目標,與局部最小性矛盾。證明不需要可微性 [1]。
它給全域性,卻不給唯一性。例如在 上最小化 ,每個 都是全域最小解。嚴格凸目標會排除不同的同值最小解,因為可行中點的成本會更低。存在性仍獨立:在 下最小化 是凸問題,卻沒有最小解。
這三個問題決定對求解器的期待。凸性使局部最小解全域;嚴格曲率可選出唯一答案;封閉性與目標成長可確保答案存在。數值程序還需要適當收斂論證,不能只靠以上三點。
現代觀點
白話版。 現代凸最佳化仍從建模與幾何開始;新方法改變如何存取可行集合,以及花多少成本取得準確證書。
Grant、Boyd 與 Ye 的 disciplined convex programming [2] 以已驗證的組合規則組織模型。這是建模方法,不保證任意方便公式都凸。代數上凸的式子,也可能需要改寫,讓規則系統看得出凸性。
Pokutta 的 2024 Frank–Wolfe 綜述 [3] 區分投影、barrier 與線性最小化 oracle 等集合存取方式。容易描述的集合,投影仍可能很貴;線性最小化有時較便宜,凸組合則維持可行。後續章節會推導更新與條件。
Applegate 等人的 PDLP 報告 [4] 於 2025 首次公開、2026 修訂,研究實用的一階線性規劃求解器,連結原始—對偶模型、尺度調整、restart 與可行性修整。這是原創求解器研究,不是綜述;它說明即使熟悉的凸問題,實作與需求精度仍重要。
目前挑戰包含以不過度膨脹的輔助變數表達複雜限制、利用稀疏矩陣、讓尺度下的容忍值有意義,以及把求解器嵌入較大流程時維持證書。學習式特徵可能非凸,後續分配問題卻凸,各階段保證應分開描述。
這是經挑選的閱讀路線,不宣稱檢閱所有最佳化綜述。核心理論依 [1],現代觀點明確指出每個來源支持哪種延伸。
重點整理
- 變數、固定資料、目標、限制與單位必須明確。
- 可行、有界、達到最佳值與數值停止,是不同問題。
- 凸集合包含所有非負且權重總和一的平均。
- 仿射集合、多面體、範數球與錐是可重用積木。
- 交集與仿射轉換保留凸性,聯集通常不會。
- 閉凸集合投影唯一,並提供幾何證書。
- 凸最佳化保證針對建立的問題及其假設。
練習
- 建立三種非負資源的預算配置模型,以平方距離接近固定目標,說明單位、變數與資料。
提示
向量 、非負、總和限制與固定目標。
- 直接證明兩個凸集合的交集凸,並提出聯集反例。
提示
線段留在兩者中;分離區間否證聯集。
- 三種配置擇一時,何時凸混合能實際操作,何時只是鬆弛?
提示
時間分配與不可分硬體。
- 推導中心在原點的二範數球投影,說明內部點的情況。
提示
外部點沿徑向落在邊界。
- 提出最佳值有限卻未達到的凸問題,說明缺少哪個存在條件。
提示
開區間排除極限點。
- 限制殘差為 ,為何沒有尺度與應用單位就不能判斷是否足夠?
提示
同一不等式縮放後,原始殘差會改變。
參考文獻
- Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004。閱讀:第 1–2 章;第 4.1–4.2 與 8.1 節補充問題術語及投影。官方書籍頁、官方免費 PDF。
- Michael Grant, Stephen Boyd and Yinyu Ye, “Disciplined Convex Programming,” in Global Optimization: From Theory to Implementation, Springer, 2006。作者出版頁。
- Sebastian Pokutta, “The Frank-Wolfe Algorithm: A Short Introduction,” Jahresbericht der Deutschen Mathematiker-Vereinigung, 126, 2024。開放綜述。
- David Applegate, Mateo Díaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue and Warren Schudy, “PDLP: A Practical First-Order Method for Large-Scale Linear Programming,” arXiv preprint, 2025,2026 修訂。已驗證論文記錄。
檢查理解
本篇有 6 題練習。不看提示,你能解出來嗎?
前往練習 ↑下一篇 OPT 02・凸函數、組合規則與共軛 · 13 分鐘