23无约束极值问题.ppt

济南大学管理学院 * 2.4 约束极值问题 例:考虑非线性规划并验证它为凸规划，用K－T条件求解。 +x2 济南大学管理学院 * 2.4 约束极值问题 计算目标和约束函数的海赛阵 济南大学管理学院 * 2.4 约束极值问题 K-T表达式为： 3 1 济南大学管理学院 * 2.4 约束极值问题 1 2 3 4 1 2 g1=0 g2=0 g4=0 x1 g3=0 x2 x* ▽g2(x*) ▽g1(x*) -▽f(x*) (2,2)T 济南大学管理学院 * 2.4 约束极值问题 用K-T条件求解： 济南大学管理学院 * 2.4 约束极值问题 济南大学管理学院 * 2.4 约束极值问题 可能的K-T点出现在下列情况： ①两约束曲线的交点：g1与g2,g1与g3,g1与g4,g2与g3,g2与g4,g3与g4。 ②目标函数与一条曲线相交的情况： g1，g2, g3, g4 对每一个情况求得满足(1)~(6)的点(x1,x2)T及乘子u1,u2,u3,u4,验证当满足可得，且ui≥ 0时，即为一个K-T点。 下面举几个情况： ● g1与g2交点：x=(2,1)T∈S ,I={1,2} 则u3=u4=0 解 济南大学管理学院 * 2.4 约束极值问题 济南大学管理学院 * 2.4 约束极值问题 济南大学管理学院 * 2.4 约束极值问题 基本思想：将约束与目标组合在一起，化为无约束极值问题求解。 ★内点法（罚函数法）：从可行域的内部逐步逼近最优解。 ★外点法（障碍函数法）：从可行域的外部逐步逼近最优解。 三、制约函数法 济南大学管理学院 * 2.4 约束极值问题 外点法的关键是基于（NLP）构造一个新的目标函数P（X，M），称为罚函数。 三、制约函数法—外点法 构造新的函数 济南大学管理学院 * 2.4 约束极值问题 为了使t=0处连续，修改： 但模型的极小点不一定是原非线性规划问题的极小点，因此，加大M： 式中M是一个充分大的正数，称做(惩)罚因子。 含M的项称为(惩)罚项。 三、制约函数法—外点法 济南大学管理学院 * 2.4 约束极值问题 三、制约函数法—外点法 也可写成另一种形式 引进阶跃函数： 济南大学管理学院 * 2.4 约束极值问题 三、制约函数法—外点法 假定对某一个罚因子，如M1，X(M1) ∈ R,就加大罚因子的值。随着罚因子数值的增加，惩罚函数P(X,M)中的惩罚项所起的作用随之增大，minP(X)离可行域R的距离就会越来越近，当 0M1M2…Mk…. 趋于无穷大时，点列{X(Mk)}收敛。正是由于在达到最优解之前，迭代点往往处于可行域之外，故常称为外点法。 济南大学管理学院 * 2.4 约束极值问题 含有等式约束和不等式约束的一般非线性规划，其罚函数： 三、制约函数法—外点法 济南大学管理学院 * 2.4 约束极值问题 三、制约函数法—外点法 对外点法可作如下经济解释：把目标函数f(x)看成一种“价格”，约束条件看作某种“规定”，采购人可在规定范围内购置物品。对违反规定采取某种“罚款”政策；若符合规定，罚款为零；反之，征收罚款。此时，采购人付出的总代价应是价格和罚款的总和。采购者的目标是使总代价最小，这就是上述的无约束问题。当罚款规定得很苛刻时，违反规定支付的罚款很高，这就迫使采购人符合规定，在数学上表现为，当罚因子Mk足够大时，上述大约束问题的员优解应满足约束条件，而成为约束问题的最优解。 济南大学管理学院 * 2.4 约束极值问题 一般步骤： 三、制约函数法—外点法 济南大学管理学院 * 2.4 约束极值问题 课本例10：用罚函数法求解： 三、制约函数法—外点法 解：构造罚函数 济南大学管理学院 * 2.4 约束极值问题 例：求解非线性规划 解构造罚函数 济南大学管理学院 * 2.4 约束极值问题 济南大学管理学院 * 2.4 约束极值问题 解构造罚函数 济南大学管理学院 * 2.4 约束极值问题 济南大学管理学院 * 2.4 约束极值问题 罚函数法的一个重要特点，就是函数P(X，M)可在整个En空间内进行优化，可以任意选择初始点，这给计算带来了很大方便。但由于迭代过程常常是在可行域外进行，因而不能以中间结果直接作为近似解使用。 如果要求每次的近似解都是可行解，以便观察目标函数值的改善情况；或者，如果目标函数在可行域外的性质比较复杂，甚至没有定义，这时就无法使用上面所述的罚函数法了。 三、制约函数法—内点法 济南大学管理学院 * 障碍函数法(也称内点法) 要求迭代过程始终在可行域内进行。 改造后的目标函数具有这种性质：在可行域R的内部与边界面