完整搜尋頁面 →

OPT 01・決策建模與凸集合

最佳化入門14 分鐘更新於 2026年10月4日

先備知識:ML 01A・學習所需的線性代數、ML 01C・數值計算與梯度檢查

導覽:本頁與本系列: 導覽:本頁與本系列
用實驗理解本章 1 個互動實驗

在圓上放兩個可行點,沿著它們之間的線段移動,並比較圓盤與圓環。

你將學到

  • 把決策轉成變數、目標、限制與固定資料。
  • 區分可行、最佳、不可行、無界與未達到下確界的問題。
  • 理解仿射集合、凸組合、凸包與錐。
  • 辨認半空間、多面體、範數球、橢球與半正定錐。
  • 使用保留凸性的運算、投影與分離超平面。
  • 檢查數值解對模型與實際應用各自提供什麼證據。

先看全貌

影像復原系統選擇輸出像素,排程系統選擇資源分配,擬合程序選擇係數。三者都有許多可選答案、比較答案好壞的方式,以及允許答案的規則。最佳化把這三個要素寫清楚。

本軌以 Stephen Boyd 與 Lieven Vandenberghe 的《Convex Optimization》[1] 為主軸,學習辨認、建立與求解具有全域保證的問題。前幾章建立集合、函數、標準問題與對偶;應用連到擬合、統計估計與幾何設計;最後討論數值演算法與現代延伸。

比喻有其限制:口味不一定是凸函數,材料也可能只能整包購買。第一個能力是辨認實際決策的哪些部分適合凸模型、哪些不適合。合理建模,比對錯誤方程式使用快速求解器更重要。

凸最佳化也能出現在非凸學習流程中,例如在固定特徵上擬合線性分類器、計算受限預測、擬合校準曲線,或替困難問題建立下界。但它不會讓任意神經網路訓練自動變成凸問題。保證只屬於實際求解的那個數學模型。

從一句話到最佳化模型

白話版。 先決定可以改什麼、已知什麼、什麼答案比較好,以及必須遵守哪些規則,再選演算法。

一般純量最佳化可寫成

minimize⁡x∈Rnf0(x)subject tofi(x)≤0,i=1,…,m,hj(x)=0,j=1,…,p.\begin{aligned} \operatorname{minimize}_{x\in\mathbb R^n}\quad &f_0(x)\\ \text{subject to}\quad &f_i(x)\leq0,\quad i=1,\ldots,m,\\ &h_j(x)=0,\quad j=1,\ldots,p. \end{aligned}

xx 是含 nn 個決策變數的向量;f0f_0 是要最小化的純量目標;fif_i 是 mm 個不等式限制函數;hjh_j 是 pp 個等式限制函數。固定量測與設計參數出現在函數中,但除非模型明確指定,否則不是決策變數。

例如兩種作業的資源用量為 x1,x2x_1,x_2,容量限制可以是 2x1+x2≤52x_1+x_2\leq5,且 x1,x2≥0x_1,x_2\geq0。若固定目標配置為 bb,∥x−b∥22\|x-b\|_2^2 偏好接近目標。這些數字定義合成模型,不是產線量測。

單位也是模型的一部分。把金錢成本與影像重建誤差相加,需要權重慣例。換算尺度的係數應有可解釋含意,並經過檢查。影像從零到 255 改成零到一,其他項不變時,正則化的相對強度也可能改變。

建立簡短的建模紀錄:每個變數的意義與單位、固定輸入的來源、每個限制的理由,以及目標的解釋。這能避免把方便的公式誤認成唯一合理的任務描述。

限制與懲罰代表不同承諾

硬限制表示答案不被允許;懲罰表示某種偏差不理想,但可以換取其他好處。即使某次答案相似,兩者的含意仍不同。

例如強制 x≥0x\geq0,所有可行影像都非負;對負值加平方懲罰,仍可能容許少量負值,以換取較好的資料項。增加懲罰係數不自動等於精確限制,有限精度下尤其如此。

預算限制設定明確上限,成本懲罰則表示與係數有關的偏好。係數選擇是應用決策,凸性不會替你決定。對偶章會推導乘子如何描述放寬硬限制的敏感度。

算例:容量限制下的目標配置

目標配置未必符合現有容量。最佳化找最近的容許配置,而不是把每個座標減少相同數量。

