第1章引論

第1節線性規劃

第2節Torricelli點問題

第3節相關陣滿足性問題

第4節割問題

小結

習題

第2章集合、空間和矩陣正定性

第1節集合、線性空間與範數

2.1.1集合與運算

2.1.2向量與線性空間

2.1.3空間、集合的維數與矩陣的秩

2.1.4行列式、跡、內積和範數

第2節矩陣正定性

第3節凸集與錐

2.3.1內點和相對內點、開集、閉集和相對開集

2.3.2凸集及其性質

2.3.3多面體

2.3.4錐

2.3.5錐半序

第4節對偶集合

小結

習題

第3章凸函數及可計算問題

第1節函數

第2節凸函數

第3節共軛函數

第4節可計算性問題

3.4.1離散模型

3.4.2連續模型

3.4.3離散優化的多項式時間近似方案和連續優化可計算

小結

習題

第4章性條件與對偶問題

第1節基於導數的性條件

4.1.1一階性條件

4.1.2二階性條件

第2節約束規範

第3節Lagrange對偶

4.3.1Lagrange對偶問題

4.3.2廣義Lagrange對偶

4.3.3二次約束二次規劃問題的Lagrange對偶模型

第4節共軛對偶

4.4.1共軛對偶在線性規劃的應用

4.4.2共軛對偶與Lagrange對偶

第5節線性錐優化模型及性結論

小結

習題

第5章可計算線性錐優化模型

第1節線性規劃

第2節二階錐規劃

5.2.1其他變形模型

5.2.2二階錐可表示函數/集合概念

5.2.3常見的二階錐可表示函數/集合

5.2.4二階錐的應用

第3節半定規劃

5.3.1一般形式

5.3.2線性矩陣不等式

5.3.3半定矩陣可表示集合/函數

5.3.4半定規劃應用

第4節內點算法簡介

第5節線性錐優化問題都可計算嗎

小結

習題

第6章應用案例

第1節線性方程組近似與稀疏解

第2節投資管理問題

第3節單變量多項式優化

第4節魯棒凸二次約束二次優化問題

小結

習題

第7章CVX使用簡介

第1節使用環境和典型命令

第2節可計算凸優化規則及核心函數庫

第3節參數控制及核心函數的擴展

小結

習題

參考文獻

索引

線性錐優化是對決策變量取自一個錐，而約束和目標函數為決策變量的線性函數這類優化問題研究的統稱，其內容包括模型的建立、解性質的理論分析、解的計算求解和模型的應用等議題。簡單的線性錐優化問題其實就是大家熟悉的線性規劃問題，其決策變量限定在Rn 這個錐上，而目標和約束都是決策變量的線性函數。線性規劃問題是線性錐優化中為經典、為著名的一類。自1947年George B.Dantzig提出單純形算法後，線性規劃問題在許多學科中得到了廣泛的應用。雖說單純形算法非常實用，但在情況下，研究者舉出了計算效率降至極低的實例。
20世紀70年代末期橢球算法以及80年代初期內點算法的出現，證明了線性規劃問題是多項式時間可計算的。由此學術界更期望在給定的精度下發現更多的多項式時間可計算(簡稱可計算)問題。研究者相繼提出了二階錐規劃、半定規劃等可計算問題，並在大量實際問題中得到應用，由此引發了人們對線性錐優化問題的關注和研究興趣。

線性錐優化問題涵蓋線性規劃、二階錐規劃和半定規劃這些可計算問題，使得大量實際應用問題得以有效求解。同時，像二次約束二次規劃這種理論問題也可以在其框架下研究和求解。因此，線性錐優化非常具有代表性和挑戰性。如何利用錐的特殊結構來擴大我們在理論上對一些困難問題的了解和如何實現近似計算求解，成為數學規劃領域中的一個重要的研究方向。

基於對2013年版《線性錐優化》一書多年教學中發現的問題和積累的經驗，本書主要選取了原《線性錐優化》一書的第1章至第4章、第7章和附錄的部分內容，大量增加了二階錐可表示和半定錐可表示的一些問題，使讀者掌握化成線性錐優化模型的一些基本方法和技巧，並在每章後加入小結和習題，算是《線性錐優化》一書的一個教學版本，可作為凸分析和線性錐優化的一本完整教材。本書充分考慮凸分析內容的完整性與線性錐優化的相關性，在Euclidean空間的假設下，給出凸分析的相關結論。對原《線性錐優化》一書的內容進行了重新編排和修正，
對其中的一些證明進行了簡化和補充，以便於讀者掌握相關凸分析的基礎理論和證明技巧。

本書可作為化相關專業研究生、高年級本科生、教師、科研人員的教材或參考書。
作為引論，本書第1章從應用的視角分別介紹了隸屬於線性規劃、二階錐規劃、半定規劃和二次函數錐規劃的線性規劃問題、Torricelli點問題、相關陣滿足性問題和割問題及其數學模型的建立。具有運籌學、高等數學基礎知識的讀者閱讀這一章不會有太大困難。第2、3章介紹凸分析和非線性規劃的基礎知識，為後續章節內容做準備。特別需要關注這兩章中關於相對內點內容的討論和對偶觀點的介紹。第4、5章為本書的核心。第4章介紹性條件和共軛對偶優化問題，由此給出了線性錐優化問題解可達的充分條件這個核心結論。第5章具體給出可計算線性錐優化的模型和理論結果，包括線性規劃、二階錐規劃和半定規劃三類模型。由於具備多項式時間可計算的特點，這三類模型在很多實際問題中得以應用。可計算線性錐優化問題的計算一般采用內點算法，第5章對內點算法的框架給予簡單介紹。第6章選擇了若干個典型問題，介紹線性錐優化的應用。為了便於線性錐優化的研究和應用，我們在第7章中簡單介紹內點算法軟件CVX的使用。本書多處通過例子介紹二次函數錐規劃的模型，從而讓讀者了解一類難於求解的線性錐優化問題。

本書在清華大學教學中多次使用，得到很多同仁和同學的指正，特別是2019年秋季學期課程“數學規劃Ⅱ”的全體同學為本書提出修改建議並完成了全部習題的解答。在此，我們對所有給予我們幫助的各位同仁和同學表示衷心的感謝！也感謝國家自然科學基金(11771243)的部分資助!
後也為重要的是： 如果沒有家庭的支持，我們的工作是絕無可能完成的。謹將此書獻給趙繼新、方先安、李娟、邢睿磊！謝謝他們無盡的體諒和支持。

邢文訓方述誠

2019年鼕