数值最优化1

数值最优化主讲：陈高洁[e-mail]推荐教材：李董辉等，《数值最优化》，科学出版社参考教材：1、袁亚湘，孙文瑜，《最优化理论与方法》，科学出版社2、陈宝林，《最优化理论与算法》，清华大学出版社前言一、什么是最优化最优化是一门应用性相当广泛的学科，它讨论决策问题的最佳选择之特性，寻找最佳的计算方法，研究这些计算方法的理论性质及其实际计算表现。应用范围：信息工程及设计、经济规划、生产管理、交通运输、国防工业以及科学研究等诸多领域。二、包含的内容按照优化思想分为经典方法与现代方法。经典方法主要包括：线性规划、非线性规划、整数规划、动态规划等现代方法主要包括：随机规划、模糊规划、模拟退火算法、遗传算法、禁忌搜索和人工神经网络等。我们学习的内容主要是经典的最优化方法。内容包括无约束最优化方法、约束最优化方法、线性规划及其对偶规划等主要内容。三、学习方法1、认真听讲，课后及时复习巩固，并主动完成课后习题。2、多看参考书，通过不同学者的讲述，全方位理解最优化方法的思想方法和应用，特别是计算方法。3、学以致用，通过最优化方法的学习，培养研究生数学建模的能力和解决实际问题的能力。大家可以尝试对于一些实际问题，先建立数学模型，转化为数学问题，通过一些算法解决。课程内容一、基本概念与基础知识(第一章、第二章)二、最优性条件(第二章、第八章)三、各类算法(其它各章)第一章引言第一节最优化问题概述第二节凸集与凸函数1.最优化问题的提出例1.1.1（食谱问题）设市场上可以买到n种不同的食品，每种食品含有m种营养成分。设每单位的j种食品含i种营养成分的数量为aij，i=1,…，m,j=1,…,n.第j种食品的单位价格为cj,j=1,…,n.再设每人每天对第i种营养成分的需求量为bi,i=1,…,m.试确定在保证营养需求条件下的经济食谱。例1.1.2（数据拟合问题）设有观测数据(xk,yk),k=1,…,5,其值由表1.1给出：k12345xkyk22.0142.9853.5085.0295.47试用一个简单的函数关系拟合这些数据。2.最优化问题的数学模型,),(minnRDxxf其中是定义在上的实值函数。fnR（1.1）•无约束最优化问题（）•约束最优化问题nRD},0)(,,0)(|{EjxhIixgxDji基本概念：可行点、可行域局部最优解全局最优解*),(),(*)(xUDxxfxf.),(*)(Dxxfxf}.*|{*)(xxRxxUn其中全局极小点一定是局部极小点。到目前为止，大多数最优化算法求到的都是局部极小点。为了求得全局极小点，一种解决办法是，先求出所有的局部极小点，然后再从中找出全局极小点。**maxmin..0..000fxfxsthxsthxsxsxxx*ffx极大值问题与极小值问题的关系3.回顾几个数学概念梯度向量：Ñf(x)=(¶f(x)¶x1,,¶f(x)¶xn)Ñ2f(x)=¶2f(x)¶x12¶2f(x)¶x1¶xn¶2f(x)¶xn¶x1¶2f(x)¶xn2æèçççççççöø÷÷÷÷÷÷÷Hessian矩阵：例f(x)=12xTAx+bTx+c梯度的性质：当梯度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几个常用函数的梯度公式fxC0fx0C（1）若，则，即（2）Tbxb（3）2TxQxQx；（4）2Txxx.；；一阶Taylor展开式：).1,0(),()()()()())(()()(tyxoyxyfyfyxyxtyfyfxfTT二阶Taylor展开式：f(x)=f(y)+Ñf(y)T(x-y)+12(x-y)TÑ2f(y+t(x-y))(x-y)=f(y)+Ñf(y)T(x-y)+12(x-y)TÑ2f(y)(x-y)+o(x-y2),tÎ(0,1).多元函数的Taylor展开式在最优化方法中十分重要，许多方法及其收敛性的证明都是从它出发的。首先将向量长度概念推广到Rn(或Cn)中.)),((),(11niiiHniiiTyxxyyxyxxyyx或复数称为向量x,y的数量积(内积).将非负实数,),(122niixxxx,),(122niixxxx或称为向量x的欧氏范数.定义1.设x=(x1,x2,,xn)T,y=(y1,y2,,yn)TRn,将实数向量和矩阵的范数我们还可以用其他办法来度量Rn中向量的“大小”.例如,对于x=(x1,x2)TRn,可以用一个x的函数N(x)=max|xi|来度量x的“大小”,而且这种度量x的“大小”的方法计算起来比欧氏范数方便.在许多应用中,对度量x的“大小”的函数N(x)都要求是正定的、齐次的且满足三角不等式.下面我们给出向量范数的一般定义.(1)||x||0(||x||=0当且仅当x=0)(正定性),(2)||αx||=|α|||x||,对任何αR(或αC)(齐次性),(3)||x+y||||x||+||y||(三角不等式).则称f(x)=||x||是Rn(或Cn)上的一个向量范数(或模).定义2.(向量的范数)如果向量xRn(或Cn)的某个实值函数f(x)=||x||，满足条件:下面给出几种常用的向量范数,设x=(x1,x2,,xn)T..max.11inixx..211niixx.),(.32112212niixxxx容易证明前三种范数是的p-范数特殊情况,其中向量的-范数(最大范数)向量的1-范数..411pnipipxx向量的p-范数(0p+)向量的欧氏范数,2范数(本书中采用).xlimxpp例计算向量x=(1,-2,3)T的各种范数.解,33,2,1maxx.1,6321x.21.14321x.32222定理1.(向量范数的连续性)设函数f(x)=||x||为Rn上任一向量范数,则f(x)是x的分量x1,x2,,xn的连续函数.定理2.(向量范数的等价性)设||x||s,||x||t为Rn上任意的两种范数,则存在常数c1,c20,使得对一切xRn有.21stsxcxxc结论:如果在一种范数意义下向量序列收敛时,则在任何一种范数意义下该向量序列均收敛.定理3.,其中||·||为向量的任一种范数.0limlim)()(xxxxkkkk定义3.设{x(k)}为Rn中一向量序列,x*Rn,记x(k)=(x1(k),,xn(k))T,x*=(x1*,,xn*)T.如果则称x(k)收敛于x*.记为),,,2,1(lim)(nixxikik.lim)(xxkk下面我们将向量范数概念推广到矩阵上去.可以将Rn×n中的矩阵A=(aij)nn当作n2维向量,则由向量的2-范数可以得到Rn×n中矩阵的一种范数.)(21112ninjijFaAAF称为A的Frobenius范数.||A||F显然满足正定性、齐次性及三角不等式.下面我们给出矩阵范数的一般定义.定义4.(矩阵的范数)如果矩阵ARn×n的某个实值函数N(A)=||A||，满足条件:(1)||A||0(||A||=0当且仅当A=0)(正定性)；(2)||cA||=|c|||A||,c为实数(齐次性)；(3)对任意A,B有||A+B||||A||+||B||(三角不等式)(4)对任意A,B有||AB||||A||||B||(相容性)；则称N(A)是Rn×n上的一个矩阵范数(或模).上面我们定义的F(A)=||A||F就是Rn×n上的一个矩阵范数.上述条件(即不等式)就称为矩阵范数与向量范数的相容性条件.由于在大多数与估计有关的问题中,矩阵和向量会同时参与讨论,所以希望引进一种矩阵的范数,它是和向量范数相联系而且和向量范数相容的,即对任何向量xRn及矩阵ARn×n都成立||Ax||≤||A||||x||.为此我们再引进一种矩阵的范数.定义5.(矩阵的算子范数)设xRn,ARn×n,给出一种向量范数||x||v(如v=1,2或),相应地定义一个矩阵的非负函数.max0vvxvxAxA可验证||A||v满足定义4,所以||A||v是Rn×n上矩阵的一个范数,称为A的算子范数.定理4.设||x||v是Rn上的一个向量范数,则||A||v是Rn×n上矩阵的范数,且满足相容条件.vvvxAAx显然这种矩阵的范数||A||v依赖于向量范数||x||v的具体含义.也就是说,当给出一种具体的向量范数||x||v时,相应地就得到了一种矩阵范数||A||v.定理5.设xRn,A=(aij)Rn×n,则有常用的算子范数njijniaA11max.1niijnjaA111max.2)(.3max2AAAT（称为A的行范数）,（称为A的列范数）