取合成目標 b=(3,3)b=(3,3),在 x≥0x\geq0 與 2x1+x2≤52x_1+x_2\leq5 下最小化 12∥x−b∥22\frac12\|x-b\|_2^2。目標消耗九單位容量,因此不可行。最佳解的容量邊界為作用中限制,其法向量為 a=(2,1)a=(2,1),所以最短修正沿著 aa:

x∗=b−αa,α=a⊤b−5a⊤a=45,x∗=(75,115).x^*=b-\alpha a,\qquad \alpha=\frac{a^\top b-5}{a^\top a}=\frac45, \qquad x^*=\left(\frac75,\frac{11}5\right).

其中 x∗x^* 是候選配置、α\alpha 是修正尺度、aa 是容量限制的法向量。代入可得 2x1∗+x2∗=52x_1^*+x_2^*=5,而且兩座標都為正,所以非負限制不會改變這個投影。

為什麼它是最近的點?對任何可行 xx,都有 a⊤(x−x∗)≤0a^\top(x-x^*)\leq0。展開目標差:

12∥x−b∥22−12∥x∗−b∥22=12∥x−x∗∥22−αa⊤(x−x∗)≥0.\frac12\|x-b\|_2^2-\frac12\|x^*-b\|_2^2 =\frac12\|x-x^*\|_2^2-\alpha a^\top(x-x^*)\geq0.

其中 xx 是任意可行競爭點,其餘符號如上定義。兩項都非負,因此候選點為全域最小解,目標值為 8/58/5。這個計算在使用求解器前,就連起變數、作用中規則、修正方向與最佳值 [1]。

可行性與最佳值

白話版。 被允許的答案不一定是最佳答案。有時沒有任何答案符合規則,有時目標喜歡的是越跑越遠的選擇。

F={x:fi(x)≤0 for every i, hj(x)=0 for every j, x in all required domains}.\mathcal F=\{x:f_i(x)\leq0\ \text{for every }i,\ h_j(x)=0\ \text{for every }j,\ x\text{ in all required domains}\}.

F\mathcal F 是同時滿足所有限制與函數定義域的可行集合。集合中的點稱為可行點。最佳值為

p∗=inf⁡x∈Ff0(x).p^*=\inf_{x\in\mathcal F}f_0(x).

p∗p^* 是所有可達目標值的最大下界。最佳解 x∗x^* 是達到 f0(x∗)=p∗f_0(x^*)=p^* 的可行點。下確界存在,不代表存在達到它的點。

要區分四種情況:可行且達到有限最佳值;可行集合為空;目標向負無限延伸;有限下確界卻沒有點達到。

例如最小化 xx 且要求 x>0x>0,最佳值為零,但零不允許。最小化 −x-x 且 x≥0x\geq0,問題向下無界。同時要求 x≥1x\geq1 與 x≤0x\leq0,則不可行。求解器都可能沒有回傳有限最佳解,但原因完全不同。

非空緊緻可行集合上的連續目標會達到最小值。閉而無界的集合,若目標在無限遠成長得足夠,也可能存在最小值。解是否存在,是開始執行演算法前就屬於模型的問題。

數值狀態是有限精度計算的證據

求解器通常把限制殘差、最佳條件或原始—對偶 gap 與容忍值比較。成功狀態不表示實數意義下精確可行,更不保證量測、目標與應用限制都正確。

若應用必須真正守住安全上限,需說明數值容忍值如何對應該上限。x≤1x\leq1 與 106x≤10610^6x\leq10^6 數學等價,但未正規化殘差的尺度不同。

記錄殘差單位、尺度與容忍值。不同目標定義的數值不要直接比較。若停止原因是迭代上限,就如實報告;不能把點幾乎不動當成最佳性的證明。

仿射集合與凸集合

白話版。 仿射集合包含任意兩點之間的整條直線;凸集合只需要包含它們之間的線段。

對 u,v∈Rnu,v\in\mathbb R^n:

x=θu+(1−θ)v.x=\theta u+(1-\theta)v.

u,vu,v 為端點向量,xx 為組合,純量 θ\theta 控制直線位置。允許所有實數 θ\theta,得到整條線;限制 0≤θ≤10\leq\theta\leq1,得到線段。

包含所有仿射組合的集合是仿射集合;包含所有非負且係數總和一的凸組合,則是凸集合。所以仿射集合必為凸,但圓盤是凸而不是仿射。

