第7讲 无约束规划new

《第7讲 无约束规划new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.无约束规划无约束规划建模——引例无约束规划模型无约束规划的示意图无约束规划的性质无约束规划重要算法用MATLAB解无约束规划“定位问题”——厂址选择等引例1：某城市要选定一个供应中心(供电、供水、公天然气、网络接入等)的位置，该中心向城市中由固定位置的m个用户提供服务。问如何确定这个中心的位置才是最合理的？解设用户位置为(a,b)(i=1,2,...,m)已知，而供应中心的位置ii是(x,x)；假设运输线路不受道路影响，只考虑直线距离，则12可建立求总距离最短的数学模型为：∑m()2()2minf

2、(x,x)=x−a+x−b12i=11i2i若进一步考虑各单位的用量w不同，而运价c按距离i计算，则可建立求总总费用最小的数学模型为：∑m()2()2minf(x,x)=cwx−a+x−b12i=1i1i2i其中：c——运价(元/吨公里)；w——第i个用户的需求量.i“最小二乘问题”——解方程组引例2：在某些实际问题中，往往要求决策变量x,x,...,x满12n足(或近似满足)某些平衡条件，它表现为要求x,x,...,x满足12n方程组f(x,L,x)=0,j=1,2,L,pj1n可转化为求解问题：m

3、∑()2minf(x,L,x)1nj=1即要求均方误差最小——最小二乘问题，包括线性最小二乘和非线性最小二乘问题，在数学建模中有非常重要的应用。无约束规划模型minf(X)n标准形式：(其中f:R→R)nX∈R转化：maxf(X)=min[]−f(X)nnX∈RX∈Rx2f(X)>f(X1)>f(X2)等高线0f(xx)12X0X311X2Ox52x1x10无约束规划的示意图唯一极小(全局极小)22f(xx)=2x−2xx+x−3x+x12112212f=0f=0.298f=0.298多局部极小无约束

4、规划的性质T⎛∂f(X)∂f(X)∂f(X)⎞梯度Æ∇f(X)=⎜⎜,,L,⎟⎟Å列向量∂x∂x∂x⎝12n⎠梯度的特点：1)函数f(X)在X处增长最快的方向，负梯度方向是函数f(X)在X处下降最快的方向；2)梯度的模是函数最快的变化率;3)梯度为零是驻点，极值点是驻点，驻点不一定是极值点。⎡∂2f∂2f∂2f⎤⎢2L⎥海森(Hissian)⎢∂x1∂x1∂x2∂x1∂xn⎥矩阵Æ⎢∂2f∂2f∂2f⎥Å方、对⎢L⎥∇2f(X)=H(X)=∂x∂x2∂x∂x称矩阵⎢12∂x22n⎥⎢⎥MMLM⎢⎥⎢∂

5、2f∂2f∂2f⎥⎢L⎥2⎢⎣∂xn∂x1∂xn∂x2∂xn⎥⎦无约束规划的性质●梯度为0向量的点可能是局部最优点，需要用海森矩阵类型进一步判定；●凸函数的驻点必是全局最优点；补充1)f(X)是凸函数ÅÆ对任意定义域D中的元素X、Y和任意的数0≤a≤1，有：f(aX＋(1－a)Y)≤af(X)+(1－a)f(Y)补充2)对称矩阵的分类类别A正定A半正定A负定半负定不定定义特征值>0特征值≥0(有0)特征值<0特征值≤0(有0)其它判别方法主子式都>0

6、A

7、=0;主子式≥0－A正定－A半正定无约束规划的

8、基本算法基本思路：先求驻点，再判定是否是极值点；kS基本方法——迭代算法:先给定极小点的估计值k+2S(初始值),寻求使函数值下降一个方向,沿此方向找到一个更好的估计值,这样往复迭代,直到k+2某一点不能找到下降方向则终止算法.X迭代算法的基本框架：kS(1)选定初始点X0，令k＝0；(2)在Xk处选定下降方向Sk(若找不到则终止算法);Xk+1(3)从Xk出发沿Sk一维搜索,找到Xk+1=Xk+λSk,kkλSk使得f(Xk+1)

9、维搜索基本原则：1)最优原则：kkkkλ:f(X+λS)=minf(X+λS)kkλ>02)可接受点原则：kkkλ:f(X+λS)

10、)+∇f(X)⋅ST22+S∇f(X)S+o(S)<0牛顿法特点：二次函数1次收敛；单步迭代计算量大，且要求海森矩阵可逆。无约束规划的基本算法3.拟牛顿法为克服牛顿法的缺点，同时保持较快收敛速度的优点，kk+1∇fXk，∇f(Xk+1)，利用第k步和第k+1步得到的X，X，()k+12k−1构造一个正定矩阵H近似代替(∇f(X))，将牛顿方向改为：k+1k+1k+1S=−H∇f(x)从而得到下降方向.拟牛顿法特点：较梯度法收敛速度快速，较牛顿法稳定且计算