ch6常用约束最优化方法

1、第6章 常用约束最优化方法 1本节主要考察带有约束条件的非线性规划问题。 称问题(MP)为数学规划(Mathematical Programming)。 (MP)称 为不等式约束, 为等式约束。 称集合 为问题(MP)的可行域。 若问题(MP)中的f, gi是凸函数, hj是线性函数, 则称问题(MP)为凸规划。 26.1.1 不等式约束问题的最优性条件 考察最优化问题 记 , 称为问题(6.1.1)的可行域 (6.1.1)定义6.1.1 设 , 若对某个i有gi(x*)=0, 称gi(x)0为点x*处的起作用约束, 也称为有效约束, 积极约束(Active Constraint)。 记 为起

2、作用约束下标集。 36.1 最优性条件 若 , 则称 为点x*处的不起作用约束。其几何意义如图所示。在 处 是起作用约束, 是不起作用约束。在 处 均是不起作用约束。 4定义6.1.2 设 , 对于向量p0若存在实数 使 则称向量p为x*处关于区域D的可行方向, 若p既是可行方向又是下降方向, 则称p为可行下降方向。 5 在研究某点处的可行方向时, 只需考察这一点处的起作用约束即可, 对不起作用约束可以暂时不考虑。 对起作用的约束来说, 当变量x沿某些方向作微小的移动时仍然满足约束条件, 而沿另外一些方向作微小的移动时, 无论移动是多么的微小都将违背约束条件。对不起作用的约束来说, 变量x沿任

3、何方向作微小移动都能满足约束条件。例6.1.1 用图解法求下列问题的最优解，指出最优解处的起作用约束及目标函数的最优值。 (1)(2)解： (1)原问题可以化为： 6最优解 , 最优值 。 在x*处是起作用约束。 如图所示。 7(2)原问题可化为 最优解 , 最优值 。 在x*处是起作用约束。 8定理6.1.1(Fritz-John必要条件)设 在x*处可微, 在x*处连续, 若x*是不等式约束问题(6.1.1)的局部最优解, 则存在不全为零的数 使 【日】Masao Fukushima著，林贵华译，非线性最优化基础，科学出版社，2011年5月 9例6.1.2 验证最优化问题 在最优解 处的F

4、ritz-John条件成立 解:在 处 是起作用约束, 即 且 取 , 便有Fritz-John条件成立。 10 在Fritz-John必要条件中, 若 则Fritz-John条件中就没有目标函数的信息了, 这样的Fritz-John条件就没有多大的价值, 为了保证 , 需对约束条件加以适当的限制条件, 称之为约束规格(Constraint qualification)。在非线性规划的研究中, 有着各种不同的约束规格, 如果增加起作用约束的梯度向量线性无关的约束规格, 就得出著名Kuhn-Tucker条件。它是Kuhn和Tucker在1951年提出的, 简称为K-T条件。 11定理6.1.2(

5、Kuhn-Tucker必要条件) 设 在x*处可微, 在x* 处连续, 线性无关, 若x*是不等式约束问题 (6.1.1) 的局部最优解, 则存在 使 12 在定理6.1.2中, 若 在x*处也可微, 则有等价形式的Kuhn-Tucker条件称满足K-T条件的可行点为K-T点。 例6.1.3 对不等式约束问题 考察点 , 是否是K-T点？ 解: 经验证x(1), x(2)是可行点 由于在x(1)处只有g2(x)0是起作用约束, 此时有 13方程组 无解, 故x(1)不是K-T点。 在x(2)处, 均是起作用约束, 且 线性无关, 由 有方程组 解之有 故x(2)是K-T点。 14定理6.1.3

6、(充分条件) 设不等式约束问题(6.1.1)中, 是凸函数, 和f在点x*处可微, 在x*处连续, 且x*是K-T点, 则x*是(6.1.1)的全局最优解。 156.1.2 等式约束问题的最优性条件考查最优化问题 (6.1.2)对等式约束问题(6.1.2)可以转化为不等式约束问题来考虑 16(6.1.1)的结论可平移到(6.1.3)中来, 并得到(6.1.2)的相应结论。(6.1.2)也采用Lagrange乘数法来求解。 (6.1.3)定义3.2.3 称为等式约束问题(6.1.2)的Lagrange函数。其中 =(1, 2, , l)T 称为Lagrange乘子, 17记称 为h(x)的Jac

7、obi矩阵。定义6.1.4 若 满足: , 则 称为等式约束问题(6.1.3)的Lagrange点。设等式约束问题 (6.1.2) 中f, hj(j=1,2,l)在x*处的某个邻域内可微, h(x)的Jacobi矩阵在x*处的秩为l, 若x*是 (6.1.2) 的局部最优解, 则存在 使 18定理6.1.4(必要条件)设等式约束问题(6.1.2)中f, hj(j=1,2,l)二阶连续可微, 若存在 使得其中 ; 则x*是等式约束问题(6.1.2)的严格局部最优解。 19定理6.1.5(充分条件)例6.1.4 求解 20解：原问题可化为： 有 令 有 设向量 满足 , 则有 21此时 由定理6.