有限多點的凸組合:

x=∑i=1rθivi,θi≥0,∑i=1rθi=1.x=\sum_{i=1}^r\theta_iv_i,\qquad \theta_i\geq0,\qquad \sum_{i=1}^r\theta_i=1.

viv_i 是 rr 個端點,θi\theta_i 是權重,組合是加權平均。非負很重要;外插可以離開凸集合。

凸性本身不要求平滑邊界、有界或閉。開球是凸,無界直線也是凸,單點也是凸。空集合慣例上也算凸,因為沒有違反定義的端點。

圓盤中的線段、穿過圓環孔洞的線段,以及三角形中的凸組合。
Figure 1 — 原創合成幾何。圓盤與填滿的三角形是凸集合;圓環不是,因為兩個允許端點的連線穿過被排除的孔洞。

反例能否證,取樣不能證明

要否證凸性,只需找到集合內兩點,使其中點或線段上其他點落在集合外。圓環可用相反端點平均成中心。

要證明凸性,使用定義或保留規則。隨機測很多點對能揭露實作錯誤,卻不能保證所有端點都成立。很小的非凸缺口可能完全沒有被抽到。

這與數值梯度檢查相似:它們是實作診斷,而數學證明處理全稱敘述。兩者用途不同,應標示清楚。

程式碼:凸組合與非凸反例

以下自成一體,驗證特定點。圓盤凸性的證明來自三角不等式,不是只有 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))

凸包與鬆弛

白話版。 凸包填入原有選擇的所有加權平均。它能簡化離散決策,但新加入的點未必真的可執行。

conv⁡(S)={∑i=1rθivi:r finite, vi∈S, θi≥0, ∑iθi=1}.\operatorname{conv}(S)= \left\{\sum_{i=1}^r\theta_iv_i: r\text{ finite},\ v_i\in S,\ \theta_i\geq0,\ \sum_i\theta_i=1\right\}.

SS 是原集合,rr 是有限組合中的點數;conv⁡(S)\operatorname{conv}(S) 是包含 SS 的最小凸集合。

若必須在三個配置中選一個,凸包也容許混合。若混合代表時間分配,可能是實際可操作的選擇;若必須買一台不可分割的機器,分數配置只是鬆弛,不是原問題可行答案。

最小化問題擴大可行集合,不會提高最佳值,所以凸鬆弛可給離散問題下界。把鬆弛解變成真實離散選擇,還需額外步驟;捨入可能違反限制或傷害目標。

不可把鬆弛問題的精確最佳解說成原問題的精確最佳解。原可行集、鬆弛集合、下界與實際達成目標應分開。應用章會再討論。

常用凸集合詞彙

白話版。 多數有用模型由幾種可重用幾何形狀組成。學會辨認後,陌生方程式也比較容易理解。

超平面、半空間與多面體

H={x:a⊤x=b},P={x:a⊤x≤b}.H=\{x:a^\top x=b\},\qquad P=\{x:a^\top x\leq b\}.

x∈Rnx\in\mathbb R^n 是點,a≠0a\ne0 是法向量,bb 是純量偏移。超平面是仿射;閉半空間包含邊界與其中一側。

多面體是有限個半空間與超平面的交集,常寫 Ax≤b, Ex=dAx\leq b,\ Ex=d。A,EA,E 放係數,b,db,d 放界限,不等式逐座標比較。多面體可有界、無界、低維或空。

盒狀集合只限制各座標上下界;機率單純形再加入非負與總和一。這說明機率向量與有界像素常適合凸限制。

範數球與橢球

B={x:∥x−c∥≤r}.B=\{x:\|x-c\|\leq r\}.

cc 是中心,r≥0r\geq0 是半徑,∥⋅∥\|\cdot\| 是範數。三角不等式給出凸性。二範數球是圓形,無限範數球是盒,一範數球帶有角點。

E={c+Au:∥u∥2≤1}.\mathcal E=\{c+Au:\|u\|_2\leq1\}.

AA 把單位二範數球映射成橢球,uu 是輔助座標,cc 是中心。AA 可逆時可用正定形狀矩陣寫二次描述;AA 奇異時得到低維影像,仍然凸。

錐與矩陣不等式

凸錐對非負組合封閉:

