凸優化教程(原書第2版)

尤裏·涅斯捷羅夫（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 具有非負元素的