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

最优化方法1.教材：最优化理论与方法陈宝林，清华大学出版社2.参考书：最优化原理与方法薛嘉庆，冶金工业出版社基本知识一.引言四.极值最优化问题的经典方法二.最优化问题实例三.最优化问题及基本概念五.图解法六.梯度与Hesse阵七.Taylor展开式八.凸集与凸函数九.极小点的判定条件十.算法及相关概念十一.中止条件十二.收敛速度一.引言1.最优化定义最优化是从所有可行方案中选择最合理方案以达到最优目标的一门学科。（1）达到最优目标的方案：最优方案（最优解）（2）搜寻最优方案的方法：最优化方法最优化问题：寻求某些变量的取值使其符合某些限制条件，并使某个目标函数达到最大值或最小值的问题。一般的数学形式为：上的函数为定义在集合其中DxfDxtsxf)(..,)(min2.发展简况经典最优化理论的研究已有很久，最早可追溯到Fermat时代。1940年前，对多变量函数的数值最优化方法知之甚少，但当时已发现了若干最小二乘法和在物理上应用的最速下降法，多变量的牛顿法也很著名。40年代与50年代：线性规划（LP）的发展。二战以后，爬山法得到发展与应用（实用，粗糙）。1959年，W-C.Davidon的一个报告引入了变尺度方法。3.应用领域工程设计、军事科学、自动控制、空间技术、资源分配、计算机科学等等。例如：①桥梁结构设计；②运输问题；③参数拟合；④多波形信号发生仪中正弦波形逼近的优化设计，在中找n个分点，使过这些分点的折线和正弦函数曲线的误差最小。2,04.包含内容：最优化又称数学规划：LP、NLP、DP、IP5.分类：多目标动态问题非线性规划线性规划有约束问题无约束问题静态问题单目标最优化问题二.最优化问题实例例1：多参数曲线拟合问题已知热电阻R依赖于温度t的函数关系为：其中是待定参数。通过试验，得到itiRi150347802552861036023650。。。。。。。。。151203307利用最小二乘思想，可将其化为三维空间的无约束最优化问题，即：321expxtxxR321xx,x和组数的和15Rt1512321321exp),,(miniiixtxxRxxxf现有m种资源的数量为。计划生产n种产品1,2,…,n。有关数据如下，试问：怎样安排生产可以使利润达大？mbbb,,,21产品拥有量12…n资源1…2…………………m…单位利润…11a12ana121a22ana21ma2mamna1b2bmb1c2cnc令表示第j种产品的产量。jxnjxmibxatsxcxfjinjjijnjjj,...,2,10,...,2,1..)(max11模型：例2.生产安排问题已知有m个生产点Bi，可供应某种物质量分别为n个销地，需求量为.从到的单位运价为。问：应如何安排运输方案才能使总运费最小？),,2,1(mibi),,2,1(njcjiBjCijajC例3.运输问题（TP）运费销地产量12…n产地1…2…………………m…销量…11a12ana121a22ana21ma2mamna1b2bmb1c2cnc在产销平衡条件下，要求得总运费最小的调运方案，可得如下模型：设表示从第i个产地向第j个销地的运量，则有ijxnjmixnjcxmibxtsxazijjmiijinjijminjijij,...,1,...,10,...,2,1,...,2,1..min1111三.最优化问题及基本概念0)(0)(..)(minxhxgtsxfpjxhmixgtsxfji，，,10)(,10)(..)(minDxtsxf..)(min2.解法分类解析方法：利用函数的解析性质去构造迭代公式使之收敛到最优解（如牛顿法）。直接方法：它对函数的解析性质如可微性没有要求，而是根据一定的数学原理来确定（如0.618法）。1.模型DxxfxfxDxNxxfxfxxxxxNxfxxfxT),()(:),(),()(:}|{),())(,()(**0**00****全局最优解局部最优解邻域最优解：最优值：最优点：3.全局最优解与局部最优解四.极值问题的经典方法1.求驻点的方法000)()(1minnnRxxfxfxfxf0)(0)()())(),(min0),,(0),,(..),,(min12121121xhLxhxfxLxhxfxLxxxhxxxhtsxxxfliiilRnRxnlnn（2.Lagrange乘子法五.图解法等值线（面）的特点：1.不同值的等值线不相交;2.除极值点外，等值线是连续曲线;3.等值线稠密处导数变化快，稀疏处变化慢;六.梯度与Hesse阵1.梯度TnxfxfxfXf),...,,()(21性质1：函数在某点的梯度若不为0，则必与过该点的等值线（面）垂直。x0Lf(X)=f(X0)▽f(X0)X0L性质2：梯度方向是函数值具有最大变化率的方向，即函数值上升最快的方向。2.方向导数和下降（上升）方向（1）方向导数：||||)()(lim)(0000ptxfptxfpxft函数在点处沿着方向p的方向导数。)(xf0x（2）给定函数和方向p，如果存在实数，使得对于任意的，都有，则称p为在点处的下降方向。)(xf0t),0(t)()(0xfpxfo)(xf0x（3）性质(a).||||)()(00ppxfpxfT(b)p是下降方向;0)(0pxf0)(0pxf(c)p是下降方向。0)(0pxfTp是上升方向。（4）常用梯度公式,0c,)(bxbT,2)(xxxT.2)(AxAxxT3.Hesse矩阵（1）雅可比矩阵：设)()()(1xgxgxgm，nmjinmmnxgxxgxxgxxgxxgxg)()()()()(1111（2）海赛（Hesse）矩阵：nnjinnnnxxfxfxxfxxfxxfxxfxfxfxf2221222122122122))(()(（3）其它Ix11AAx)()()(0tpxftptpxftT)()(0ptpxfptTT)()(0201ncc七.Taylor展开式)10(,)(21)()()()(21)()()(1222pxxpxfppxfxfpopxfppxfxfpxfTTTT：))(()(21)()()()(20020000xxxfxxxxxfxfxfTT：八.凸集与凸函数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)(xxf水平集：fXxxfxD,,)(|{是凸函数}。性质：水平集一定是凸集。3.凸函数的性质定理.凸函数的局部极小点就是全局极小点。4.凸函数的判断条件定理1.)(xf是凸集X上的凸函数的充要条件是Xxx21,，有)()()()(12112xxxfxfxfT.定理2.设)(xf在凸集X上有二阶连续偏导数，则)(xf是凸函数的充要条件是Xx，有)(2xf半正定。例：正定二次函数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）必要条件：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）初始点0x；（2）按照某种规则A产生下一个迭代点)(1kkxAx。（i）如果点列}{kx收敛于最优解*x，则称算法A收敛。（ii）如果)()()(10kxfxfxf，则称算法A为下降迭代算法。.0x.1x.2xD.3x2.下降迭代算法步骤（1）给出初始点0x，令0k；（2）按照某种规则确定下降搜索方向kd；（3）按照某种规则确定搜索步长k，使得)()(kkkkxfdxf；（4）令kkkkdxx1，1:kk；（5）判断kx是否满足停止条件。是则停止，否则转第2步。搜索步长确定方法：)(min)(kkkkkdxfdxf称0)(kTkkkddxf。k为最优步长，且有十一.终止条件)(31kkkkxxxx)(41kkkkxfxfxfxf2.4.1.11kkxx21)()(kkxfxf3.xkxk+1xkxk+1x*5||)(||.5kxf。是极值点即理论上可以认为分析：)(,0||)(||kkxxf。迭代次数的门槛值）(.6Mk十二.收敛速度则称的收敛阶为。1.设算法A所得的点列为}{kx，如果,||||||||**1xxxxkk.0,}{kx二阶收敛超线性收敛线性收敛22112.