东北大学最优化方法全部课件

开始最优化方法（最优化课件研制组）退出主讲：张京最优化方法为了使系统达到最优的目标所提出的各种求解方法称为最优化方法。最优化方法是在第二次世界大战前后，在军事领域中对导弹、雷达控制的研究中逐渐发展起来的。最优化方法解决问题一般步骤：（1）提出需要进行最优化的问题，开始收集有关资料和数据；（2）建立求解最优化问题的有关数学模型，确定变量，列出目标函数和有关约束条件；（3）分析模型，选择合适的最优化方法；（4）求解方程。一般通过编制程序在电子计算机上求得最优解；（5）最优解的验证和实施。随着系统科学的发展和各个领域的需求，最优化方法不断地应用于经济、自然、军事和社会研究的各个领域。第1章预备知识1.1经典极值问题1.例子，2.数学模型第一，无约束极值问题12min,,,nfxxx或12max,,,nfxxx解法：解方程组第二，仅含等式约束的极值问题1212min,,,..,,,0,1,2,,()ninfxxxsthxxxilln或1212max,,,..,,,0,1,2,,()ninfxxxsthxxxilln解法：Lagrange乘子法1.2实例数据拟合问题原料切割问题运输问题营养配餐问题分配问题1.3基本概念1.最优化问题的向量表示法设12,,,Tnxxxx则12min,,,minnfxxxfx（1）以向量为变量的实值函数定义向量间的序关系(定义1.1)：等于＝，小于，严格小于。由此1212min,,,..,,,0,1,2,,()ninfxxxsthxxxillnmin..0fxsthx（2）以向量为变量的实向量值函数最优化问题的一般形式121212min,,,..,,,0,1,2,,(),,,0,1,2,,ninjnfxxxsthxxxillnsxxxjm（3）min..00fxsthxsx2.最优化问题的分类试验问题：用于检验、比较最优化方法优劣的一些最优化问题。3.术语目标函数fx等式约束0hx不等式约束0sx容许解（点）容许集0,0DxhxsxD*xfxx求解问题（3）是指：在容许集中找一点目标函数在该点取极小值，即对于容许集中的任，总有意一点*fxfx*x*fx**,xfx最优点（极小点）最优值最优解严格极小点局部非严格极小点严格极小点非严格极小点全局，使得全局极小点一定是局部极小点。到目前为止，大多数最优化算法求到的都是局部极小点。为了求得全局极小点，一种解决办法是，先求出所有的局部极小点，然后再从中找出全局极小点。4.极大值问题与极小值问题的关系**maxmin..0..000fxfxsthxsthxsxsxxx*ffx22min,21fxyxy1.4二维问题图解法二维极值问题有时可以用图解的方式进行求解，有明显的几何解释。例求解22,21fxyxyc0c图解法的步骤：，显然；②取0,1,4,9,c并画出相应的曲线（称之为等值线）.③确定极值点位置，并用以往所学方法求之。易知本题的极小值点*2,1Tx。再复杂点的情形见P13上的例1.7。虽然三维及以上的问题不便于在平面上画图，图解法失效，但仍有相应的等值面的概念，且等值面具有以下性质：①有不同函数值的等值面互不相交（因目标函数是单值函数的缘故）；②等值面不会在区域的内部中断，除了极值点所在的等值面以外。这是由于目标函数是连续函数的缘故；①令⑶等值面稠密的地方，目标函数值变化得比较快；等值面稀疏的地方，目标函数值变化得比较慢；⑷在极值点附近，等值面（等值线）一般近似地呈现为同心椭球面族（椭圆线族）。1.5梯度和Hesse矩阵本段讨论都基于对函数fx以下及今后的讨论中还经常要用到以下一些向量的知识。可微的假定。1212,,,,,,,,TTnnaaaabbbb1122nnabababab,ab与。记作1212,,,,Tnnbbababaaab。向量也常用希腊字母,,,,,等表示。向量内积的性质：ⅰ),,（对称性）；,,,,,kkⅱ)（线性性）；,00,0ⅲ),当且仅当时，（正定性）；向量的内积设则称为向量的内积，其实，,向量的长单位向量1向量的夹角，,,arccos0,向量的正交,,02（正交性）1.可微10:,nfDRRxDn,lnp定义1.7设.如果存在维向量对于可任意小的维非零向量，总有000lim0Tpfxpfxlpp在点那么称函数fx处可微。0x若令00Tfxpfxlpp便得到（1.9）的等价形式00Tfxpfxlpop.（1.10）2.梯度1:nfRR0xfx定理1.1若在点处可微，则在该点关于各个变量的一阶偏导数存在，并且12,,,Tnfxfxfxlxxxfxn12,,,Tnfxfxfxxxxfxxfx定义1.8以函数的个偏导数为分量的向量称为在点处的梯度，记为。。fxx梯度也称为函数关于变量于是，（1.10）可写为000Tfxpfxfxpop这个公式与一元函数展开到两项的Taylor公式是相对的。梯度的性质：当梯度fx连续时，0fxfxfxx第一，若，则必垂直于过点处的等值面；的一阶偏导数。第二，梯度方向是函数具有最大变化率的方向。下面以221212,1fxxxx为例来解释这个性质。上图是该函数的等值线图。B00,3TxBM0xp今考虑一点，不妨取坐标为。设想有出发沿某个方向移动到了点，其坐标，那么目标函数值将产生如下变化量一动点从设为00fxpfx假定1p。试问：动点沿哪个方向移动会使目标函数值有最多的下降或上升？从图上看，这相当于问：在以点B为圆心、以1为半径的圆周上，哪一个点具有最大的或最小的目标函数值。fx0xp为了一般地描述函数在点处沿情况及变化速度，须引入上升方向和下降方向及方向导数的概念。方向的变化fx0xpfx0xp函数在点处沿方向的变化反映的是函数在一条直线上的变化，空间中由一点和一方向所确定的直线方程为10,xxtptR上升方向和下降方向设1:nfRR是连续函数。00,t00fxtpfxpfx0x0,0,t00fxtpfxpfx0x若存在，对于都有，则称方向是在点处的上升方向；若存在对于都有，则称方向是在点处的下降方向。1:nfRR0xep定义1.9设在点处可微，是非方向上的单位向量。如果极限零向量000limtfxtefxtfx0xp0fxp存在，则称其为函数在点处沿方向的方向导数，。记作fxp12,,,nfxfxfxxxx思考：与的异同。00fxppfx0x若，则方向是在点处的上升方向；根据极限理论，易见00fxppfx0x若，则方向是在点处的下降方向。因此，方向导数的正负决定了函数值的升降。1:nfRR0x00Tfxfxep定理1.2设在点处可微，则，ep其中是非零向量方向上的单位向量。00Tfxppfx0x00Tfxppfx0x定理1.2又表明：只要，则方向是在点处的上升方向；只要，则方向是在点处的下降方向。函数值升降的快慢则是由方向导数绝对值的大小决定的。绝对值越大，升或降的速度就越快；绝对值越小，升或降的速度就越慢。这是因为000cos,fxfxefxpp0000cos,fxfxfxpfxp据此有p0fx0fxp0fxⅰ)等号成立当且仅当与同方向或与同方向。且当与同方向时，0fxp取到最大值0fx。p0fx当与同方向时，0fxp取到最小值0fx0,fxp00fxpⅱ)若是锐角，则;0,fxp00fxp若是钝角，则。fx0xp因此，方向导数又可以称为函数在点处沿方向的变化率。使函数值下降最快的方向称为最速下降方向。最速下降方向为0pfx例1.8P19几个常用函数的梯度公式fxC0fx0C（1）若，则，即（2）Tbxb（3）2TxQxQx；（4）2Txxx.；；2.Hesse矩阵fxx问：函数关于变量的二阶导数又是什么？先来看什么是向量值函数的可微。定义1.11设0g:,nmDRRxD。若gx的所有分量12,,gxgx,mgx0xgx0x在点都可微，则称向量值函数在点处可微。gx0x定义表明，在点处可微，则0000lim0,1,2,,Tiiipgxpgxgxpimp成立，其用向量形式可简单地表示为0000lim0Tpgxpgxgxpp其中1020011110200022210200mmmnnngxgxgxxxxgxgxgxgxxxxgxgxgxxxxgx0x称为向量值函数在点处的导数，0Tgxgx0x而称为向量值函数在点处的Jacobi矩阵。1:nfRR,gxfx设具有二阶连续偏导数，且则矩阵2222121122221222222212nnnnnfxfxfxxxxxxfxfxfxfxxxxxxfxfxfxxxxxxfxx2fx2fxfx称为函数关于变量的二阶导数，简记为。也称为多元实值函数的Hesse矩阵。例1.9P21几个特殊的向量值函数的导数公式：（1）cO；（2）xI；（3）TAxA；0tfxtp111:,:nfRRRR（4）设，其中。则020,.TTtfxtpptpfxtpp利用（4），可得多元函数展开到三项的Taylor公式212TTfxpfxfxppfxp（1.29）或212TTfxpfxfxppfxpop（1.31）这个公式与一元函数展开到三项的Taylor公式是相对应的。多元函数的Taylor展开式在最优化方法中十分重要，许多方法及其收敛性的证明都是从它出发的。1.凸集1.6凸函数与凸规划直观上，凸集就是空间中内部无“洞”，边界又不向内凹的一些点的集合，其基本特征是该集合中任意两点间的线段仍然属于这个集合。非凸集凸集空间中两点间的线段是由点的凸组合定义的。12,,,nxxxnRl定义1.12设是中的个已知点。nxR11liia12,,,naaa点，若存在满足的非负实数对于使得1liiixaxx12,,,nxxx，则称是的一个凸组合。12,,,naaa11liiax12,,,nxxx又若是满足的正实数，则称是的一个严格凸组合。12,xx1122xaxax12,xx两点的凸组合恰是连接两点的的线段。线段，而严格凸组合是不含端点nCRCCC定义1.13设集合。如果