凸優化：算法與複雜性（簡體書）

凸優化的數學研究已經有一個世紀了，最近的一些相關發展也激發了人們對這個問題的新興趣.首先是認識到在20世紀80年代發展起來用於解決線性規劃的內點法，也可以用來解決凸優化問題.這種方法使我們能夠解決某些新的凸優化問題，如半定規劃和二階錐規劃，幾乎與線性規劃一樣容易.
第二個發展是發現凸優化問題（超越最小二乘法和線性規劃）在實踐中使用得更普遍.自1990年以來，在自動控制系統、估計和信號處理、通信和網絡、電子電路設計、數據分析和建模、統計和金融等領域已發現許多凸優化的應用.凸優化在組合優化和全局優化中也有著廣泛的應用，如被用來尋找最優值的界，以及近似解.我們相信凸優化還有許多其他應用有待發現.
將一個問題識別或表述為凸優化問題有很大的優勢.最基本的優點是，使用內點法或其他特殊的凸優化方法可以非常可靠和有效地解決問題.這些求解方法是可靠的，可以嵌入到計算機輔助設計或分析工具中，甚至可以嵌入到實時反應或自動控制系統中.將問題描述為凸優化問題也有理論或概念上的優勢.例如，相關聯的對偶問題通常對原始問題存在一個有趣的解釋，有時會產生一個有效的或分布式的解決方法.
本書主要由六章組成.第1章綜合介紹了一些機器學習中的凸優化問題和凸性的基本性質，以及凸性質存在的意義.第2章主要介紹有限維凸優化方法，包括重心法、橢球法、Vaidya割平面法以及共軛梯度法.第3章主要介紹維度無關的凸優化方法，包括Lipschitz函數的投影次梯度下降、光滑函數的梯度下降、條件梯度下降、幾何下降以及Nesterov加速梯度下降.第4章主要介紹鏡像下降的非歐氏空間與維度無關的凸優化方法以及關於MD、DA和MP的向量場觀點.第5章主要介紹迭代收縮閾值算法、快速ISTA算法、CMD和RDA算法、鞍點鏡像下降法的超越黑箱模型，以及超越黑箱模型的實際應用.第6章主要介紹凸優化和隨機性的結合，包括（非）光滑隨機優化、隨機坐標下降、鞍點的隨機加速、凸松弛與隨機取整以及基於隨機遊動的方法.
本書是Sébastien Bubeck教授凝聚多年心血，專門為計算機科學家打造的一本專著，它內容翔實，推導過程簡潔，主要把機器學習中涉及的凸優化設計思想，通過簡練的數學語言進行了闡述.在此，我也推薦讀者在閱讀本書時，通過自己擅長的計算機語言進行相關算法實現，並對實現過程進行性能優化和延伸.本書可以考慮作為計算機科學、軟件工程、統計學、應用數學、數據科學與大數據、人工智能等專業本科生和研究生的基礎教材，也可作為數據科學家、工程師和科研人員的案頭工具書.
本書主要由劉曉駿負責翻譯、校對、審核、統稿和定稿，郭濤及其團隊參與了譯稿的校對工作，在此對他們表示衷心感謝.感謝機械工業出版社王春華編輯和柯敬賢編輯，他們在本書的翻譯和出版過程中給了我悉心的指導.感謝所有參與本書出版的出版社工作人員對本書做出的貢獻.
為了能夠讓讀者盡快讀到這本書，我加快了翻譯進度，但本書涵蓋內容多，翻譯難度大，任務重，加上本人翻譯水平有限，在翻譯過程中難免有錯漏之處，歡迎讀者在閱讀過程中將關於本書的勘誤、存在的問題和完善意見提交到Github.

劉曉駿
2020年夏於華南理工大學

譯者序
致謝
第1章緒論1
11機器學習中的若幹凸優化問題1
12凸性的基本性質3
13凸性的作用5
14黑箱模型7
15結構性優化8
16結果的概述和免責聲明9
第2章有限維的凸優化12
21重心法12
22橢球法14
23Vaidya割平面法18
231體積障礙19
232Vaidya算法20
233Vaidya方法分析20
234限制條件和體積障礙22
24共軛梯度26
第3章維度無關的凸優化30
31Lipschitz函數的投影次梯度下降31
32光滑函數的梯度下降33
33條件梯度下降39
34強凸性43
341 強凸函數和Lipschitz函數44
342強凸光滑函數45
35下限47
36幾何下降52
361熱身賽：梯度下降的幾何學替代方案53
362加速度55
363幾何下降法56
37Nesterov加速梯度下降58
371光滑強凸情況58
372光滑的情況62
第4章非歐氏空間幾乎維度無關的凸優化65
41鏡像映射66
42鏡像下降67
43鏡像下降的標準設置70
44惰性鏡像下降72
45鏡像代理74
46關於MD、DA和MP的向量場觀點76
第5章超越黑箱模型78
51光滑項與簡單非光滑項之和78
52非光滑函數的光滑鞍點表示80
521鞍點計算81
522鞍點鏡像下降82
523鞍點鏡像代理83
524應用84
53內點法87
531障礙法87
532牛頓法的傳統分析88
533自和諧函數90
534ν自和諧障礙92
535路徑跟蹤方案95
536線性規劃和半定規劃的內點法96
第6章凸優化與隨機性98
61非光滑隨機優化99
62光滑隨機優化與小批量SGD100
63光滑函數與強凸函數的和103
64隨機坐標下降107
641坐標平滑優化的RCD算法108
642用於光滑和強凸優化的RCD110
65鞍點的隨機加速112
66凸松弛與隨機取整113
67基於隨機遊動的方法117
參考文獻120