第07章 无约束问题

对无约束问题的综述
无约束问最优化问题，就是问题中无约束条件，它的数学模型为)(min x f ，无约束最优化计算方法不仅本身有着不少实际应用，而且与约束最优化计算方法有着紧密的联系：一方面有些处理无约束最优化问题的方法能直接推广应用于约束最优化问题；另一方面，还可以把一些约束最优化问题转化为无约束最优化问题来处理.无约束最化问题按维数搜索可分为一维无约束搜索方法和多维无约束最优方法，对于一维无约束搜索方法，也称为一维搜索方法，目前常见的有三点二次插值法、Fibonacci 法、黄金分割法、进退法及牛顿切线法。

其求解方法在理论上都是寻找出局部极值点，即所搜寻区域是单峰函数。

多维无约束最优化方法大多是逐次一维搜索的迭代算法.这类迭代算法可分为两类.一类不涉及导数，只用到函数值，称为直接法.另一类需要用目标函数的导函数，称为解析法.根据搜索方向的取法不同，可以有各种算法.下面主要论述一下解析型算法，解析型的算法有：梯度法：又称最速下降法.这是早期的解析法，收敛速度较慢.牛顿法：收敛速度快，但不稳定，计算也较困难.共轭梯度法：收敛较快，效果较好.变尺度法：这是一类效率较高的方法.根据秩的不同又可分为DFP 和BFGS 两种，是最常用的方法.这些迭代算法的基本思想是：在一个近似点处选定一个有利搜索方向，沿这个方向进行一维寻查，得出新的近似点.然后对新点施行同样手续，如此反复迭代，直到满足预定的精度要求为止.为简单形式n )(min E x x f ∈，（n 维欧氏空间））k k k p x x ()()1(λ+=+且满足f[X(k+1)]<f[X(k)]这样逐步迭代直至满足精度条件
‖▽f[X(k+1)]‖<
ε1 (梯度绝对值<ε1)。

4. 无约束规划无约束规划建模——引例无约束规划模型无约束规划的示意图无约束规划的性质无约束规划重要算法用MATLAB解无约束规划引例1：某城市要选定一个供应中心(供电、供水、公天然气、网络接入等)的位置，该中心向城市中由固定位置的m 个用户提供服务。

问如何确定这个中心的位置才是最合理的？解设用户位置为(a i , b i )(i =1,2,...,m )已知，而供应中心的位置是(x 1, x 2)；假设运输线路不受道路影响，只考虑直线距离，则可建立求总距离最短的数学模型为：()()∑=−+−=m i i i b x a x x x f 1222121),(min 其中：c ——运价(元/吨公里)；w i ——第i 个用户的需求量.()()∑=−+−=m i i i i b x a x w c x x f 1222121),(min 若进一步考虑各单位的用量w i 不同，而运价c 按距离计算，则可建立求总总费用最小的数学模型为：“定位问题”——厂址选择等引例2：在某些实际问题中，往往要求决策变量x 1, x 2, ..., x n 满足(或近似满足)某些平衡条件，它表现为要求x 1, x 2, ..., x n 满足方程组pj x x f n j ,,2,1 ,0),,(1L L ==即要求均方误差最小——最小二乘问题，包括线性最小二乘和非线性最小二乘问题，在数学建模中有非常重要的应用。

()∑=m j n x x f 121),,(min L 可转化为求解问题：“最小二乘问题”——解方程组无约束规划模型标准形式：()X f n R X ∈min ):(R R f n →其中()()[]X f X f n n RX R X −=∈∈ min max 转化：等高线1x 2x )(21x x f O 1x 2x 05310X 1X 2X )(0X f )(1X f >)(2X f >无约束规划的示意图多局部极小298.0=f 0=f298.0=f 唯一极小(全局极小)2122212121322)(x x x x x x x x f +−+−=⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂==∇22221222222212122122122)()(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 X H X f L M L M M L L 无约束规划的性质梯度ÆT n x X f x X f x X f X f ⎟⎟⎠⎞⎜⎜⎝⎛∂∂∂∂∂∂=∇)(,,)(,)()(21L Å列向量梯度的特点：1)函数f (X )在X 处增长最快的方向，负梯度方向是函数f (X )在X 处下降最快的方向；2)梯度的模是函数最快的变化率; 3)梯度为零是驻点，极值点是驻点，驻点不一定是极值点。

