12录优性条件 二阶必要条件：若于二阶可微，由一阶必要条件有 f+al)=f()+a2V"f(W+O(o) 由若V2f(x)非半正定，由定义存在t使得tTV2f(x)t<0,从而在a充分小时即有f()>f(运+a), 矛盾 二阶充分条件：由正定定义，对任何t,a272f(x)t>0,从而在a充分小时一定有f()< f(位+a)。对每个单位向量t考虑最优的a()>0,由于所有可能t构成的集合（高维球面）是紧集，且 可验证a()连续性，存在a0=mi血ta()>0,于是{杠|x-<ao}内五是最小点，从而是极小值。 不过，这里只有必要条件与充分条件，并不能完整进行刻画。好在，当函数∫有一定性质的时候， 必要条件可以提升为充要条件，这个重要性质就是凸性。 定义1.5（凸函数） R”上的西f为凸函数，当其满足对红，y∈R”,入∈0,1有 f(+(1-)≤()+(1-)f( 对凸函数还有两个重要的等价定义，这里进行列举，后文凸优化中详细证明： 命遵1.6（凸函数等价定义） R”上的可微函数∫为凸函数 当且仅当其满足对红，y∈R”有 f)≥fa)+Vfx)(g-x) R上的二阶可微函数∫为凸函教，当且仅当其满足对V红∈R有f(x)半正定 事实上凸函数不必定义在R”上，只需要定义在凸集上就可以谈论，此处由于问题是无约束的，考虑 全空间即可。 有了等价定义后，就可以有无约束优化的最优条件： 定理17（凸函数下的充要条件） f(工)是R”上的可微凸函教，则五是全局最优解的充要条件是了f()=0, 证明必要性根据之前定理得到。对于充分性，由一阶等价条件直接得到()≥∫()。 1.2.2约束问题的最优条件 在有约束的情况下，想判断一个点是否是局部最优解就要困难很多。约束导致可行域的复杂，也 导致了最优判定必须考虑边界的情况。对此，有如下的直观定义与性质： 定义1.8（可行方向、下降方向） Rm中，对x∈S与非零向量d,若存在6>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 < 0，从而在 α 充分小时即有 f(¯x) > f(¯x + αt)， 矛盾。 二阶充分条件：由正定定义，对任何 t，1 2 α 2 t T ∇2f(x)t > 0，从而在 α 充分小时一定有 f(¯x) < f(¯x + αt)。对每个单位向量 t 考虑最优的 α(t) > 0，由于所有可能 t 构成的集合 (高维球面) 是紧集，且 可验证 α(t) 连续性，存在 α0 = mint α(t) > 0，于是 {x | ∥x − x¯∥ < α0} 内 x¯ 是最小点，从而是极小值。 不过，这里只有必要条件与充分条件，并不能完整进行刻画。好在，当函数 f 有一定性质的时候， 必要条件可以提升为充要条件，这个重要性质就是凸性。 定义 1.5 (凸函数) ♣ R n 上的函数 f 为凸函数，当其满足对 ∀x, y ∈ R n , λ ∈ [0, 1] 有 f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y) 对凸函数还有两个重要的等价定义，这里进行列举，后文凸优化中详细证明： 命题 1.6 (凸函数等价定义) ♠ R n 上的可微函数 f 为凸函数，当且仅当其满足对 ∀x, y ∈ R n 有 f(y) ≥ f(x) + ∇f(x) T (y − x) R n 上的二阶可微函数 f 为凸函数，当且仅当其满足对 ∀x ∈ R n 有 ∇2f(x) 半正定。 事实上凸函数不必定义在 R n 上，只需要定义在凸集上就可以谈论，此处由于问题是无约束的，考虑 全空间即可。 有了等价定义后，就可以有无约束优化的最优条件： 定理 1.7 (凸函数下的充要条件) ♡ f(x) 是 R n 上的可微凸函数，则 x¯ 是全局最优解的充要条件是 ∇f(¯x) = 0。 证明 必要性根据之前定理得到。对于充分性，由一阶等价条件直接得到 f(y) ≥ f(¯x)。 1.2.2 约束问题的最优条件 在有约束的情况下，想判断一个点是否是局部最优解就要困难很多。约束导致可行域的复杂，也 导致了最优判定必须考虑边界的情况。对此，有如下的直观定义与性质： 定义 1.8 (可行方向、下降方向) ♣ R n 中，对 x ∈ S 与非零向量 d，若存在 δ > 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()Td<o) Fo(z)={d|Vgu(r)Td>0.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} Fg(x) = {d | ∇gi(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")Td<o 7g(x*)Td>0i∈I(s*) Vhi(")Td=0 j=1,....I 无解。记I(x）=1,,k,并记 A=(Vf(x),-7g,(x),-V9t(x),B=(-7(x),,-Vu(x*) 则条件即ATd<0,BTd=0无解。下证A入+Bu=0,入≥0有解，这样记入=(0，，k),4= (,m)即得结论。 [下方证明需含凸集分离定理（详见参考资料）在内的分析与线代知识，可跳过。」 记 则条件为SS=8,可径正二者均为B条，图光保据合东分考定里，存在烧平面（间）叶(（C）-0 分离两凸集，也即 由连续性，对任何S1闭包与S2闭包中的1,2，大于等于号仍成立。取1=0（卿d=0),利用 s2范图可知必须m≥0，而取S2闭包中的s2=0,S中d=-(Ap1+Bp2)可知-‖Ap1+Bpm2≥0， 所以只能Ap1+Bp2=0,这里,即为所需的解入。 现实中更常用的是其特殊情况： 定理1.12Kuhn-Tucker必要条件) 若x*为式1.3)中的可行点，记I()={i|g(x)=0} 连续性要求：∫，9，i∈T(x)与所有j在x可微，g,i年T()在x*连续，且向量集{Vg(r),i∈ (x),7h(x),j=1,l}线性无关. 在满足上述要求时，若x*是局部最优解，则存在M≥0，i∈T(x)与4，j=1,,1使得 Vf(z)- ∑Ag.e)-∑4,e)=0 1= 证明根据Fritz-John条件，由于，，西不全为0，餐设0=0，则存在不全为0的,西使得 ∑iez红)Vg(r)+=1山Vh(z)=0,与线性无关矛盾，因此o>0,同除以0即得到Kuhn Tucker必要条件。 定义Lagrange函数L(红，A,川)=fe)-∑m1A9:(x)-∑14yh(),则K-T条件可以表达为对
1.2 最优性条件 否则，根据几何必要条件，不等式组 ∇f(x ∗ ) T d < 0 ∇gi(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, BT d = 0 无解。下证 Aλ + Bµ = 0, λ ≥ 0 有解，这样记 λ = (λ0, . . . , λk), µ = (µ1, . . . , µm) 即得结论。 [下方证明需含凸集分离定理 (详见参考资料) 在内的分析与线代知识，可跳过。] 记 S1 = λ µ ! | ∃d, λ = A T d, µ = B T d , S2 = λ µ ! | λ < 0, µ = 0 则条件为 S1∩S2 = ∅。可验证二者均为凸集，因此根据凸集分离定理，存在超平面 p1 p2 !T x+ q1 q2 ! = 0 分离两凸集，也即 ∀s1 ∈ S1, s2 ∈ S2, p1 p2 !T s1 + q1 q2 ! ≥ 0 ≥ p1 p2 !T s2 + q1 q2 ! ⇒ p1 p2 !T s1 ≥ p1 p2 !T s2 由连续性，对任何 S1 闭包与 S2 闭包中的 s1, s2，大于等于号仍成立。取 s1 = 0 (即 d = 0)，利用 s2 范围可知必须 p1 ≥ 0，而取 S2 闭包中的 s2 = 0，S1 中 d = −(Ap1 + Bp2) 可知 −∥Ap1 + Bp2∥ 2 ≥ 0， 所以只能 Ap1 + Bp2 = 0，这里 p1, p2 即为所需的解 λ, µ。 现实中更常用的是其特殊情况： 定理 1.12 (Kuhn-Tucker 必要条件) ♡ 若 x ∗ 为式 (1.3) 中的可行点，记 I(x) = {i | gi(x) = 0}。 连续性要求：f, gi , i ∈ I(x ∗ ) 与所有 hj 在 x ∗ 可微，gi , i /∈ I(x) 在 x ∗ 连续，且向量集 {∇gi(x ∗ ), i ∈ I(x ∗ ), ∇hj (x ∗ ), j = 1, . . . , l} 线性无关。 在满足上述要求时，若 x ∗ 是局部最优解，则存在 λi ≥ 0, i ∈ I(x) 与 µj , j = 1, . . . , l 使得 ∇f(x ∗ ) − X i∈I(x∗) λi∇gi(x ∗ ) − X l j=1 µj∇hj (x ∗ ) = 0 证明 根据 Fritz-John 条件，由于 λ0, λi , µj 不全为 0，假设 λ0 = 0，则存在不全为 0 的 λi , µj 使得 P i∈I(x∗) λi∇gi(x ∗ ) + Pl j=1 µj∇hj (x ∗ ) = 0，与线性无关矛盾，因此 λ0 > 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