约束优化方法教学 讲义.ppt

（4）收敛判断： 由于 Jk={3， 5} 代入K—T条件： 间接解法 0、引言 基本思想：通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解，这类方法称为序列无约束最小化方法。简称为SUMT法。 五、惩罚函数法 将有约束的优化问题转化为无约束优化问题来求解。前提：一是不能破坏约束问题的约束条件，二是使它归结到原约束问题的同一最优解上去。 构成一个新的目标函数，称为惩罚函数 从而有 惩罚项必须具有以下极限性质： 求解该新目标函数的无约束极小值，以期得到原问题的约束最优解。按一定的法则改变罚因子r1 和r2的值，求得一序列的无约束最优解，不断地逼近原约束优化问题的最优解。 根据约束形式和定义的泛函及罚因子的递推方法等不同，罚函数法可分为内点法、外点法和混合罚函数法三种。这种方法是1968年由美国学者A．V．Fiacco和G．P．Mcormick提出的，把不等式约束引入数学模型中，为求多维有约束非线性规划问题开创了一个新局面。 内点法 这种方法将新目标函数定义于可行域内，序列迭代点在可行域内逐步逼近约束边界上的最优点。内点法只能用来求解具有不等式约束的优化问题。 对于只具有不等式约束的优化问题： 转化后的惩罚函数形式为： 或： rk是惩罚因子，它是一个由大到小且趋近于0的正数列，即: 由于内点法的迭代过程在可行域内进行，“障碍项”的作用是阻止迭代点越出可行域。由“障碍项”的函数形式可知，当迭代点靠近某一约束边界时，其值趋近于0，而“障碍项”的值陡然增加，并趋近于无穷大，好像在可行域的边界上筑起了一道“高墙”，使迭代点始终不能越出可行域。显然，只有当惩罚因子 时，才能求得在约束边界上的最优解。 罚因子的作用是：由于内点法只能在可行域内迭代，而最优解很可能在可行域内靠近边界处或就在边界上，此时尽管泛函的值很大，但罚因子是不断递减的正值，经多次迭代，接近最优解时，惩罚项已是很小的正值。 内点法为构造为在可性域的边界上，构造围墙，在域内进行寻优 围墙—要高，要窄 五、罚函数法 内点法函数寻优逼近的过程 五、罚函数法 框图 例5-2 用内点法求 的约束最优解。 解: 用内点法求解该问题时，首先构造内点惩罚函数: 用解析法求函数的极小值，运用极值条件： 联立求解得： 时不满足约束条件 应舍去 。 无约束极值点为 当 1）? 初始点x0的选取 使用内点法时，初始点应选择一个离约束边界较远的可行点。如太靠近某一约束边界，构造的惩罚函数可能由于障碍项的值很大而变得畸形，使求解无约束优化问题发生困难. 2）? 惩罚因子初值r0的选取 惩罚因子的初值应适当，否则会影响迭代计算的正常进行。一般而言，太大，将增加迭代次数；太小，会使惩罚函数的性态变坏，甚至难以收敛到极值点。无一般性的有效方法。对于不同的问题，都要经过多次试算，才能决定一个适当 r0 ? 3) 惩罚因子的缩减系数c的选取 在构造序列惩罚函数时，惩罚因子r是一个逐次递减到0的数列，相邻两次迭代的惩罚因子的关系为 : 式中的c称为惩罚因子的缩减系数，c为小于1的正数。一般的看法是，c值的大小在迭代过程中不起决定性作用，通常的取值范围在0.1~0.7之间。 4) 收敛条件 算法步骤： 1）选择可行域内初始点X(0); 2）选取初始罚因子r(0)与罚因子降低系数c，并置K←0； 3）求minφ(x(K),r(K))解出最优点xK*； 4）当K=0转步骤5），否则转步骤6）； 5）K←K+1，r(K+1)←r(K)， xK+10←xK* ，并转步骤3）； 6）按终止准则判别，若满足转步骤7），否则转步骤5）； 7）输出最优解（X*，F*），停止计算。 2.? 外点法 外点法是从可行域的外部构造一个点序列去逼近原约束问题的最优解。外点法可以用来求解含不等式和等式约束的优化问题。 外点惩罚函数的形式为： r是惩罚因子 , 外点法的迭代过程在可行域之外进行，惩罚项的作用是迫使迭代点逼近约束边界或等式约束曲面。由惩罚项的形式可知，当迭代点x 不可行时，惩罚项的值大于0。 五、罚函数法 外点罚函数的基本思想 构造惩罚项，对违反约束的解进行惩罚，将其靠近可性域 解为外点 是从可性域外无限接近可性域 需要 构造足够大的惩罚项！！ 第三节：复合形法 例 用复合形法求解以下优化问题，已知收敛精度值为0.1。 第三节 复合形法 解：（1）取顶点数为2N=4，产生初始复合形顶点并检验可行性，计算各点的目标函数值，确定好、次坏、坏、中心