无约束优化算法--最速下降法.docx

无约束优化算法无约束优化算法问题，是指优化问题的可行集为，无约束的标准形式为：1. 最优性条件（1） 极小值点的一阶必要条件设为连续可微函数，如果为局部极小值点，则为驻点，即梯度。（2） 极小值的二阶必要条件设为二阶连续可微函数，如果为局部极小值点，则为驻点，即梯度，二阶 半正定。（3） 极小值点的二阶充分条件设为二阶连续可微函数，如果梯度，二阶 正定，则为的局部极小值点，。以上三个定理为搜索最优点以及判断一个点是否为最优点的基本依据。经典的优化算法的停止条件为，例如在程序中，即在导数范数小于某特定误差限时停止。误差限较大，则算法迭代次数减少，计算时间缩短，但解得质量降低；误差限较小，则算法迭代次数增加，计算时间增加，但解的质量提高；误差限一般为，可以根据实际情况设定合适的误差限。当然，还有极小值点的二阶必要条件与极小值点的二阶充分条件，对的判断，由于目标函数比较复杂，二阶导数矩阵的计算量极大，所以一般算法都在迭代过程中对进行修正，得到，在修正的过程中始终保持的正定性，以此方法解决极小值点的二阶条件问题。2. 最速下降法2.1 算法原理最速下降法是早期的优化算法，其理论根据函数的一阶泰勒展开：由得到根据下降要求故实际中要求根据上式选取合适的，得。最速下降法取。由于近似的有：取，则由知：最速下降法有全局收敛性，并且是线性收敛的，算法比较简单。一般来说，在实际计算中，最速下降法在开始迭代时效果较好，有时能很快地找到最优解得附近，但是当局继续迭代时，常常发生扭摆现象，以致不能达到最优解。2.2 算法步骤给定控制误差。步骤1：取初始点，令步骤2：计算。步骤3：若，则，停止计算；否则，令，由一维搜索步长，使得步骤4：令，转步骤2。MATLAB中实现最速下降法的函数为，函数是求解无约束优化问题的主要函数，最速下降法仅仅是函数所使用的算法之一。语法：输入参数：目标函数，一般用M文件形式给出：优化算法初始迭代点：参数设置函数输出：最优点输出：最优点对应的函数值：函数结束信息：函数基本信息，包括迭代次数、目标函数最大计算次数、使用的算法名称、计算规模。：最优点的导数：最优点的二阶导数2.3 程序示例MATLAB函数使用方法：1. 目标函数程序与2. 参数设置（）：大规模计算模式 关闭：阵修正方式，采用最速下降法（不需要修正）：目标函数导数解析式，使用，不使用：最大目标函数计算次数，250次：显示迭代过程3. 函数计算：初始迭代点4. 计算结果 First-order Iteration Func-count f(x) Step-size optimality 0 1 267.62 1.23e+003 1 2 214.416 0.000813405 519 2 9 5.83639 0.00098493 13.4 3 15 5.78292 0.000567305 1.58 4 18 5.73127 0.0387979 12.9 5 24 5.68023 0.000583736 1.59 6 27 5.63081 0.0367599 12.5 7 33 5.5819 0.000600291 1.6 8 36 5.53444 0.0349482 12.1 9 42 5.48743 0.000617009 1.61 10 45 5.44173 0.0333245 11.7 11 51 5.39641 0.000633925 1.62 12 54 5.35228 0.0318587 11.3 13 60 5.30849 0.000651074 1.63 14 63 5.26579 0.0305271 11 15 69 5.22338 0.000668487 1.64 16 72 5.18197 0.0293106 10.7 17 78 5.14082 0.000686194 1.64 18 81 5.10059 0.0281937 10.4 19 87 5.06058 0.000704225 1.65 First-order Iteration Func-count f(x) Step-size optimality 20 90 5.02144 0.0271635 10.1 21 96 4.98249 0.000722609 1.66 22 99 4.94433 0.0262095 9.89 23 105 4.90635 0.000741376 1.67 24 108 4.86912 0.0253228 9.65 25 114 4.83204 0.000760554 1.68 26 117 4.79566 0.0244958 9.42 27 123 4.7594 0.000780174 1.69 28 126 4.72381 0.023722 9.2 29 132 4.68833 0.000800267 1.7 30 135 4.65347 0.022996 8.99 31 141 4.61871 0.000820866 1.7 32 144 4.58453 0.022313 8.79 33 150 4.55043 0.000842002 1.71 34 153 4.5169 0.0216689 8.6 35 159 4.48343 0.000863711 1.72 36 162 4.45049 0.0210601 8.42 37 168 4.4176 0.000886029 1.73 38 171 4.38522 0.0204834 8.24 39 177 4.35289 0.000908995 1.74 First-order Iteration Func-count f(x) Step-size optimality 40 180 4.32103 0.019936 8.07 41 186 4.2892 0.000932649 1.75 42 189 4.25784 0.0194154 7.91 43 195 4.2265 0.000957033 1.76 44 198 4.19559 0.0189194 7.75 45 204 4.1647 0.000982194 1.77 46 207 4.13423 0.0184462 7.6 47 213 4.10377 0.00100818 1.78 48 216 4.07371 0.0179939 7.45 49 222 4.04364 0.00103505 1.79 50 225 4.01396 0.0175609 7.3 51 231 3.98427 0.00106284 1.8 52 234 3.95495 0.0171458 7.16 53 240 3.92561 0.00108886 1.8 54 243 3.89441 0.0181085 7.29 55 249 3.86321 0.00111764 1.82 Solver stopped prematurely.fminunc stopped because it exceeded the function evaluation limit,options.MaxFunEvals = 250 (the selected value).x = -0.9634 0.9372fval = 3.8632exitflag = 0output = iterations: 56 funcCount: 250 stepsize: 0.0011 firstorderopt: 1.8155 algorithm: medium-scale: Quasi-Newton line search message: 1x146 char从结果可见，在250次最大的目标函数计算次数内，算法没有到最优点1,1。将最大目标函数计算次数调高到2500次，则，计算结果：fminunc stopped because it exceeded the iteration limit,options.MaxIter = 400 (the default value).x = 0.9770 0.9542fval = 5.3808e-004exitflag = 0output = iterations: 401 funcCount: 1462 stepsize: 0.0142 firstorderopt: 0.0574 algorithm: medium-scale: Quasi-Newton line search message: 1x131 char从以上两个算法的结果可以看出，最速下降法对函数不是十分有效。当目标函数不可微分或者导数求解复杂时，可以无需提供目标函数的导函数的解析形式，MATLAB可以使用差分的方法求导（下降方向），对应的代码为计算结果：fminunc stopped because it exceeded the function evaluation limit,options.MaxFunEvals = 250 (the selected value).x = -1.2553 1.5640fval = 5.1002exitflag