8、1.5知(1,2)T是问题的严格局部最优解。 6.1.3 混合约束问题的最优性条件现在考查既含不等式约束又含等式约束的最优化问题 22记定理6.1.6(Fritz John必要条件) 设混合约束问题(6.1.4)中的 在点x*处可微, 在x*点处连续, 在点x*处连续可微, 若x*是(6.1.4)的局部最优解, 则存在数:使 23 在定理6.1.6中, 若还有条件, 在点x*处可微, 则Fritz-John条件可改写为设混合约束问题中 在点x*处可微, 在点x*处连续, 在点x*处连续可微, 且 线性无关, 若x*是(MP) 的局部最优解, 则存在 使 24定理6.1.7 (Kuhn-Tuck

9、er必要条件) 在定理6.1.7中若还有条件 在点x*处可微, 则Kuhn-Tucker条件可改写为： 25设混合约束问题(6.1.4)中的 在点x*处可微, 若x*满足(6.1.4) 的 Kuhn-Tucker 条件, 并且 是凸函数, 是线性函数, 则x*是(6.1.4)的全局最优解。 定理6.1.8(充分条件)例6.1.5 求解解： 26由Kuhn-Tucker条件有： 27解此方程组得解 由于f(x), g(x)是凸函数, h(x)是线性函数, 而且x*是Kuhn-Tucker点, 故由定理6.1.8知(1, 1)T 是问题的全局最优解。6.2 罚函数法 罚函数法又称为序列无约束极小化

10、方法(Sequential Unconstrained Minimization Technique), 简称SUMT。其基本思想是:利用问题中的约束函数作出适当的惩罚函数(Penalty function), 由此构造出带参数的辅助函数, 将约束问题转化为求解一系列无约束最优化问题。 286.2.1 外罚函数法(外点法) 该方法的基本思想是迭代点在可行域的外部移动, 随着迭代次数的增加, “惩罚”也愈增大, 以迫使迭代点向可行域接近。 如对不等式约束问题 (6.2.1)构造辅助函数 (6.2.2)对等式约束问题 (6.2.3) 29构造辅助函数 (6.2.4)对混合约束问题 (6.2.5)构

11、造辅助函数 (6.2.6)其中 为充分大的正数, 这样就将约束问题转化为求解无约束问题:(6.2.7) 30 称为罚参数, 当x为可行点时, F(x,)=f(x)。当x不是可行点时, 在x处辅助函数中的惩罚项是很大的数, 它的存在是对脱离可行域的点的一种惩罚, 其作用是在最优化过程中迫使迭代点靠近可行域, 这样求解无约束最优化问题便能得到约束问题的近似解, 而且罚参数的值越大, 近似程度就越好。 31 在实际计算中, 罚参数的选择十分重要。若太大, 就会给无约束问题的求解带来困难, 若太小则惩罚的力度不够, 将使无约束问题的解与约束问题解之间误差达不到要求, 因此实用中的罚参数常取为递增且趋于

12、无穷大的正数列k, 如取初始罚参数00 和增大系数2 , 则 32其中 迭代的终止条件可取:或终止条件为: 算法(外罚函数法) 1. 选择初始点x(0), 罚参数列k, 误差0, k1 2. 构造辅助函数3. 用某种无约束最优化算法, 以x(k-1)为初值求解 得最优解x(k)。4. 若x(k)满足终止条件, 停止计算并输出x*=x(k)。否则 令kk+1, 转2。 33定理6.2.1 设f(x), gi(x), hj(x)(i=1, 2, , m; j=1, 2, , l)连续, 约束问题(6.2.5)存在最优解, 若x(k)是由外罚函数法产生的无穷点列, 并且x*为其极限点, 则x*是约束

13、问题(6.2.5)的最优解。 34解: 构造辅助函数 由 有: 令 有: 该问题的准确解为(0.25,0.75)T; 现取k=0.14k-1例6.2.1 求解 迭代次数kx(k)10.1(0.071429,0.214286)T20.4(0.153846,0.461538)T31.6(0.216216,0.648649)T46.4(0.240602,0.721804)T525.6(0.247582,0.742747)T6102.4(0.249391,0.748173)T7409.6(0.249898,0.749542)T81638.4(0.249962,0.749886)T96553.6(0.2

14、49990,0.749971)T1026214.4(0.249998,0.749993)T 356.2.2 内罚函数法(内点法) 内罚函数法又称为内点法, 障碍函数法, 该方法是从满足约束条件的可行域的内点开始迭代, 并且对企图穿越可行域的边界的点予以“惩罚”。而且迭代点愈接近边界, “惩罚”就越大, 从而保证迭代点的可行性。此时辅助函数中惩罚项的作用相当于在可行域的边界设置障碍, 不让可行点穿越到可行域之外, 因此又叫障碍函数法。 36内点法只适合于解不等式约束问题 (6.2.8)记 或 称B(x)为内罚函数, 也称为障碍函数(Barrier function) 。 37记 称D0为可行域

