第一次基础知识概要.ppt

十一. 收敛速度 则称 的收敛阶为 。 1. 设算法A所得的点列为 ，如果 2. 基 础 知 识 一.引言 二.最优化问题实例 三.极值最优化问题的经典方法 四.最优化问题及基本概念 五.梯度与Hesse阵 六.Taylor展开式 七.凸集与凸函数 八.极小点的判定条件 九.算法及相关概念 十.中止条件 十一.收敛速度 一. 引 言 1. 最优化定义 最优化是从所有可能方案中选择最合理方案以达到最优目标的一门学科。 （1） 达到最优目标的方案：最优方案（最优解） （2） 搜寻最优方案的方法：最优化方法 最优化问题：寻求某些变量的取值使其符合某些限制条件， 并使某个目标函数达到最大值或最小值的问题。 一般的数学形式为： 其中 D 为可行域。 例. 2.包含内容： 最优化又称数学规划： LP、NLP、DP、IP i　 　ti Ri　 1 50 34780 2 55 28610 3 60 23650 。。。　 。。。　 。。。　 15 120 3307 二. 最优化问题实例 试确定函数关系。 利用最小二乘思想，可将其化为无约束最优化问题： … … m … … … … … … 2 1 n … … … 2 1 产量 销量 销 地 产地 运费 在产销平衡条件下，要求总运费最小的调运方案，可得如下模型。 三. 极值最优化问题的经典方法 1.无约束极值问题 必要条件： 2. 约束极值问题 四. 最优化问题及基本概念 1.模型 3.解法分类： 解析方法：利用函数的解析性质去构造迭代公式使之收敛到最优解（如牛顿法）。 直接方法：它对函数的分析性质如可微性没有要求，而是根据一定的数学原理来确定（如0.618法）。 2.基本概念：全局最优解与局部最优解 五. 梯度与Hesse阵 1. 梯度 性质1：函数在某点的梯度若不为0， 则必与过该点的等值线（面）垂直。 x0 L f(X)=f(X0) ▽f(X0) X0 L 性质2：梯度方向是函数具有最大变化率的方向，即函数值上升最快的方向。 2. 方向导数和下降（上升）方向 （1）方向导数： （2）给定函数 和方向p，如果存在实数 ，使得对于任意的 ，都有 ，则称p为 在点 处的下降方向。 （3） 性质 (a) . (b) p是下降方向; (c) p是下降方向。 p 是上升方向。 （4） 常用梯度公式 3. Hesse矩阵 （1）雅可比矩阵：设 （2）海赛（Hesse） 矩阵： （3）其它 例 已知 ，求 （1） ， 。 （2）判断向量 是否为函数 在点 的下降方向？ 解： （1） （2） 所以向量 是函数 在点 的 下降方向。 六. Taylor展开式 例 函数 在点 的泰勒展开式为 七. 凸集与凸函数 1.凸集 （1）凸组合： （2）凸集： 2.凸函数 设 ，任取 ，如果 有 ，则称 f 为X上的 (严格)凸函数。 例子： 水平集： 是凸函数}。 性质：水平集一定是凸集。 3. 凸函数的性质 定理. 凸函数的局部极小点就是全局极小点。 4. 凸函数的判断条件 定理1. 是凸集X上的凸函数的充要条件是 ，有 . 定理2.设 在凸集X上有二阶连续偏导数，则 是凸 函数的充要条件是 ，有 半正定。 例：正定二次函数 ，其中 是正定矩阵。 是凸函数。 5. 凸规划 （1） 其中 是凸函数， 是凸集。 （2） 其中 是线性函数。 是凸函数, 八.