运筹学_非线性规划_2_约束极值.ppt

“ ” 2016 “ ” 非线性规划之 约束极值问题 7. 约束极值问题的最优性条件 Kuhn - Tucker 条件（极值点的必要条件） Kuhn –Tucker ( K –T ) 条件: 上述为K –T条件，满足该条件的可行点称为 K –T点。 若定义 Lagrange 函数 极值点的充分条件： 若 x* 为 K –T 点，且对符合以下条件的方向 p 例. 用 K –T 条件解问题 解. Lagrange 函数 K –T 条件 可行性条件 8. 二次规划 Lagrange 函数 K –T 条件 求二次规划的 K –T 点等价于求线性等式及不等式组 (i)、(ii)、(iii)、(iv) 的一个可行点，并且满足互补条件 (*) 。 设 x 0 是一个满足条件 (i) 、(ii) 的基本可行解，则求 (i) - (iv) 的可行点可转化为线性规划问题: 上述线性规划有初始基本可行解： 初始基本可行解中的基变量包括 x 0 中的基变量和所有 z j 。 9. 可行方向法 在迭代点 x k ，选择一个可行下降方向 p k 为搜索方向， 则 p k 应满足 p k 可以通过解下述线性规划获得： 改进方法：在找可行下降方向时考虑所有约束，即 可证：改进方法具有全局收敛性。 10. 制约函数法 将约束非线性规划问题转化为一系列无约束问题求解。（SUMT：Sequential Unconstrained Minimization Technique） （1）外点法 记可行域为 D 构造罚函数 其中 c 是充分大的正数。 考虑无约束问题 F(x) 称为增广目标函数，它的极小点也是原问题的极小点，但 F(x) 不能保持原目标函数 f (x) 可能具有的良好性态（如连续、光滑），因为 F(x) 在可行域 D 的边界上发生跳跃。 另构造罚函数 “ ” 2016 “ ”