本書旨在幫助需要學習“凸優化”或者“非線性優化”方法以解決信號處理與通信領域中相關優化問題的工程類專業研究生、學者和工程技術人員。本書構建起了從基礎數學理論到實際應用之間的橋梁，並強調兩者的平衡，一共包括10章和1個附錄。第1章介紹了一些常用的數學基礎與定義，第2章介紹了凸集，第3章介紹了凸函數，第4章介紹了凸優化問題和問題重構，以上4章構成了基本凸優化問題所需的數學基礎。接下來介紹了一些典型的凸優化問題，包括第5章的幾何規劃，第6章的線性規劃、二次規劃和二次約束二次規劃，第7章的二階錐規劃，第8章的半正定規劃，第9章的“對偶”原理。在這些章節中，讀者可以看到第2章到第4章介紹的基本知識將如何正確、有效地應用於通信和/或信號處理中的實際問題。最後在第10章介紹了廣泛用於求解具體凸優化問題的內點法，以試圖在數值上為求解線性規劃或非線性凸優化問題提供更加有效的計算性能。

祁忠勇，博士畢業於美國南加州大學，1989年至今在臺灣清華大學電機工程繫擔任正教授，IEEE會士，研究方向主要包括無線通信與信號處理、凸函數分析及優化、盲信號分離、醫學及高光譜影像分析等，至今已出版學術專著2本，發表國際頂級期刊和會議論文200餘篇。
陳翔，在清華大學電子工程繫獲工學學士和工學博士學位，現為中山大學電子與信息工程學院副教授、博士生導師。陳翔博士的主要研究方向為5G移動通信、衛星通信、軟件無線電。至今已在國內外知名期刊和會議上發表論文80餘篇。瀋超。在北京交通大學信號與信息處理專業獲博士學位，現為北京交通大學軌道交通控制與安全國家重點實驗室副教授、博士生導師。主要研究優化理論在4G、5G和6G無線通信繫統中的應用，在國際知名期刊和會議上發表論文50餘篇。

