内点法地基本原理以与举例计算.docxVIP

一、内点法 基本原理 内点法的特点是将构造的新的无约束目标函数——惩罚函数定义在可行域内， 并在可行 域内求惩罚函数的极值点， 即求解无约束问题时的探索点总是在可行域内部， 这样，在求解 内点惩罚函数的序列无约束优化问题的过程中， 所求得的系列无约束优化问题的解总是可行 解，从而在可行域内部逐步逼近原约束优化问题的最优解。 。 内点法是求解不等式约束最优化问题的一种十分有效方法， 但不能处理等式约束。 因为 构造的内点惩罚函数是定义在可行域内的函数， 而等式约束优化问题不存在可行域空间， 因 此，内点法不能用来求解等式约束优化问题。 对于目标函数为 min f ( X ) s.t. gu ( X ) 0 （ u=1,2,3, ? m） 的最优化问题，利用内点法进行求解时，构造惩罚函数的一般表达式为 ( X , r (k ) ) f ( X ) r ( k) m 1 1 gu ( X ) m m 或者 (X , r k ) f ( X ) r k ln gu ( X ) f ( X ) r k ln gu (X ) u 1 u 1 而对于 f ( X ) 受约束于 gu ( X ) 0(u 1,2, ,m) 的最优化问题，其惩罚函数的一般形式为 ( X , r k ) f ( X ) r k m 1 u 1 gu ( X ) 或 ( X , r k ) f ( X ) r k m ln gu ( X ) u 1 k ----- 惩罚因子，是递减的正数序列，即 式中， r r 0 r 1 r 2 r k r k 1 0 lim r k 0 k 通常取 r k 1.0,0.1,0.01,0.001, 。 上述惩罚函数表达式的右边第二项，称为惩罚项，有时还称为障碍项。 说明： 当迭代点在可行域内部时，有 ( X ) 0 （ ， ， ， ，? ），而 r k 0 ，则惩罚 gu u =1 2 3 4m 项恒为正值， 当设计点由可行域内部向约束边界移动时， 惩罚项的值要急剧增大并趋向无穷 大，于是惩罚函数的值也急剧增大直至无穷大， 起到惩罚的作用， 使其在迭代过程中始终不 会触及约束边界。 2. 内点法的迭代步骤 （ 1）取初始惩罚因子 r (0) 0 ，允许误差 0 ； （ 2）在可行域 D 内取初始点 X 0 ，令 k 1 ； （ 3）构造惩罚函数 ( X , r k ) ，从 X (k 1) 点出发用无约束优化方法求解惩罚函数 ( X ,r k ) 的极值点 X (r k ) ； （4）检查迭代终止准则：如果满足 X (r k ) X ( r k 1 ) 1 10 5 10 7 或 k k 1 ( X , r ) ( X , r ) 2 103 104 ( X , r k 1 ) 则停止迭代计算，并以 X (r k ) 为原目标函数 f ( X ) 的约束最优解，否则转入下一步； 根据情况，终止准则还可有如下的形式： f ( X k ) f ( X k 1 ) 或 r 或  m k 1 1 gu ( X ) r k m ln gu (X ) u 1 5）取 r k 1 Cr k , X 0 X (r k ), k k 1 ，转向步骤 3）。 递减系数 C 0.1 0.5 ，常取 0.1 ，亦可取 0.02 。 采用内点法应注意的几个问题： （ 1）初始点 0 的选取 X 初始点 X 0 必须严格在可行域内，满足所有的约束条件，避免为约束边界上的点。 如果约束条件比较简单， 可以直接人工输入； 若问题比较复杂， 可采用随机数的方式产 生初始点 X 0 ，具体方程参照复合形法介绍。 （ 2）关于初始惩罚因子 r (0) 的选择。实践经验表明，初始惩罚因子 r (0) 选的恰当与否， 会显著地影响内点法的收敛速度，甚至解题的成败。 若 r 0 ( X , r k 值选得太小，则在新目标函数即惩罚函数 ) 中惩罚项的作用就会很小， 这时求 ( X , r k ) 的无约束极值，犹如原目标函数 f ( X ) 本身的无约束极值，而这个极值点 又不大可能接近 f ( X ) 的约束极值点，且有跑出可行域的危险。相反，若 r 0 值取得过大， 则开始几次构造的惩罚函数 ( X , r k ) 的无约束极值点就会离约束边界很远， 将使计算效率 降低。可取 r 0 1～ 50，但多数情况是取 r 0 1 。 通常，当初始点 X 0 是一个严格的内点时，则应使惩罚项 m 1 r 0 在新目标函 u 1 gu ( X 0 ) k 0 ) 的作用相当，于是得 数 ( X , r ) 中所起的作用与原目标函数 f ( X 0 r