最优化理论课件 第1章

最优化理论与方法主要内容第一章运筹学思想与运筹学建模第二章基本概念和理论基础第三章线性规划第四章最优化搜索算法的结构与一维搜索第五章无约束最优化方法第六章约束最优化方法第七章目标规划第八章整数规划第九章层次分析法第十章智能优化计算简介第一章运筹学思想与运筹学建模第一章运筹学思想与运筹学建模运筹学—简称OR（美）Operation`sResearch（英）OperationalResearch“运筹于帷幄之中，决胜于千里之外”三个来源：军事、管理、经济三个组成部分：运用分析理论、竞争理论、随机服务理论一、什么是运筹学为决策机构在对其控制下的业务活动进行决策时，提供一门量化为基础的科学方法。或是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。运筹学是一种给出问题坏的答案的艺术，否则的话，问题的结果会更坏。二、运筹学的应用原则1)合伙原则：应善于同各有关人员合作2)催化原则：善于引导人们改变一些常规看法3)互相渗透原则：多部门彼此渗透地考虑4)独立原则：不应受某些特殊情况所左右5)宽容原则：思路宽、方法多，不局限在某一特定方法上6)平衡原则：考虑各种矛盾的平衡、关系的平衡三、运筹学解决问题的工作步骤1）提出问题：目标、约束、决策变量、参数2）建立模型：变量、参数、目标之间的关系表示3）模型求解：数学方法及其他方法4）解的检验：制定检验准则、讨论与现实的一致性5）灵敏性分析：参数扰动对解的影响情况6）解的实施：回到实践中7）后评估：考察问题是否得到完满解决四、运筹学模型的构造思路及评价1.直接分析法2.类比方法3.模拟方法4.数据分析法5.试验分析法6.构想法模型评价:易于理解、易于探查错误、易于计算等优化模型的一般形式Opt.f(xi,yj,k)s.t.gh(xi,yj,k),0h=1,2,…,m其中：xi为决策变量（可控制）yj为已知参数k为随机因素f,gh为（一般或广义）函数建模举例（略）——自看五、基本概念和符号1、向量和子空间投影定理(1)n维欧氏空间：Rn点（向量）：xRn,x=(x1,x2,…,xn)T分量xiR(实数集)方向（自由向量）：dRn,d0d=(d1,d2,…,dn)T表示从0指向d的方向实用中，常用x+d表示从x点出发沿d方向移动d长度得到的点d0xx+(1/2)d五、基本概念和符号（续）1、向量和子空间投影定理(2)向量运算：x,yRnnx,y的内积：xTy=xiyi=x1y1+x2y2+…+xnyni=1x,y的距离：‖x-y‖=[(x-y)T(x-y)](1/2)x的长度：‖x‖=[xTx](1/2)三角不等式：‖x+y‖≤‖x‖＋‖y‖点列的收敛：设点列｛x(k)｝Rn,xRn点列｛x(k)｝收敛到x，记limx(k)=xlim‖x(k)-x‖=0limxi(k)=xi,ikkkx+yyx五、基本概念和符号（续）1、向量和子空间投影定理(3)子空间：设d(1),d(2),…,d(m)Rn,d(k)0m记L(d(1),d(2),…,d(m))={x=jd(j)jR}j=1为由向量d(1),d(2),…,d(m)生成的子空间，简记为L。正交子空间：设L为Rn的子空间，其正交子空间为L＝{xRnxTy=0,yL}子空间投影定理：设L为Rn的子空间。那么xRn，唯一xL,yL,使z=x+y,且x为问题min‖z-u‖s.t.uL的唯一解，最优值为‖y‖。特别，L＝Rn时，正交子空间L＝{0}（零空间）五、基本概念和符号（续）规定：x,yRn，x≤yxi≤yi，i类似规定x≥y，x=y，xy,xy.一个有用的定理设xRn，R，L为Rn的线性子空间，(1)若xTy≤,yRn且y≥0，则x≤0，≥0.(2)若xTy≤,yLRn，则xL，≥0.(特别,L＝Rn时,x=0)定理的其他形式：“若xTy≤,yRn且y≤0，则x≥0，≥0.”“若xTy≥,yRn且y≥0，则x≥0，≤0.”“若xTy≥,yRn且y≤0，则x≤0，≤0.”“若xTy≥,yLRn，则xL，≤0.”五、基本概念和符号（续）2、多元函数及其导数(1)n元函数：f(x):RnR线性函数：f(x)=cTx+b=cixi+b二次函数：f(x)=(1/2)xTQx+cTx+b=(1/2)ijaijxixj+cixi+b向量值线性函数：F(x)=Ax+dRm其中A为mn矩阵，d为m维向量F(x)=(f1(x),f2(x),…,fm(x))T记aiT为A的第i行向量，f(x)=aiTx五、基本概念和符号（续）2、多元函数及其导数(2)梯度（一阶偏导数向量）：f(x)＝(f/x1,f/x2,…,f/xn)TRn.线性函数：f(x)=cTx+b,f(x)=c二次函数：f(x)=(1/2)xTQx+cTx+bf(x)=Qx+c向量值线性函数：F(x)=Ax+dRmF/x=AT五、基本概念和符号（续）2、多元函数及其导数(3)Hesse阵（二阶偏导数矩阵）：2f/x12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五、基本概念和符号（续）2、多元函数及其导数(4)n元函数的Taylor展开式及中值公式：设f(x):RnR，二阶可导。在x*的邻域内一阶Taylor展开式：f(x)=f(x*)+fT(x*)(x-x*)+o‖x-x*‖二阶Taylor展开式：f(x)=f(x*)+fT(x)(x-x*)+(1/2)(x-x*)T2f(x*)(x-x*)+o‖x-x*‖2一阶中值公式：对x,,使f(x)=f(x*)+［f(x*+(x-x*))]T(x-x*)Lagrange余项：对x,,记xx*+(x-x*)f(x)=f(x*)+fT(x)(x-x*)+(1/2)(x-x*)T2f(x)(x-x*)第一章其它基础知识复习下列知识：线性代数的有关概念：向量与矩阵的运算、向量的线性相关和线性无关，矩阵的秩，正定、半正定矩阵，线性空间等；集合的有关概念：开集、闭集，集合运算，内点、边界点等。