第五章-约束优化方法(1)

第五章约束优化方法约束优化方法概述约束优化问题的最优解及其必要条件约束坐标轮换法约束随机方向法复合形法惩罚函数法教学要求：1、掌握约束优化局部最优解的必要条件。2、掌握复合形法得原理及程序设计。3、掌握内点法和外点法的惩罚函数的构造原理及程序设计。约束优化方法概述在工程实际中，优化问题大都属于有约束的优化问题，即其设计变量的取值要受到一定的限制，用于求解约束优化问题最优解的方法称为约束优化方法。一、约束优化问题的类型根据约束条件类型的不同可以分为三种，其数学模型分别如下：1、不等式约束优化问题（IP型）2、等式约束优化问题（EP型）3、一般约束优化问题（GP型）二、约束优化方法的分类约束优化方法按求解原理的不同可以分为直接法和间接法两类。1、直接法只能求解不等式约束优化问题的最优解。其根本做法是在约束条件所限制的可行域内直接求解目标函数的最优解。如：约束坐标轮换法、复合形法等。其基本要点：选取初始点、确定搜索方向及适当步长。搜索原则：每次产生的迭代点必须满足可行性与适用性两个条件。适用性：当前迭代点的目标函数值较前一点是下降的，即满足F(xk+1)F(xk)可行性：迭代点必须在约束条件所限制的可行域内，即满足gu(x)0,u=1,2,…,p2、间接法该方法可以求解等式约束优化问题和一般约束优化问题。其基本思想是将约束优化问题通过一定的方法进行改变，将约束优化问题转化为无约束优化问题，再采用无约束优化方法进行求解。如：惩罚函数法5.1约束优化问题的最优解及其必要条件5.1.1局部最优解与全局最优解对于具有不等式约束的优化问题，若目标函数是凸集上的凸函数，则局部最优点就是全局最优点。如左图所示，无论初始点选在何处，搜索将最终达到唯一的最优点。否则，目标函数或可行域至少有一个是非凸性的，则可能出现两个或更多个局部最优点，如右图所示，此时全局最优点是全部局部最优点中函数值最小的一个。对于具有等式约束的优化问题，若出现两个或两个以上的局部最优点，此时全局最优点是全部局部最优点中函数值最小的一个。对于具有一般约束的优化问题，若出现两个或两个以上的局部最优点，此时全局最优点是全部局部最优点中函数值最小且同时满足等式约束与不等式约束的一个。例如：设数学模型为该优化问题的最优点如下图所示，对于这两个局部最小点x1*=[-10]T,x2*=[50]T，其函数值不同，F(x1*)=4,F(x2*)=16。全局最优点为x1*=[-10]TF*=4h(x)h(x)g(x)x1*x2*x1x2246-25.1.2起作用约束与不起作用约束对于一般约束优化问题，其约束分为两类：等式约束、不等式约束。在可行设计点x(k)处，对于不等式约束，若gi(x(k))=o，则称第i个约束gi(x)为可行点的起作用约束；否则，若gi(x(k))o，则称gi(x)为可行点的不起作用约束。即只有在可行域的边界上的点才有起作用约束，所有约束对可行域内部的点都是不起作用约束。对于等式约束，凡是满足该约束的任一可行点，该等式约束都是起作用约束。1、约束优化问题的最优解不仅与目标函数有关，而且与约束集合的性质有关。2、在可行设计点x(k)处，起作用约束在该点的邻域内不但起限制可行域范围的作用，而且还可以提供可行搜索方向的信息。3、由于约束最优点一般发生在起作用约束上，不起作用约束在求解最优点的过程中，可以认为是无任何影响，所以可以略去不起作用约束，把所有起作用约束当作等式约束问题求解最优点。5.2约束优化问题极小点的条件约束优化问题极小点的条件，是指在满足约束条件下，目标函数局部极小点的存在条件。约束问题最优解的存在条件有两种：一是极小点在可行域内部，二是极小点在可行域的一个或几个边界交汇处。5.2.1不等式约束问题解的必要条件第一种情况：如图所示，g1(x*)=0，g2(x*)0，g3(x*)0。所以g1(x)为起作用约束，g2(x)、g3(x)为不起作用约束。由于约束最优点是目标函数与约束g1(x)边界的切点，故目标函数与约束函数的梯度必共线，而且方向一致。若取非负乘子1*0，则在x*处存在如下关系F(x*)-1*g1(x*)=0x*g1(x*)g3(x)F(x*)g1(x)g2(x)第二种情况：如图所示，若最优点位于两约束的交点上，则目标函数的梯度矢量夹于两约束函数梯度矢量之间。则目标函数的梯度可以表示为约束函数梯度的线性组合，若取非负乘子1*0，2*0，则在x*处存在如下关系F(x*)=1*g1(x*)+2*g2(x*)g1(x*)g2(x*)g2(x)g1(x)F(x*)结论：对于不等式约束优化问题，其最优解的必要条件为5.2.2等式约束问题解的必要条件如图所示，目标函数梯度矢量与约束函数梯度矢量共线。因此，一定存在一个乘子，使得下式成立：F(x*)-*h(x*)=0对于一般等式约束优化问题，其最优解必要条件为x*h(x)=0F(x*)h(x*)5.2.3一般约束问题解的必要条件由上述不等式约束优化与等式约束优化问题解的必要条件，可以推出一般约束优化问题最优解的条件：5.2.4库恩-塔克条件在优化实用计算中，为判断可行迭代点是否是约束最优点，或者对输出的可行结果进行检查，观察其是否满足约束最优解的必要条件，引入库恩-塔克条件。λuμv称为拉格朗日乘子上式也称为约束优化问题局部最优点的必要条件。在迭代点处展开式的形式为……一般情况下，其作用约束数J不大于问题的维数其中是待定系数矢量如果点是最优点，则必须满足K-T条件；反之，满足K-T条件的点则不一定是约束最优点。解上式，得一组λj（j=1，2……J），如果λj（j=1，2……J）均为非负，表示满足K-T条件。该条件是为极小点的必要条件。只有当目标函数是凸函数，约束构成的可行域是凸集时，则满足K-T条件的点是全局极小点的必要而充分条件。当迭代点有两个起作用约束，写出目标函数与约束集的关系如下：讨论:约束最优解的必要条件——几何条件最优点非最优点区域内区域外例题5.1设约束优化问题D：它的当前迭代点为，试用K-T条件判别它是否为约束最优点。解：⑴计算点的诸约束函数值⑵点的起作用约束是⑶求点的诸梯度⑷求拉格朗日乘子按K-T条件应有写成线性方程组解得乘子均为非负，满足约束最优解一阶必要条件如图所示，点确实是该约束优化问题的局部解。而且，由于F(x)是凸函数，可行域为凸集，所以该点也是问题的全局最优解上题图约束坐标轮换法约束随机方向法复合型法惩罚函数法5.3常用约束优化方法5.3.1约束坐标轮换法约束坐标轮换法与无约束坐标轮换法的区别约束坐标轮换法的基本思想与无约束坐标轮换法基本相同，其主要区别如下：1、沿坐标方向搜索的迭代步长采用加速步长，而不是采用最优步长。因为按照最优步长所得到的迭代点往往超出了可行域。2、对于每一个迭代点，不仅要检查目标函数值是否下降，而且必须检查是否在可行域内，即进行适用性和可行性的检查。以为起点，取一个适当的初步步长按迭代式一.方法概述首先在可行域D内任取一初始点，并取迭代精度ε。取得沿x1坐标轴正向的第一个迭代点，检查该点的适用性和可行性，即检查?)()()0()1(1xFxF?)1(1Dx如果两者均满足，则步长加倍再按迭代式获得沿x1正向的第二个迭代点。下面的各次迭代，只要对新迭代点的适用性和可行性的检查都通过，再倍增步长后按迭代式不断产生新迭代点但是，当迭代点到达时，该点已违反了可行性条件，于是返回到前一迭代点作为沿e1方向搜索的终点。转而改沿x2坐标轴正向进行搜索。在图示情况下，正向的第一个迭代点目标函数值增加，即不再满足适用性条件，故改取该坐标轴的反方向，并取步长进行迭代，以后的迭代方向与前述的相同，以加速步长继续迭代，直到至少违反适用性与可行性条件之一时，可确定沿e2方向的迭代终点。如此反复的进行各坐标轴方向的迭代，点列将逐步逼近最优点x*。当迭代点到达，如出现下面的情况：不论沿e1或e2正，反方向以步长进行搜索，所得邻近的四个点当他们都不能同时满足适用性和可行性条件时，此即可作为约束最优点输出。如果要获得精度更高些的解，还可以缩减初始步长。后在继续迭代，直至时，才输出最优点，并停止计算。约束坐标轮换法算法明了、迭代简单、便于掌握和运用。但是其收敛速度较慢，而且在某些情况下，会出现“死点”。如图中的点xk，该点已经逼近约束边界，其后的迭代点无论沿何方向，都不可能同时满足适用性及可行性的要求。故xk点作为最优解输出，但显然它就是一个伪最优点。为辨别输出最优点的真伪，可以用K-T条件检验。5.3.2随机方向法参看右图预先选定可行初始点，利用随机函数构成随机方向S1，按给定的初始步长，沿S1方向取得试探点检查x点的适用性和可行性若满足将作为新的起点再产生另一随机方向S2，以步长重复以上过程，得到沿S2方向的最终成功点。如此循环，点列必将逼近于约束最优点x*。继续按下面的迭代式在S1方向上获取新点。重复上述步骤，迭代点可沿S1方向前进。直至到达某迭代点不能同时满足适用性和可行性条件时结束。退回到前一点作为该方向搜索中的最终成功点，记作。若在某个换向转折处，沿某随机方向的试探点目标函数值增大或者越出可行域，则弃去该方向，再产生另一随机方向作试探。试探成功就前进，否则，重新产生新随机方向。约束随机方向法的搜索方向比坐标轮换法要灵活多。当预定的随机方向限定数M足够大时它不会像坐标轮换法那样出现“病态”而导致输出伪最优点。当在某个转折点处沿M个随机方向试探均失败，如图中点，则说明以此点为中心，为半径的圆周上M个点都不是适用且可行的点。此时，可将初始步长缩半后继续试探。直到，且沿M个随机方向都试探失败时，则最后一个成功点就是达到预定精度要求的约束最优点，迭代即可结束。M是预先规定的在某转折点处产生随机方向所允许的最大数目。一般在50-500范围内选取。对于性态不好的目标函数或可行域有狭长弯道的问题，M应取较大值。5.3.3复合形法复合形法是求解约束优化问题的一种重要的直接解法。一、复合形法的基本思想基本思路是在可行域内构造一个具有k个顶点的初始复合形。对该复合形各顶点的目标函数值进行比较，去掉目标函数值最大的顶点（称最坏点），然后按一定法则求出目标函数值下降的可行的新点,并用此点代替最坏点，构成新的复合形，复合形就向最优点移动一步，直至逼近最优点。引例：设有一约束优化的模型为D：该问题的目标函数见下图目标函数等直线和可行域的几何描述迭代过程)()(00)4(Hxxxx二、初始复合形的构成要构成初始复合形，实际上就是确定k个可行点作为复合形的顶点，顶点数目一般在n+1k2n范围内。对于维数较低的优化问题，因顶点数目较少，可以由设计者自行凑出可行点作为复合形顶点。但对于维数较高的优化问题，这种方法常常很困难。为此，提出构成复合形的随机方法。该方法是先产生k个随机点，然后再把那些非可行随机点调入可行域内，最终使k个随机点都成为可行点而构成初始复合形。构成复合形的随机方法：1、产生k个随机点利用标准随机函数产生在（0，1）区间内均匀分布的随机数i，然后产生区间（ai，bi）内的随机变量xi，xi=ai+i（bi-ai），i=1，2，…，n。以这n个随机变量为坐标构成随机点x,第一个点记作x(i)同理，再次产生在（0，1）区间内均匀分布的随机数i，然后获得区间（ai，bi）内的随机点x(2)，依次类推，可以获得k个随机点x(1)、x(2)、x(3)、...、x(k)。可以看出，产生k个随机点总共需要产生kn个随机数。2、将非可行点移入可行域用上述方法的随机点不一定是可行点。但是只要它们中至少有一个点在可行域内，就可以用一定的方法将非可行点移入可行域。如果k个随机点没有一个是可行点，则应重新产生随机点，直至其中有至少一个是可行点为止。将非可行点移入可行域的方法：依次检查随机点x(1)、x(2)、x(3)、...、x(k)的可行性。将查出的第一个可行点x(j)与x(1)对调，则新的x(1)点为可行点，然后检查