运筹学和最优化.ppt
《运筹学和最优化.ppt》由会员分享,可在线阅读,更多相关《运筹学和最优化.ppt(30页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、运筹学和最优化现在学习的是第1页,共30页2.0、预备知识、预备知识1 1、向量和子空间投影定理、向量和子空间投影定理(1)(1)n n维欧氏空间:维欧氏空间:R Rn n 点(向量)点(向量):x R Rn n,x=(=(x1,x2,xn)T T 分量分量 xi R R(实数集实数集)方向(自由向量)方向(自由向量):d R Rn n,d 0 d=(=(d1,d2,dn)T T 表示从表示从0 0指向指向d 的方向的方向 实用中,常用实用中,常用 x+d 表示从表示从x 点出发沿点出发沿d 方向移动方向移动 d 长度得到的点长度得到的点d0 xx+(1/2)d现在学习的是第2页,共30页2.
2、02.0、预备知识(续)、预备知识(续)、预备知识(续)、预备知识(续)1 1、向量和子空间投影定理、向量和子空间投影定理(2)(2)向量运算:向量运算:x,y R Rn n n x,y 的内积:的内积:xTy=xiyi=x1y1+x2y2+xnyn i=1 x,y 的距离:的距离:x-y=(x-y)T(x-y)(1/2)x 的长度:的长度:x=xTx(1/2)三角不等式三角不等式:x+y xy 点列的收敛:点列的收敛:设点列设点列x(k)R Rn n ,x R Rn n 点列点列x(k)收敛到收敛到 x,记记lim x(k)=x limx(k)-x=0 lim xi(k)=xi,ik k k
3、x+yyx现在学习的是第3页,共30页2.02.0、预备知识(续)、预备知识(续)、预备知识(续)、预备知识(续)1 1、向量和子空间投影定理、向量和子空间投影定理(3)(3)子空间:子空间:设设 d(1),d(2),d(m)R Rn n,d(k)0 m 记记 L L(d(1),d(2),d(m)=)=x=j d(j)j R j=1为由向量为由向量d(1),d(2),d(m)生成的子空间,简记为生成的子空间,简记为L L。l正交子空间:设正交子空间:设 L 为为R Rn n的的子空间,其正交子空间为子空间,其正交子空间为 L x R Rn n xTy=0,y L l子空间投影定理:子空间投影定
4、理:设设 L 为为R Rn n的的子空间。那么子空间。那么 x R Rn n,唯一唯一 x L,y L,使使 z=x+y,且且 x 为问题为问题 min z-u s.t.u L 的唯一解,最优值为的唯一解,最优值为y。l特别,特别,L R Rn n 时,正交子空间时,正交子空间 L 0(零空间零空间)现在学习的是第4页,共30页2.02.0、预备知识(续)、预备知识(续)、预备知识(续)、预备知识(续)l规定:规定:x,y R Rn n,x y xi yi,i 类类似规定似规定 x y,x=y,x y.l一个有用的定理一个有用的定理 设设 x R Rn n,R R,L L为为R Rn n 的线
5、性子空间,的线性子空间,(1)(1)若若 xTy ,y R Rn n 且且 y 0,则则 x 0,0.(2)(2)若若 xTy ,y L L R Rn n,则则 x L L,0.(特别特别,L LR Rn n时时,x=0=0)l定理的其他形式:定理的其他形式:“若若 xTy ,y R Rn n 且且 y 0,则则 x 0,0.”“若若 xTy ,y R Rn n 且且 y 0,则则 x 0,0.”“若若 xTy ,y R Rn n 且且 y 0,则则 x 0,0.”“若若 xTy ,y L L R Rn n,则则 x L L,0.”现在学习的是第5页,共30页2.02.0、预备知识(续)、预备
6、知识(续)、预备知识(续)、预备知识(续)2 2、多元函数及其导数、多元函数及其导数(1)(1)n n元函数:元函数:f(x):):R Rn n R R 线性函数线性函数:f(x)=cTx+b=ci xi +b 二次函数二次函数:f(x)=(1/2)xTQx+cTx+b =(1/2)i j aij xi xj +ci xi +b 向量值线性函数:向量值线性函数:F(x)=Ax+d R Rm m其中其中 A为为 m n矩阵,矩阵,d为为m维向量维向量 F(x)=(f1(x),f2(x),fm(x)T 记记 aiT为为A的第的第i行向量,行向量,fi(x)=aiTx现在学习的是第6页,共30页2.
7、02.0、预备知识(续)、预备知识(续)、预备知识(续)、预备知识(续)2 2、多元函数及其导数、多元函数及其导数(2)(2)梯度(一阶偏导数向量):梯度(一阶偏导数向量):f(x)(f/x1,f/x2,f/xn)T T R Rn n .线性函数线性函数:f(x)=cTx+b,f(x)=c 二次函数二次函数:f(x)=(1/2)xTQx+cTx+b f(x)=Qx+c 向量值线性函数:向量值线性函数:F(x)=Ax+d R Rm m F/x=AT现在学习的是第7页,共30页2.02.0、预备知识(续)、预备知识(续)、预备知识(续)、预备知识(续)2 2、多元函数及其导数、多元函数及其导数(3
8、)Hesse(3)Hesse 阵(二阶偏导数矩阵):阵(二阶偏导数矩阵):2f/x1 2 2f/x2 x1 2f/xn x1 2f(x)=)=2f/x1 x2 2f/x22 2f/xn x2 2f/x1 xn 2f/x2 xn 2f/xn2 线性函数线性函数:f(x)=cTx+b,2f(x)=0 二次函数二次函数:f(x)=(1/2)xTQx+cTx+b,2f(x)=Q现在学习的是第8页,共30页2.02.0、预备知识(续)、预备知识(续)、预备知识(续)、预备知识(续)2 2、多元函数及其导数、多元函数及其导数(4)(4)n n元函数的元函数的TaylorTaylor展开式及中值公式:展开式
9、及中值公式:设设 f(x):):R Rn n R R ,二阶可导。在二阶可导。在x*的邻域内的邻域内l一阶一阶TaylorTaylor展开式:展开式:f(x)=f(x*)+f T(x*)(x-x*)+ox-x*l二阶二阶TaylorTaylor展开式:展开式:f(x)=f(x*)+f T(x)(x-x*)+(1/2)(x-x*)T 2f(x*)(x-x*)+ox-x*2l一阶中值公式:对一阶中值公式:对x,使使 f(x)=f(x*)+f(x*+(x-x*)T(x-x*)lLagrange余项:余项:对对x,记记x x*+(x-x*)f(x)=f(x*)+f T(x)(x-x*)+(1/2)(x
10、-x*)T 2f(x )(x-x*)现在学习的是第9页,共30页2.1 2.1 数学规划模型的一般形式数学规划模型的一般形式 min min f(x)-目标函数目标函数 s.t.s.t.x S-约束集合,可行集约束集合,可行集其中,其中,S R Rn n,f:S R R,x S称(称(f S)的可行解的可行解l最优解最优解:x*S,满足满足f(x*)f(x),x S。则称则称 x*为为(f S)的全局最优解的全局最优解(最优解最优解),),记记 g.opt.(global optimum),),简记简记 opt.l最优值最优值:x*为为(f S)的最优解的最优解,则称则称 f*=f(x*)为为
11、 (f S)的最优值的最优值(最优目标函数值最优目标函数值)(f S)现在学习的是第10页,共30页2.1 2.1 数学规划模型的一般形式(续)数学规划模型的一般形式(续)l局部最优解局部最优解:x*S,x*的邻域的邻域 N(x*),使满足,使满足 f(x*)f(x),x S N(x*)。则称则称 x*为为(f S)的局部最优的局部最优解解,记记 l.opt.(local optimum)l在上述定义中,当在上述定义中,当x x*时有严格不等式成立,时有严格不等式成立,则分别称则分别称 x*为为(f S)的严格全局最优解和严格局部最优解。的严格全局最优解和严格局部最优解。严格严格l.opt.严
12、格严格g.opt.l.opt.现在学习的是第11页,共30页2.1 2.1 数学规划模型的一般形式(续)数学规划模型的一般形式(续)l函数形式函数形式:f(x),gi(x),hj(x):RnR min f(x)(fgh)s.t.gi(x)0 ,i=1,2,m hj(x)=0 ,j=1,2,ll矩阵形式矩阵形式:min f(x),f(x):RnR(fgh)s.t.g(x)0 ,g(x):RnRm h(x)=0 ,h(x):RnRl 当当 f(x),gi(x),hj(x)均为线性函数时,称线性规划;均为线性函数时,称线性规划;若其中有非线性函数时,称非线性规划。若其中有非线性函数时,称非线性规划。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 优化
限制150内