日录 第1章最优化绪论 1.1最优化概述 1.2最优性条件 > 第2章线性规划 0 2.1基本模型 10 16 2.3付偶理论 22 第3章网络流与动态规划 26 3.1网络最优化 3.2流的相关问题 34 33动态规划. 第4章无约束最优化 43 4.1一维搜索.. 43 4.2梯度方法 43牛顿方法.... 51 4.4信赖域法 55 第5章有约束最优化 58 5.1二次规划.. 58 5.2逐步二次规 ……。。4…。。。·。。。……。·…。。。。…。。…·。…··。。……。。。。… 53罚函数。。 68 5.4内点法 71 第6章凸优化 75 6.1凸函数... 6.2对偶性质 6.3数值解法....，. 6 第7章大数据中的优化 7.1稀疏优化 93 7.2随机梯度法 98 7.3批次梯度法 105 7.4随机牛顿法 7.5更多常用算法 ....,..114
目录 第 1 章 最优化绪论 1 1.1 最优化概述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 最优性条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 下降算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 第 2 章 线性规划 10 2.1 基本模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 单纯形法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 对偶理论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 第 3 章 网络流与动态规划 26 3.1 网络最优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2 流的相关问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.3 动态规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 第 4 章 无约束最优化 43 4.1 一维搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2 梯度方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.3 牛顿方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.4 信赖域法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 第 5 章 有约束最优化 58 5.1 二次规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.2 逐步二次规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.3 罚函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.4 内点法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 第 6 章 凸优化 75 6.1 凸函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.2 对偶性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6.3 数值解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 第 7 章 大数据中的优化 93 7.1 稀疏优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 7.2 随机梯度法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 7.3 批次梯度法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 7.4 随机牛顿法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 7.5 更多常用算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
目 第8章总结 121 附录A数学基础 122 A1分析…………………·…·… 122 A2代数，123 附录B数学进阶 126 附录C参考资料 129
目录 第 8 章 总结 121 附录 A 数学基础 122 A.1 分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 A.2 代数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 附录 B 数学进阶 126 附录 C 参考资料 129 ii
第1章最优化绪论 内容提要 口运筹学简介 口算法改效村刘画 口最优化的数学表达 口算法评价方式 口无约束问题最优条件 口选代下降基本算法 口约束问题最优条件 1.1最优化概述 111运筹学简介 运筹学(Operations Research,.OR)是从二十世纪三四十年代（即二战期间）发展起来的一门应用性 很强的学科。它的研究对象是人类对各种资源的运用及筹划活动，如战争、后勤、生产规划、经营管 理、资本运作、工程设计等。研究内容就是资源筹划活动中各种问题的模型化及其数学方法，学科分 支包括： 。线性规划Leontief,1932] 。非线性规划[Kuhn Tucker,l95l] 。整数规划IGoMory,1958) 。目标规划Pareto.18961 。动态规划Bellman,.1957] 。图论与网络分析Euler,1736 。网络计划[Gant,1917刀 。存储论Harris,1915] 。排队论Erlang,1909 。博弈论Neumann,1928 。决策论Bernoulli.1738 。启发式算法[1940s] 运筹学的主要分析过程包括定性分析与定量分析。定性分析往往是解决问题的第一步，具体来说 即主要决策的内容、不同方案有效性的度量与比较各方案时度量间可能的权衡；与之相对，管理决策 过程时往往需要的是定量分析，标准步骤是： I.表达问题Definition of the problem] 列出问题的要素，其中包含可控的变量[决策变、不可控的变量[参数、各变量的约束条件与 确定最佳方案采用的目标度量。 2.建立模型[Construction of the model] 将上方四个要素的关系用一定的数学模型进行刻画。 3.分析求解Solution of the model]
第 1 章 最优化绪论 内容提要 h 运筹学简介 h 最优化的数学表达 h 无约束问题最优条件 h 约束问题最优条件 h 算法收敛性刻画 h 算法评价方式 h 迭代下降基本算法 1.1 最优化概述 1.1.1 运筹学简介 运筹学 (Operations Research, OR) 是从二十世纪三四十年代 (即二战期间) 发展起来的一门应用性 很强的学科。它的研究对象是人类对各种资源的运用及筹划活动，如战争、后勤、生产规划、经营管 理、资本运作、工程设计等。研究内容就是资源筹划活动中各种问题的模型化及其数学方法，学科分 支包括： 线性规划 [Leontief, 1932] 非线性规划 [Kuhn Tucker, 1951] 整数规划 [GoMory, 1958] 目标规划 [Pareto, 1896] 动态规划 [Bellman, 1957] 图论与网络分析 [Euler, 1736] 网络计划 [Gantt, 1917] 存储论 [Harris, 1915] 排队论 [Erlang, 1909] 博弈论 [Neumann, 1928] 决策论 [Bernoulli, 1738] 启发式算法 [1940s] …… 运筹学的主要分析过程包括定性分析与定量分析。定性分析往往是解决问题的第一步，具体来说 即主要决策的内容、不同方案有效性的度量与比较各方案时度量间可能的权衡；与之相对，管理决策 过程时往往需要的是定量分析，标准步骤是： 1. 表达问题 [Definition of the problem] 列出问题的要素，其中包含可控的变量 [决策变量]、不可控的变量 [参数]、各变量的约束条件与 确定最佳方案采用的目标度量。 2. 建立模型 [Construction of the model] 将上方四个要素的关系用一定的数学模型进行刻画。 3. 分析求解 [Solution of the model]
11最优化概述 分析模型并用各种数学方法和手段来求解模型，进而确定解对模型的技术条件的灵敏度。 4.检验与改进Validation of the model] 将模型的解应用到实际问颗中，检验解的合理性和有效性.可能产生的问颗和修改模型。 5.解的实施mplementation of the solution] 将模型的解应用于实际问题，并最终解决实际问题。 其中，建立模型的过程非常重要。它将实际问题简化、抽象为了反映实际问题的数学模型，而通 过求解数学模型得到的结果可以返回到实际问题中检验。，各种优化模型与求解它们的数学方法构成了 运筹学的大部分内容，微分方程模型、统计模型、最优化模型等都是可供选择的代表性模型，但有限 的模型并不能完全适用于所有实际问题。 一般的运筹学参考书不会着重叙述建立模型的过程，这并不是说建模不重要；相反，建模在任何时候 任何场合都是极其重要的。 1.1.2最优化问题 在很多实际应用问题中，从数学上看都是非适定ll-posed]的，即解不唯一。对于这样的实际问题 人们住往通过制定相应的目标准则，然后从众多的解中选出在一定条件下最好的解。而这，正是最优 化理论与方法所研究的内容。本节对最优化的基本概念作一些简要的介绍，并给出最优化建模方法的 相关知识。 最优化讨论的是为找出实际问题的最优解决策略而采取的模型化及方法，其过程是：先把待解决 的问题用最优化形式描述为在给定的约束条件下找出使某个目标函数达到最大小值的解，再采用数学 上严密的算法来求解。 最优化方法作为数学工具已在现实中被广泛应用，大多数代表性的算法也都有程序库与软件包。但是 有效利用这些成果的前提是待解决问题已化为最优化问题的形式，而转化的过程并不简单。 最优化方法在生产规划、经济管理、工业工程、交通运输、国防等重要领域中都有着广泛的应用 并已受到政府部门、科研机构和产业界的高度重视。例如，运筹学和计算几何的交叉分支“选址问题” 就关联到许多现实的选址模型。 此外，很多机器学习任务本质上都是最优化问题，如监督学习中的回归、分类，无监督学习中的 聚类等等"Optimization lies at the heart of machine learning")。 在数学上，最优化一般的描述是：在给定的约束条件[constraint]下，找出决策变量[decision variable] 的一个值，使得被称为目标函数[objective function]的表达愿望尺度的函数值达到最值。由于决策变量 般有多个，可以用向量x=(1,,工n)T来表示，于是问题写为： minf(z)s.t. (1.1) 目标函数∫是定义在包含S的适当集合中的实值函数。 若所需的是最大位，利用maxg(x)=一min(-g(r)可以转化为上方的形式。 定义1.1（可行域） 在式(1.1)中，S是问题变量x的可取值之集合，称为问题的可行城。 若S=R”,则问题为minre贯mf(x),称为无约束最优化问题，否则称为带约束最优化问题。 从属性上，最优化问题可以分为两大类，一类是具有离散变量（也即可行域是有限个点）的问题 又称为组合优化问题；另一类则是我们讨论的重点，具有连续变量的优化问题。这样的问题通常可写
1.1 最优化概述 分析模型并用各种数学方法和手段来求解模型，进而确定解对模型的技术条件的灵敏度。 4. 检验与改进 [Validation of the model] 将模型的解应用到实际问题中，检验解的合理性和有效性，可能产生的问题和修改模型。 5. 解的实施 [Implementation of the solution] 将模型的解应用于实际问题，并最终解决实际问题。 其中，建立模型的过程非常重要。它将实际问题简化、抽象为了反映实际问题的数学模型，而通 过求解数学模型得到的结果可以返回到实际问题中检验。各种优化模型与求解它们的数学方法构成了 运筹学的大部分内容，微分方程模型、统计模型、最优化模型等都是可供选择的代表性模型，但有限 的模型并不能完全适用于所有实际问题。 一般的运筹学参考书不会着重叙述建立模型的过程，这并不是说建模不重要；相反，建模在任何时候 任何场合都是极其重要的。 1.1.2 最优化问题 在很多实际应用问题中，从数学上看都是非适定 [ill-posed] 的, 即解不唯一。对于这样的实际问题， 人们往往通过制定相应的目标准则，然后从众多的解中选出在一定条件下最好的解。而这，正是最优 化理论与方法所研究的内容。本节对最优化的基本概念作一些简要的介绍，并给出最优化建模方法的 相关知识。 最优化讨论的是为找出实际问题的最优解决策略而采取的模型化及方法，其过程是：先把待解决 的问题用最优化形式描述为在给定的约束条件下找出使某个目标函数达到最大/小值的解，再采用数学 上严密的算法来求解。 最优化方法作为数学工具已在现实中被广泛应用，大多数代表性的算法也都有程序库与软件包。但是， 有效利用这些成果的前提是待解决问题已化为最优化问题的形式，而转化的过程并不简单。 最优化方法在生产规划、经济管理、工业工程、交通运输、国防等重要领域中都有着广泛的应用， 并已受到政府部门、科研机构和产业界的高度重视。例如，运筹学和计算几何的交叉分支“选址问题”， 就关联到许多现实的选址模型。 此外，很多机器学习任务本质上都是最优化问题，如监督学习中的回归、分类，无监督学习中的 聚类等等 (”Optimization lies at the heart of machine learning”)。 在数学上，最优化一般的描述是：在给定的约束条件 [constraint] 下，找出决策变量 [decision variable] 的一个值，使得被称为目标函数 [objective function] 的表达愿望尺度的函数值达到最值。由于决策变量 一般有多个，可以用向量 x = (x1, . . . , xn) T 来表示，于是问题写为： min f(x) s.t. x ∈ S ⊂ R n (1.1) 目标函数 f 是定义在包含 S 的适当集合中的实值函数。 若所需的是最大值，利用 max g(x) = − min(−g(x)) 可以转化为上方的形式。 定义 1.1 (可行域) ♣ 在式 (1.1) 中，S 是问题变量 x 的可取值之集合，称为问题的可行域。 若 S = R n，则问题为 minx∈Rn f(x)，称为无约束最优化问题，否则称为带约束最优化问题。 从属性上，最优化问题可以分为两大类，一类是具有离散变量 (也即可行域是有限个点) 的问题， 又称为组合优化问题；另一类则是我们讨论的重点，具有连续变量的优化问题。这样的问题通常可写 2
12录优性条件 min f(x) s.t.gi()=0 i={1...,m} (1.2) c(x)20 ieI 其中c(工)为约束函数，￡，1分别为等式约来与不等式约来的指标集合。 定义12（线性规划 当目标函数与约束函数都是线性函数时，最优化问题称为线性规划[Lincar Programming],否则 称为非线性规划Nonlinear Programming]。 根搭决策变量、目标西数和要求的不同，最优化还被分为整数规划、动态规划、网络规划、非光滑规 划、随机规划、多目标规划等 对一般的非线性规划问题，式(1.2)的，都是n变量的确定的实值函数，且c一般个数有限。f 与中至少有一个是非线性的。 定义13（可行解、最优解） 式(1.1)中满足约来条件x∈S的x称为问题的可行解[feasible solutionl 若可行解x进一步满足f(z)≤fz),z∈S,则x称为问题的全局最优解[global optimal solutionl 此外，若可行解x满足f(r)≤f(),江∈SnU(),其中U(x)代表包含x的某邻城，则 r称为问题的局部最优解local optimal solution]。 不少问题的目标函数或约束条件可能很复杂，导致找出全局最优解非常困难。这时，目标往往是 求出局部的最优解。而具体的相关研究分为两个方面：一是研究最优解的性质，二是设计有效算法来 获得问题的解。 1.2最优性条件 12.1无约束问题的最优条件 问题的最优解所满足的必要或者充分条件称为最优性条件，它为最优化问题求解算法的设计、分 析提供必不可少的理论基础。对于无约束最优化问题，最优条件的形式较为简洁的： 定理1.4（无约束向愿的极值条件） 一阶必要条件：f(x)在点量处可微，若其为极小值，则又f()=0。 二阶必要条件：f)在点无处二阶可微，若其为极小值，则Vf()=0,且7f()半正定。 二阶充分条件：f(x)在点亚处二阶可微，若7f()=0,且V2f()正定，则其为极小值。 证明一阶必要条件：若f可微，其可在元邻域展开为 f(+at)=f()+avf()t+O(a2) 于是若极小值点Vf(①)≠0，取t=-Vf(),在a充分小时即有f(①)>f(任+a),矛盾
1.2 最优性条件 为 min f(x) s.t. gi(x) = 0 i ∈ E = {1, . . . , m} ci(x) ≥ 0 i ∈ I (1.2) 其中 ci(x) 为约束函数，E, I 分别为等式约束与不等式约束的指标集合。 定义 1.2 (线性规划) ♣ 当目标函数与约束函数都是线性函数时，最优化问题称为线性规划 [Linear Programming]，否则 称为非线性规划 [Nonlinear Programming]。 根据决策变量、目标函数和要求的不同，最优化还被分为整数规划、动态规划、网络规划、非光滑规 划、随机规划、多目标规划等。 对一般的非线性规划问题，式 (1.2) 的 f, ci 都是 n 变量的确定的实值函数，且 ci 一般个数有限。f 与 ci 中至少有一个是非线性的。 定义 1.3 (可行解、最优解) ♣ 式 (1.1) 中满足约束条件 x ∈ S 的 x 称为问题的可行解 [feasible solution]。 若可行解 x ∗ 进一步满足 f(x ∗ ) ≤ f(x), ∀x ∈ S，则 x ∗ 称为问题的全局最优解 [global optimal solution]。 此外，若可行解 x ∗ 满足 f(x ∗ ) ≤ f(x), ∀x ∈ S ∩ U(x ∗ )，其中 U(x ∗ ) 代表包含 x ∗ 的某邻域，则 x ∗ 称为问题的局部最优解 [local optimal solution]。 不少问题的目标函数或约束条件可能很复杂，导致找出全局最优解非常困难。这时，目标往往是 求出局部的最优解。而具体的相关研究分为两个方面：一是研究最优解的性质，二是设计有效算法来 获得问题的解。 1.2 最优性条件 1.2.1 无约束问题的最优条件 问题的最优解所满足的必要或者充分条件称为最优性条件，它为最优化问题求解算法的设计、分 析提供必不可少的理论基础。对于无约束最优化问题，最优条件的形式较为简洁的： 定理 1.4 (无约束问题的极值条件) ♡ 一阶必要条件：f(x) 在点 x¯ 处可微，若其为极小值，则 ∇f(¯x) = 0。 二阶必要条件：f(x) 在点 x¯ 处二阶可微，若其为极小值，则 ∇f(¯x) = 0，且 ∇2f(¯x) 半正定。 二阶充分条件：f(x) 在点 x¯ 处二阶可微，若 ∇f(¯x) = 0，且 ∇2f(¯x) 正定，则其为极小值。 证明 一阶必要条件：若 f 可微，其可在 x¯ 邻域展开为 f(¯x + αt) = f(¯x) + α∇f(¯x) T t + O(α 2 ) 于是若极小值点 ∇f(¯x) ̸= 0，取 t = −∇f(¯x)，在 α 充分小时即有 f(¯x) > f(¯x + αt)，矛盾。 3