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

13下降算法 m>1或0=1且p取1时定义式中B=0,则称{n}是超线性收敛的虽然名为线性收敛，实际上的逼近速度其实是指数量级，例如假设每个=，则k一x‖≤ x0-x‖。评价算法优劣的另一个重要标准是计算复杂性。虽然最优化可以追溯到十分古老的极值问题，但它成为一门独立的学科是在二十世纪四十年代末，而这个年代也恰恰是计算机从理论成为现实的年代。从Dantzig提出了求解一般线性规划问题的单纯形法起，各种最优化问题的理论及应用研究得到迅速发展，特别是线性规划由于其模型的普遍性和实用性，相关算法的进展引起广泛的重视。随者计算机技术的发展，实际问颗的规模械来戴大，计算复杂性成为了研究线性规划算法的重要标准，对非线性规划的算法也是如此。本讲义以基础理论的介绍为主，不将复杂度的分析与优化作为重点，更多相关理论可以参考附录文献绪论的最后，我们介绍两种基本的迭代算法结构。迭代算法的基本思想是：给定一个初始点，按照某一迭代规则产生一个点列，使得当其是有穷点列时，其最后一个点是最优化模型问题的最优解，否则它有极限点且其极限点是最优化模型问题的最优解一个好的迭代算法应具备的典型特征是：迭代点k能稳定地接近局部极小点*的小邻域，然后迅速收敛于。一般地，对于某种算法，我们需要证明其迭代点列的聚点（即子列的极限点）为一局部极小点。在实际计算中，当指定的收敛准则满足时，送代即终止。算法1.18（达代算法-两步法） 1计算初始点0 2.构造价值西数妙，取某个满足7(xk)Td<0的方向d为dk。 3.确定步长因子，使得该价值函数值有某种程度的下降。 4.计算xk+1=xk+Qkd。 5.若满足事先给定的选代终止条件则算法终止，否则回到第二步。这是一种经典的算法结构，每次迭代分为确定方向与确定步长两个基本操作。价值函数[merit func- io地可以直接取为目标函数∫，也可以是某个与目标函数相关的可微函数。此外，也可以通过邻域的限制，每次找范围内的近似极小点，一步到位：算法1.19（选代算法。一步法） 1.计算初始点0 2.构造价值函数妙在k附近（如一定半径内）的二次近似函数。 3.计算在范国内的最小点，得到影作为更新位移向量。 4.计算xk+1=x十Sk。 5.若满足事先给定的选代终止条件则算法终止，否则回到第二步。两种方法各有优劣，也有各自不同的适应场景，在之后的章节中，我们会进一步对这两种结构进行细化

1.3 下降算法 ♣ p0 > 1 或 p0 = 1 且 p 取 1 时定义式中 β = 0，则称 {xn} 是超线性收敛的。虽然名为线性收敛，实际上的逼近速度其实是指数量级，例如假设每个 ∥xk+1−x ∗∥ ∥xk−x∗∥ = 1 2，则 ∥xk −x ∗∥ ≤ 1 2 k ∥x0 − x ∗∥。评价算法优劣的另一个重要标准是计算复杂性。虽然最优化可以追溯到十分古老的极值问题，但它成为一门独立的学科是在二十世纪四十年代末，而这个年代也恰恰是计算机从理论成为现实的年代。从 Dantzig 提出了求解一般线性规划问题的单纯形法起，各种最优化问题的理论及应用研究得到迅速发展，特别是线性规划由于其模型的普遍性和实用性，相关算法的进展引起广泛的重视。随着计算机技术的发展，实际问题的规模越来越大，计算复杂性成为了研究线性规划算法的重要标准，对非线性规划的算法也是如此。本讲义以基础理论的介绍为主，不将复杂度的分析与优化作为重点，更多相关理论可以参考附录文献。绪论的最后，我们介绍两种基本的迭代算法结构。迭代算法的基本思想是：给定一个初始点，按照某一迭代规则产生一个点列，使得当其是有穷点列时，其最后一个点是最优化模型问题的最优解，否则它有极限点且其极限点是最优化模型问题的最优解。一个好的迭代算法应具备的典型特征是：迭代点 xk 能稳定地接近局部极小点 x ∗ 的小邻域，然后迅速收敛于 x。一般地，对于某种算法，我们需要证明其迭代点列 xk 的聚点 (即子列的极限点) 为一局部极小点。在实际计算中，当指定的收敛准则满足时，迭代即终止。算法 1.18 (迭代算法-两步法) ♠ 1. 计算初始点 x0。 2. 构造价值函数 ψ，取某个满足 ∇ψ(xk) T d < 0 的方向 d 为 dk。 3. 确定步长因子 αk，使得该价值函数值有某种程度的下降。 4. 计算 xk+1 = xk + αkdk。 5. 若满足事先给定的迭代终止条件则算法终止，否则回到第二步。这是一种经典的算法结构，每次迭代分为确定方向与确定步长两个基本操作。价值函数 [merit function]ψ 可以直接取为目标函数 f，也可以是某个与目标函数相关的可微函数。此外，也可以通过邻域的限制，每次找范围内的近似极小点，一步到位：算法 1.19 (迭代算法-一步法) ♠ 1. 计算初始点 x0。 2. 构造价值函数 ψ 在 xk 附近 (如一定半径内) 的二次近似函数 ψk。 3. 计算 ψk 在范围内的最小点，得到 sk 作为更新位移向量。 4. 计算 xk+1 = xk + sk。 5. 若满足事先给定的迭代终止条件则算法终止，否则回到第二步。两种方法各有优劣，也有各自不同的适应场景，在之后的章节中，我们会进一步对这两种结构进行细化。 9

2.1基木模型转化为标准型。 xg=4+1-2x2 解先将最优化目标转化为min4r1一2，接着对约束条件进行处理。记工4=12-21-32，则 (x6=1-2-3 r2=x6-r7 有C3,x4,5≥0。由x2无约束，记 ,于是可以排列出方程组（这里已经调整了b的 x6,r7≥0 符号)： -1100 2 4 20103 -3 100-1-1 3 26 再结合x=(红1,3，，x7)≥0即得到约束条件。 2.1.2凸集基础知识在给出了标准型以后，我们希望能够确定线性规划问题解的情况，以及解的可能性质。为了解决这些问题，我们需要先引入凸集的概念：定义2.2（凸集）若一个集合SCR”满足红，y∈S,入∈[0，，江+(1-g∈S,则称集合S是凸的。空直观来看，这也就是集合中的任意两点所连线段都属于此集合。线性规划的每个约束条件，都相当于用若干维的平面去分割空间，而利用凸集的直观理解，可以想像，若被分割的区域是凸集，无论取分割出的哪一部分（不等式约束）还是相交的部分（等式约束），取出的部分仍然是凸集。不仅如此，每次都使用大于等于号分割，闭集的性质亦得到保持，重复此过程可以得到：定理2.3（线性规划可行域性质）线性规划问题的可行城是闭凸集证明假设变量个数为n,由于®”为闭凸集，利用归纳法，从式(21)的形式中只需说明，定义集合 A={x∈Rm|aTx=b}与集合B={r∈Rm|aTx之b},当T是闭凸集时，AnT与BnT都是闭凸集，这样每次新增条件后都是闭凸集利用极限保序性可以验证B是闭集，类似得A是闭集。由于闭集的交是闭集，A∩T与B门T是闭集。由定义，若ar1=a2=b,则a(1+(1-)2)=b+(1-b=b,从而A是凸集，将前方等号换成大于等于号即知B是凸集。于是，只需要证明凸集的交是凸集，由定义知成立。综上即得证。从而，为了研究线性规划的可行域性质，只需要研究闭凸集的性质。更准确来说，由于每步都是用超平面划分，最后划分出的一定是一个“多面体”的样子。从直观上看，如果可行域有界，多面体的

2.1 基本模型转化为标准型。解先将最优化目标转化为 min 4x1 − x2，接着对约束条件进行处理。记    x3 = 4 + x1 − 2x2 x4 = 12 − 2x1 − 3x2 x5 = x1 − x2 − 3 ，则有 x3, x4, x5 ≥ 0。由 x2 无约束，记    x2 = x6 − x7 x6, x7 ≥ 0 ，于是可以排列出方程组 (这里已经调整了 b 的符号)：   −1 1 0 0 2 −2 2 0 1 0 3 −3 1 0 0 −1 −1 1     x1 x3 x4 x5 x6 x7   =   4 12 3   再结合 x = (x1, x3, . . . , x7) T ≥ 0 即得到约束条件。 2.1.2 凸集基础知识在给出了标准型以后，我们希望能够确定线性规划问题解的情况，以及解的可能性质。为了解决这些问题，我们需要先引入凸集的概念：定义 2.2 (凸集) ♣ 若一个集合 S ⊂ R n 满足 ∀x, y ∈ S, λ ∈ [0, 1], λx + (1 − λ)y ∈ S，则称集合 S 是凸的。直观来看，这也就是集合中的任意两点所连线段都属于此集合。线性规划的每个约束条件，都相当于用若干维的平面去分割空间，而利用凸集的直观理解，可以想像，若被分割的区域是凸集，无论取分割出的哪一部分 (不等式约束) 还是相交的部分 (等式约束)，取出的部分仍然是凸集。不仅如此，每次都使用大于等于号分割，闭集的性质亦得到保持，重复此过程可以得到：定理 2.3 (线性规划可行域性质) ♡ 线性规划问题的可行域是闭凸集。证明假设变量个数为 n，由于 R n 为闭凸集，利用归纳法，从式 (2.1) 的形式中只需说明，定义集合 A = {x ∈ R n | a T x = b} 与集合 B = {x ∈ R n | a T x ≥ b}，当 T 是闭凸集时，A ∩ T 与 B ∩ T 都是闭凸集，这样每次新增条件后都是闭凸集。利用极限保序性可以验证 B 是闭集，类似得 A 是闭集。由于闭集的交是闭集，A ∩ T 与 B ∩ T 是闭集。由定义，若 a T x1 = a T x2 = b，则 a T (λx1 + (1 − λ)x2) = λb + (1 − λ)b = b，从而 A 是凸集，将前方等号换成大于等于号即知 B 是凸集。于是，只需要证明凸集的交是凸集，由定义知成立。综上即得证。从而，为了研究线性规划的可行域性质，只需要研究闭凸集的性质。更准确来说，由于每步都是用超平面划分，最后划分出的一定是一个“多面体”的样子。从直观上看，如果可行域有界，多面体的 11

2.1基木模型顶点连线可以得到棱，棱连线可以得到表面，表面再连线就能得到整体，也就是说，从几个特殊“顶点”可以“连接”出整个集合。这就引出了如下的定义：定义2.4（极点凸组合）对非空凸集S,若x∈S满足，只要存在1,2∈S使得E=x1+(1-)2,入∈(0,1)，则必须1=2=，那么称x为S的一个极点。对于R”中的一些点a1,,an,定义它们的一个凸组合为∑1a,其中≥0，∑1=1名至直观上，板点也就是“不处在米其他两点连接的线段中的点”，与上方多面体的项点一致。凸组合则可以看成若干个点通过不断连接线段能连出的所有点。定理25（凸集的等价定）集合S是凸的等价于其中任意有限个点的凸组合仍在其中。证明右推左：根据凸集的定义，两个点的凸组合就是x+(1一)以，入∈0,1，于是只要任意两个点的凸组合在其中，集合即为凸集，任意有限个点自然也正确。左推右：归纳。任意两个点由凸集定义可知凸组合在其中。若任意n-1个点的凸组合在其中，任意n 个点时，若1=1，则其他入必须为0，实际上是一个点，否则∑1Aa:=1a1+(1-A1)∑2a 由凸组合定义可知均非负，且计算得和为1，从而∑2头a:是2，am的凸组合，记为a0 再由定义知入1a1+(1-入1)a0在凸集中，从而成立。关于有界闭凸集，类似上方不断连线的过程可以得到如下性质：命2.6（有界闭凸集的性质）有界闭凸集=其极点的凸组合得到的集合但事实上，在凸集不是平面分割出时（如圆），由于会出现无限个极点的情况，证明是有些复杂的，也不在线性规划的考虑范畴内，因此这里不予证明。遗憾的是，对于无界集合，并不能简单通过极点确定。例如，R”是凸集，但其不存在任何极点。考察几何可以发现，这时的凸集一定能向某些方向延伸，于是有定义：定义2.7（方向、极方向）设SCR”为闭凸集，d为一个非零向量。若Hz∈S,入≥0有x+Ad∈S,则称向量d为S的方向。设d1,d。为S的两个方向，若对任何入>0有d1≠入d,则称它们不同对S的某方向d,若满足，只要存在d山，d2为S的方向使得d=1d山1+2d2,1,2≥0，则必须 d1=d2=d,那么称d为S的一个极方向。值得注意的是，这里的方向对应的是射线的方向，而不是直线，例如R有两个方向，1，-1，且两个方向都是极方向。练习2.2给出以下集合的全部极点与极方向：。S:={x∈R2|x1≥0，x2≥0，x1+x221} 。T:={z∈R21x1+2x2≥0，x2-x1≥0，x2≤1} 解如图21，由几何关系可以看出极点即为顶点，也即不等式约束能尽量多取等的点。因此分别考虑三 12

2.1 基本模型顶点连线可以得到棱，棱连线可以得到表面，表面再连线就能得到整体，也就是说，从几个特殊“顶点”可以“连接”出整个集合。这就引出了如下的定义：定义 2.4 (极点、凸组合) ♣ 对非空凸集 S，若 x ∈ S 满足，只要存在 x1, x2 ∈ S 使得 x = λx1 + (1 − λ)x2, λ ∈ (0, 1)，则必须 x1 = x2 = x，那么称 x 为 S 的一个极点。对于 R n 中的一些点 a1, . . . , an，定义它们的一个凸组合为 Pn i=1 λiai，其中 λi ≥ 0, Pn i=1 λi = 1。直观上，极点也就是“不处在某其他两点连接的线段中的点”，与上方多面体的顶点一致。凸组合则可以看成若干个点通过不断连接线段能连出的所有点。定理 2.5 (凸集的等价定义) ♡ 集合 S 是凸的等价于其中任意有限个点的凸组合仍在其中。证明右推左：根据凸集的定义，两个点的凸组合就是 λx + (1 − λ)y, λ ∈ [0, 1]，于是只要任意两个点的凸组合在其中，集合即为凸集，任意有限个点自然也正确。左推右：归纳。任意两个点由凸集定义可知凸组合在其中。若任意 n−1 个点的凸组合在其中，任意 n 个点时，若 λ1 = 1，则其他 λi 必须为 0，实际上是一个点，否则 Pn i=1 λiai = λ1a1+(1−λ1) Pn i=2 λi 1−λ1 ai。由凸组合定义可知 λi 1−λ1 均非负，且计算得和为 1，从而 Pn i=2 λi 1−λ1 ai 是 a2, . . . , an 的凸组合，记为 a0，再由定义知 λ1a1 + (1 − λ1)a0 在凸集中，从而成立。关于有界闭凸集，类似上方不断连线的过程可以得到如下性质：命题 2.6 (有界闭凸集的性质) ♠ 有界闭凸集 = 其极点的凸组合得到的集合但事实上，在凸集不是平面分割出时 (如圆)，由于会出现无限个极点的情况，证明是有些复杂的，也不在线性规划的考虑范畴内，因此这里不予证明。遗憾的是，对于无界集合，并不能简单通过极点确定。例如，R n 是凸集，但其不存在任何极点。考察几何可以发现，这时的凸集一定能向某些方向延伸，于是有定义：定义 2.7 (方向、极方向) ♣ 设 S ⊂ R n 为闭凸集，d 为一个非零向量。若 ∀x ∈ S, λ ≥ 0 有 x + λd ∈ S，则称向量 d 为 S 的方向。设 d1, d2 为 S 的两个方向，若对任何 λ > 0 有 d1 ̸= λd2，则称它们不同。对 S 的某方向 d，若满足，只要存在 d1, d2 为 S 的方向使得 d = λ1d1 + λ2d2, λ1, λ2 ≥ 0，则必须 d1 = d2 = d，那么称 d 为 S 的一个极方向。值得注意的是，这里的方向对应的是射线的方向，而不是直线，例如 R 有两个方向，1, −1，且两个方向都是极方向。练习 2.2 给出以下集合的全部极点与极方向： S := {x ∈ R 2 | x1 ≥ 0, x2 ≥ 0, x1 + x2 ≥ 1} T := {x ∈ R 2 | x1 + 2x2 ≥ 0, x2 − x1 ≥ 0, x2 ≤ 1} 解如图2.1，由几何关系可以看出极点即为顶点，也即不等式约束能尽量多取等的点。因此分别考虑三 12

2.1基木模型个不等式中的两个取等（注意S前两个不等式取等不满足第三个不等式，舍去）可知S的极点为(0,1) 与(1,0)，T的极点为(0,0)，(-2,1)，(1,1)。T是有界集合，不存在极方向，而S的极方向由定义可以理解为方向中的“边界”，于是为(0,1)与(1,0)。S有两个极点，两个极方向；T有三个极点，没有极方向。图2.1：S.T区域示意图在有了极点与极方向后，可以进一步刻画线性规划可行域的性质：定理2.8（凸集表示定理设集合S={红|Az=b,x≥0}非空，则其满足 1.极点集非空有限 2极方向集合为空等价于S有界； 3.S无界时，存在有限个极方向四，，d0: 4.x∈S台x=0+=14d),其中0为极点的凸组合，所有4之0。证明 1.为说明极点集合非空，取S中为零的分量最多的点（之一），记为，下面说明是极点。若否，有 x四≠x②eS满足x四+(1-)x②)=弘，入e(0,1)。对y为0的分量，由于x,x②≥0，必然x,x②)的对应分量都为0，于是由y是零分量最多的点可知x),x2②)的其他分量均不为0。记a=x1-x2,计算可知Aa=0,于是0=y+t0,t∈R都满足Ag心=b.记r为|监l,a≠0 中取到最小值的下标，考虑-兰，可验证其∈S且比y多一个为0的分量（即第r个分量），矛盾。为说明授点个数有限，假设极点y的分量B,,B非零，我们证明A的第B1,,B:列线性无关。这样一来，假设这些列拼成的矩阵为B4,由于秩为k,可以从中选出可逆k阶方阵B 而弘，b的对应分量为-，b-,则有-=B二b。也就是说，对每一种非零分量选取，得到的极点是至多唯一的，因此极点总个数不超过选取数2”。记这些列为aB1,,aB,若线性相关，则存在不全为0的入使得∑入aB,=0。将B:分量为入，其他为0的向量记作入，由定义可知对充分小的6有y十，g-6以均在S中，而y为两者平均，因此不是极点，矛盾。 2.当S有界时，根据方向定义可知S方向集合为空，板方向集合因而为空。否则，我们先证明方向集合非空。假设已知Ar=b的一个解x0。由S无界，对任何n存在满足x-x01>n的

