凸最佳化（convex optimization）

想像一片形狀像單一光滑碗的地形——沒有假凹陷、沒有隱藏的側谷，就只有一個最低點。把彈珠丟在任何地方，它都滾向那個唯一的底；沒有別處能把它卡住。凸最佳化就是最小化恰好具有這個神奇性質的函數：任何局部極小自動是全域極小，所以「局部夠好」就等於「可能的最佳」。

一個集合是凸（convex）的，若它任兩點之間的直線段都留在集合內（圓盤是凸的，月牙不是）。一個函數 f 是凸的，若它的圖形從不凸出到任兩點連線（弦）之上——形式上對 0 <= t <= 1 有 f(t a + (1-t) b) <= t f(a) + (1-t) f(b)；對光滑 f 等價於它的海森矩陣處處半正定（曲面向上彎、絕不向下）。一個凸最佳化問題是在凸的可行集上最小化凸目標。決定性的後果是：一階條件變成充分、而不只是必要：若 grad f(x*) = 0（或對應的 KKT 條件成立），則 x* 是全域極小——沒有壞的局部極小或鞍點來困住你。碗（最小平方）、線性規劃、成本正定的二次規劃，以及許多機器學習損失（邏輯迴歸、SVM、LASSO）都是凸的。

這是整個最佳化中最重要的分界線之一：凸問題在強烈的意義下是「可解的」——高效演算法（內點法，以及無約束情形下任何下降法）能可靠又快速地找到經認證的全域最佳，並有嚴格保證。非凸問題（多數深度神經網路、許多設計問題）沒有這種保證；你得到一個局部最佳，且很少知道它離真正最佳有多遠。誠實的提醒是「凸」是個強假設：真實問題往往非凸，大量實務功夫不是花在把問題改寫成凸的（凸鬆弛），就是乾脆接受非凸訓練只是在尋找一個好的局部極小、而非全域。Rockafellar 那句名言是：真正的分水嶺不在線性與非線性之間，而在凸與非凸之間。