凸優化教程(原書第2版)（簡體書）

寫作本書的想法來自Springer的編輯，他們建議作者更新著作Introductory Lectures on Convex Optimization: Basic Course，這是2003年由Kluwer出版社出版的［39］事實上，這本書的主要部分寫於1997~1998年，所以其內容至少有20年的歷史對於凸優化這樣一個活躍的領域，這確實是很長的時間
然而，在開始研究相關內容之後，作者很快意識到，這一不大的目標根本無法實現［39］主要是為關於凸優化的短學期課程(12節課)服務的，反映了當時該領域的主要算法成果因此，一些重要的概念和想法，特別是與各種對偶理論有關的，被毫不留情地從內容中刪除了在某種意義上，［39］仍然適用於介紹凸優化算法基本概念的較短課程對該內容的任何擴充都需要做出復雜的解釋，以說明為什麼所選的內容比書架上的許多其他有趣的候選材料更為重要
於是，作者做出了一個艱難的決定——寫一本新書，它包括［39］的所有內容，以及該領域在過去20年中最重要的進展從時間節點上看，本書涵蓋的時間段直到2012年當然，為了保持一致性，我們添加了幾篇最新發表的論文成果，這對書中討論的主題很重要因此，有關隨機坐標下降法和通用方法的較新結果、零階算法的復雜度結果和求解大規模問題的方法仍然沒有包括進來然而，在我們看來，這些非常有意義的主題還沒有成熟到可以進行專題介紹的地步，尤其是以講課的形式
從方法論的角度看，這本書的新穎之處主要在於對偶的大量出現現在讀者可以從兩個方面看待問題：原始和對偶與［39］相比，本書的內容增加了一倍，這看起來對一個全面的介紹來說是合理的但是很顯然，本書的內容太多了，不適合作為一個學期的教材然而，它很適合一個兩學期的課程，或者，它的不同部分可以分別用於不同的現代優化教學課程我們將在“引言”的最後討論這個問題
在本書中，我們包括三個對專題文獻來說全新的主題
● 光滑技術該方法完全改變了我們對大多數應用中出現的非光滑優化問題復雜度的理解它基於可用光滑函數逼近不可微凸函數，並用快速梯度法極小化新目標與標準的次梯度法相比，新算法每次迭代的復雜度沒有變化，然而，新算法迭代次數的估計值變成與標準次梯度算法迭代次數的平方根成正比由於在實踐中這些迭代次數通常是成千上萬甚至百萬的數量級，所以計算時間方面的好處非常驚人
● 二階算法的全局復雜度界二階算法及其最著名的代表——牛頓法，是數值分析中最古老的算法之一然而，在牛頓法的三次正則化被發現之後，它們的全局復雜度分析才剛剛開始對於這種經典算法的新變形，我們可以為不同問題類給出全局復雜度界因此，我們現在可以比較不同的二階方法的全局效率，並開發加速算法這些算法的一個全新特點是極小化過程中用到目標函數的模型積累同時，我們可以為它們推導復雜度下界，並研究最優的二階算法對於求解非線性方程組的算法也可以進行類似的修改
● 相對尺度優化定義最優化問題近似解的標準方法是引入絕對精度然而，在許多工程應用中，以相對尺度(百分比)來度量解的質量是很自然的為了朝這個方向調整極小化算法，我們引入了目標函數的一個特殊模型，並為計算一個與目標函數拓撲結構相兼容的適度度量應用了高效的預處理算法因此，我們得到了非常有效的優化算法，其復雜度界與輸入數據的大小具有弱依賴關係
我們希望本書對廣大讀者有用處，包括數學、經濟學和工程專業的學生，不同領域的實踐者，以及優化理論、運籌學和計算機科學的研究人員過去幾十年這個領域發展的主要經驗是，有效的優化算法只能通過智能地使用特定問題實例的結構來研究為了做到這一點，參考成功的例子總是有用的我們相信本書將為感興趣的讀者提供大量這類信息

尤裡·涅斯捷羅夫，比利時新魯汶
2018年1月

譯者序
前言
致謝
引言
第一部分黑箱優化
第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2Kelley算法
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1Oracle線性優化
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求解一些輔助優化問題
參考文獻評注
參考文獻
索引