內容大鋼
凸優化在應用數學、經濟金融、工程、電腦科學,特別是數據科學和機器學習方面越來越重要,本書對凸優化進行了全面且現代的介紹。
本書由該領域的權威專家撰寫,內容包括凸優化的演算法理論的新進展,不但包含一階、二階極小化加速技術的一個統一且嚴格的表述,而且為讀者提供了光滑化方法的完整處理,這極大地擴展了梯度類型方法的應用範圍。此外,本書還詳細討論了結構優化的幾種有效方法,包括相對尺度優化法和多項式時間內點法。
本書對理論優化的研究人員以及從事優化問題工作的專業人士非常有用,它提供了許多成功的例子來說明如何開發非常快速的專門極小化演算法。基於作者的講座實踐,本書自然也可以作為工程、經濟、電腦科學和數學學科學生的介紹性及高級凸優化課程教材。
作者介紹
(俄羅斯)尤里·涅斯捷羅夫|責編:柯敬賢|譯者:周水生
尤里·涅斯捷羅夫(Yurii Nesterov)是著名的優化專家。他是Nesterov梯度加速法、多項式時間內點法、平滑技術、正則化牛頓法等方面開創性著作的作者。曾獲丹吉格獎(2000)、馮·諾依曼理論獎(2009)、SIAM傑出論文獎(2014)、歐洲金獎(2016)等多項國際大獎。
目錄
譯者序
前言
致謝
引言
第一部分 黑箱優化
第1章 非線性優化
1.1 非線性優化引論
1.1.1 問題的一般描述
1.1.2 數值方法的性能
1.1.3 全局優化的複雜度界
1.1.4 優化領域的「身份證」
1.2 無約束極小化的局部演算法
1.2.1 鬆弛和近似
1.2.2 可微函數類
1.2.3 梯度法
1.2.4 牛頓法
1.3 非線性優化中的一階方法
1.3.1 梯度法和牛頓法有何不同
1.3.2 共軛梯度法
1.3.3 約束極小化問題
第2章 光滑凸優化
2.1 光滑函數的極小化
2.1.1 光滑凸函數
2.1.2 函數類F∞,1L(n)的複雜度下界
2.1.3 強凸函數類
2.1.4 函數類S∞,1μ,L(n)的複雜度下界
2.1.5 梯度法
2.2 最優演算法
2.2.1 估計序列
2.2.2 降低梯度的范數
2.2.3 凸集
2.2.4 梯度映射
2.2.5 簡單集上的極小化問題
2.3 具有光滑分量的極小化問題
2.3.1 極小極大問題
2.3.2 梯度映射
2.3.3 極小極大問題的極小化方法
2.3.4 帶有函數約束的優化問題
2.3.5 約束極小化問題的演算法
第3章 非光滑凸優化
3.1 一般凸函數
3.1.1 動機和定義
3.1.2 凸函數運算
3.1.3 連續性和可微性
3.1.4 分離定理
3.1.5 次梯度
3.1.6 次梯度計算
3.1.7 最優性條件
3.1.8 極小極大定理
3.1.9 原始對偶演算法的基本要素
3.2 非光滑極小化方法
3.2.1 一般複雜度下界
3.2.2 估計近似解性能
3.2.3 次梯度演算法
3.2.4 函數約束的極小化問題
3.2.5 最優拉格朗日乘子的近似
3.2.6 強凸函數
3.2.7 有限維問題的複雜度界
3.2.8 割平面演算法
3.3 完整數據的演算法
3.3.1 目標函數的非光滑模型
3.3.2 Kelley演算法
3.3.3 水平集法
3.3.4 約束極小化問題
第4章 二階演算法
4.1 牛頓法的三次正則化
4.1.1 二次逼近的三次正則化
4.1.2 一般收斂性結果
4.1.3 具體問題類的全局效率界
4.1.4 實現問題
4.1.5 全局複雜度界
4.2 加速的三次牛頓法
4.2.1 實向量空間
4.2.2 一致凸函數
4.2.3 牛頓迭代的三次正則化
4.2.4 一個加速演算法
4.2.5 二階演算法的全局非退化性
4.2.6 極小化強凸函數
4.2.7 偽加速
4.2.8 降低梯度的范數
4.2.9 非退化問題的複雜度
4.3 最優二階演算法
4.3.1 複雜度下界
4.3.2 一個概念性最優演算法
4.3.3 搜索過程的複雜度
4.4 修正的高斯牛頓法
4.4.1 高斯牛頓迭代的二次正則化
4.4.2 修正的高斯牛頓過程
4.4.3 全局收斂速率
4.4.4 討論
第二部分 結構優化
第5章 多項式時間內點法
5.1 自和諧函數
5.1.1 凸優化中的黑箱概念
5.1.2 牛頓法實際上做什麼
5.1.3 自和諧函數的定義
5.1.4 主要不等式
5.1.5 自和諧性和Fenchel對偶
5.2 自和諧函數極小化
5.2.1 牛頓法的局部收斂性
5.2.2 路徑跟蹤演算法
5.2.3 強凸函數極小化
5.3 自和諧障礙函數
5.3.1 研究動機
5.3.2 自和諧障礙函數的定義
5.3.3 主要不等式
5.3.4 路徑跟蹤演算法
5.3.5 確定解析中心
5.3.6 函數約束問題
5.4 顯式結構問題的應用
5.4.1 自和諧障礙函數參數的下界
5.4.2 上界:通用障礙函數和極集
5.4.3 線性和二次優化
5.4.4 半定優化
5.4.5 極端橢球
5.4.6 構造凸集的自和諧障礙函數
5.4.7 自和諧障礙函數的例子
5.4.8 可分優化
5.4.9 極小化演算法的選擇
第6章 目標函數的原始對偶模型
6.1 目標函數顯式模型的光滑化
6.1.1 不可微函數的光滑近似
6.1.2 目標函數的極小極大模型
6.1.3 合成極小化問題的快速梯度法
6.1.4 應用實例
6.1.5 演算法實現的討論
6.2 非光滑凸優化的過間隙技術
6.2.1 原始對偶問題的結構
6.2.2 過間隙條件
6.2.3 收斂性分析
6.2.4 極小化強凸函數
6.3 半定優化中的光滑化技術
6.3.1 光滑化特徵值的對稱函數
6.3.2 極小化對稱矩陣的最大特徵值
6.4 目標函數的局部模型極小化
6.4.1 Oracle線性優化
6.4.2 合成目標函數的條件梯度演算法
6.4.3 收縮型條件梯度
6.4.4 原始對偶解的計算
6.4.5 合成項的強凸性
6.4.6 極小化二次模型
第7章 相對尺度優化
7.1 目標函數的齊次模型
7.1.1 圓錐無約束極小化問題
7.1.2 次梯度近似演算法
7.1.3 問題結構的直接使用
7.1.4 應用實例
7.2 凸集的近似
7.2.1 計算近似橢球
7.2.2 極小化線性函數的最大絕對值
7.2.3 具有非負元素的雙線性矩陣博弈
7.2.4 極小化對稱矩陣的譜半徑
7.3 障礙函數次梯度演算法
7.3.1 自和諧障礙函數的光滑化
7.3.2 障礙函數次梯度法
7.3.3 正凹函數極大化
7.3.4 應用
7.3.5 隨機規劃的替代——在線優化
7.4 混合精度優化
7.4.1 嚴格正函數
7.4.2 擬牛頓法
7.4.3 近似解的解釋
附錄A 求解一些輔助優化問題
參考文獻評註
參考文獻
索引