无约束优化选址问题

无约束优化选址问题无约束优化选址问题 超市选址问题 问题的提出 怎么选择超市的地址 使得居民区离超市所在位 置距离最近 居民区位置用二维坐标表示 X Y i 1 2 n ii 此问题的优化模型为 min D n i ii yyxx 1 22 实例分析 某投资商想在城市居民区新建一个超市 已知其五个居民区的位置坐标如下表 XY 1103 2 411 36 2 4214 5 51 为使超市离居民区距离之和达到最小 该如何选择超市的位置 居民区坐标位置图绘制如下 则此问题的优化模型为 minD 22 3 10 yx 22 11 4 yx 22 2 6 yx 22 14 2 yx 22 1 5 yx 函数用 MATLAB 画出曲面图以及等高线图 X Y meshgrid 10 0 1 10 Z sqrt X 10 2 Y 3 2 sqrt X 4 2 Y 11 2 sqrt X 6 2 Y 2 2 sqrt X 2 2 Y 14 2 sqrt X 5 2 Y 1 2 surf X Y Z shading interp xlabel X ylabel Y zlabel Z title surf of surface X Y meshgrid 10 0 1 10 Z sqrt X 10 2 Y 3 2 sqrt X 4 2 Y 11 2 sqrt X 6 2 Y 2 2 sqrt X 2 2 Y 14 2 sqrt X 5 2 Y 1 2 contour X Y Z 100 shading interp xlabel X ylabel Y title contour of surface 我们可以用无约束优化算法中的最速下降法进行求解 Grad m function x val k grad fun gfun x0 功能 用最速下降法求解无约束问题 min f x 输入 x0是初始点 fun gfun分别是目标函数和梯度 输出 x val分别是近似最优点和最优值 k是迭代次数 maxk 5000 最大迭代次数 rho 0 5 sigma 0 4 k 0 epsilon 1e 5 while k maxk g feval gfun x0 计算梯度 d g 计算搜索方向 if norm d epsilon break end m 0 mk 0 while m 20 Armijo搜索 if feval fun x0 rho m d su x 1 5145 5 4837 val 41 8050 k 4 运行时间分析 修正牛顿法 function x val k revisenm fun gfun Hess x0 功能 用修正牛顿法求解无约束问题 min f x 输入 x0是初始点 fun gfun Hess 分别是求 目标函数 梯度 Hesse 阵的函数 输出 x val分别是近似最优点和最优值 k是迭代次数 n length x0 maxk 150 rho 0 55 sigma 0 4 tau 0 0 k 0 epsilon 1e 5 while k maxk gk feval gfun x0 计算梯度 muk norm gk 1 tau Gk feval Hess x0 计算Hesse阵 Ak Gk muk eye n dk Ak gk 解方程组Gk dk gk 计算搜索方向 if norm gk epsilon break end 检验终止准则 m 0 mk 0 while m 20 用Armijo搜索求步长 if feval fun x0 rho m dk e x 1 5145 5 4837 val 41 8050 k 12 运行时间 最速下降法阻尼牛顿法修正牛顿法 最优点 1 5146 5 4837 1 5145 5 4837 1 5145 5 4837 最优值 41 805041 805041 8050 迭代次数44412 运行时间0 0790 0090 020 修正牛顿法是最速下降法和牛顿法的结合 从表格可以看出 阻尼牛顿法的收敛速度 比修正牛顿法还要好 问题扩展 n个居民区到超市的最短距离问题 其目标函数的坐标值我们用for循环实现对数据的读取 Fun m function f fun x n 6 A 1 2 3 4 5 6 B 0 1 2 3 4 5 f 0 for i 1 n f f sqrt x 1 A i 2 x 2 B i 2 end f 梯度函数 Gfun m function g gfun x g 2 x 1 2 2 x 1 1 2 x 2 2 1 2 2 x 1 4 2 x 1 2 2 x 2 1 2 1 2 2 x 1 6 2 x 1 3 2 x 2 2 2 1 2 2 x 1 8 2 x 1 4 2 x 2 3 2 1 2 2 x 1 10 2 x 1 5 2 x 2 4 2 1 2 2 x 1 12 2 x 1 6 2 x 2 5 2 1 2 x 2 x 1 1 2 x 2 2 1 2 2 x 2 2 2 x 1 2 2 x 2 1 2 1 2 2 x 2 4 2 x 1 3 2 x 2 2 2 1 2 2 x 2 6 2 x 1 4 2 x 2 3 2 1 2 2 x 2 8 2 x 1 5 2 x