15、的内部, 记为intD1。构造辅助函数 参数d0称为罚参数, 实用中罚参数取为单调减小的正数列dk, 常取d00,2, 令 初始点x(0)必须选在可行域的内部, 终止条件可取为: 或 38算法(内罚函数法)1. 选初始点x(0)D0, 罚参数列dk, 误差0, 令k1。 2. 构造辅助函数或 3. 选用某种无约束非线性规划方法, 以x(k-1)为初值求 解 得最优解x(k)。4. 若x(k)满足终止条件, 停止计算并输出最优解x*=x(k)。 否则令kk+1转2。 39定理6.2.2 设f(x), gi(x)(i=1, 2, , m)连续, 约束问题(6.2.8)存在最优解, 若x(k)是由内

16、罚函数法产生的无穷点列, 并且x*为其极限点, 则x*是约束问题(6.2.5)的最优解。例6.2.2 求解 解: 构造辅助函数 由 有 (当dk0+时) 迭代次数dkx(k)11(1.4142360,1.0000000)T20.1(1.1472697,0.3162277)T30.01(1.0488088,0.1000000)T40.001(1.0156883,0.0316227)T50.0001(1.0049876,0.0100000)T60.00001(1.0001581,0.0003162)T70.000001(1.0004999.0.0010000)T80.0000001(1.00015

17、81,0.0003162)T90.00000001(1.0000499,0.0001000)T100.000000001(1.0000158,0.0000316)T用解析法求最优解非常困难, 现取dk=10-(k-1), 得前10次计算结果为: 6.3 乘子法 乘子法是将罚函数法和Lagrange函数结合起来, 构造出更适当的辅助函数, 并借助Lagrange 乘子的迭代进行求解。 1. 等式约束问题的乘子法(P-H乘子法) 考察等式约束问题:其中f, hj(j=1, 2, , l)是二阶连续函数。 (6.3.1)构造辅助函数 (6.3.2) 41 42其中: 辅助函数F(x,)与Lagran

18、ge函数相比增加了惩罚项 , 而与罚函数相比又增加了乘子项Th(x), 这使得辅助函数与Lagrange函数和罚函数相比具有不同的性态, 而且对辅助函数来说, 只须取足够大的罚参数, 不必让+就可通过求解无约束问题(6.3.2)来得到等式约束问题(6.3.1)的局部最优解。 定理6.3.1 设x*是等式约束问题的局部最优解, *是相应的最优Lagrange乘子, 即:则存在00, 使得对所有的0, x*是F(x,*,)的严格局部极小点。 反之, 若存在 , 满足 , 且对某个 , 为 的无约束极小值点, 而且又满足二阶充分条件, 则 是等式约束问题的严格局部最优解。 43且对每个满足 的非零向

19、量p, 均有二阶充分条件成立, 即 44 由定理6.3.1的结论可知, 若知道了最优乘子*, 则只需取充分大的罚参数, 就可通过求F(x, *, )的极小值点来得到等式约束问题的最优解, 但在应用中最优乘子*一般难于得到,所以在实用中, 先给定充分大的和初始估计 , 然后在迭代过程中逐步修正, 使趋于* 。 假设在第k次迭代中Lagrange乘子向量的估计值为 , 罚参数取 , 得到 的极小值点为 , 此时有: 45若 线性无关, 则x(k)为等式约束问题(6.3.1)的最优解就应该有K-T条件成立, 即比较上面二式的结果就有:所以有迭代公式: 这样就可能有: 若(k)不收敛, 或者收敛速度慢

20、, 就增大罚参数, 再进行新的迭代, 收敛的快慢常用 来判断。 46算法(P-H方法)1. 给出初值x(0), 初始估计(1), 罚参数, 误差 0, 常数 。 2. 以x(k-1)为初值, 求解无约束问题 得最优解x(k)。 3. 若 或 , 停止计算, 输出近似 解x*=x(k); 否则转4。 4. 若 , 令 , 转5。 5. 计算 转2。 47例6.3.1 用乘子法求解 解: 构造辅助函数 由 得最优解 现取 48迭代次数(k)x(k)10(0.0714285,0.2142857)T2-0.0714285(0.1813186,0.5439559)T3-0.1813186(0.24071

21、87,0.7221562)T4-0.2407187(0.2496510,0.7489532)T5-0.2496510(0.2499966,0.7499898)T6-0.2499966(0.2499999,0.7499999)T6.3.2. 不等式约束问题的乘子法(Rockafellar乘子法) 引入松弛变量y=(y1, y2, , ym)T。将不等式约束问题化为等式约束问题 构造辅助函数为: 49 该方法是Rockafellar在1973年提出的, 考察不等式约束问题:将不等式约束问题转化为无约束问题: 将辅助函数配方得: 50为使辅助函数F(x,y,)达到极小, 取代入辅助函数中有: 将不等