第1章 數學背景
1．1 數學基礎
1．1．1 向量範數
1．1．2 矩陣範數
1．1．3 內積
1．1．4 範數球
1．1．5 內點
1．1．6 補集、擴展集與和集
1．1．7 閉包與邊界
1．1．8 上確界與下確界
1．1．9 函數
1．1．10 連續性
1．1．11 導數與梯度
1．1．12 Hessian 矩陣
1．1．13 Taylor 級數
1．2 線性代數回顧
1．2．1 向量子空間
1．2．2 張成空間、零空間和正交投影算子
1．2．3 矩陣行列式與逆
1．2．4 正定性與半正定性
1．2．5 特征值分解
1．2．6 半正定矩陣的平方根分解
1．2．7 奇異值分解
1．2．8 最小二乘近似
1．3 總結與討論
參考文獻
第2章 凸集
2．1 仿射集與凸集
2．1．1 直線與線段
2．1．2 仿射集與仿射包
2．1．3 相對內部和相對邊界
2．1．4 凸集和凸包
2．1．5 錐與錐包
2．2 凸集的重要例子
2．2．1 超平面與半空間
2．2．2 歐氏球與橢球
2．2．3 多面體
2．2．3 多面體
2．2．5 範數錐
2．2．6 半正定錐
2．3 保凸運算
2．3．1 交集
2．3．2 仿射函數
2．3．3 透視函數及線性分式函數
2．4 廣義不等式
2．4．1 真錐與廣義不等式
2．4．2 廣義不等式的性質
2．4．3 最小
2．5 對偶範數與對偶錐
2．5．1 對偶範數
2．5．2 對偶錐
2．6 分離與支撐超平面
2．6．1 分離超平面定理
2．6．2 支撐超平面
2．7 總結與討論
參考文獻
第3章 凸函數
3．1 基本性質和例子
3．1．1 定義和基本性質
3．1．2 一階條件
3．1．3 二階條件
3．1．4 例子
3．1．5 上境圖
3．1．6 Jensen 不等式
3．2 保凸運算
3．2．1 非負加權和
3．2．2 仿射映射復合
3．2．3 復合函數
3．2．4 逐點最大和上確界
3．2．5 逐點最小和下確界
3．2．6 透視函數
3．3 擬凸函數
3．3．1 定義和例子
3．3．2 修正的 Jensen 不等式
3．3．3 一階條件
3．3．4 二階條件
3．4 關於廣義不等式的單調性
3．5 關於廣義不等式的凸性
3．6 總結與討論
參考文獻
第4章 凸優化問題
4．1 優化問題的標準型
4．1．1 部分專業術語
4．1．2 最優值和最優解
4．1．3 等價問題和可行問題
4．2 凸優化問題
4．2．1 全局最優性
4．2．2 最優準則
4．3 等價表示與變換
4．3．1 等價問題：上境圖形式
4．3．2 等價問題：消除等式約束
4．3．3 等價問題：函數變換
4．3．4 等價問題：變量變換
4．3．5 復變量問題的重構
4．4 廣義不等式意義下的凸優化問題
4．4．1 廣義不等式意義下的凸優化問題
4．4．2 向量優化
4．5 擬凸優化
4．6 分塊連續上界最小化
4．6．1 穩定點
4．6．2 分塊連續上界最小化
4．7 連續凸近似
4．8 總結與討論
參考文獻
第5章 幾何規劃
5．1 一些基礎知識
5．2 幾何規劃
5．3 凸幾何規劃
5．4 縮合法
5．4．1 連續 GP 近似
5．4．2 物理層秘密通信
5．5 總結與討論
參考文獻
第6章 線性規劃和二次規劃
6．1 線性規劃（LP）
6．2 LP 應用實例
6．2．1 食譜問題
6．2．2 Chebyshev 中心
6．2．3 -範數近似問題
6．2．4 -範數近似問題
6．2．5 行列式最大化
6．3 線性規劃/凸幾何在盲源分離中的應用
6．3．1 基於 LP 的獨立信源 nBSS
6．3．2 基於線性規劃的高光譜分解
6．3．3 基於單純形幾何的高光譜分解
6．4 二次規劃
6．5 高光譜圖像分析中的 QP 和凸幾何理論應用
6．5．1數目估計的 GENE-CH 算法
6．5．2數目估計的 GENE-AH 算法
6．6 二次約束二次規劃
6．7 QP 和 QCQP 在波束成形設計中的應用
6．7．1 接收波束成形：平均旁瓣能量最小化
6．7．2 接收波束成形：最大旁瓣能量最小化
6．7．3 QCQP 在認知無線電發射波束成形設計中的應用 ．
6．8 總結與討論
參考文獻
第7章 二階錐規劃
7．1 二階錐規劃
7．2 魯棒線性規劃
7．3 概率約束的線性規劃
7．4 魯棒最小二乘逼近
7．5 基於二階錐規劃的魯棒接收波束成形
7．5．1 最小方差波束設計
7．5．2 基於二階錐規劃的魯棒波束成形
7．6 基於二階錐規劃的下行波束成形
7．6．1 功率最小化準則下的波束成形
7．6．2 最大最小公平準則下的波束成形
7．6．3 多小區波束成形
7．6．4 家庭基站波束成形
7．7 總結與討論
參考文獻
第8章 半正定規劃
8．1 半正定規劃
8．2 利用 Schur 補將 QCQP 和 SOCP 轉化為 SDP
8．3 S-引理（S-procedure）
8．4 SDP 在組合優化中的應用
8．4．1 Boolean 二次規劃
8．4．2 實例 I：MAXCUT
8．4．3 實例 II：ML MIMO 檢測
8．4．4 基於半正定松弛的 BQP 近似
8．4．5 實例 III：高階 QAM OSTBC 非相干 LFSDR 方法
8．5 SDR 在發射波束成形設計中的應用
8．5．1 下行廣播信道的波束成形
8．5．2 認知無線電的發射波束成形
8．5．3 安全通信中的發射波束成形設計：人工噪聲輔助法
8．5．4 最壞情況魯棒發射波束成形：單小區 MISO 場景
8．5．5 最壞情況魯棒發射波束成形：多小區 MISO 場景
8．5．6 中斷約束下 MISO 干擾信道的協作波束成形：集中式算法 242
8．5．7 中斷約束下 MISO 干擾信道的協作波束成形：基於 BSUM 的高效算法
8．5．8 中斷約束下的魯棒發射波束成形：單小區 MISO 場景 255
8．5．9 中斷約束下的魯棒發射波束成形：多小區 MISO 場景 260
8．6 總結與討論
參考文獻
第9章 對偶
9．1 Lagrange 對偶函數和共軛函數
9．1．1 Lagrange 對偶函數
9．1．2 共軛函數
9．1．3 Lagrange 對偶函數和共軛函數之間的關繫
9．2 Lagrange 對偶問題
9．3 強對偶性
9．3．1 Slater 條件
9．3．2 S-引理（S-lemma）
9．4 強對偶性的含義
9．4．1 強對偶性和弱對偶性的最大{最小特性
9．4．2 次優條件
9．4．3 互補松弛
9．5 Karush-Kuhn-Tucker（KKT）最優性條件
9．6 Lagrange 對偶優化
9．7 交替方向乘子法（ADMM）
9．8 廣義不等式問題的對偶性
9．8．1 Lagrange 對偶和 KKT 條件
9．8．2 錐規劃的 Lagrange 對偶和 KKT 條件
9．8．3 SDP 的 Lagrange 對偶和 KKT 條件
9．9 擇一性定理
9．9．1 弱擇一性
9．9．2 強擇一性
9．9．3 S-引理（S-procedure）的證明
9．10 總結與討論
參考文獻
第10章 內點法
10．1 不等式和等式約束下的凸問題
10．2 Newton 法和障礙函數
10．2．1 等式約束下的 Newton 法
10．2．2 障礙函數
10．3 中心路徑
10．4 障礙法
10．5 原-對偶內點法
10．5．1 原-對偶搜索方向
10．5．2 代理對偶間隙
10．5．3 原-對偶內點法
10．5．4 原-對偶內點法解決半正定規劃問題
10．6 總結與討論
參考文獻
附錄A 凸優化求解工具
A．1 SeDuMi
A．2 CVX
A．3 有限脈衝響應（FIR）濾波器的設計
A．3．1 問題構造
A．3．2 利用 SeDuMi 解決問題
A．3．3 利用 CVX 解決問題
A．4 結論
參考文獻
索引

前言

凸優化已經成為解決諸多科學與工程問題的有效工具之一。近20年來，凸優化被成功且廣泛地應用於解決信號處理、 多輸入多輸出（MIMO）無線通信和網絡中的各種問題，前者包括生物醫學和高光譜圖像分析中的盲源分離（BSS）問題，後者包括相干/非相干檢測、發射/魯棒/分布式的波束賦形設計、物理層安全通信等。尤其需要看到，當前4G繫統已經大規模商用，諸如大規模MIMO、毫米波通信、全雙工MIMO、注重能效的多小區協作波束賦形等5G相關技術也得到深入研究。從公開資料和文獻中，我們可以看到此類研究廣泛地使用凸優化工具。這都充分地顯示了凸優化理論在5G研發以及各類跨 學科的科學與工程應用中的關鍵作用。

從2008年春季開始，作者在臺灣清華大學（NTHU）開始執教“無線通信的優化設計”這一研究生課程。與其他課程類似，作者也為此準備了相應的教學講義。起初的教學講義基本上是基於Convex Optimization（Stephen Boyd和Lieven Vandenberghe著，劍橋大學出版社，2004年版）這一經典教材編寫的，此外也融入了部分公開發表的研究成果，以及作者之前同事馬榮健教授（目前為香港中文大學教授，於2005年8月至2007年7月在NTHU執教該課程） 提供的部分材料。

作者根據多年的教學經驗了解到，許多工科學生不能將數學理論與實際應用之間進行切實的聯繫，所以在抽像的數學理論面前往往會茫然無措。慢慢地，他們就失去了學習強大的數學理論和工具的動力，久而久之也使得他們不能利用所學的數學來研究、解決具體問題。為了幫助學生充分掌握凸優化這一強大的數學工具，作者試圖通過該課程的講義構建起從基礎數學理論到實際應用的橋梁。在本書中，作者對這些講義、材料結集出版，並真誠地希望讀者，特別是學習該工具的學生可以通過本書而有所受益。

在過去的十年中，就“信號處理與通信的凸優化理論”這一課程，作者基於所編寫的講義在國內的一些主要大學進行了10多次的短期課程教學，如山東大學（2010年1月）、清華大學（2010年8月和2012年8月）、天津大學（2011年8月）、北京交通大學（2013年7月和2015年7月）、電子科技大學（2013年11月、2014年9月和2015年9月）、廈門大學（2013年12月）和中山大學（2015年8月）等。這些短期課程與學術會議、研討會、座談會等傳統的短期課程截然不同，後者往往受限於時間而隻能通過幻燈片對相關內容進行概要性的介紹，缺乏具體的細節。而本人教授的短期課程則是在連續兩周的時間內，通過32學時的時間對凸優化理論中幾乎所有的理論、證明、例子、算法設計與實現，以及最新的研究應用進行具體的介紹。這使得整個短期課程猶如一次完整的探索學習之旅，而不僅僅是學習一門純粹的數學課程。在課程結束時，聽眾可以進一步通過期末課程設計來解決一個實際問題，從而獲得親身實踐的經驗。這些年的短期課程過程中，聽眾也給了作者很多積極、正面的反饋，目前他們中的很多人已然成為利用凸優化進行研究的專家，在多個領域迸發出了諸多的研究突破和成功應用。

本書介紹了凸優化的基礎理論和實際應用，並強調兩者的平衡。本書適合於需要學習“凸優化”或者“非線性優化”以解決優化問題，並更希望了解數學與應用之橋梁的一年級工程類專業研究生。當然，諸如線性代數、矩陣論、微積分等課程是閱讀本書的數學基礎。如果您計劃利用本書進行一學期的課程教學，那麼基於本人多年的教學經驗，作者提供如下的建議。首先，在第1 章～第4章的教學之後進行一次期中考試。 其次，第5章～第8章中的應用可以選擇性地進行介紹，然後布置一次課程設計作業，請學生以1～2人為一組研讀一篇論文。這一作業的目的是讓學生利用所學的知識解決實際的具體問題，從而掌握指定論文中涉及的所有理論、分析和仿真/實驗結果。然後進行第9章～第10章的教學。最後安排一次期末考試，並請每組學生將其課程設計進行口頭報告。經過這些年的多次教學實踐，作者認為這種做法可以充分鼓舞學生，對學生比較有益。

本書包含10章和1個附錄，基本上以因果順序進行編寫，即深入學習每章時都需要充分學習並掌握前面章節中介紹的知識。

第1章介紹了隨後章節中需要使用的一些數學基礎。第2章介紹凸集。第3章介紹的凸函數是隨後第4章內容的基礎。第4章介紹凸問題和問題重構。第2～第4章內容都給出了許多具體的例子。

接下來介紹一些典型的凸優化問題（或簡稱為凸問題），包括第5章介紹的幾何規劃 (GP)，第6章介紹的線性規劃（LP）、二次規劃（QP）和二次約束二次規劃（QCQP），第7章介紹的二階錐規劃（SOCP），第8章介紹的半定規劃（SDP）。其中幾何規劃問題看似非凸，實則可以轉化為一個凸問題。在這些章節中，讀者可以看到第2章～第4章介紹的基本知識將如何正確、有效地應用於通信和/或信號處理中的實際問題。針對所考慮的問題，本書給出了其中的關鍵思想、理念和重要的轉化步驟。同時為了讓讀者從直觀上理解算法的精度和有效性，也選擇性地給出了一些具有代表性的仿真結果，以及基於生物醫學、高光譜圖像實際數據的實驗結果。當然，讀者可以通過閱讀具體的研究論文來進一步了解細節，從而完全地掌握如何將優化理論應用於具體的研究。由於SDP已廣泛應用於無線通信和網絡的優化設計，因此在第8章中特別介紹了一些更具挑戰性的應用，其中各種復雜的SDP優化問題也正是當前5G研發中普遍存在和關注的核心問題。

第9章引入的“對偶”至關重要，與第2章～第4章介紹的內容互相補充。 這是因為針對不同的凸優化問題，有些適合使用之前介紹的最優性條件進行求解，有些則更適合使用第9章介紹的Karush-Kuhn-Tucker（KKT）條件進行有效的求解。此外，根據作者的經驗，對具體優化問題所設計的算法進行解析的性能評估和復雜性分析，無論是對算法設計還是對未來研究的突破方面都具有重要的意義。這些分析可以定性和定量地證明和解釋模擬和實驗結果，從而為所設計算法的適用性提供一個堅實的基礎，而這些分析往往非常依賴於微妙的對偶理論。另外，一旦將優化問題轉化為了一個凸問題，就可以利用現成的凸優化工具包，如CVX和SeDuMi來求解。CVX和SeDuMi工具包的使用在附錄A中進行介紹。這些工具包在研究階段可能足夠我們的需求，但在實時處理或在線處理等實際應用場景下，工具包就不一定適合於實際的需求了。因此，第10章介紹了內點法。內點法實際上是試圖在數值上解決第9章介紹的KKT條件。內點法已被廣泛用於求解具體的凸優化問題，並可以提供更加有效的計算性能。

對整個教學講義的整理不僅需要大量的精力，也需要大量的時間。本書得以結集出版，還要歸功於作者許多學生的努力和投入，他們包括我以前的博士學生，如ArulMurugan Ambikapathi博士、王堃宇博士、李威錆博士、林家祥博士。我以前的碩士學生，如邱奕霖、瀋郁瑄、Tung-Chi Ye和Yu-Ping Chang等則幫助繪制了本書中很多的示意圖。作者衷心感謝他們的奉獻精神和辛勤工作。作者還需特別感謝以前的同事馬榮健教授，博士生張縱輝博士、詹宗翰博士，訪問學者Fei Ma博士，訪問博士生陳翔博士、瀋超博士、秦浩浩博士、何飛博士、徐桂賢、張凱、陸揚、Christian Weiss，來訪的碩士生李磊和歐澤良，以及其他所有直接或間接提供幫助的研究生。