第四章非线性规划5-可行方向法

第五节 可行方向法（FDM ）可行方向法是用梯度去求解约束非线性最优化问题的一种有代表性的直接探索方法，也是求解大型约束优化设计问题的主要方法之一。其收敛速度快，效果较好，适用于大中型约束最优化问题，但程序比较复杂。可行方向法(Feasible Direction Method)是一种直接搜索方法，其搜索方向的获取利用了目标函数和约束函数的梯度信息。用目标函数的梯度可以得到目标函数值的下降方向，而利用约束函数的梯度则可以得到可行的搜索方向。因此，可行方向法的搜索方向实质上是既使目标函数值下降，同时又可行的方向，即可行下降方向。满足这一条件的方法就称为可行方向法。一、基本原理当求解目标函数的极小值 min() . 0 1,23,nufXRstgm当设计点 处于起作用约束 上时，下降可行方向 S 必须同时满足条件：()kiTiSX()0kf由于于多数非线性规划的最优点都处在可行区的约束边界上或者几个约束边界的交点上，因此最优搜索如能沿着约束边界附近进行，就有可能加速最优化搜索的进程。按照这一基本思路，在任意选定初始点后到最后得到最优点必须解决三个问题：一是如何尽快使最优搜索从初始点到达约束边界二是到达边界后怎样判断所找到的边界点是否是最优点；三是如果边界点经判断不是最优点，那么下一步应如何进行最优搜索。二、如何从初始点尽快到达边界在任意选定初始点 之后，首先判断 是否为可行点，0X0X若是可行点，则选择目标函数的负梯度方向作为下一步的搜索方向。若是非可行点，则选择目标函数的梯度方向为搜索方向。搜索的步长可采用试探的方法逐步缩小，直到最后到达边界。如图 5-13 表示了初始点为可行点 时的搜索过程。从初始点 出发沿 方向，取步长为 t，进行0X0()f搜索，得到 100()tf若 仍在可行区内，则把步长加大一倍继续搜索得到121()Xtf若 仍在可行区内，则把步长再加大一倍继续搜索，如1此方法得到新点只要仍在可行区内，则加大步长只到得到的点进入非可行区。一旦进入非可行区后，即可改变方向，沿得到点的梯度方向进行搜索，此时步长为原步长的一半进行搜索。每次判断得到的点 是否属于可行区，若是则沿 ，若否，则沿 方向搜索，但kX()kfX()kfX是步长一直是前一个步长的一半，如此反复，只到收敛到边界上。收敛到边界点的条件是,只要任一个约束函数为 0：（i=1,2,m ）()0kig搜索过程中的两条原则：一是搜索方向由迭代点处于可行区还是非可行区而取负梯度方向或是梯度方向；二是搜索步长在第次越过约束边界前步长是逐次增加的，而此后不管迭代点是可行点还是非可行点都是逐次减小的。这两条原则对于初始点为非可行点时也向样适用，即初始点 X0 为非可行点时，进入可行区之前步长是每次加大的，一旦首次跨进可行区，则以后的步长每次都是缩小的。三、到达边界后怎样判断所找到的边界点是否是最优点库恩-塔克条件：（D 为补偿向量）11nrFGC且令 （D 与所有起作用约束正交）0()T零 向 量通过求解 D 的值来判断。（1）若 D=0（零向量） ，且 Ci0 时（i=1,2,3, ,r） ） ，则设计点为局部最优点，如果问题是凸规划，则为全局最优点；（2）若 D0，则该点不是最优点。（3）若 D=0（零向量） ，但 Ci0 不能满足，则将 Ci0 对应的 从 中剔除，形成新的igG之后再重新计算 C 和 D，此时，必有 D0。如图中的 A 点，当对应的 剔除后，A 点即变成了G 1与 B 点同类型的点，所以，必有 D0。另外，从 A 到 E 搜索过程中，约束边界 g1=0 已经不是起作用的约束了。应当从 中剔除。四、如果边界点经判断不是最优点，那么下一步应如何进行最优搜索。当约束界面上的设计点经判断不符合 K-T 条件而为非最优点时，就必须继续进行最优捏索，确定最优搜索方向。方法的不同可以得到不同的搜索方向，也就构成了不问的可行方向法。常用的有三种方法确定搜索方向：1. 由约束面上的 点出发，沿可行下降方向作一维最优化探索，若所得新点 在可行域内，则kX 1kX再沿 方向作一维最优化探索；若所得新点不在可行域内，则应将它移至约束面上再重复上述()kf步骤。当 时，则停止迭代。2.由点 出发，沿可行下降方向以最大步长从一个约束面到另一约束面，如此进行，直至满足式库k恩塔克条件3. 沿着约束面进行探索，把补偿向量 D 的方向作为最优搜索方向。D 的方向总是指向最优点而不会背离最优点，所以沿这个方向进行搜索有可能向最优点逼近。然而，由于沿 D 方向前进有可能进入非可行区因此沿 D 方向走一步后，就应该沿 方向再回到约束边界面上，()kfX得到新的界面点，再判断其是否为最优点，如此反复，直到逼近最优点 E 满足预定精度要求为止。在沿 D 的方向进行最优搜索的过程中还必须解决搜索步长确定这一问题。从 出发再沿 D 的方向前进，如果步长 S