αu+βv∈Kfor u,v∈K, α,β≥0.\alpha u+\beta v\in K \quad\text{for }u,v\in K,\ \alpha,\beta\geq0.

KK 是錐,u,vu,v 是其中的點,α,β\alpha,\beta 是非負純量;權重不需要總和一。非負 orthant 是例子。

二階錐包含 ∥z∥2≤t\|z\|_2\leq t 的 (t,z)(t,z),其中 tt 是純量,zz 是向量,可表達許多範數限制。

半正定錐包含滿足下式的對稱矩陣:

v⊤Xv≥0for every v∈Rn.v^\top Xv\geq0\quad\text{for every }v\in\mathbb R^n.

X∈Rn×nX\in\mathbb R^{n\times n} 對稱,vv 是任意測試向量。記為 X⪰0X\succeq0,不等於每個矩陣元素非負。共變異數矩陣自然落在此錐中。

廣義不等式用錐定義順序:x⪯Kyx\preceq_Ky 表示 y−x∈Ky-x\in K。Orthant 對應逐座標順序,對稱矩陣則對應半正定順序,必須說明使用哪個錐。

保留凸性的運算

白話版。 已知一個集合凸後,可以透過特定運算得到另一個凸集合。這些規則比一直畫圖更可靠。

凸集合的交集仍凸:兩端點的線段會同時留在每個集合內。因此加入更多凸限制很直接。

仿射映射與仿射逆像保留凸性。CC 凸時,{Ax+b:x∈C}\{Ax+b:x\in C\} 與 {x:Ax+b∈C}\{x:Ax+b\in C\} 都凸;A,bA,b 是固定矩陣與向量。一般非線性轉換沒有此保證。

Cartesian product 與集合和保留凸性。取部分座標的投影是仿射映射,因此消去輔助變數後仍凸。這是 extended formulation 的基礎:增加變數反而可能更容易描述。

聯集通常不凸,兩個分離的球就示範失敗。限制敘述中的「且」改成「或」,即使每個分支都凸,也可能根本改變問題。

矩陣變數也一樣。X,YX,Y 半正定時,0≤θ≤10\leq\theta\leq1 下的 θX+(1−θ)Y\theta X+(1-\theta)Y 半正定,對每個向量檢查二次型即可。

兩個可重用的短證明

凸性證明通常追蹤一條線段如何通過集合構造。假設 u,v∈C1∩C2u,v\in C_1\cap C_2,且 C1,C2C_1,C_2 都凸。對 0≤θ≤10\leq\theta\leq1,混合點 θu+(1−θ)v\theta u+(1-\theta)v 同時屬於兩集合,因此屬於交集。任意多個凸集合的交集也可用相同推理。

對仿射映射,令 y1=Au+by_1=Au+b、y2=Av+by_2=Av+b,其中 u,v∈Cu,v\in C。兩映射點的混合為

θy1+(1−θ)y2=A[θu+(1−θ)v]+b.\theta y_1+(1-\theta)y_2 =A[\theta u+(1-\theta)v]+b.

其中 CC 是凸集合、A,bA,b 是固定轉換資料、y1,y2y_1,y_2 是映射後的點。中括號內的點屬於 CC,所以混合點也在映射集合內。這就是消去輔助座標仍保留凸可行集合的原因 [1,第 2.3 節]。

聯集的對應證明會失敗,因為兩端點可能來自不同集合。例如 −1∈[−2,−1]-1\in[-2,-1]、1∈[1,2]1\in[1,2],但中點零不屬於任何一個區間。兩區間各自凸,聯集卻不凸。對建模而言,同時滿足凸規則保留凸性;二選一規則則可能破壞它。

投影與分離超平面

白話版。 投影找離任意點最近的允許點。從投影指向原點的方向,也能描述可行集合位於邊界哪一側。

非空閉凸集合 CC 的二範數投影為

ΠC(y)=arg⁡min⁡x∈C12∥x−y∥22.\Pi_C(y)=\arg\min_{x\in C}\frac12\|x-y\|_2^2.

yy 是查詢點,xx 是可行候選,ΠC(y)\Pi_C(y) 是唯一最小點。平方二範數的嚴格凸性確保唯一;其他距離或非凸集合未必如此。

令 z=ΠC(y)z=\Pi_C(y):

(y−z)⊤(x−z)≤0for every x∈C.(y-z)^\top(x-z)\leq0\quad\text{for every }x\in C.