一、实验目的1、掌握MATLAB优化工具箱的基本用法，对不同算法进行初步分析、比较。

2、练习用无约束优化方法建立和求解实际问题的模型（包括最小二乘拟合）。

二、实验容项目一：某分子由25个原子组成，并且已经通过实验测量得到了其中某些原子队之间的距离（假设在平面结构上讨论），如表所示。

请你确定每个原子的位置关系。

原子对距离原子对距离原子对距离原子对距离(4,1) 0.9607 (5,4) 0.4758 (18,8) 0.8363 (15,13) 0.5725 (12,1) 0.4399 (12,4) 1.3402 (13,9) 0.3208 (19,13) 0.7660 (13,1) 0.8143 (24,4) 0.7006 (15,9) 0.1574 (15,14) 0.4394 (17,1) 1.3765 (8,6) 0.4945 (22,9) 1.2736 (16,14) 1.0952 (21,1) 1.2722 (13,6) 1.0559 (11,10) 0.5781 (20,16) 1.0422(5,2) 0.5294 (19,6) 0.6810 (13,10) 0.9254 (23,16) 1.8255 (16,2) 0.6144 (25,6) 0.3587 (19,10) 0.6401 (18,17) 1.4325 (17,2) 0.3766 (8,7) 0.3351 (20,10) 0.2467 (19,17) 1.0851 (25,2) 0.6893 (14,7) 0.2878 (22,10) 0.4727 (20,19) 0.4995(5,3) 0.9488 (16,7) 1.1346 (18,11) 1.3840 (23,19) 1.2277 (20,3) 0.8000 (20,7) 0.3870 (25,11) 0.4366 (24,19) 1.1271(21,3) 1.1090 (21,7) 0.7511 (15,12) 1.0307 (23,21) 0.7060 (24,3) 1.1432 (14,8) 0.4439 (17,12) 1.3904 (23,22) 0.8025问题分析：每个原子的位置都是未知的，在坐标系中只有相对的位置参数，不妨固定原子1的坐标为（0，0）。

无约束问题的数值解
无约束问题是指没有任何条件限制的数学问题。

对于这类问题，通常需要使用数值方法来求解。

常用的数值方法包括：
1. 精确法：通过暴力枚举的方式，找到问题的精确解。

这种方法适用于问题规模较小的情况，但是当问题规模增大时，计算量会变得非常大。

2. 迭代法：通过不断迭代，逼近问题的解。

这种方法适用于问题规模较大的情况，但是收敛速度可能会比较慢。

3. 随机化算法：通过引入随机性，来寻找问题的解。

这种方法适用于一些难以求解的问题，但是收敛速度也可能比较慢。

4. 神经网络方法：通过构建神经网络模型，来逼近问题的解。

这种方法适用于一些复杂的非线性问题，但是需要大量的训练数据和计算资源。

需要注意的是，对于不同的问题，选择不同的数值方法可能会产生不同的效果。

因此，在实际应用中，需要根据具体的问题特点和计算要求，选择适合的数值方法。

实验7无约束优化生医0 王言2010013212【实验目的】1．掌握用MATLAB优化工具箱的基本用法，对不同算法进行初步分析、比较。

2．练习用无约束优化方法建立和求解实际问题模型（包括最小二乘拟合）。

【实验内容】5. 某分子由25个原子组成，并且已经通过实验测量得到了其中某些原子对之间的距离（假设在平面结构上讨论），如表7.8所示。

请你确定每个原子的位置关系。

