最优化模型与算法――基于PYTHON实现

本书介绍了很优化模型的基础知识，梳理了大数据和人工智能时代涌现出来的很优化算法，使用Python语言给出算法的代码，展示了若干实例。本书主要内容包括很优化模型基础知识和很优化算法两部分，介绍了凸集合、凸函数、凸优化模型、对偶理论，梳理了梯度下降法、牛顿法、Lagrange 乘子法、DC 规划算法、梯度投影法、随机梯度下降法、在线梯度下降法等优化算法。本书的读者只需要具备微积分和线性代数的基础知识即可。读者可登录华信教育资源网免费下载书中案例的源代码。

目    录 第1章 凸集合 1 1.1 仿射集、凸集和凸锥 1 1.1.1 直线与线段 1 1.1.2 仿射集 1 1.1.3 仿射维数与相对内部 3 1.1.4 凸集合 3 1.1.5 凸锥 5 1.2 凸集合的示例 5 1.2.1 超平面和半空间 5 1.2.2 欧氏球和椭球 6 1.2.3 范数球和范数锥 7 1.2.4 多面体 7 1.2.5 半正定锥 7 1.3 保持凸性的运算 8 1.3.1 交集 8 1.3.2 仿射变换 8 1.4 支撑超平面 10 1.5 对偶锥 10 练习题 11 参考文献 13 第2章 凸函数 14 2.1 凸函数的定义和例子 14 2.1.1 凸函数的概念 14 2.1.2 凸函数的例子 18 2.1.3 强凸性 19 2.1.4 其他凸集合和凸不等式 20 2.2 保持凸性的运算 22 2.3 共轭函数 25 2.3.1 共轭函数的概念 25 2.3.2 共轭概念的理解 27 2.4 次梯度与次微分 27 2.4.1 次微分的概念 27 2.4.2 对偶 29 练习题 29 参考文献 32 第3章 凸优化模型 33 3.1 优化模型 33 3.1.1 基本术语 33 3.1.2 等价问题 34 3.2 标准形式及很优性条件 35 3.2.1 标准形式的凸优化问题 35 3.2.2 局部很优解与全局很优解 36 3.2.3 很优性条件 36 3.3 线性规划 38 3.3.1 标准型线性规划和不等式线性规划 38 3.3.2 线性规划转化为标准型 39 3.3.3 线性规划应用举例 39 3.4 二次规划模型 41 3.4.1 二次规划的例子 42 3.4.2 二阶锥规划 44 3.5 几何规划 44 3.5.1 几何规划的扩展 45 3.5.2 几何规划转化为凸优化问题 45 3.5.3 几何规划的例子 46 3.6 广义不等式约束 47 3.6.1 锥规划问题 47 3.6.2 半定规划 47 3.6.3 组合优化中的SDP 48 练习题 50 参考文献 52 第4章 对偶理论 53 4.1 Lagrange对偶函数 53 4.1.1 Lagrange函数 53 4.1.2 Lagrange对偶函数 53 4.1.3 很优值的下界 54 4.1.4 Lagrange对偶函数的例子 54 4.2 Lagrange对偶问题 55 4.2.1 对偶约束 55 4.2.2 弱对偶性 57 4.2.3 强对偶性与Slater约束规范 57 4.3 Lagrange对偶的理解 58 4.3.1 鞍点 58 4.3.2 博弈论解读 58 4.4 很优性条件 59 4.4.1 非凸问题的KKT条件 60 4.4.2 凸问题的KKT条件 60 4.4.3 通过对偶求解优化问题 61 练习题 62 参考文献 64 第5章 非凸优化算法 65 5.1 全局优化算法的复杂度 65 5.2 优化算法构造思想 68 5.3 梯度下降法 69 5.4 牛顿法 78 5.4.1 牛顿法思想 79 5.4.2 梯度下降法与牛顿法的关系 82 5.5 拟牛顿法 84 5.6 共轭梯度法 89 5.6.1 生成Q共轭方向 92 5.6.2 共轭梯度迭代公式 93 5.7 最小二乘问题 95 5.7.1 高斯-牛顿法 95 5.7.2 高斯-牛顿法与牛顿法的关系 96 5.7.3 增量梯度方法 97 5.8 Lagrange乘子法 98 5.8.1 二次惩罚函数法 100 5.8.2 拉格朗日乘子估计-不准确最小化 100 5.8.3 关于条件数较大的问题 101 5.8.4 乘子方法的主要思想 102 5.9 DC规划算法及CCCP算法 104 5.10 进化算法 107 应用案例5.1：CCCP算法求解基于ramp损失的二分类问题 113 练习题 118 参考文献 119 第6章 凸优化算法 120 6.1 梯度投影法 120 6.1.1 基于投影方法的可行方向和步长规则 120 6.1.2 步长选择和收敛性 121 6.1.3 收敛速度 122 6.2 坐标下降法 123 6.2.1 算法 123 6.2.2 收敛性 123 6.2.3 有利于使用坐标下降法的问题结构 125 6.3 迫近梯度法 126 6.3.1 正则化模型的方法 126 6.3.2 使用凸正则项的一阶方法 127 6.4 交替方向乘子法 130 6.4.1 ADMM算法 130 6.4.2 收敛性 132 6.4.3 应用举例：ADMM方法求解Lasso问题 133 6.4.4 应用举例：ADMM算法求解Bi-convex问题 135 6.5 随机梯度下降法 137 6.5.1 随机优化方法与批处理优化方法 138 6.5.2 随机方法的动机 138 6.5.3 SG算法的收敛性分析 142 6.5.4 降噪-梯度聚合方法 144 6.5.5 二阶方法―高斯-牛顿法 148 6.5.6 动量梯度法 150 6.5.7 加速梯度法 151 6.6 在线凸优化 152 6.6.1 在线凸优化的基本框架 152 6.6.2 Follow-The-Leader 152 6.6.3 Follow-The-Regularized-Leader 154 6.6.4 在线梯度下降法 156 6.6.5 强凸正则子 158 6.6.6 在线镜像下降(OMD) 159 练习题 162 参考文献 163