22、式约束问题转化为求解无约束问题:由等式约束计算乘子的公式： 51代入（1），可得而 521. 给出初值x(0), 初始估计(1), 罚参数, 误差0, 常数 。 算法(Rockafellar乘子法) 终止条件：4. 若 ，转向5，否则令, ，转5。5. 计算 转2 532. 以x(k-1)为初值, 求解无约束问题 得最优解x(k)。3. 按式（2）计算 ，若 ，则 为近似最优解，停止计算，否则转向4例6.3.2 用Rockafellar乘子法求解 解: 构造辅助函数为: 54由 有: 取 , 数值计算结果如下表: 55迭代次数(k)x(k)11(0.65,0.325)T21.3(0.665,0

23、.3325)T31.33(0.6665,0.33325)T41.333(0.66665,0.333325)T51.3333(0.666665,0.3333325)T61.33333(0.6666665,0.33333325)T71.333333(0.66666667,0.333333333)T6.3.3. 混合约束问题的乘子法(PHR法)构造辅助函数为: 56 该方法是Rockafellar在PH算法的基础上提出的。考察混合约束最优化问题:迭代过程中, 取充分大的 , 并不断地修正乘子 和 , 修正公式为: 实用中罚参数 也可取为不断增加的数列 。 57 数值试验的结果表明, 乘子法克服了罚函

24、数法的病态性质, 它比罚函数法优越, 收敛速度快, 目前是求解约束最优化问题的最好算法之一。6.4 可行方向法 可行方向法的特点是: 在可行的迭代点处不断地构造适当的可行下降方向。 6.4.1 Frank-Wolfe方法 其中f是连续可微的非线性函数: 该方法是Frank和Wolfe于1956年提出的求解线性约束的一种算法, 考察线性约束的非线性规划问题 (6.4.1) 58记 Frank-wolfe法的基本思想是: 将目标函数f(x)线性化, 通过求解线性规划来得到可行下降方向, 并沿此方向在可行域内作一维搜索。 假设 是第k次近似解, 将f(x)在x(k)处进行一阶Taylor展开有: 由

25、此构造线性规划: 假设该线性规划有最优解y(k), 则有(6.4.2) 59定理6.4.1 设f(x)连续可微, , y(k)是相应线性规划问题(6.4.2)的解, 则有: 当 时, x(k)是最优化问题 (6.4.1)的K-T点。 (2) 当 时, 向量 是f(x)在点x(k)处关于可行域D的可行下降方向。 60算法(Frank-Wolfe法) 1. 给定初始可行点x(0), 误差0, k0。 2. 构造线性规划 并求得最优解y(k)。3. 若 , 停止计算, 输出解x*=x(k)。 否则转4。 4. 从x(k)出发沿方向pk=y(k)-x(k)进行一维搜索 5. 令 ; 转2。 61定理6

26、.4.2 设f(x)连续可微, D有界, , x(k)是由Frank-Wolfe法得到的点列, 则当x(k)是有限点列时, 其最后一个点x*是问题 (6.4.1)的K-T点。(2) 当x(k)是无限点列时, 它必有极限点, 并且其极限 点 是问题(6.4.1)的K-T点。 62 例6.4.1 利用Frank-Wolfe方法求解 解：取初值x(0)=(0, 0)T, 误差=10-6第一轮迭代: 构造近似线性规划 63求解此线性规划得解 由于 , 构造可行下降方向 一维搜索求解: 得步长 64第二轮迭代: 构造近似线性规划 求解此线性规划得y(1)=(0, 1)T。由于 , 构造可行下降方向 一维搜索求解 得步长 65第三轮迭代: 构造近似线性规划 得最优解 由于 , 停止计算输出最优解 x(2)是问题的K-T点。而且由于问题是凸规划, 故x(2)又是问题的整体最优解。 66 Frank-Wolfe法将问题归结为求解一系列辅助线性规划问题, 方法简单方便。但是由于该方法是一种可行方向法, 在每次迭代中, 搜索方向总是指向某个极点, 并且当迭代点接近收敛时, 搜索方向与目标函数的梯度向量正交。由前面无约束问题的结论可知, 这种搜索方向不是最好的下降方向, 因此算法收敛较慢。但该种方法对某些问题, 如研究交通问题时, 能得到较好的计算结果。因此Frank