第四讲：无约束优化.ppt

数学预备知识 1 梯度 * 无约束优化 标准形式： 定义1 设f(X)是定义在n维欧氏空间的 上的 可微函数，我们称 为函数 f(X)在点X处的梯度，记为▽ f(X). 1，梯度方向是函数在点X处增长最快的方向， 负梯度方向是函数在点X处下降最快的方向. 2，梯度的模是函数沿这一方向的变化率. 3，满足梯度 的点称为驻点，在区域内部 极值点必为驻点，而驻点不一定是极值点. 2 黑塞（Hesse）矩阵 定义2 设f(X)是定义在 上的二阶可微函数，则 以其二阶偏导数为元素构成的下述n×n 矩阵称 为函数f(X)在点X的黑塞矩阵，记为H(X)或 . 当f(X) 二阶偏导数连续时H(X)是 对称矩阵. 当f(X)是二次函数： 时， 即二次函数的黑塞矩阵与点X无关. 例1，设 求 和 解 3 多元函数的泰勒展开式 定理1 （多元函数的泰勒展开式）设f(X) 是定义在 上的函数，且 为一给 定点， 为任一点，那么 1. 若f(X)连续可微，则存在 ，使 其中 2. 若f(X)二次连续可微，则存在 使 其中 3. 若f(X)二次连续可微，则 5.1.4 正定矩阵、负定矩阵、半定矩阵、不定矩阵 有两个奇数阶主子式，其中一个为正，另一个为负 特征值既有大于零的又有小于零的实对称矩阵 不定矩阵 特征值都不大于零的实对称矩阵 半负定矩阵 特征值都小于零的实对称矩阵 负定矩阵 特征值都不小于零的实对称矩阵 半正定矩阵 特征值都大于零的实对称矩阵 正定矩阵 充 要 条 件 定 义 名 称 5.2 无约束最优化问题的解 5.2.1 无条件最优化问题的最优性条件 1. 用黑塞矩阵判断驻点的性质 已知函数f(X)的驻点 ，可以利用驻点处的黑塞矩阵来 判断驻点的性质： （1）若 是正定的，则驻点 是极小点； （2）若 是负定的，则驻点 是极大点； （3）若 是不定的，则驻点 不是极值点； （4）若 是半定的，则驻点 可能是极值点； 也可能不是极值点，视高阶导数情况而定. 2 极值点的必要条件和充分条件 定义1 对于问题（1），设 是任一给定点，P是 是非零向量，若存在一个数 ，使得对于任意 都有 ,则称P是f(X)在 处的下降方向. 定理1 设 可微，如果存在向量 使得 定理2 （一阶必要条件）设f 在点 可微，如果 是（1）的局部最优解，则必有 称为驻点. 定理3 （二阶必要条件）设f 在点 二次可微， 如果 是（1）的局部最优解，则必有 且黑塞矩阵是半正定的. 定理4 （二阶充分条件）设f 在点 二次可微， 如果 且 正定， 则 是问题（1）的 严格局部最优解 定理5（充要条件）设f 是定义在n维欧氏空间 上的 凸函数， 则 为全局极值点的充要条件是 .若f是严格凸函数，则全局极值点是唯一的. 搜索算法概述 搜索法的基本思想：首先给定目标函数的极小点的初始估计 然后按照一定的规则产生一个点列 这种规则通常就叫做算法 希望点列的极限就是函数的极小值点 ； 最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法. 5.2.3．最速下降法（共轭梯度法）算法步骤： 5.2.4牛顿法算法步骤： 如果f是对称正定矩阵A的二次函数，则用牛顿法，经过一次迭代 就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点， 但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收 敛速度还是很快的. 牛顿法的收敛速度虽然较快，但要求黑塞矩阵可逆，要计算二阶导数和逆矩阵，就加大了计算机的计算量和存储量. 3．拟牛顿法 返回 MATLAB优化工具箱简介 1.MATLAB求解优化问题的主要函数 2.优化函数的输入变量 使用优化函数或优化工具箱中其他优化函数时, 输入变量见下表: 3.优化函数的输出变量见下表: 4．控制参数选项的设置 (3) MaxIter: 允许进行迭代的最大次数,取值为正整数. 选项中常用的几个参数的名称、含义、取值如下: (1) 陈列: 显示水平.取值为off时,不显示输出; 取值为iter时,显示每次迭代的信息;取值为final时,显示最终结果.默认值为final. (2) MaxFunEvals: 允许进行函数评价的最大次数,取值为正整数. 例：opts=optimset(Display, iter, TolFun,1e-8) 该语句创建一个称为选择的优化选项结构,其中显示参数设为iter, TolFun参数设为1e-8. 控制参数选项可以通过函数optim