信号处理与通信中的凸优化: 从基础到应用

本书旨在帮助需要学习“凸优化”或者“非线性优化”方法以解决信号处理与通信领域中相关优化问题的工程类专业研究生、学者和工程技术人员。本书构建起了从基础数学理论到实际应用之间的桥梁，并强调两者的平衡，一共包括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，来访的硕士生李磊和欧泽良，以及其他所有直接或间接提供帮助的研究生。