zz 是投影,xx 遍歷所有可行點。從 zz 朝任意可行 xx 移動一小步,平方距離不能下降,就得到此條件。

若 y∉Cy\notin C,y−z≠0y-z\ne0,它定義通過 zz 的超平面,使可行集合與 yy 分處兩側,給出具體分離構造。

更一般的分離定理比較不相交凸集合 [1,第 2.5 節]。沒有附加假設時,分離未必有正 margin;閉性、緊緻性與集合距離都影響嚴格分離。

外部點投影至圓盤,投影處的切線讓圓盤位於另一側。
Figure 2 — 原創解析示意:外部點投影至單位圓盤,投影方向提供分離超平面的法向量。

程式碼:盒與球的投影

盒投影逐座標裁切;球投影只對外部點縮放。[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)

取樣只展示投影不等式,不能替代所有可行點的證明。複雜集合的投影本身可能需要最佳化,所以「投影梯度」不代表投影便宜。

推導投影檢查條件

投影不等式來自檢查每個可行方向,而不是畫一條看起來合理的切線。令 z=ΠC(y)z=\Pi_C(y),任取 x∈Cx\in C。凸性使 z+θ(x−z)z+\theta(x-z) 在 0≤θ≤10\leq\theta\leq1 時可行。因為 zz 最小化平方距離,其單側方向導數必須非負:

ddθ12∥z+θ(x−z)−y∥22∣θ=0=(z−y)⊤(x−z)≥0.\left.\frac{d}{d\theta}\frac12\|z+\theta(x-z)-y\|_2^2\right|_{\theta=0} =(z-y)^\top(x-z)\geq0.

其中 yy 是查詢點、zz 是其投影、xx 是可行比較點、θ\theta 是線段參數。這便得到前面的分離不等式。它也充分:把 xx 處距離展開,就得到 zz 處距離,加上一個非負內積與 12∥x−z∥22\frac12\|x-z\|_2^2。

唯一性也很直接。若不同的 z1,z2z_1,z_2 都最小化平方距離,可行中點的值會嚴格更小。封閉性則確保存在:最小化序列留在有界的距離次水平集合內,因此有收斂子序列,而極限仍在 CC。非空、封閉與凸性各自扮演明確角色 [1]。

內部、相對內部與隱藏等式

白話版。 集合可能在自己的平面內有活動空間,卻在完整周圍空間沒有內部。

機率向量座標總和一,位於超平面,完整向量空間中的內部是空。但座標嚴格正的點,仍可位於此超平面中的相對內部。

仿射包是包含 CC 的最小仿射集合;相對內部是在仿射包中量測的內部。這與可行性條件和對偶有關,不能要求完整維度內部而排除有用的等式模型。

不等式也可能隱藏等式:同時要求 a⊤x≤ba^\top x\leq b 與 a⊤x≥ba^\top x\geq b,就強制等號。辨認它能改善解釋與數值處理。

嚴格可行不是「算出很小違反」。它要求相關不等式嚴格成立,同時滿足等式。對偶與內點章會說明何時需要此條件。

凸問題需要集合與函數都合適

白話版。 允許選擇是凸,只完成一半;目標形狀與等式也必須符合條件。

凸最小化使用凸目標、凸不等式函數與仿射等式 [1]。下一章定義凸函數並推導辨認規則。

凸可行集合本身不夠:在盒上最小化有多個谷地的函數仍非凸。凸目標加不連通離散限制,也非凸。

整體問題凸時,每個局部最小點都是全域最小點。但解未必唯一,線性目標可能在整個面上相同。可行集合上的嚴格凸性,可在存在最小值時保證唯一。

全域性與唯一性不保證所有尺度都容易。巨大密集問題可能超過記憶體,病態問題的緊容忍值可能難求。凸性提供結構優勢,但計算量與實作仍重要。

為什麼局部最小解必須是全域最小解

凸性把較好的遠處答案連到目前點,排除局部陷阱。假設 xx 是凸可行集合 CC 上凸函數 ff 的局部最小解,但某個可行 yy 有 f(y)<f(x)f(y)<f(x)。對任意 0<θ≤10<\theta\leq1,定義 zθ=(1−θ)x+θyz_\theta=(1-\theta)x+\theta y,則

