无约束最优化与非线性规划.ppt

无约束最优化和非线性规划 1.建模实例 2.数学预备知识 3.无约束最优化问题的解 4.非线性规划的数学模型 5.非线性规划的解 6.非线性规划建模实例 1.建模实例 2.数学预备知识 3.无约束最优化问题的解 4.非线性规划的数学模型 5.非线性规划问题的最优性条件 6.非线性规划规划问题的求解方法 * 如图1，有一条河，两个工厂P 和Q位于河岸L（直线）的同一侧，工厂 P 和 Q 距离河岸L分别为8千米和10千米，两个工厂的距离为14千米，现要在河的工厂一侧选一点R，在R处建一个水泵站，向两工厂P、Q 输水，请你给出一个经济合理的设计方案。 8 l 10 Q 14 P 河 图1 R 即找一点 R ，使 R 到P、Q及直线 l 的距离之和为最小。 P Q R Q 这里建立的是关于x、y的二元函数，可以归结为如下模型： 建立如图３的坐标系，则易得P（0，10）、 Q（ 8 ，8）设点R(x , y ) ， 则S(R)＝|PR| + |RQ| + |RM| ＝ 　 1、梯度 关于梯度： 1）梯度方向是函数 在点 X 处增长变化率最大的方向,负梯度方向是下降最快的方向。 设 是定义在 n 维欧氏空间 上的可微函数，则： 为函数 在点X处的梯度，记为 2）梯度的模： 是函数 沿这一方向的变化率。 3）满足 的点称为驻点，在区域内部，极值点必为驻点，而驻点不一定为极值点. 2、海赛矩阵 为函数 的二阶偏导数矩阵. 特别若 为二次函数 时，其 海赛矩阵 ，与点X的位置无关. 3、多元函数Taylor展开 一次展开 二次展开 其中： 3、正定矩阵、负定矩阵、半正定矩阵、半负定矩阵 特征值都大不大于零的实对称矩阵 半负定矩阵 特征值都小于零的实对称矩阵 负定矩阵 特征值都大不小于零的实对称矩阵 半正定矩阵 特征值都大于零的实对称矩阵 正定矩阵 有两个奇数阶主子式，其中一个为正，另一个为负 特征值既有大于零又有小于零的实对称矩阵 不定矩阵 充要条件 定义 名称 其中 为各阶主子式。 考虑无约束最优化问题： 1）有海赛矩阵判断驻点性质 已知函数 的驻点 ： A）若 是正定的，则驻点 是极小值； B）若 是负定的，则驻点 是极大值； C）若 是不定的，则驻点 不是极值点； D）若 是半定的，则驻点 可能是极值点，可能不是极值点，需视高阶导数的性质而定。 2）极值点的必要条件和充分条件 定义1 对于 问题，设 是任意 给定点，P为非零向量，若存在一个数 ，使得对于 任意 ，都有 ，则称P是 在 处的下降方向. 定理1 ，则P为 在X处的下降方向。 设 在 可微，如果存在向量 ，使得 定理2 （一阶必要条件）设 f 在点 可微，如果 是局部 最优解，则必有 定理3 （二阶必要条件）设 f 在点 二阶可微，如果 局部最优解，则必有 是 且Hessian矩阵 是半正定的. 定理4 (二阶充分条件)设 f 在点 二阶可微，如果 最优解。 是问题的严格局部 且Hessian矩阵 是正定的，则 定理5 （充要条件）设 f 是 上的凸函数， 极值点的充要条件是 。若 f 是严格凸函数， 则全局极值点是唯一的。 则 为全局 解法 1.搜索法 希望点列，且极限是 f(x)的一个极小值点 。 搜索方向序列，对应 的搜索方向。 步长序列。 在给定初始点后，使得每次迭代使目标函数值有所下降。 使得 搜索算法 搜索方向的确定： 不防取 根据步长的决定方法派生了不同的搜索算法： 1、简单算法： 但不一定保证下降性质。 2、一维搜索算法： 最优步长法。 3、一维搜索直接算法： 试探 决定步长的合理长度。 可接受点算法。 若 则称为黄金分割法。 （又称梯度法） 牛顿法 基本思想是用一个二次函数去近似目标函数 f(x) ，然后精确 地给出这个二次函数的极小值点