最优化方法第一次基础知识

1、最优化方法最优化方法 1.1.教教 材：最优化理论与方法材：最优化理论与方法 陈宝林，清华大学出版社陈宝林，清华大学出版社2.2.参考书：最优化原理与方法参考书：最优化原理与方法 薛嘉庆，冶金工业出版社薛嘉庆，冶金工业出版社 基本知识基本知识一一. .引言引言四四. .极值最优化问题的经典方法极值最优化问题的经典方法二二. .最优化问题实例最优化问题实例三三. .最优化问题及基本概念最优化问题及基本概念五五. .图解法图解法六六. .梯度与梯度与HesseHesse阵阵七七. .TaylorTaylor展开式展开式八八. .凸集与凸函数凸集与凸函数九九. .极小点的判定条件极小点的判定条件十十

2、. .算法及相关概念算法及相关概念十一十一. .中止条件中止条件十二十二. .收敛速度收敛速度一一. 引言引言1. 1. 最优化定义最优化定义最优化是从所有可行方案中选择最合理方案以达到最优目标最优化是从所有可行方案中选择最合理方案以达到最优目标的一门学科。的一门学科。（1 1） 达到最优目标的方案：最优方案（最优解）达到最优目标的方案：最优方案（最优解）（2 2） 搜寻最优方案的方法：最优化方法搜寻最优方案的方法：最优化方法最优化问题：寻求某些变量的取值使其符合某些限制条件，最优化问题：寻求某些变量的取值使其符合某些限制条件，并使某个目标函数达到最大值或最小值的问题。并使某个目标函数达到最大

