第五章约束优化方法

1第五章约束优化方法5.1约束优化问题的最优解5.2约束优化问题极小点的条件5.3常用的约束优化方法5.3.1约束坐标轮换法5.3.2约束随机方向法5.3.3复合形法5.3.5惩罚函数法2概述约束优化问题最优解****12...TnXxxx*min()()FXFX最优值最优点约束最优解和无约束最优解无论是在数学模型上还是几何意义上均是不同的概念3(2,0)等值线等值线族的中心1x()Fx2x无约束最优解解：等值线的共同中心.2212112min()44TnFXxxxXxxR数学模型:4数学模型:1x()Fx2x可行域约束最优解51x2xo211()gX4()gX3()gX2()gX*1X*120TX无约束最优点*2X*20.581.34TX约束最优点6约束优化问题的类型1.不等式约束优化问题(IP型)2.等式约束优化问题(EP型)3.一般约束优化问题(GP型)7约束优化方法分类约束优化方法约束坐标轮换法直接法：约束随机方向法复合形法间接法：惩罚函数法直接法：设法使每一次迭代产生的新迭代点限制在可行域内，且一步一步的降低目标函数值，直至最后获得一个可行域内的约束最优解。间接法：将约束优化问题通过一定形式的变换，转化为无约束优化问题，然后采用约束优化方法进行求解。85.3.1约束坐标轮换法基本思想:与无约束坐标轮换法类似,依此沿坐标轴方向寻优,逐步逼近最优点。1x2xo(0)X(1)1X(1)2X(1)3X(1)4X(1)X(2)1X(2)1X(2)2X(2)3X(2)X(3)X(4)X91x2xo(0)X(1)1X(1)2X(1)3X(1)4X(1)X任取一个初始点(0)XD取初始步长α0沿e1方向(1)(0)11XXe0检查可行性:适用性:(1)(0)1?FXFX(1)1?XD2(1)(0)21XXe检查......加速步长(1)(0)31,2XXe(1)(0)41,2XXe检查可行性:适用性:(1)1)?(XD(1)(1)3XX101x2xo(0)X(1)1X(1)2X(1)3X(1)4X(1)X(2)1X(2)1X(2)2X(2)3X(2)X沿e2方向(2)(1)12XXe0检查可行性:适用性:(2)(1)1?FXFX(2)1?XD(2)(0)22,2XXe检查可行性:适用性:(2)2?XD(2)(2)2XX检查可行性:适用性:(2)(1)1()?FXFX(1)2?XD(2)(1)12XXe(2)(1)2?FXFX(2)(0)32,2XXe检查可行性:适用性:(2)3)?(XD111x2xo(0)X(1)1X(1)2X(1)3X(1)4X(1)X(2)1X(2)1X(2)2X(2)3X(2)X(3)X沿e1方向(3)(2)11XXe0检查可行性:适用性:(3)2)?(XD2(4)(0)12XXe检查可行性:适用性:(3)(2)1?FXFX(3)1?XD(3)(2)21XXe(3)(3)1XX沿e2方向0检查可行性:适用性:(4)(3)1()?FXFX(4)1?XD0(4)(0)12XXe检查......121x2xo(0)X(1)1X(1)2X(1)3X(1)4X(1)X(2)1X(2)1X(2)2X(2)3X(2)X(3)X沿坐标轴方向找不到合适的点:缩减初始步长α0←0.5α0继续迭代终止准则:α0≤ε约束坐标轮换法与无约束坐标轮换法的区别：①步长无约束:最优步长约束:加速步长②对每一个迭代点的检查无约束:检查适用性约束:检查适用性和可行性③终止准则无约束:点距准则约束:步长准则13特点:1x2xo(0)X(1)1X(1)2X(1)3X(1)4X(1)X(2)1X(2)1X(2)2X(2)3X(2)X(3)X约束坐标轮换法具有算法明了、迭代简单、便于设计者掌握运用等优点。但是，它的收敛速度较慢，对于维数较高的优化问题(例如10维以上)很费机时。另外，这种方法在某些情况下还会出现“死点”的病态，导致输出伪最优点。避免输出伪最优点的办法:1、输入不同的初始点2、用不同的不长多次计算14基本原理：典型的“瞎子爬山”式的数值选代解法。在可行域内，任选初始点x(0)，以给定的步长a=a0，沿按某方法产生的随机方向S(1)取探索点x=x(0)+aS(1），若该点同时符合下降性（F(x)F(x(0)))和可行性（x∈D)则表示x点探索成功。并以它为新的起始点，继续按上面的迭代公式在S(1）方向上获取新的成功探索点……..5.3.2约束随机方向法155.3.2约束随机方向法任取一个初始点(0)XD取初始步长α00利用随机函数构成随机方向S(1)检查可行性:适用性:?()XD(0)(1)XXS(0)?FXFX?XD(0)()?FXFX(0)(0)(1),XXXXS检查(0)X(1)S(1)X(2)S(2)X若m个方向都不行,则减小步长:α0←0.5α0终止准则:α0≤ε(3)X16说明当在某个转折点处沿m个(预先限定的次数)随机方向试探均失败，则说明以此点为中心，α0为半径的圆周上各点都不是适用、可行点。此时，可将初始步长α0缩半后继续试探。直到α0≤ε，且沿m个随机方向都试探失败时，则最后一个成功点(如图中的x(3))就是达到预定精度ε要求的约束最优点，迭代即可结束。m是预先规定在某转折点处产生随机方向所允许的最大数目。一般可在50~500范围内选取。约束随机方向法的搜索方向比坐标轮换法要灵活得多。当预定的随机方向限定数m足够大时，它不会像约束坐标轮换法那样出现“病态”而导致输出伪最优点。17随机搜索方向的产生在（a,b）之间的随机数：yi=ai+(bi–ai)（-1,1）之间的随机数：yi=2-1设是在区间(一l，1)上的两个随机数。将它们分别作为坐标轴上的分量所构成的向量即为相应的二维随机向量，其单位向量：同理，n维问题,随机方向的单位向量：ii在算法语言所使用的函数库中，有一种随机函数RND(X)。利用这一随机函数可在程序运行过程中产生一个0到1之间的随机数。(i＝l，2，…，n)0,1i18约束随机方向搜索法的特点：对目标函数的性态无特殊要求，程序设计简单，使用方便。在维数较少的情况下是一种十分有效的方法，适用于小型问题。195.3.3复合形法基本思想：在可行域中选取K个点作为一复合形（多面体）的K个顶点。比较各点函数值的大小，去掉函数值最大所对应的最坏点，而代之最坏点的映射点构成新的复合形。不断重复上述过程，使复合形不断向最优点移动和收缩，直至满足选代精度为止。1xo2x132X0X(R)n+l≤k≤2n20[引例]设有一约束优化问题的数学模型1xo2x4g3g2g1g5g21一、复合形法的基本思想步骤：第一步：初始复合形的构成顶点X(1)、X(2)、X(3)第二步：对复合形进行调优迭代计算顶点X(1)、X(2)、X(3)F1F2F3↓↓X(H)X(L)坏点好点先求出除坏点外，其余各点构成的图形的形心点X0再求坏点X(H)相对于形心点X0的映射点X(R)1xo2x132X0X(R)22步骤：第一步：初始复合形的构成第二步：对复合形进行调优迭代计算形心点X0映射点X(R)α:反射系数，一般开始是取α=1.31xo2x132()()00()RHXXXX()()00()RHXXXX检查可行性:适用性:()?RXD()()?RHFXFX新复合形4点的映射复合形的收缩23二、初始复合形的构成方法一:试凑法方法二:随机产生(1)产生K个随机点随机数(i＝l，2，…，n)0,1i12...TnXxxx(1,2,...)iiiiixabain(2)将非可行点调入可行域123424终止条件:12()()211{()()}KjLjfXfXK25例:用复合形法求解下例约束最优化问题，迭代精度取01.02221)3()(min2xxXfRx04)(2211xxXg0)(22xXg05.0)(13xXg解：取复合形的顶点数:4222nK(1)获得初始复合形:本例采用人为给定四个点25.0)1(X21)2(X36.0)3(X6.29.0)4(X检验各点是否可行：将各点的坐标值代入以上三个约束方程，均满足约束要求，这四个点为可行点，用作初始复合形的四个顶点26(2)迭代计算获得新复合形计算复合形各顶点目标函数值，定出最坏点最好点计算除坏点外其余各顶点的中心25.10)()1(Xf8)()2(Xf76.14)()3(Xf17.11)()4(Xf)3()(XXH)2()(XXL2.28.0}6.29.02125.0{141}(11)4()2()1()(XXXKXC将代入诸约束条件均满足，可知在可行城内。)(CX取，求坏点的映射点3.1a)(HX)(RX)()()()()(HcCRXXaXX16.106.1)36.02.28.0(3.12.28.0)(CX在可行域内)(RX27计算并与比较：)()(RXf)()(RXf用替换，亦即替换构成新的复合形：)(1092.5)()()(HRXfXf)(RX)(HX比较各点目标函数值，定出最坏点:最好点:6.29.0,16.106.1,21,25.0)4()3()2()1(XXXX)4()(XXH)3()(XXL2284.4})1092.517.11()1092.51092.5()1092.58()1092.525.10(41{}))((())()(())()(())()((41{})()(1{212222212)3()4(2)3()3(2)3()2(2)3()1(1212)()(XfXfXfXfXfXfXfXfXfXfKKjLj（3）检验迭代终止条件2829复合形法的特点:对目标函数及约束函数无特殊要求，适应性强，计算量一般，收敛较快，适用中小型问题。是现有解不等式约束优化问题的一种重要的直接法。305.3.5惩罚函数法将约束优化问题通过一定形式的变换，转化为无约束优化问题，然后采用约束优化方法进行求解转化必须满足条件：1、不破坏原约束问题的约束条件，2、最优解必须归结到原约束问题的最优解上去。约束优化问题的间接法有:消元法、拉格朗日乘子法、惩罚函数法等.31minφ(x，r(k)，m(k))(5.56)x∈Rn式中，φ(x，r(k)，m(k))为增广函数，称为惩罚函数，简称罚函数将一般约束优化问题数学模型minF(x)x∈Rn：gu(x)≥0，u＝l，2，…，phv(x)=0，v=1，2，…，q转化成为一个如下的无约束优化问题构造的新目标函数一般形式为惩罚函数法惩罚项32按照惩罚函数构成的形式不同，惩罚函数法又分为三种：1、内点惩罚函数法2、外点惩罚函数法3、混合惩罚函数法33一、内点惩罚函数法基本思想：将新目标函数定义于可行域内，序列迭代点在可行域内逐步逼近原目标函数约束边界上的最优点。将约束优化问题：minF(x)x∈:gu(x)≥0(u=12……m)转化为无约束优化问题其中：r(1)r(2)r(3)…r(k)…0是一个递减的正值数列：r(k)＝Cr(k-1)，0＜C＜1(k)=0limkr34内点惩罚函数法的思路:当X由可行域内靠近任一约束边界时,惩罚项值趋于无穷