第四章约束最优化方法

第四章

约束最优化方法简介上一章介绍了无约束问题的最优化方法，但实际问题中，大多数都是有约束条件的问题.求解带有约束条件的问题比起无约束问题要困难得多，也复杂得多.在每次迭代时，不仅要使目标函数值有所下降，而且要使迭代点都落在可行域内.求解带有约束的极值问题常用方法有：将约束问题化为一个或一系列的无约束极值问题；将非线性规划化为近似的线性规划；将复杂问题变为较简单问题，等等.2§4.1最优性条件考虑只含不等式约束条件下求极小值问题的数学模型：34定义4.1.15定义4.1.2定理4.1.16库恩-塔克（Kuhn-Tucker）条件库恩-塔克条件是非线性规划领域中的重要理论成果之一，是确定某点为局部最优解的一阶必要条件.只要是最优点（同时是正则点）就必满足这个条件.但一般来说它不是充分条件，即满足这个条件的点不一定是最优点.但对于凸规划，库恩-塔克条件既是必要条件，也是充分条件.71、只含有不等式约束891011122、同时含有等式与不等式约束1314例：求下列非线性规划问题的K-T点.151617181920§4.2可行方向法可以看到，利用K-T条件求极小点是很困难的，因此带有约束的极值问题仍以迭代算法为主要的求解方法.21221、约束为线性函数的情形可行下降方向的确定232425262、约束为非线性函数的情形27282930步长的确定311、当约束为线性函数时32333435363738例用可行方向法求解3940414243444546472、当约束为非线性函数时48495051§4.3近似规划法近似规划是一种线性化的方法，将非线性规划线性化，然后解线性规划来求原问题的近似最优解.525354近似规划法的算法步骤：5556例：用近似规划法求解下列问题575859606162636465§4.4制约函数法基本思想：通过构造制约函数，将约束问题转化为一系列无约束问题，进而用无约束最优化方法求解，因此该方法也称为序列无约束最小化技术，简记为SUMT（sequentialunconstrainedminimizationtechnique）.常用的制约函数基本上有两类：一为惩罚函数（或称罚函数），一为障碍函数.对应于这两种函数，SUMT有外点法与内点法之分.661、外点法基本原理：通过构造一个由目标函数与约束函数组成的惩罚函数的办法，对惩罚函数实行极小化来实现这一目的.

为了便于说明问题，先考虑只含有不等式约束的问题：676869707172外点法的计算步骤73例：用外点法求解非线性规划747576772、内点法基本原理：

78与外点法不同的是，内点法要求整个迭代过程始终在可行域内部进行.初始点也必须选一个严格内点.然后再在可行域边界上设置一道“障碍”，以阻止搜索点到可行域边界上去，一旦接近可行域边界时，就要受到很大的惩罚，迫使迭代点始终留在可行域内部.与外点法相似，用目标函数叠加一个惩罚项来构成制约函数，在内点法中称为障碍函数.要求障碍函数具备这样的功能：在可行域内部离边界面较远之处，障碍函数与目标函数尽可能地接近，而在接近边界面时，可以变成很大的值.因此满足这种要求得障碍函数其极小值显然不会在可行域的边界上达到.也就是说，用障碍函数来代替原有目标函数，且在可行域内使其极小化.因极小点不在可行域的边界上，因而这种障碍函数具有无约束性质的极值，可用无约束极值法求解.798081内点法的计算步骤8283例：用内点法求解非线性规划848586初始内点的求法878889