3、值或最小值的问题。 一般的数学形式为：一般的数学形式为：上上的的函函数数为为定定义义在在集集合合其其中中DxfDxtsxf)(.,)(min 2. 2. 发展简况发展简况q经典最优化理论的研究已有很久，最早可追溯到经典最优化理论的研究已有很久，最早可追溯到FermatFermat时代。时代。q19401940年前，对多变量函数的数值最优化方法知之年前，对多变量函数的数值最优化方法知之甚少，但当时已发现了若干最小二乘法和在物理上甚少，但当时已发现了若干最小二乘法和在物理上应用的最速下降法，多变量的牛顿法也很著名。应用的最速下降法，多变量的牛顿法也很著名。q 40 40年代与年代与5050年代：线

4、性规划（年代：线性规划（LPLP）的发展。的发展。q 二战以后，爬山法得到发展与应用（实用，粗糙）。二战以后，爬山法得到发展与应用（实用，粗糙）。q 1959 1959年，年，W-C.DavidonW-C.Davidon的一个报告引入了变尺度方的一个报告引入了变尺度方 法。法。3.3.应用领域应用领域工程设计、军事科学、自动控制、空间技术、资源工程设计、军事科学、自动控制、空间技术、资源分配、计算机科学等等。例如：分配、计算机科学等等。例如：桥梁结构设计；桥梁结构设计；运输问题；运输问题；参数拟合；参数拟合；多波形信号发生仪中正弦波形逼近的优化设计，多波形信号发生仪中正弦波形逼近的优化设计，在

5、在 中找中找 n n 个分点，使过这些分点的折线和个分点，使过这些分点的折线和正弦函数曲线的误差最小。正弦函数曲线的误差最小。 2,04.4.包含内容：包含内容：最优化又称数学规划：最优化又称数学规划： LPLP、NLPNLP、DPDP、IPIP5.5.分类：分类： 多多目目标标动动态态问问题题非非线线性性规规划划线线性性规规划划有有约约束束问问题题无无约约束束问问题题静静态态问问题题单单目目标标最最优优化化问问题题二二. . 最优化问题实例最优化问题实例例例1 1：多参数曲线拟合问题：多参数曲线拟合问题已知热电阻已知热电阻 R 依赖于温度依赖于温度 t 的函数关系为：的函数关系为：其中其中

6、是待定参数。通过试验，得到是待定参数。通过试验，得到it ti iR Ri i1 1505034780347802 2555528610286103 360602365023650。151512012033073307利用最小二乘思想，可将其化为三维空间的无约束最优化利用最小二乘思想，可将其化为三维空间的无约束最优化问题，即：问题，即： 321expxtxxR321xx,x和和组组数数的的和和15Rt 1512321321exp),(miniiixtxxRxxxf现有现有 m 种资源的数量为种资源的数量为 。计划生产。计划生产 n 种产种产品品1 1,2,2,n,n。有关数据如下，试问：怎样安

7、排生产可以使利有关数据如下，试问：怎样安排生产可以使利润达大？润达大？mbbb,21产品拥有量 1 2 n 资源 1 2 m单位利润11a12ana121a22ana21ma2mamna1b2bmb1c2cnc令令 表示第表示第 j 种产品的产量。种产品的产量。jx njxmibxatsxcxfjinjjijnjjj,.,2 , 10,.,2 , 1.)(max11模模型型：例例2. 2. 生产安排问题生产安排问题已知有已知有m m个生产点个生产点B Bi i，可供应某种物质量分别为可供应某种物质量分别为 n n个销地个销地 ，需求量为需求量为 . . 从从 到到 的单的单位运价为位运价为 。

8、问：应如何安排运输方案才能使总运费最小？。问：应如何安排运输方案才能使总运费最小？),2, 1(mibi ),2,1(njcj iBjCijajC例例3. 3. 运输问题（运输问题（TPTP）运费 销 地产量 1 2 n 产地 1 2 m 销量 11a12ana121a22ana21ma2mamna1b2bmb1c2cnc在产销平衡条件下，要求得总运费最小的调运方案，可得如下在产销平衡条件下，要求得总运费最小的调运方案，可得如下模型：模型：设设 表示从第表示从第i个产地向第个产地向第j个销地的运量，则有个销地的运量，则有ijx njmixnjcxmibxtsxazijjmiijinjijmin

9、jijij,.,1,.,10,.,2,1,.,2,1.min1111三三. . 最优化问题及基本概念最优化问题及基本概念 0)(0)(.)(minxhxgtsxf pjxhmixgtsxfji，, 10)(, 10)(.)(minDxtsxf .)(min2.2.解法分类解法分类 解析方法：利用函数的解析性质去构造迭代公式使之收敛到最优解（如牛顿法）。 直接方法：它对函数的解析性质如可微性没有要求，而是根据一定的数学原理来确定（如0.618法）。1.1.模型模型DxxfxfxDxNxxfxfxxxxxNxfxxfxT ),()(:),(),()(:|),()(,()(*0*00*全全局局最最优

10、优解解局局部部最最优优解解邻邻域域最最优优解解：最最优优值值：最最优优点点：3.3.全局最优解与局部最优解全局最优解与局部最优解四四. . 极值问题的经典方法极值问题的经典方法1.1.求驻点的方法求驻点的方法 000)()(1minnnRxxfxfxfxf 0)(0)()()(),(min0),(0),(.),(min12121121xhLxhxfxLxhxfxLxxxhxxxhtsxxxfliiilRnRxnlnn（2.Lagrange 2.Lagrange 乘子法乘子法五. 图解法等值线（面）的特点：1.不同值的等值线不相交 ;2.除极值点外，等值线是连续曲线 ;3.等值线稠密处导数变化快

11、，稀疏处变化慢 ;六六. 梯度与梯度与Hesse阵阵1. 梯度梯度TnxfxfxfXf),.,()(21 性质性质1：函数在某点的梯度若不为：函数在某点的梯度若不为0， 则必与过该点的等值线则必与过该点的等值线（面）垂直。（面）垂直。x0Lf(X)=f(X0)f(X0)X0L性质性质2：梯度方向是函数值具有最大变化率的方向，即函数值：梯度方向是函数值具有最大变化率的方向，即函数值上升最快的方向。上升最快的方向。2. 方向导数和下降（上升）方向方向导数和下降（上升）方向（1）方向导数方向导数：|)()(lim)(0000ptxfptxfpxft 函数函数 在点在点 处沿着方向处沿着方向p 的方向

12、导数。的方向导数。)(xf0 x（2）给定函数）给定函数 和方向和方向p，如果存在实数如果存在实数 ，使得对，使得对于任意的于任意的 ，都有，都有 ，则称，则称p为为 在在点点 处的下降方向。处的下降方向。)(xf0 t),0(t )()(0 xfpxfo )(xf0 x（3） 性质性质 (a) . |)()(00ppxfpxfT (b) p是下降方向是下降方向; 0)(0pxf 0)(0pxf(c) p是下降方向。是下降方向。 0)(0pxfTp是上升方向。（4）常用梯度公式）常用梯度公式,0 c,)(bxbT ,2)(xxxT .2)(AxAxxT 3. Hesse矩阵矩阵（1）雅可比矩阵

13、：设雅可比矩阵：设 )()()(1xgxgxgm，nmjinmmnxgxxgxxgxxgxxgxg )()()()()(1111（2）海赛（海赛（Hesse） 矩阵矩阵：nnjinnnnxxfxfxxfxxfxxfxxfxfxfxf 2221222122122122)()(（3）其它Ix 11AAx )()()(0tpxft ptpxftT)()(0 ptpxfptTT)()(02 01 ncc七七. Taylor展开式展开式)10(,)(21)()()()(21)()()(1222 pxxpxfppxfxfpopxfppxfxfpxfTTTT： )()(21)()()()(20020000

14、xxxfxxxxxfxfxfTT：八八. 凸集与凸函数凸集与凸函数1.凸集凸集（1）凸组合：已知凸组合：已知,nRX 任取k个点 ， Xxi 如果存在常数0 ia，),2,1(ki 11 kiia，使得 xxakiii1，则称 x为ix),2,1(ki 的凸组合。的凸组合。（2）凸集：设集合）凸集：设集合nRX ，如果X中任意两点的凸组合仍然属于X，则称X为凸集。2.凸函数凸函数设设RRXfn :，任取任取Xxx 21,，如果如果1,0,2121 iiaaa，有有)()()(22112211xfaxfaxaxaf ，则称则称f为为X上的（严格）上的（严格）凸函数。凸函数。例子：例子： 2)(x

15、xf 水平集水平集： fXxxfxD,)(| 是凸函数是凸函数。性质：水平集一定是凸集。性质：水平集一定是凸集。3. 凸函数的性质凸函数的性质定理定理. 凸函数的局部极小点就是全局极小点。凸函数的局部极小点就是全局极小点。4. 凸函数的判断条件凸函数的判断条件定理定理1. )(xf是凸集是凸集X上的凸函数的充要条件是上的凸函数的充要条件是Xxx 21,，有，有)()()()(12112xxxfxfxfT .定理定理2.设设)(xf在凸集在凸集X上有二阶连续偏导数，则上有二阶连续偏导数，则)(xf是凸是凸函数的充要条件是函数的充要条件是Xx ，有，有)(2xf 半正定。半正定。例：正定二次函数例

16、：正定二次函数cxbAxxxfTT 21)(，其中，其中A是正定矩阵。是正定矩阵。)(xf是凸函数。是凸函数。5. 凸规划凸规划（1）Dxtsxf .)(min其中其中)(xf是凸函数，是凸函数，D是凸集。是凸集。（2）)(minxf 0)(0)(0)(0)(.11xhxhxgxgtskl其中其中),2,1()(, )(lixgxfi 是线性函数是线性函数.),2,1( )(kjxhj 是凸函数是凸函数,6. 二次规划二次规划mnmnnnnTTRp,RA,Rc,Rb,RQ,RxxpAx. t . scxbQxx)x(fmin 1021这里这里九九. 极小点的判定条件极小点的判定条件（1）必要条

17、件：）必要条件：0)()(min)(xfxfxf（2）充分条件：）充分条件：0)(0)(2 xfxf)(min)(xfxf 2221xxo)xx)(x( f)xx()xx()x( f)x( f)x( fTT 02)x(f（3） 两个结论两个结论 函数在极小点附近的等值线为近似的同心椭圆。函数在极小点附近的等值线为近似的同心椭圆。有有唯唯一一的的极极值值点点：正正定定二二次次函函数数bQxcxbQxxxfTT1*21)( 十十. 算法及相关概念算法及相关概念1、迭代算法、迭代算法集合集合 D上的迭代算法上的迭代算法A： （1）初始点）初始点0 x；（2）按照某种规则）按照某种规则A产生下一个迭代

18、点产生下一个迭代点)(1kkxAx 。（i）如果点列如果点列kx收敛于最优解收敛于最优解*x，则称算法，则称算法A收敛。收敛。（ii）如果如果 )()()(10kxfxfxf，则称算法，则称算法A为为下降迭代算法。下降迭代算法。.0 x.1x.2xD.3x2.下降迭代算法步骤下降迭代算法步骤（1）给出初始点）给出初始点0 x，令，令0 k；（2）按照某种规则确定下降搜索方向）按照某种规则确定下降搜索方向kd；（3）按照某种规则确定搜索步长）按照某种规则确定搜索步长k ，使得，使得)()(kkkkxfdxf ；（4）令）令kkkkdxx 1，1: kk；（5）判断）判断kx是否满足停止条件。是则停止，否则转第是否满足停止条件。是则停止，否则转第2步。步。搜索步长确定方法：搜索步长确定方法：)(min)(kkkkkdxfdxf 称称0)( kTkkkddxf 。k 为最优步长，且