线性锥优化是线性规划的延伸,也是非线性规划,尤其是二次规划的一种新型研究工具,其理论性强,应用面广,值得深入研究。本书系统地介绍了线性锥优化的相关理论、模型和计算方法,主要内容包括:线性锥优化简介、基础知识、最优性条件与对偶、可计算线性锥优化、二次函数锥规划、线性锥优化近似算法、应用案例和内点算法软件介绍等。
本书不仅包含了线性规划、二阶锥规划和半定规划等基本模型,还引进二次函数锥规划来探讨更一般化的线性锥优化模型。同时,在共辄对偶理论的基础上,系统地建立了线性锥优化的对偶模型,分析了原始与对偶模型之间的强对偶性质。本书的主要内容来源于我们研究小组近些年工作总结,一些研究结果还非常初始,仍然具有较新的研究价值和可能的扩展空间。
样章试读
目录
- 目录
第1章 引论 1
1.1 线性规划 1
1.2 Torricelli点问题 3
1.3 相关阵满足性问题 4
1.4 最大割问题 5
1.5 小结及相关工作 7
第2章 基础知识 9
2.1 集合、向量与空间 9
2.2 集合的凸性与锥 18
2.3 对偶集合 35
2.4 函数 38
2.5 共辄函数 46
2.6 可计算性问题 52
2.7 小结及相关工作 56
第3章 最优性条件与对偶 57
3.1 最优性条件 57
3.2 约束规范 67
3.3 Lagrange对偶 73
3.4 共辄对偶 79
3.5 线性锥优化模型及最优性 89
3.6 小结及相关工作 96
第4章 可计算线性锥优化 98
4.1 线性规划 98
4.2 二阶锥规划 99
4.2.1 一般形式 103
4.2.2 二阶锥可表示函数/集舍 106
4.2.3 常见的二阶锥可表示函数/集合 108
4.2.4 凸二次约束二次规划 110
4.2.5 鲁棒线性规划 111
4.3 半定规划 112
4.3.1 半定规划松弛 120
4.3.2 秩一分解 122
4.3.3 随机近似方法 125
4.4 内点算法简介 127
4.5 小结及相关工作 141
第5章 二次函数锥规划 142
5.1 二次约束二次规划 142
5.2 二次函数锥规划 149
5.3 可计算松弛或限定方法 158
5.4 二次约束二次规划最优解的计算 161
5.4.1 全局最优性条件 162
5.4.2 可解类与算法 168
5.4.3 算例 170
5.4.4 KKT条件及全局最优性条件讨论 172
5.5 小结及相关工作 172
第6章 线性锥优化近似算法 175
6 1 线性化重构技术 176
6.2 有效冗余约束 187
6.2.1 C=Sn+1+和C=Sn+1++Nn+1的情况 194
6.2.2 冗余约束算法及算例 197
6.3 椭球覆盖法 199
6.3.1 近似计算的基本理论 200
6.3.2 自适应逼近方案 203
6.3.3 敏感点与自适应逼近算法 205
6.3.4 算法与应用 208
6.4 二阶锥覆盖法 212
6.4.1 二阶锥的线性矩阵不等式表示 212
6.4.2 二阶锥覆盖的构造 215
6.4.3 二阶锥覆盖在协正规划中的应用 217
6.5 小结及相关工作 224
第7章 应用案例 225
7.1 线性方程组的近似解 225
7.2 投资管理问题 230
7.3 单变量多项式优化 233
7.4 鲁棒优化 235
7.5 协正锥的判定 238
7.6 小结 245
附录 CVX使用简介 247
A.1 使用环境和典型命令 247
A.2 可计算凸优化规则及核心函数库 254
A.3 参数控制及核心函数的扩展 258
A.4 小结 262
参考文献 263
索引 268
《运筹与管理科学丛书》已出版书目 273