2.1 基本模型个不等式中的两个取等 (注意 S 前两个不等式取等不满足第三个不等式，舍去) 可知 S 的极点为 (0, 1) 与 (1, 0)，T 的极点为 (0, 0),(−2, 1),(1, 1)。T 是有界集合，不存在极方向，而 S 的极方向由定义可以理解为方向中的“边界”，于是为 (0, 1) 与 (1, 0)。S 有两个极点，两个极方向；T 有三个极点，没有极方向。图 2.1: S、T 区域示意图在有了极点与极方向后，可以进一步刻画线性规划可行域的性质：定理 2.8 (凸集表示定理) ♡ 设集合 S = {x | Ax = b, x ≥ 0} 非空，则其满足： 1. 极点集非空有限； 2. 极方向集合为空等价于 S 有界； 3. S 无界时，存在有限个极方向 d (1), . . . , d(l)； 4. x ∈ S ⇔ x = x0 + Pl j=1 µjd (j)，其中 x0 为极点的凸组合，所有 µj ≥ 0。证明 1. 为说明极点集合非空，取 S 中为零的分量最多的点 (之一)，记为 y，下面说明 y 是极点。若否，有 x (1) ̸= x (2) ∈ S 满足 λx(1) + (1 − λ)x (2) = y, λ ∈ (0, 1)。对 y 为 0 的分量，由于 x (1), x(2) ≥ 0，必然 x (1), x(2) 的对应分量都为 0，于是由 y 是零分量最多的点可知 x (1), x(2) 的其他分量均不为 0。记 α = x1 −x2，计算可知 Aα = 0，于是 y (t) = y +tα, t ∈ R 都满足 Ay(t) = b。记 r 为 | yi αi |, αi ̸= 0 中取到最小值的下标，考虑 y − yr αr α，可验证其 ∈ S 且比 y 多一个为 0 的分量 (即第 r 个分量)，矛盾。为说明极点个数有限，假设极点 y 的分量 yB1 , . . . , yBk 非零，我们证明 A 的第 B1, . . . , Bk 列线性无关。这样一来，假设这些列拼成的矩阵为 B+，由于秩为 k，可以从中选出可逆 k 阶方阵 B−，而 y, b 的对应分量为 y−, b−，则有 y− = B −1 − b−。也就是说，对每一种非零分量选取，得到的极点是至多唯一的，因此极点总个数不超过选取数 2 n。记这些列为 aB1 , . . . , aBk，若线性相关，则存在不全为 0 的 λi 使得 P i λiaBi = 0。将 Bi 分量为 λi，其他为 0 的向量记作 λ，由定义可知对充分小的 δ 有 y + δλ, y − δλ 均在 S 中，而 y 为两者平均，因此不是极点，矛盾。 2. 当 S 有界时，根据方向定义可知 S 方向集合为空，极方向集合因而为空。否则，我们先证明方向集合非空。假设已知 Ax = b 的一个解 x0。由 S 无界，对任何 n 存在满足 ∥xn − x0∥1 > n 的 13