中国科学技术大学：《运筹学》课程教学资源（教案讲义）运筹学讲义、最优化讲义.pdf_大学文库

目录第 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

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

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

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