约束优化方法.ppt

第五章约束优化方法约束优化方法概述2、等式约束优化问题（EP型）
3、一般约束优化问题（GP型）二、约束优化方法的分类约束优化方法按求解原理的不同可以分为直接法和间接法两类。
1、直接法只能求解不等式约束优化问题的最优解。其根本做法是在约束条件所限制的可行域内直接求解目标函数的最优解。如：约束坐标轮换法、复合形法等。其基本要点：选取初始点、确定搜索方向及适当步长。搜索原则：每次产生的迭代点必须满足可行性与适用性两个条件。适用性：当前迭代点的目标函数值较前一点是下降的，即满足F(xk+1)<F(xk)5.1约束优化问题的最优解及其必要条件对于具有等式约束的优化问题，若出现两个或两个以上的局部最优点，此时全局最优点是全部局部最优点中函数值最小的一个。对于具有一般约束的优化问题，若出现两个或两个以上的局部最优点，此时全局最优点是全部局部最优点中函数值最小且同时满足等式约束与不等式约束的一个。例如：设数学模型为该优化问题的最优点如下图所示，对于这两个局部最小点x1*=[-10]T,x2*=[50]T，其函数值不同，F(x1*)=4,F(x2*)=16。全局最优点为x1*=[-10]TF*=45.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*)=0
第二种情况：如图所示，若最优点位于两约束的交点上，则目标函数的梯度矢量夹于两约束函数梯度矢量之间。则目标函数的梯度可以表示为约束函数梯度的线性组合，若取非负乘子1*0，2*0，则在x*处存在如下关系F(x*)=1*g1(x*)+2*g2(x*)
结论：
对于不等式约束优化问题，其最优解的必要条件为5.2.2等式约束问题解的必要条件如图所示，目标函数梯度矢量与约束函数梯度矢量共线。因此，一定存在一个乘子，使得下式成立：F(x*)-*h(x*)=0
对于一般等式约束优化问题，其最优解必要条件为5.2.3一般约束问题解的必要条件由上述不等式约束优化与等式约束优化问题解的必要条件，可以推出一般约束优化问题最优解的条件：5.2.4库恩-塔克条件
在优化实用计算中，为判断可行迭代点是否是约束最优点，或者对输出的可行结果进行检查，观察其是否满足约束最优解的必要条件，引入库恩-塔克条件。λuμv称为拉格朗日乘子
上式也称为约束优化问题局部最优点的必要条件。在迭代点处展开式的形式为如果点是最优点，则必须满足K-T条件；
反之，满足K-T条件的点则不一定是约束最优点。当迭代点有两个起作用约束，写出目标函数与
约束集的关系如下：例题5.1设约束优化问题⑵点的起作用约束是上题图约束坐标轮换法
约束随机方向法
复合型法
惩罚函数法5.3.1约束坐标轮换法以为起点，取一个适
当的初步步长
按迭代式取得沿x1坐标轴正向的第一个迭代点，检查该点的
适用性和可行性，即检查但是，当迭代点到达时，该点已违反了可行性条件，
于是返回到前一迭代点作为沿e1方向搜索的终点。当迭代点到达，如出现下面的情况：约束坐标轮换法算法明了、迭代简单、便于掌握和运用。但是其收敛速度较慢，而且在某些情况下，会出现“死点”。如图中的点xk，该点已经逼近约束边界，其后的迭代点无论沿何方向，都不可能同时满足适用性及可行性的要求。故xk点作为最优解