最优化方法刘第七章.pptx

1、第七章约束最优化方法1 7.2 罚函数法2基本思想设法将约束问题求解转化为无约束问题求解具体说：根据约束的特点，构造某种惩罚函数，然后把它加到目标函数中去，将约束问题的求解化为一系列无约束问题的求解惩罚策略：企图违反约束的迭代点给予很大的目标函数值迫使一系列无约束问题的极小点或者无限地靠近可行域，或者一直保持在可行域内移动，直到收敛到极小点3外罚函数法引例：求解等式约束问题:解:图解法求出最优解构造：但是性态极坏，无法用有效的无约束优化算法求解4设想构造：其中是很大的正数求解此无约束问题得：当时，有：5等式约束问题构造：其中为参数，称为罚因子分析：当不是可行解时，越大，惩罚越重因此当充分大时，

2、应充分小即的极小点应充分逼近可行域，进而逼近(1)的最优解6不等式约束问题构造：分析：当不是可行解时，越大，惩罚越重因此当充分大时，应充分小即的极小点应充分逼近可行域，进而逼近(2)的最优解7一般约束问题构造：其中：注：一般取8例1：用外罚函数法求解：解：即：因此：9令：得：最优值：当时：10注：(1)往往不满足约束条件，都是从可行域外部趋向于的因此叫外罚函数法(2)通过求解一系列无约束最优化问题来求解约束最优化问题的方法，又称为序列无约束极小化技术SUMT.外罚函数法,又称SUMT外点法11外罚函数法算法Step1:给出(可是不可行点)，罚因子放大系数Step2:以为初始点求无约束问题：得S

3、tep3:若则停；否则转step4Step4:令转step2.12例2：用SUMT外点法求解：取求解迭代过程见下表：130.1(1.4539,0.7608)0.09350.18311(1.1687,0.7407)0.57530.390810(0.9906,0.8425)0.52030.1926100(0.9507,0.8875)1.94050.026714收敛性分析引理1：对于由SUMT外点法产生的点列总有：15收敛性分析定理1：设约束问题(3)和无约束问题(4)的整体最优解为和对正数序列且则由SUMT外点法产生的点列的任何聚点必是(3)的整体最优解证：不妨设因为和分别为(3)和(4)的整体最

4、优解，且所以有：16为单调有界序列，设其极限为亦为单调有界序列，设其极限为且连续；即为可行解为最优解；连续；即为(3)的整体最优解17外罚函数法评价(1)如果有了求解无约束问题的好算法，利用外罚函数法求解约束问题很方便(2)每个近似解往往不是可行解，这是某些实际问题所无法接受的内罚函数法可以解决(3)由收敛性定理取越大越好，而越大将造成增广目标函数的Hesse阵条件数越大，趋于病态，给无约束问题求解增加很大困难，甚至无法求解乘子法可解决这个问题18内罚函数法惩罚策略：在可行域的边界上筑起一道很高的“围墙”，当迭代点靠近边界时，目标函数值陡然增大，以示惩罚，阻止迭代点穿越边界，这样就可以把最优解

5、“挡”在可行域内了注：惩罚策略只适合于不等式约束问题，并且要求可行域的内点集非空19不等式约束问题构造：其中：或分析：为可行域的内点时，为有限正数，几乎不受惩罚；接近边界时，趋于无穷大，施以很重的惩罚；迫使极小点落在可行域内，最终逼近极小点20例3：用内罚函数法求解：解：令：21所以当时，注：一般最优解很难用解析法求出，需采用序列无约束最优化方法22内罚函数法算法Step1:给出(要求是可行点)，罚因子缩小系数Step2:以为初始点求无约束问题：得Step3:若则停；否则转step4Step4:令转step2.23例4：用SUMT内点法求解：取迭代结果见下表：2410(2.0402,3.162

6、3)12.529012.77551(1.1473,0.3162)3.61650.99510.1(1.0488,0.1000)2.96670.30490.01(1.0157,0.0316)2.76160.09530.001(1.0016,0.0316)2.70460.094125收敛性分析引理2：对于由SUMT内点法产生的点列总有：定理2：设可行域的内点集非空，在上存在极小点对严格单减正数列且则由SUMT外点法产生的点列的任何聚点是约束问题(2)的最优解26证：由于由引理2知单调减少且下有界，于是它有极限，记作即：若能证明：则可得：再由的连续性，可得：即是(2)的最优解27再证：由的连续性知，对

