第一次基础知识幻灯片.pptVIP

* 最优化方法 1.教 材：最优化理论与方法 陈宝林，清华大学出版社 2.参考书：最优化原理与方法 薛嘉庆，冶金工业出版社 基本知识 一.引言 四.极值最优化问题的经典方法 二.最优化问题实例 三.最优化问题及基本概念 五.图解法 六.梯度与Hesse阵 七.Taylor展开式 八.凸集与凸函数 九.极小点的判定条件 十.算法及相关概念 十一.中止条件 十二.收敛速度 一. 引言 1. 最优化定义 最优化是从所有可行方案中选择最合理方案以达到最优目标的一门学科。 （1） 达到最优目标的方案：最优方案（最优解） （2） 搜寻最优方案的方法：最优化方法 最优化问题：寻求某些变量的取值使其符合某些限制条件，并使某个目标函数达到最大值或最小值的问题。 一般的数学形式为： 2. 发展简况 经典最优化理论的研究已有很久，最早可追溯到Fermat时代。 1940年前，对多变量函数的数值最优化方法知之甚少，但当时已发现了若干最小二乘法和在物理上应用的最速下降法，多变量的牛顿法也很著名。 40年代与50年代：线性规划（LP）的发展。 二战以后，爬山法得到发展与应用（实用，粗糙）。 1959年，W-C.Davidon的一个报告引入了变尺度方 法。 3.应用领域 工程设计、军事科学、自动控制、空间技术、资源分配、计算机科学等等。例如： ①桥梁结构设计； ②运输问题； ③参数拟合； ④多波形信号发生仪中正弦波形逼近的优化设计，在 中找 n 个分点，使过这些分点的折线和正弦函数曲线的误差最小。 4.包含内容： 最优化又称数学规划： LP、NLP、DP、IP 5.分类： 二. 最优化问题实例 例1：多参数曲线拟合问题 已知热电阻 R 依赖于温度 t 的函数关系为： 其中 是待定参数。通过试验，得到 3307 120 15 。。。　 。。。　 。。。　 23650 60 3 28610 55 2 34780 50 1 Ri　 ti i　 利用最小二乘思想，可将其化为三维空间的无约束最优化问题，即： 现有 m 种资源的数量为 。计划生产 n 种产品1,2,…,n。有关数据如下，试问：怎样安排生产可以使利润达大？ … … m … … … … … … 2 1 n … … … 2 1 拥有量 单位利润 产品 资源 令 表示第 j 种产品的产量。 例2. 生产安排问题 已知有m个生产点Bi，可供应某种物质量分别为 n个销地 ，需求量为 . 从 到 的单位运价为 。问：应如何安排运输方案才能使总运费最小？ 例3. 运输问题（TP） … … m … … … … … … 2 1 n … … … 2 1 产量 销量 销 地 产地 运费 在产销平衡条件下，要求得总运费最小的调运方案，可得如下模型： 设 表示从第i个产地向第j个销地的运量，则有 三. 最优化问题及基本概念 2.解法分类 解析方法：利用函数的解析性质去构造迭代公式使之收敛到最优解（如牛顿法）。 直接方法：它对函数的解析性质如可微性没有要求，而是根据一定的数学原理来确定（如0.618法）。 1.模型 3.全局最优解与局部最优解 四. 极值问题的经典方法 1.求驻点的方法 2.Lagrange 乘子法 五. 图解法 等值线（面）的特点： 1.不同值的等值线不相交 ; 2.除极值点外，等值线是连续曲线 ; 3.等值线稠密处导数变化快，稀疏处变化慢 ; 六. 梯度与Hesse阵 1. 梯度 性质1：函数在某点的梯度若不为0， 则必与过该点的等值线（面）垂直。 x0 L f(X)=f(X0) ▽f(X0) X0 L 性质2：梯度方向是函数值具有最大变化率的方向，即函数值上升最快的方向。 2. 方向导数和下降（上升）方向 （1）方向导数： 函数 在点 处沿着方向p 的方向导数。 （2）给定函数 和方向p，如果存在实数 ，使得对于任意的 ，都有 ，则称p为 在点 处的下降方向。 （3） 性质 (a) . (b)