表7.8解：分析与建模： 不妨设第i 点坐标为，其中第一个点坐标为，问题即为求达到最小值的解，则问题转化为无约束优化：，其中：Matlab 代码如下：M 文件：function f=location(x,d);x(1)=0; x(26)=0;f(1)=(x(4))^2+(x(29))^2-d(1)^2; f(2)=(x(12))^2+(x(37))^2-d(2)^2; f(3)=(x(13))^2+(x(38))^2-d(3)^2; f(4)=(x(17))^2+(x(42))^2-d(4)^2; f(5)=(x(21))^2+(x(36))^2-d(5)^2;f(6)=(x(5)-x(2))^2+(x(30)-x(27))^2-d(6)^2; f(7)=(x(16)-x(2))^2+(x(41)-x(27))^2-d(7)^2; f(8)=(x(17)-x(2))^2+(x(42)-x(27))^2-d(8)^2; f(9)=(x(25)-x(2))^2+(x(50)-x(27))^2-d(9)^2; f(10)=(x(5)-x(3))^2+(x(30)-x(28))^2-d(10)^2; f(11)=(x(20)-x(3))^2+(x(45)-x(28))^2-d(11)^2; f(12)=(x(21)-x(3))^2+(x(46)-x(28))^2-d(12)^2; f(13)=(x(24)-x(3))^2+(x(49)-x(28))^2-d(13)^2;),(i i y x )0,0(),(11=y x ∑--+-ji ij j i j id y y x x,2222])()[(∑--+-ji ij j i j i d y y x x ,2222])()[(min ⎥⎦⎤⎢⎣⎡=252432252432y y y y x x x x xf(14)=(x(5)-x(4))^2+(x(30)-x(29))^2-d(14)^2;f(15)=(x(12)-x(4))^2+(x(37)-x(29))^2-d(15)^2;f(16)=(x(24)-x(4))^2+(x(49)-x(29))^2-d(16)^2;f(17)=(x(8)-x(6))^2+(x(33)-x(31))^2-d(17)^2;f(18)=(x(13)-x(6))^2+(x(38)-x(31))^2-d(18)^2;f(19)=(x(19)-x(6))^2+(x(44)-x(31))^2-d(19)^2;f(20)=(x(25)-x(6))^2+(x(50)-x(31))^2-d(20)^2;f(21)=(x(8)-x(7))^2+(x(33)-x(32))^2-d(21)^2;f(22)=(x(14)-x(7))^2+(x(39)-x(32))^2-d(22)^2;f(23)=(x(16)-x(7))^2+(x(41)-x(32))^2-d(23)^2;f(24)=(x(20)-x(7))^2+(x(45)-x(32))^2-d(24)^2;f(25)=(x(21)-x(7))^2+(x(46)-x(32))^2-d(25)^2;f(26)=(x(14)-x(8))^2+(x(39)-x(33))^2-d(26)^2;f(27)=(x(18)-x(8))^2+(x(43)-x(33))^2-d(27)^2;f(28)=(x(13)-x(9))^2+(x(38)-x(34))^2-d(28)^2;f(29)=(x(15)-x(9))^2+(x(40)-x(34))^2-d(29)^2;f(30)=(x(22)-x(9))^2+(x(47)-x(34))^2-d(30)^2;f(31)=(x(11)-x(10))^2+(x(36)-x(35))^2-d(31)^2;f(32)=(x(13)-x(10))^2+(x(38)-x(35))^2-d(32)^2;f(33)=(x(19)-x(10))^2+(x(44)-x(35))^2-d(33)^2;f(34)=(x(20)-x(10))^2+(x(45)-x(35))^2-d(34)^2;f(35)=(x(22)-x(10))^2+(x(47)-x(35))^2-d(35)^2;f(36)=(x(18)-x(11))^2+(x(43)-x(36))^2-d(36)^2;f(37)=(x(25)-x(11))^2+(x(50)-x(36))^2-d(37)^2;f(38)=(x(15)-x(12))^2+(x(40)-x(37))^2-d(38)^2;f(39)=(x(17)-x(12))^2+(x(42)-x(37))^2-d(39)^2;f(40)=(x(15)-x(13))^2+(x(40)-x(38))^2-d(40)^2;f(41)=(x(19)-x(13))^2+(x(44)-x(38))^2-d(41)^2;f(42)=(x(15)-x(14))^2+(x(40)-x(39))^2-d(42)^2;f(43)=(x(16)-x(14))^2+(x(41)-x(39))^2-d(43)^2;f(44)=(x(20)-x(16))^2+(x(45)-x(41))^2-d(44)^2;f(45)=(x(23)-x(16))^2+(x(48)-x(41))^2-d(45)^2;f(46)=(x(18)-x(17))^2+(x(43)-x(42))^2-d(46)^2;f(47)=(x(19)-x(17))^2+(x(44)-x(42))^2-d(47)^2;f(48)=(x(20)-x(19))^2+(x(45)-x(44))^2-d(48)^2;f(49)=(x(23)-x(19))^2+(x(48)-x(44))^2-d(49)^2;f(50)=(x(24)-x(19))^2+(x(49)-x(44))^2-d(50)^2;f(51)=(x(23)-x(21))^2+(x(48)-x(46))^2-d(51)^2;f(52)=(x(23)-x(22))^2+(x(48)-x(47))^2-d(52)^2;end主文件：d=[0.9607 0.4399 0.8143 1.3765 1.2722 0.5294 0.6144 0.3766 0.6893 0.94880.8000 1.1090 1.1432 0.4758 1.3402 0.7006 0.4945 1.0559 0.6810 0.3587 0.3351 0.2878 1.1346 0.3870 0.7511 0.4439 0.8363 0.3208 0.1574 1.2736 0.5781 0.92540.6401 0.2467 0.4727 1.3840 0.4366 1.0307 1.3904 0.5725 0.7660 0.4394 1.09521.0422 1.8255 1.4325 1.0851 0.4995 1.2277 1.1271 0.7060 0.8052]';x0=[zeros(1,1),ones(1,24),zeros(1,1),ones(1,24)];[x,norm1]=lsqnonlin(@location,x0,[],[],[],d);xnorm1运行结果x =Columns 1 through 100 0.1925 1.3539 0.8210 0.6910 1.11740.7470 0.9049 0.4348 1.0297Columns 11 through 200.4536 -0.4604 0.7045 0.5812 0.3521 0.12710.4361 1.5726 1.3993 0.9407Columns 21 through 300.2642 1.5103 0.9707 0.3404 0.8626 00.9330 1.6449 0.5483 0.9793Columns 31 through 401.3858 1.2540 0.9459 0.6425 1.2754 1.24390.2204 0.4145 1.2862 0.8651Columns 41 through 500.3007 1.2927 0.4275 0.7643 0.9601 1.83231.3226 1.9180 1.0981 1.1166norm1 =0.0316改变初值：x0=[zeros(1,2),ones(1,22),zeros(1,2),ones(1,22)];结果是：x =Columns 1 through 100 0.8285 0.5479 0.8712 0.8802 1.5054 0.7397 1.0346 0.0074 1.3647Columns 11 through 201.0327 -0.4290 0.4778 0.6123 0.1921 1.4165 0.6782 1.3906 1.2647 1.0951Columns 21 through 300.0732 1.0151 0.1085 0.7128 1.4644 1.00001.5112 0.0944 0.5051 0.9830Columns 31 through 400.8822 0.7628 0.6989 1.0033 0.7893 1.2701 0.3074 0.6494 0.9350 1.1299Columns 41 through 501.6768 1.1750 -0.0659 0.2455 0.6879 1.1010 0.3047 0.4028 1.2196 1.2407Columns 51 through 521.0000 1.0000norm1 =0.2330这一组norm1较大，因此第一组初值较好。