第四章非线性规划1-约束极值问题

第四章 非线性规划无 约 束 最 优 化 问 题 线 性 规 划约 束 最 优 化 问 题 非 线 性 规 划凸 规 划约 束 最 优 化 问 题 非 凸 规 划 直 接 解 法约 束 最 优 化 问 题 求 解 方 法 间 接 解 法间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于这类方法可以选用有效的无约束优化方法，且易于处理同时具有不等式约束和等式约束的问题，因而在工程优化中得到了广泛的应用。直接解法是在满足不等式约束的可行设汁区域内直接按索问题的约束最优解。第一节 目标函数的约束极值问题所谓约束优化设计问题的最优性条件就是指在满足等式和不等式约束条件下，其目标函数值最小的点必须满足的条件，须注意的是，这只是对约束的局部最优解而言。对于带有约束条件的目标函数，其求最优解的过程可归结为：一、约束与方向的定义一）起作用约束与松弛约束对于一个不等式约束 来说，如果所讨论的设计点 使该约束 (或者说()0gX()kX)0g当时正处在该约束的边界上) 时，则称这个约束是 点的一个 起作用约束或紧约束，而其他满足(kX()k的约束称为松弛约束。0g可行方向冗余约束 40g当一个设计点同时有几个约束起作用时，即可定义起作用约束集合为 ()()|0,12,kkuIXgm其意义是对 点此时所有起作用约束下标的集合。()k二）冗余约束如果一个不等式约束条件的约束面(即)对可行域的大小不发生影响，或是0g约束面不与可行域 D 相交，即此约束称为冗余约束。三）可行方向可行方向：一个设计点 在可行域内，()kX沿某一个方向 S 移动，仍可得到一个属于可行域的新点，则称该方向为可行方向。1）设计点为自由点设计点 在可行域内是一个自由点，在()k各个方向上都可以作出移动得到新点仍属于可行域，如图所示。2）设计点为约束边界点当设计点 处于起作用约束 上时，它的移动就会受到可行性的限制。此时， 点的可行方向()kXig ()kXS 必满足条件：（解释： ， ） ）()0Tkig()()cos,()TkkTkii iSXSg,()90Tki当 时，方向 S 是约束函数 在,9kiXi点处的切线方向，即 。()k ()0Tkig当某个设计点 x 同时有几个约束起作用时(如图中的x 点是约束 和约束 约束面的交点)，其可行方10g2向集合为： ()1()|()0,TkkuVXSgXI即图中阴影部分的任一方向都是可行方向。同理，对于有不等式约束起作用约束集合和等式约束的情况，其可行方向的集合为： ()1|(),()0TkkuvIShX四）下降可行方向沿某一个可行方向 S 移动一个微小距离 0，有 ,（亦即 f（ ） 的方向导数小()()kkfXSf()kX于 0） ，则称 S 为下降可行方向。对于一个求目标函数极小化问题，当沿某个可行方向向量作出微小的移动时，其目标函数的变化为： (1)()()()kkkTkfXfSfSf对于充分小 ，若()0()(1)()/0TkkkSfffX成立，则 不是函数的局部极小点，因为沿着 S 方向存在目标函数值更小的点。()X反之，若对于任何可行方向 S 均有()(1)()/Tkkkfff成立，则 是函数的局部极小点，因为沿着任意 S 方向找不到一个目标函数值更小的点。()刚好是上式的一种极限情况。0TkSfX根据以上分析，对于点 的可行方向 ，若满足 （或()k()1kVX()0TkfX，此时方向向量与负梯度方向夹角小于 ）的条件，则称此可行方向 S 为目标函()Tkf90数的下降可行方向，并定义2()|()0|()TkTkVXSfSf为 点的目标函数下降可行方向集合。k二、约束问题的最优解条件一）约束极值问题的不同情况在约束条件下的优化问题比无约束条件下的优化问题更为复杂，因为约束最优点不仅与目标函数本身的性质有关，而且还与约束函数的性质有关。在存在约束的条件下，为了要满足约束条件的限制，其最优点即约束最优点，不一定是目标函数的自然极值点，如图所示。约束问题最优点可能出现两种情况：一种是最优点在可行域的内部，即最优点 是个内点，此时的所有约束均为不起支配作用，这就*X是说，目标函数无约束极小点也就是约束最优点；（无约束极值）另一种情况是最优点在可行域的边界上，对于这种情况，其极值条件不仅与目标函数而且也与约束集合的性质有关，即该点既在起作用约束的约束面上，又是目标函数值最小的点。 （约束极值）二）约束极值的必要条件 库恩-塔克条件点成为约束最优点 的必要条件为：是否存在一个可行方向 ，使得()kX(*)X()1kSVX，若存在，则 不是 。()0TSf()k(*)或者：在 点周围是否存在下降可行方向，用集合的形式表示为：()k()12|()0,|()0kTkkkTkuVSgIXSf（ ） （ ）1.只有一个起作用约束条件的情况从设计空间的几何意义可以很清楚的了解到这一点。在图 a 中，目标函数和约束函数均为凸函数，仅有一个起作用的约束，在 存在一个可行方向向()k量 S，使得 （或 ）成立，S 就是一个可行下降方向， 不()0TkfX()0TkSfX()kX是约束最优点。目标函数在该点处沿约束面的切线方向的方向导数或变化率不等于零，不稳定点在图 b 中，在 不存在一个可行方向向量 S，使得 （或()kX()0TkfX）成立，因此 是一个局部约束最优点。此处是目标函数等值线与约束函数边()0TkSf()k界的切点，在该点处约束函数的梯度向量与目标函数的负梯度向量重合。目标函数在该点处沿约束面的切线方向的方向导数或变化率等于零。2.有两个起作用的约束条件的情况图 a， 为非约束最优点， 位于 和 构成的夹角之外。()kX()kfX()1kg()2kX图 b， 为约束最优点， 位于 和 构成的夹角之内。这时，() ()()()可以表示为 和 的线性组合：()kf()1kg()2k()()()12 ,0)XX3.一般情况将上述条件推广到一般情况，表述如下：设某一设计点 有 q 个起作用约束，也就是 在 q 个约束面的交集上。 为局部最优点()kX()kX()kX的必要条件是：目标函数负梯度 可以表示成所有起作用约束 的线性组合，即：()kfug() ()1 0,(12,)qkkuufg其 中这就是约束优化问题最优解的必要条件库恩-塔克条件（Kuhn-Tucker condition）4. 库恩-塔克条件的几何意义库恩-塔克条件的几何意义如图，起作用约束的梯度向量，在设计空间内构成一个椎体，目标函数的负梯度方向应包含在此椎体内。库恩-塔克条件判定的只是局部最优点，只有当目标函数和约束函数均为凸函数时（即所谓的凸规划问题） ，判定的条件极值点才是全域最优点，并且库恩-塔克条件也才是充分条件。库恩-塔克条件的重要性在于：（1）可以通过这个条件检验 是否为条件极值点；()kX（2）可以检验一种搜索方法是否合理，如果用这种方法求得的最优点符合 K-T 条件，则该方法可以认为是可行的。三）k-T 条件的算例作业：三、约束优化迭代终止准则库恩-塔克条件： () ()1 0,(12,)rkkuufXgXr其 中（i=1,2,3, ,n）()(0kkuuIXi ifxx用矩阵形式表示：令 () Ff1212()(),(,) TnTnfffXfXxxb 12()() (),Tuuuuu nggXggxx令 r 为起作用约束的数目12(,rG11122 212)()()()()()rrrnnnrgXgXxxgXgXxx 令 121(,)TrCnnrFG于是库恩-塔克条件可写为方程组 1 (1,2)riuibg这样得到了 n 个方程，而未知数只有 r 个，r0 时，则设计点为约束极值点。因此，可以通过求解 D 的值来判断。将公式进行变换，求取 D 的表达式：（左乘 ）11TTTrnrnrrnFCGTG（ ）rrrG0D（左乘 ，注意逆矩阵存在的条件）11 1TTrrnrrnCF1T1rDF对上式进行讨论：（1）若 D=0（零向量） ，且 Ci0 时（i=1,2,3, ,r） ） ，则设计点为局部最优点，如果问题是凸规划，则为全局最优点；（2）若 D0