4.无约束规划 无约束规划建模—引例 无约束规划模型 无约束规划的示意图 无约束规划的性质 无约束规划重要算法 2 用MATLAB解无约束规划
4. 无约束规划 无约束规划建模——引例 无约束规划模型 无约束规划的示意图 无约束规划的性质 无约束规划重要算法 用MATLAB解无约束规划
“定位问题”一厂址选择等 引例1： 某城市要选定一个供应中心（供电、供水、公天然气、 网络接入等)的位置，该中心向城市中由固定位置的个用户提 供服务。问如何确定这个中心的位置才是最合理的？ 解设用户位置为(4，b=1,2,m已知，而供应中心的位置 是(c,x2)；假设运输线路不受道路影响，只考虑直线距离，则 可建立求总距离最短的数学模型为： min f(x,x2）=∑2V(x,-a}+(2-,月 若进一步考虑各单位的用量w,不同，而运价c按距离 计算，则可建立求总总费用最小的数学模型为： mimf(x,x2)=c∑0w,V(c,-a}+(2-b,月 其中：c—运价（元/吨公里）；w,—第个用户的需求量
引例1： 某城市要选定一个供应中心(供电、供水、公天然气、 网络接入等)的位置，该中心向城市中由固定位置的m个用户提 供服务。问如何确定这个中心的位置才是最合理的？ 解 设用户位置为(ai , bi )(i=1,2,...,m)已知，而供应中心的位置 是(x1 , x2 )；假设运输线路不受道路影响，只考虑直线距离，则 可建立求总距离最短的数学模型为： ( ) ( ) = = − + − m i x x x ai x bi f 1 2 2 2 1 2 1 min ( , ) 其中：c——运价(元/吨公里)；wi——第i个用户的需求量. ( ) ( ) = = − + − m i wi x ai x bi f x x c 1 2 2 2 1 2 1 min ( , ) 若进一步考虑各单位的用量wi不同，而运价c按距离 计算，则可建立求总总费用最小的数学模型为： “定位问题”——厂址选择等
“最小二乘问题”一解方程组 引例2：在某些实际问题中，往往要求决策变量x1,x2,,xn满 足（或近似满足）某些平衡条件，它表现为要求x1,X2,,xn满足 方程组 f(x1,…,xn)=03j=1,2,…,p 可转化为求解问题： min 2G,,x,月 即要求均方误差最小—最小二乘问题，包括线性最小 二乘和非线性最小二乘问题，在数学建模中有非常重要的应 用
引例2：在某些实际问题中，往往要求决策变量x1 , x2 , ..., xn满 足(或近似满足)某些平衡条件，它表现为要求x1 , x2 , ..., xn满足 方程组 fj (x1 , , xn ) = 0, j = 1,2, , p 即要求均方误差最小——最小二乘问题，包括线性最小 二乘和非线性最小二乘问题，在数学建模中有非常重要的应 用。 ( ) = m j x xn f 1 2 1 min ( ,, ) 可转化为求解问题： “最小二乘问题”——解方程组
无约束规划模型 标准形式： ip(x) (其中f:R”>R) 转化： axf(x)=-in上f(x】 等高孩 f(X)>f(X)>f(X2) f(x) 3 0 X2 0
无约束规划模型 标准形式： f (X ) n XR min ( f : R R) 其中 n → f (X) f (X) n n X R X R = − − 转化： max min 等高线 1 x 2 x ( ) x1 x2 f O 1 x 2 x 0 5 3 1 X0 X1 X2 ( ) X0 f ( ) X1 f ( ) X2 f
无约束视对的示意，图 睢一极小 全局极小) f(K1x2)=2x2-2x2+-3x1+x2 f=0.298 f=0.298 多局部极小 f(x1x2)=2x7-1.05x4 31 x1x2+x经 6
无约束规划的示意图 多局部极小 f = 0.298 f = 0 f = 0.298 唯一极小 (全局极小) 1 2 2 1 2 2 2 1 2 1 f (x x ) = 2x − 2x x + x − 3x + x
无约束现艾白的性质 af(x)af(x) af(x) 梯度→f()= ←列向量 0x1 0x2 梯度的特点：1)函数f)在X处增长最快的方向，负梯度方向 是函数f)在X处下降最快的方向；2)梯度的模是函数最快的 变化率；3)梯度为零是驻点，极值点是驻点，驻点不一定是极 值点。 o'f o'f o'f 海森(Hessian) 0x1 Ox 8x2 ox oxn 矩阵→ o'f o'f 2f ←方、对 f(X)=H(X)= x Ox2 2 Ox x0x 称矩阵 : 02f o'f o'f ox ox1 oxox
= = 2 2 2 2 1 2 2 2 2 2 2 1 2 2 1 2 1 2 2 2 1 2 2 ( ) ( ) n n n n n x f x x f x x f x x f x f x x f x x f x x f x f f X H X 无约束规划的性质 梯度→ T xn f X x f X x f X f X = ( ) , , ( ) , ( ) ( ) 1 2 列向量 梯度的特点：1) 函数f(X)在X处增长最快的方向，负梯度方向 是函数f(X)在X处下降最快的方向；2)梯度的模是函数最快的 变化率; 3) 梯度为零是驻点，极值点是驻点，驻点不一定是极 值点。 海森(Hessian) 矩阵→ 方、对 称矩阵
元约束规义树的性质 梯度为0向量的点可能是局部最优点，需要用海 森矩阵类型进一步判定； ●凸函数的驻点必是全局最优点； 补充)凶是凸函数←→对任意定义域D中的元素 X、Y和任意的数0sas1,有： faX+(1-0))≤f)+(1-M)f) 补充2)对称矩阵的分类 类别 A正定 A半正定 A负定 半负定 不定 定义 特征值>0 特征值≥0（有0） 特征值0 A=0;主子式20 A正定 一A半正定
无约束规划的性质 ● 梯度为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 |A|=0;主子式≥ 0 －A正定 －A半正定
f出)=-片- f出)=x+ fx龙)=戈-写
无约束视文刻的甚本算法 基本思路：先求驻点，在判定是否是极值点； 基本方法一 迭代算法：先给定极小点的估计值 Sh+2 (初始值)，寻求使函数值下降一个方向，沿此方 向找到一个更好的估计值，这样往复迭代，直到 某一点不能找到下降方向则终止算法. 迭代算法的基本框架： (1)选定初始点XW,令k=0: (2)在X处选定下降方向S(若找不到则终止算法)； X+1 (3)从X出发沿Sf一维搜索，找到X+1=X+入S, 使得fX+)fX: (4)从k=k+1,转(2)
无约束规划的基本算法 基本思路：先求驻点，在判定是否是极值点； 基本方法——迭代算法: 先给定极小点的估计值 (初始值), 寻求使函数值下降一个方向, 沿此方 向找到一个更好的估计值, 这样往复迭代, 直到 某一点不能找到下降方向则终止算法. 迭代算法的基本框架： (1) 选定初始点X0 ，令k＝0； (2)在Xk处选定下降方向S k (若找不到则终止算法); (3) 从Xk出发沿S k一维搜索, 找到Xk+1= Xk +λkS k , 使得 f(Xk+1)<f(Xk )； (4) 从k=k+1, 转(2). k X k+1 X k+2 X k+1 S k S k+2 S k k S
无约束规艾刘的基本算法 维搜索基本原则：)最优原则： 九：f(X*+九xS)=minf(X+S) 2>0 2)可接受点原则： 元：f(X*+2S)<fX) 一维搜索方法：0.618法、插值法等 下降方向：与梯度点乘为负值的方向 Vf(x).sk<0 (f(X+S)=f(x)+Vf(X)".S+olls<0
无约束规划的基本算法 一维搜索基本原则：1) 最优原则： 2) 可接受点原则： : ( ) min ( ) 0 k k k k k k f X S f X S + = + : ( ) ( ) k k k k k f X + S f X 一维搜索方法： 0.618法、插值法等 下降方向：与梯度点乘为负值的方向 ( ) 0 k T k f X S (f (X + S) = f (X) + f (X) S + o( S ) 0) T