f(zθ)≤(1−θ)f(x)+θf(y)<f(x).f(z_\theta)\leq(1-\theta)f(x)+\theta f(y)<f(x).

其中 zθz_\theta 是可行線段點、θ\theta 是混合權重。任意小的正 θ\theta 都能讓該點任意靠近 xx,而且改善目標,與局部最小性矛盾。證明不需要可微性 [1]。

它給全域性,卻不給唯一性。例如在 0≤x1,x2≤10\leq x_1,x_2\leq1 上最小化 x1x_1,每個 (0,x2)(0,x_2) 都是全域最小解。嚴格凸目標會排除不同的同值最小解,因為可行中點的成本會更低。存在性仍獨立:在 x>0x>0 下最小化 xx 是凸問題,卻沒有最小解。

這三個問題決定對求解器的期待。凸性使局部最小解全域;嚴格曲率可選出唯一答案;封閉性與目標成長可確保答案存在。數值程序還需要適當收斂論證,不能只靠以上三點。

現代觀點

白話版。 現代凸最佳化仍從建模與幾何開始;新方法改變如何存取可行集合,以及花多少成本取得準確證書。

Grant、Boyd 與 Ye 的 disciplined convex programming [2] 以已驗證的組合規則組織模型。這是建模方法,不保證任意方便公式都凸。代數上凸的式子,也可能需要改寫,讓規則系統看得出凸性。

Pokutta 的 2024 Frank–Wolfe 綜述 [3] 區分投影、barrier 與線性最小化 oracle 等集合存取方式。容易描述的集合,投影仍可能很貴;線性最小化有時較便宜,凸組合則維持可行。後續章節會推導更新與條件。

Applegate 等人的 PDLP 報告 [4] 於 2025 首次公開、2026 修訂,研究實用的一階線性規劃求解器,連結原始—對偶模型、尺度調整、restart 與可行性修整。這是原創求解器研究,不是綜述;它說明即使熟悉的凸問題,實作與需求精度仍重要。

目前挑戰包含以不過度膨脹的輔助變數表達複雜限制、利用稀疏矩陣、讓尺度下的容忍值有意義,以及把求解器嵌入較大流程時維持證書。學習式特徵可能非凸,後續分配問題卻凸,各階段保證應分開描述。

這是經挑選的閱讀路線,不宣稱檢閱所有最佳化綜述。核心理論依 [1],現代觀點明確指出每個來源支持哪種延伸。

重點整理

  • 變數、固定資料、目標、限制與單位必須明確。
  • 可行、有界、達到最佳值與數值停止,是不同問題。
  • 凸集合包含所有非負且權重總和一的平均。
  • 仿射集合、多面體、範數球與錐是可重用積木。
  • 交集與仿射轉換保留凸性,聯集通常不會。
  • 閉凸集合投影唯一,並提供幾何證書。
  • 凸最佳化保證針對建立的問題及其假設。

練習

  1. 建立三種非負資源的預算配置模型,以平方距離接近固定目標,說明單位、變數與資料。
提示

向量 xx、非負、總和限制與固定目標。

  1. 直接證明兩個凸集合的交集凸,並提出聯集反例。
提示

線段留在兩者中;分離區間否證聯集。

  1. 三種配置擇一時,何時凸混合能實際操作,何時只是鬆弛?
提示

時間分配與不可分硬體。

  1. 推導中心在原點的二範數球投影,說明內部點的情況。
提示

外部點沿徑向落在邊界。

  1. 提出最佳值有限卻未達到的凸問題,說明缺少哪個存在條件。
提示

開區間排除極限點。

  1. 限制殘差為 10−610^{-6},為何沒有尺度與應用單位就不能判斷是否足夠?
提示

同一不等式縮放後,原始殘差會改變。

參考文獻

  1. Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004。閱讀:第 1–2 章;第 4.1–4.2 與 8.1 節補充問題術語及投影。官方書籍頁、官方免費 PDF。
  2. Michael Grant, Stephen Boyd and Yinyu Ye, “Disciplined Convex Programming,” in Global Optimization: From Theory to Implementation, Springer, 2006。作者出版頁。
  3. Sebastian Pokutta, “The Frank-Wolfe Algorithm: A Short Introduction,” Jahresbericht der Deutschen Mathematiker-Vereinigung, 126, 2024。開放綜述。
  4. 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 分鐘