无约束规划new

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

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

2、量wi不同，而运价c按距离无约束规划重要算法计算，则可建立求总总费用最小的数学模型为：∑m()2()2用MATLAB解无约束规划minf(x1,x2)=ci=1wix1−ai+x2−bi其中：c——运价(元/吨公里)；wi——第i个用户的需求量.“最小二乘问题”——解方程组无约束规划模型引例2：在某些实际问题中，往往要求决策变量x1,x2,...,xn满足(或近似满足)某些平衡条件，它表现为要求x1,x2,...,xn满足minf(X)n标准形式：(其中f:R→R)方程组X∈Rnf(x,L,x)=0,j=1,2,L,pj1

3、n()([])转化：maxfX=min−fXnnX∈RX∈R可转化为求解问题：mx22f(X)>f(X1)>f(X2)min∑()f(x,L,x)等高线01nf(xx)j=112X0即要求均方误差最小——最小二乘问题，包括线性最小X311二乘和非线性最小二乘问题，在数学建模中有非常重要的应X2用。Ox52x1x10无约束规划的示意图无约束规划的性质T∂f(X)∂f(X)∂f(X)梯度Æ∇f(X)=,,L,Å列向量唯一极小∂x1∂x2∂xn(全局极小)梯度的特点：1)函数f(X)在X处增长最快的方向，负梯度方

4、向是函数f(X)在X处下降最快的方向；2)梯度的模是函数最快的f(xx)=2x2−2xx+x2−3x+x变化率;3)梯度为零是驻点，极值点是驻点，驻点不一定是极12112212值点。∂2f∂2f∂2f2Lf=0海森(Hissian)∂x1∂x1∂x2∂x1∂xnf=0.298矩阵Æ∂2f∂2f∂2fÅ方、对L∇2f(X)=H(X)=∂x∂x∂x2∂x∂x称矩阵1222nf=0.298MMLM多局部极小∂2f∂2f∂2fL2∂xn∂x1∂xn∂x2∂xn1无约束规划的性质●梯度

5、为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半正定无约束规划的基本算法无约束规划的基本算法基本思路：先求驻点，在判定是否是极值点；一维搜索基本原则：1)最优原则：kS基本

8、方法——迭代算法:先给定极小点的估计值Sk+2λ:f(Xk+λSk)=minf(Xk+λSk)kk(初始值),寻求使函数值下降一个方向,沿此方λ>0向找到一个更好的估计值,这样往复迭代,直到2)可接受点原则：k+2kkkXλ:f(X+λS)

9、kSk,λSk∇f(Xk)T⋅Sk<0k使得f(Xk+1)

10、：3.牛顿法k[]2k−1kSk+1=−Hk+1∇f(xk+1)S=−∇f(X)∇f(X)从而得到下降方向.Tf(X+S)=f(X)+∇f(X)⋅S拟牛顿法特点：较梯度法收敛速度快速，较牛顿法T22+S∇f(X)S+o(S)<0稳定且计算量小。牛顿法特点：二次函数1次收敛；单步迭代计算量大，且要4.信赖