7、于任意小的正数存在取满足的使得：由知，对于同一个存在当时又因为28乘子法引例：求解等式约束问题:解:最优解分析：对于任何关于的极小点是不存在的正因为如此，才引进外罚函数法的29问题：能否找到某个使恰好是的无约束极小呢？回答是否定的设想：能否在不改变最优解的前提下，以某个在最优解处梯度为零的函数来取代呢？启发：(增广Lagrange函数)通过求解增广Lagrange函数的序列无约束问题来获得原约束问题的解30等式约束问题的乘子法其中和二阶连续可微设为Lagrange乘子向量，则对应Lagrange 函数为：设是的极小点， 是相应的乘子向量 (1)可等价为：31启发：采用外罚函数法构造：我们将证明

8、：适当大时，是极小点但是未知的，在求的同时，采用迭代法求出这是乘子法的基本思想32定理：设与满足为问题(1)的严格局部极小点的二阶充分条件，则存在使对所有为的严格局部极小点；反之，若且对某个是无约束问题(5)的局部极小点，则是约束问题(1)的局部极小点.33算法构造采用迭代法求点列使设已有和则由一阶最优性条件有：要求和且采用：或：34例5：用乘子法求解：解：增广Lagrange函数为：令：得：35所以：乘子迭代公式为：即：取：所以：设对上式取极限有：得：得：36等式约束的乘子法(PH算法)Step1:给出Step2:以为初始点求无约束问题：得Step3:若则停；否则转step4Step4:当及

9、放大系数转step5;否则令转step5;Step5:令转step2;37作业(1)用外罚函数法求解：(2)用内罚函数法求解：38 7.4 SQP方法39基本思想无约束变尺度法是在牛顿法的基础上发展而来的，而牛顿法可以看作是求梯度零点（最优性条件）的一种方法对于约束最优化问题，我们同样希望用牛顿法来求解K-T点，并在此基础上发展形成了约束变尺度法SQP算法与有关算法相比具有许多显著的优点，目前认为该方法是求解中小规模约束问题的十分有效的方法40等式约束问题其Lagrange函数为：一阶最优性条件为：或者为：其中表示约束的Jacobi矩阵：41上述方程组是含有个方程和个未知量的非线性方程组，用牛

10、顿法解这个方程组可得：其中和是下面牛顿方程组的解：42把这个方程组展开得：考虑到以及可以将方程组改写成：所得解为和43而以上方程组恰好是下面二次规划问题的一阶必要条件，是其最优Lagrange乘子注：(1)SQP方法就是通过求解一系列二次规划问题产生收敛于问题最优解和Lagrange乘子的迭代序列和44(2)二次规划问题中，约束是原问题约束的线性近似，但目标函数却不是原问题中目标函数的二次近似这个函数的Hesse阵为它不仅包含目标函数的二阶导数信息，而且还包含了所有约束函数的二阶导数信息45一般约束最优化问题每次迭代所要求解的二次规划子问题为：46注：(1)以上方法实质上是求等式约束问题的La

11、grange函数的平稳点，被称为拉格朗日牛顿法，它最早是由Wilson(1963)提出的(2)以上方法虽然收敛速度可达二阶，但是仅仅是局部收敛的，对初始点的选取要求较高为了保证全局收敛性，必须定义某一衡量和的好坏、在原问题最优解处达到极小的效益函数,然后针对效益函数沿由(3)确定的方向进行线性搜索。47(3)Lagrange-Newton法最主要的缺点是要求计算Lagrange函数的Hesse阵，使其因为计算量太大而失去应用价值。为了克服计算Hesse阵的缺点，借鉴无约束最优化中的拟牛顿法，在每次迭代中用一正定阵近似Hesse阵，而随着迭代的进行将用拟牛顿公式对进行修正。因此，人们常称这类算法为约束变尺度法。(4)Lagrange-Newton法最重要的理论贡献是：由它我们得知可通过逐步求解(3)的二次规划子问题来求解一般的非线性约束问题。48SQP方法的一般迭代格式Step1:给定正定阵令Step2:求解二次规划子问题得解及其对应的乘子49Step3:针对所选的效益函数从点沿方向进行线搜索确定步长并令Step4:利用等信息，采用某种拟牛顿公式对进行修正，得到令转Step2注：上述算法中，当时，即为无约束变尺度法的格式50效益函数Han(韩世平)1977年提出用如下的精确罚函数作效益函数：注：在线搜索中，使下降，相当于兼顾了的下降和违反约束