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