第四章约束最优化方法讲解.ppt

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