日录 第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
12录优性条件 二阶必要条件：若于二阶可微，由一阶必要条件有 f+al)=f()+a2V"f(W+O(o) 由若V2f(x)非半正定，由定义存在t使得tTV2f(x)tf(运+a), 矛盾 二阶充分条件：由正定定义，对任何t,a272f(x)t>0,从而在a充分小时一定有f()0,由于所有可能t构成的集合（高维球面）是紧集，且 可验证a()连续性，存在a0=mi血ta()>0,于是{杠|x-0使得x+d∈S,以∈(0，)，则称d是S在x处 的可行方向，并记所有S在r处的可行方向集合为F(红，S) 对Rm上实函数f与向量工，非零向量d,若存在6>0使得f(x+d<f(r),以∈(0，)，则 称d为f在x处的下降方向，并记所有S在x处的下降方向集合为Do(红，S)。 若f可微，记所有满足Vf(x)Td<0的向量d构成D(红，f)
1.2 最优性条件 二阶必要条件：若 f 二阶可微，由一阶必要条件有 f(¯x + αt) = f(¯x) + 1 2 α 2 t T ∇2 f(x)t + O(α 3 ) 由若 ∇2f(x) 非半正定，由定义存在 t 使得 t T ∇2f(x)t f(¯x + αt)， 矛盾。 二阶充分条件：由正定定义，对任何 t，1 2 α 2 t T ∇2f(x)t > 0，从而在 α 充分小时一定有 f(¯x) 0，由于所有可能 t 构成的集合 (高维球面) 是紧集，且 可验证 α(t) 连续性，存在 α0 = mint α(t) > 0，于是 {x | ∥x − x¯∥ 0 使得 x + λd ∈ S, ∀λ ∈ (0, δ)，则称 d 是 S 在 x 处 的可行方向，并记所有 S 在 x 处的可行方向集合为 F(x, S)。 对 R n 上实函数 f 与向量 x，非零向量 d，若存在 δ > 0 使得 f(x + λd) < f(x), ∀λ ∈ (0, δ)，则 称 d 为 f 在 x 处的下降方向，并记所有 S 在 x 处的下降方向集合为 D0(x, S)。 若 f 可微，记所有满足 ∇f(x) T d < 0 的向量 d 构成 D(x, f)。 4
12最优性条件 至可行方向也即“这个方向还没有到边界”，下降方向也脚“∫沿此方向局部下降” 定理19儿何必要条件) 对约束最优化问题minre3fx,x'是问题的局部最优解，则F(x',S)nDo(x',S)=a。 当f可微时，D,f)CD(,D,此x是问题的局部最优解可推出F,S)nD(,S)= 明根据定义，若F(r*.S)∩D(x*,S)≠@，假设其中有方向d,取可行方向的6与下降方向的6的 最小值为0，则f(x*+d),入∈(0,6)中的每个点都是比f(x)更小的可行点，矛盾。利用一阶泰勒展 开与前文无约束最优化时相同可证D(x,f)CDo(x*,f),于是即得可微时结论。 下面，我们针对具体的可行域进行更细节的讨论。式(12)一般可以更进一步写为如下形式： min f() s.t.g()≥0i=1,,m (1.3) h(c)=0j=1..,l 比起式(12)，式(13)中的指标集合成为了有限集合，之后讨论的也基本是这种情况。此时，上方 的必要条件可以进一步细化： 命题110儿何必要条件-函数约束 记I()={9()=0,也即对不等式约束取等的指标集合。在式(1.3)中定义 Dy(r)={dl vf()Td0.ViEI(a)} Fh(z)={d|Vhj()Td=0,vj} 若x*为局部最优解，了，h,i∈T(x)与所有在x°可微，h,iI(x)在x'连续，且所有 Vh(),j=1,,l线性无关，则有 Di()nF()nEn(")=3 这个结论的证明需要一些精细而复杂的微分几何操作，此处略过。从这个定理出发，即可以得到 重要的Fiz-John条件 定理1.11下itz-John必要条件) 若x*为式(13)中的可行点，记I(x)={i|g(x)=0}. 连续性要求：，9，iI()与所有h在x可微，9，i生I()在x连续。 在满足上述要求时，若x°是局部最优解，则存在不全为0的0，入，i∈T(x*),4,j=1,,1使 得 AoVf(r)"-∑MVgm(r')-∑h,Vhg(r')=0 iI(x*) 且0≥0，M≥0，ieI(e). 证明若V(e)j=1,,1线性相关，可直接取合适的凸，0，入均为0即得结论
1.2 最优性条件 可行方向也即“这个方向还没有碰到边界”，下降方向也即“f 沿此方向局部下降”。 定理 1.9 (几何必要条件) ♡ 对约束最优化问题 minx∈S f(x)，x ∗ 是问题的局部最优解，则 F(x ∗ , S) ∩ D0(x ∗ , S) = ∅。 当 f 可微时，D(x ∗ , f) ⊂ D0(x ∗ , f)，因此 x ∗ 是问题的局部最优解可推出 F(x ∗ , S)∩D(x ∗ , S) = ∅。 证明 根据定义，若 F(x ∗ , S) ∩ D0(x ∗ , S) ̸= ∅，假设其中有方向 d，取可行方向的 δ 与下降方向的 δ 的 最小值为 δ0，则 f(x ∗ + λd), λ ∈ (0, δ) 中的每个点都是比 f(x ∗ ) 更小的可行点，矛盾。利用一阶泰勒展 开与前文无约束最优化时相同可证 D(x ∗ , f) ⊂ D0(x ∗ , f)，于是即得可微时结论。 下面，我们针对具体的可行域进行更细节的讨论。式 (1.2) 一般可以更进一步写为如下形式： min f(x) s.t. gi(x) ≥ 0 i = 1, . . . , m hj (x) = 0 j = 1, . . . , l (1.3) 比起式 (1.2)，式 (1.3) 中的指标集合成为了有限集合，之后讨论的也基本是这种情况。此时，上方 的必要条件可以进一步细化： 命题 1.10 (几何必要条件-函数约束) ♠ 记 I(x) = {i | gi(x) = 0}，也即对不等式约束取等的指标集合。在式 (1.3) 中定义 Df (x) = {d | ∇f(x) T d 0, ∀i ∈ I(x)} Fh(x) = {d | ∇hj (x) T d = 0, ∀j} 若 x ∗ 为局部最优解，f, gi , i ∈ I(x ∗ ) 与所有 hj 在 x ∗ 可微，gi , i /∈ I(x ∗ ) 在 x ∗ 连续，且所有 ∇hj (x ∗ ), j = 1, . . . , l 线性无关，则有 Df (x ∗ ) ∩ Fg(x ∗ ) ∩ Fh(x ∗ ) = ∅ 这个结论的证明需要一些精细而复杂的微分几何操作，此处略过。从这个定理出发，即可以得到 重要的 Fritz-John 条件： 定理 1.11 (Fritz-John 必要条件) ♡ 若 x ∗ 为式 (1.3) 中的可行点，记 I(x) = {i | gi(x) = 0}。 连续性要求：f, gi , i ∈ I(x ∗ ) 与所有 hj 在 x ∗ 可微，gi , i /∈ I(x ∗ ) 在 x ∗ 连续。 在满足上述要求时，若 x ∗ 是局部最优解，则存在不全为 0 的 λ0, λi , i ∈ I(x ∗ ), µj , j = 1, . . . , l 使 得 λ0∇f(x ∗ ) − X i∈I(x∗) λi∇gi(x ∗ ) − X l j=1 µj∇hj (x ∗ ) = 0 且 λ0 ≥ 0, λi ≥ 0, i ∈ I(x ∗ )。 证明 若 ∇hj (x ∗ ), j = 1, . . . , l 线性相关，可直接取合适的 µj，λ0, λi 均为 0 即得结论。 5
12录优性条件 否则，根据几何必要条件，不等式组 [vf(r")Td0i∈I(s*) Vhi(")Td=0 j=1,....I 无解。记I(x）=1,,k,并记 A=(Vf(x),-7g,(x),-V9t(x),B=(-7(x),,-Vu(x*) 则条件即ATd0,同除以0即得到Kuhn Tucker必要条件。 定义Lagrange函数L(红，A,川)=fe)-∑m1A9:(x)-∑14yh(),则K-T条件可以表达为对
1.2 最优性条件 否则，根据几何必要条件，不等式组 ∇f(x ∗ ) T d 0 i ∈ I(§ ∗ ) ∇hi(x ∗ ) T d = 0 j = 1, . . . , l 无解。记 I(x ∗ ) = i1, . . . , ik，并记 A = (∇f(x ∗ ), −∇gi1 (x ∗ ), . . . , −∇gik (x ∗ )), B = (−∇h1(x ∗ ), . . . , −∇hl(x ∗ )) 则条件即 AT d 0，同除以 λ0 即得到 KuhnTucker 必要条件。 定义 Lagrange 函数 L(x, λ, µ) = f(x) − Pm i=1 λigi(x) − Pl j=1 µjhj (x)，则 K-T 条件可以表达为对 6
13下降算法 x存在入，μ使得（将条件中i生I(x)的M记为0）： VxL(c,入川=0 9(a)≥0 i=1,,m h(r)=0 j=1,,1 (K-T) 入>0 i=1,…,m gE(x）=0 i=1,.,m 这也是KT条件的经典表达形式。 有时KT条件也叫KKT条件，取自Karush--Khn--Tucker三个人的首字母。 虽然这些条件仍然是必要条件，当可行域与优化目标具有某些性质时，类似无约束最优化问题，这 些条件也能“升级”成充分必要条件，之后所说的线性规划问题就是一个例子。 1.3下降算法 1.3.1基本定义 之前讨论的最优性条件是“最优解的判断”，但是并没有说明得到最优解的方式。现实中，在求解 最优化问题时最常用的计算方法是迭代下降算法。以下的定义给出了算法的抽象表述： 定义1.13（算法映射） 空间X上的一个算法A定义为X上的点到X上的集合的一个味射，也即上→A(回CX。品 直观的理解是，迭代算法的目的是从初始点0开始，得到一列点xk,使得它们可以趋向最优解 而将算法定义为点到集合的映射，代表着xk的下一个点工k+1是在A(k)中任意选取的。 至之所以不直接定义为点到点的映射，是因为很多时候（如非精确一维控索时）无法知道下一个点的具体 取值，只能确定在某个范因内。 仿照映射连续性的定义，可以给出算法某种意义上连续的刻画 定义114算法闭性) 定义集合列Ak的“下闭极很”m infkoAk为{y|3纵∈Ak,limk→e班=}，也即所有能成 为集合列中逐个取点的极限点的点“。 设X,Y是RP,R9中的闭集，A为X上的点到Y的子集的函数，若对任何满足im→x=x0 的k有mimk+A()CA(r0),则称A在0处是闭的。若对每个Z都有A在处是 闭的，则称A在Z上是闭的。 “此定义与记号为方便书写用，并非专业定义记号。 为了描述算法的性质，我们还需要刻画迭代目标、迭代过程与迭代结果。迭代目标可以用一个集 合表示，称为解集合，如无约束优化中取所有梯度为0的点，有约束优化中取所有KT点。迭代过 程与送代结果则可以通过下降函数与收敛性表示：
1.3 下降算法 x 存在 λ, µ 使得 (将条件中 i /∈ I(x ∗ ) 的 λi 记为 0)： ∇xL(x, λ, µ) = 0 gi(x) ≥ 0 i = 1, . . . , m hj (x) = 0 j = 1, . . . , l λi ≥ 0 i = 1, . . . , m λigi(x) = 0 i = 1, . . . , m (K-T) 这也是 K-T 条件的经典表达形式。 有时 K-T 条件也叫 KKT 条件，取自 Karush–Kuhn–Tucker 三个人的首字母。 虽然这些条件仍然是必要条件，当可行域与优化目标具有某些性质时，类似无约束最优化问题，这 些条件也能“升级”成充分必要条件，之后所说的线性规划问题就是一个例子。 1.3 下降算法 1.3.1 基本定义 之前讨论的最优性条件是“最优解的判断”，但是并没有说明得到最优解的方式。现实中，在求解 最优化问题时最常用的计算方法是迭代下降算法。以下的定义给出了算法的抽象表述： 定义 1.13 (算法映射) ♣ 空间 X 上的一个算法 A 定义为 X 上的点到 X 上的集合的一个映射，也即 x → A(x) ⊂ X。 直观的理解是，迭代算法的目的是从初始点 x0 开始，得到一列点 xk，使得它们可以趋向最优解。 而将算法定义为点到集合的映射，代表着 xk 的下一个点 xk+1 是在 A(xk) 中任意选取的。 之所以不直接定义为点到点的映射，是因为很多时候 (如非精确一维搜索时) 无法知道下一个点的具体 取值，只能确定在某个范围内。 仿照映射连续性的定义，可以给出算法某种意义上连续的刻画： 定义 1.14 (算法闭性) ♣ 定义集合列 Ak 的“下闭极限”lim infk→∞Ak 为 {y | ∃yk ∈ Ak, limk→∞ yk = y}，也即所有能成 为集合列中逐个取点的极限点的点a。 设 X, Y 是 R p , R q 中的闭集，A 为 X 上的点到 Y 的子集的函数，若对任何满足 limk→∞ xk = x0 的 xk 有 lim infk→∞A(xk) ⊂ A(x0)，则称 A 在 x0 处是闭的。若对每个 z ∈ Z 都有 A 在 z 处是 闭的，则称 A 在 Z 上是闭的。 a此定义与记号为方便书写用，并非专业定义/记号。 为了描述算法的性质，我们还需要刻画迭代目标、迭代过程与迭代结果。迭代目标可以用一个集 合 Ω 表示，称为解集合，如无约束优化中取所有梯度为 0 的点，有约束优化中取所有 K-T 点。迭代过 程与迭代结果则可以通过下降函数与收敛性表示： 7
1.3下降算法 定义1.15（下降南数、收敛性） 对解集合∈X与X上的算法A,X上的连续实函数中：X→R称为关于与A的下降函数 当且仗当： ()<(x)x生n,y∈A(a ()≤(r)x∈，y∈A(a 对解集合2∈X与X上的算法A,若从x0CX出发，无论每次的E+1从A(红)中如何选取， 得到序列{红}的每个收敛子列极限都在D中，则称A在0处收敛于L。若对每个y∈Y都有 A在处收敛于，则称A在Y上收敛于B. 作如上的抽象后，就可以从数学角度找到算法收敛的必要条件，也即： 定理1.16（收敛性条件） 对解集合2∈X与X上的算法A,从某个初始点0出发，每次E+1从A(x)中任意选取，得 到序列{红n}。在下列条件均满足时，{红n}的每个收敛子列极限都在中： 。{红n}包含于X的个紧子集中“。 。存在关于卫与A的下降西数中。 。A在X\2上是闭的。 “在R”上，包含在紧集中即为有界。 证明先证（工）的极限存在。由%包舍在紧子集中，其存在收敛子列：，设极限为工。由连续性可 知（工k,)→（四）。另一方面，根据条件(rk)是单调下降的，由数列极限知识即得()→()。 若x生2，考虑子列k+1,其必然也有收敛子列，假设收敛至五，根据已证，有()=()。 然而，由于A在卫补集上闭，工k+1∈A(%,)可推出五∈A(),根据下降函数定义与工生即有 ()<()，矛盾。 1.3.2迭代方法概述 虽然我们从理论中得到了收敛性的结果，对现实的算法，迭代不可能无穷下去，需要规定一些实 用的终止迭代过程的准则，一般称为收敛准则或停机准则，例如（仁为充分小正数）： 。rk+1-x<e或 :ll <E 。fe)-fe<e或<e o7f(xk)‖<e 而评价算法优劣的一个重要标准就是收敛的快慢，在数学上可以定义为： 定义1.17（收敛阶、线性收敛） 假设imk→oxk=x,且满足（假设所有rk均非r*) nzk+1-‖ 0≤1 lim sup-xP =B<0 则称{红n}以p阶收敛。 设所有这样的p构成集合P,称其上确界%=spP为{红n}的收敛阶。 若P0=1,且存在0<B<1使P取1时定义式成立，则称{红n}是以收敛比B线性收敛的。若
1.3 下降算法 定义 1.15 (下降函数、收敛性) ♣ 对解集合 Ω ∈ X 与 X 上的算法 A，X 上的连续实函数 ψ : X → R 称为关于 Ω 与 A 的下降函数 当且仅当： ψ(y) < ψ(x) x /∈ Ω, y ∈ A(x) ψ(y) ≤ ψ(x) x ∈ Ω, y ∈ A(x) 对解集合 Ω ∈ X 与 X 上的算法 A，若从 x0 ⊂ X 出发，无论每次的 xk+1 从 A(xk) 中如何选取， 得到序列 {xn} 的每个收敛子列极限都在 Ω 中，则称 A 在 x0 处收敛于 Ω。若对每个 y ∈ Y 都有 A 在 y 处收敛于 Ω，则称 A 在 Y 上收敛于 Ω。 作如上的抽象后，就可以从数学角度找到算法收敛的必要条件，也即： 定理 1.16 (收敛性条件) ♡ 对解集合 Ω ∈ X 与 X 上的算法 A，从某个初始点 x0 出发，每次 xk+1 从 A(xk) 中任意选取，得 到序列 {xn}。在下列条件均满足时，{xn} 的每个收敛子列极限都在 Ω 中： {xn} 包含于 X 的某个紧子集中a。 存在关于 Ω 与 A 的下降函数 ψ。 A 在 X\Ω 上是闭的。 a在 R n 上，包含在紧集中即为有界。 证明 先证 ψ(xk) 的极限存在。由 xk 包含在紧子集中，其存在收敛子列 xki，设极限为 x。由连续性可 知 ψ(xki ) → ψ(x)。另一方面，根据条件 ψ(xk) 是单调下降的，由数列极限知识即得 ψ(xk) → ψ(x)。 若 x /∈ Ω，考虑子列 xki+1，其必然也有收敛子列，假设收敛至 x¯，根据已证，有 ψ(¯x) = ψ(x)。 然而，由于 A 在 Ω 补集上闭，xki+1 ∈ A(xki ) 可推出 x¯ ∈ A(x)，根据下降函数定义与 x /∈ Ω 即有 ψ(¯x) < ψ(x)，矛盾。 1.3.2 迭代方法概述 虽然我们从理论中得到了收敛性的结果，对现实的算法，迭代不可能无穷下去，需要规定一些实 用的终止迭代过程的准则，一般称为收敛准则或停机准则，例如 (ε 为充分小正数)： ∥xk+1 − xk∥ < ε 或 ∥xk+1−xk∥ ∥xk∥ < ε |f(xk+1) − f(xk)| < ε 或 |f(xk+1)−f(xk)| |f(xk)| < ε ∥∇f(xk)∥ < ε 而评价算法优劣的一个重要标准就是收敛的快慢，在数学上可以定义为： 定义 1.17 (收敛阶、线性收敛) 假设 limk→∞ xk = x ∗，且满足 (假设所有 xk 均非 x ∗ ) 0 ≤ lim sup k→∞ ∥xk+1 − x ∗∥ ∥xk − x ∗∥ p = β < ∞ 则称 {xn} 以 p 阶收敛。 设所有这样的 p 构成集合 P，称其上确界 p0 = sup P 为 {xn} 的收敛阶。 若 p0 = 1，且存在 0 < β < 1 使 p 取 1 时定义式成立，则称 {xn} 是以收敛比 β 线性收敛的。若 8
