mtlab无约束最优化问题

第16章无约束最优化问题 单变量最小化 基本数学原理 本节讨论只有一个变量时的最小化问题， 即一维搜索问题。 该问题在某些情况下可以直 接用于求解实际问题 ，但大多数情况下它是作为多变量最优化方法的基础，因为进行多变 量最优化要用到一维搜索算法。该问题的数学模型为 min f xx 1  x  x 2 式中,x,x 1x2为标量, f x为函数,返回标量 该问题的搜索过程可用下式表达 x k1  x k *d, 式中x k为本次迭代的值,d为搜索方向,为搜索方向上的步长参数.所以一维搜索就是要利用本 次迭代的信息来构造下次迭代的条件. 求解单变量最优化问题的方法有很多种。根据目标函数是否需要求导，可以分为两类， 即直接法和间接法。直接法不需要目标函数的导数，而间接法则需要用到目标函数的导数。 1.直接法 常用的一维直接法主要有消去法和近似法两种。 （1）消去法。该法利用单峰函数具有的消去性质进行反复迭代，逐渐消去不包含 极小 点的区间，缩小搜索区间，直到搜索区间缩小到给定的允许精度为止。一种典型的消去 法为黄金分割搜索法（GoIden Section Search ） 。黄金分割搜索法的基本思想是在单峰区 间内适当插入两点， 将区间分为 3 段， 然后通过比较这两点函数值的大小来确定是删去最左 段还是删去最右段，或是同时删去左、右两段保留中间段。重复该过程使区间无限缩小。插 入点的位置放在区间的黄金分割点及其对称点上， 所以该法称为黄金分割搜索法。 该法的优 点是算法简单，效率较高，稳定性好。 （2）多项式近似法。该法用于目标函数比较复杂的情况。此时寻找一个与它近似 的函 数来代替目标函数， 并用近似函数的极小点作为原函数极小点的近似。 常用的近似函数 为二次和三次多项式。 二次内插涉及到形如下式的二次函数数据拟合问题 m q   a2 b c 其中步长极值为 b . 2a 然后只要利用 3 个梯度或函数方程组就可以确定系数a 和 b,从而可以确定*。得 到该 值以后，进行搜索区间的收索。在缩短的新区间中，重新安排3 点求出下一次的近似极 小点*，如此迭代下去，直到满足终止准则为止。其迭代公式为 1 23 f x 1  31 f x 2  12 f x 3 x k1  2 23 f x 1  31 f x 2  12 f x 3 * 式中  ij  x i 2 x2 j , ij  x i  x j . 二次插值法的计算速度比黄金分割搜索法的快， 但是对于一些强烈扭曲或可能多峰 的 函数，该法的收敛速度会变得很慢，甚至失败。 2．间接法 间接法需要计算目标函数导数， 优点是计算速度很快。 常见的间接法包括牛顿切 线 法、对分法、割线法和三次插值多项式近似法等。 优化工具箱中用得较多的是三次插值 法。 三次插值的基本思想与二次插值的一致， 它是用 4 个已知点构造一个三次多项式 P3x，用它逼近函数fx，以P3x的极小点作为数fx的近似极小点。一般地讲， 三次插值法比二次插值法的收敛速度要快些，但每次迭代需要计算两个导数值。 三次插值法的迭代公式为 x k1  x 2  x 2  x 1 式中  1  f x 1  f x 2  3 2 1 f x 2  2  1 f x 2  f x 1  2 2 f x 1  f x 2 x 1  x 2 1 2 2   f x 1 f x 2 . 如果函数的导数容易求得， 一般来说首先考虑使用三次插值法， 因为它具有较高的效率。 对于只需要计算函数值的方法中， 二次插值法是一个很好的方法， 它的收敛速度较快，在极 小点所在区间较小时尤其如此。 黄金分割法则是一种十分稳定的方法， 并且计算简单。由于 以上原因， 优化工具箱中用得较多的方法是二次插值法、三次插值法以及二次、三次混合 插值法和黄金分割法。 有关函数介绍 1. fminbnd 函数 利用该函数找到固定区间内单变量函数最小值。调用格式为 x fminbnd fun,x1,x2 返回区间{x1,x2} 上 fun 参数描述的标量函数的最 小值x。 x fminbnd fun,x1,x2,options用 options 参数指定的优化参数进行最小 化。 x fminbnd fun,x1,x2,options,p1,p2,提供另外的参数 p1,p2 等，传 输给目标函数 fun。如果没有设置 options 选项，则令 options[ ]。 [x,fvaI]fminbnd 返回解 x 处目标函数的值。 [x,fvaI,exitfIag]fminbnd返回exitfIag 值描述 fminbnd 函数的退出 条件。 [x,fvaI,exitfIag,output]fminbnd 返回包含优化信息的结构输出。 与 fminbnd 函数相关的细节内容包含在fun, options, exitfIag 和 output 等参数中， 如表 16-1 所示。 表 16-1 参数描述表 参数描述 fun需要最小化的目标函数。 fun 函数需要输入标量参数x，返回 x 处的目标 函数标量值 f。可以将 fun 函数指定为命令行，如 xfminbndinlinesinx*x’x0 同样，fun 参数可以是一个包含函数名的字符串。对应的函数可以是 M 文件、内部函数或 MEX 文件。若 fun’ymfun’，则 M 文件函数必须有下面 的形式 functionfmyfunx f 计算 x 处的函数值 优化参数选项。可以用optimset 函数设置或该变这些参数的值. options 参数有以下几个选项 DispIay显示的水平。选择 ‘off’，不显示输出；选择 ‘iter’， 显示每一步迭代过程的输出；选择 ‘final’，显示最终结果 MaxFunEvaIs函数评价的最大允许次数 MaxIter最大允许次数 ToIXx处的终止容限 描述退出条件 0 表示目标函数收敛于解x处 0 表示已经达到函数评价或迭代的最大次数 xfminbndop16_1,0, x 即剪掉的正方形的边长为时水槽的容积最大。 水槽的最大容积计算 yop16_1x y 所以水槽的最大容积为 . 无约束非线性规划问题 基本数学原理 无约束最优化问题在实际应用中也比较常见， 如工程中常见的参数反演问题。 另外， 许多有约束最优化问题可以转化为无约束最优化问题进行求解。 求解无约束最优化问题的方法主要有两类，即 直接搜索法 Direct search 和梯度法 Gradient 。 直接搜索法适用于目标函数高度非线性， 没有导数或导数很难计算的情况。由于实 际工作中很多问题都是非线性的， 故直接搜索法不失为一种有效的解决办法。 常用的直接搜 索法为单纯