6_2_非线性规划_一维搜索_0506.ppt

第六章 非线性规划 一维搜索 概述 当用迭代法求函数的极小点时，常常要用到一维搜索，即沿某一已知方向求目标函数的极小点。 一维搜索的方法很多，常用的有试探法、插值法和微积分中的求根法，下面我们首先给出一维搜索算法的基本思想，然后对一些经典的算法进行探讨。 一维搜索的基本思想 一维搜索的基本方法 一维搜索的实施步骤 确定搜索区间 一维搜索的实施步骤 确定搜索区间 一维搜索的实施步骤 确定搜索区间 一维搜索的实施步骤 确定搜索区间的算法图示 一维搜索的实施步骤 逐步缩小搜索区间 试探法——黄金分割法 算法概述 0.618法又称黄金分割法，它是一种等比例缩短区间的直接搜索方法 其基本思想是通过比较单峰区间内两点的函数值，不断舍弃单峰区间的左端或右端的一部分，使区间按固定区间缩小率逐步缩小，直到极小点所在区间缩小到给定的误差范围内而得到近似最优解 由于前面的内容已经涉及了如何逐步缩小搜索区间，那么本方法的关键就是如何保证区间缩小率不变。 试探法——黄金分割法 算法分析 试探法——黄金分割法 算法分析 试探法——黄金分割法 算法流程 试探法——黄金分割法 算法流程图 插值法——牛顿法 黄金分割法的局限性 对于0.618法，对于所计算的各个探索点上的函数值，仅仅用来比较其大小，而在各试探点的具体函数值等这些非常有用的信息却没有被利用，因此算法收敛速度都较慢，为了充分利用有用的信息，我们有插值法或称为多项式逼近法。 插值法的基本思想 插值法——牛顿法 插值法的常用工具 多项式是函数逼近最常用的一种工具，在搜索区间内利用若干探索点处的函数值来构造低次多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小点的近似值。在这里介绍两种用二次多项式函数逼近原函数的方法。一种方法是牛顿法，它是利用一点的函数值、一阶导数值和二阶导数值来构造二次函数的。另一种方法是抛物线法，它是利用三个点的函数值来构造二次函数的。在这里，我们只重点介绍牛顿法。然后在下一小节简要介绍一下抛物线法的迭代公式。 插值法——牛顿法 牛顿法算法思想 插值法——牛顿法 牛顿法算法分析 插值法——牛顿法 牛顿法算法流程 插值法——牛顿法 牛顿法算法示意图 插值法——牛顿法 牛顿法的优缺点 抛物线法 抛物线法 当函数具有比较好的解析性质时，牛顿法与抛物线法通常比0.618法的效果更好 一维搜索的MATLAB求解 求解函数 一维搜索的MATLAB求解 函数概要 fminbnd函数可以计算一元函数最小值优化问题，它用于求解一维设计变量在固定区间内的目标函数的最小值，亦即最优化问题的约束条件只有设计变量的上下界。其求解的算法是我们在前面小结中重点讲述的基于黄金分割法和抛物线插值法。 在使用fminbnd进行优化的过程中，除非x1和x2十分接近，否则算法将不会在区间的端点评价目标函数，因而设计变量的限制条件需要指定为开区间(x1,x2)，如果目标函数的最小值恰好在x1处或者x2处取得，fminbnd将返回该区间的一个内点，且其与端点x1或者x2的距离不超过2TolX，其中TolX为最优解x处的误差限。 一维搜索的MATLAB求解 输入参数和输出参数 一维搜索的MATLAB求解 一维搜索的MATLAB求解 控制参数设置 一维搜索的MATLAB求解 命令详解 x = fminbnd(fun,x1,x2) 返回标量函数fun在满足x1<x<x2条件下取最小值时设计变量x的值。 x = fminbnd(fun,x1,x2,options) 在求解问题的同时用options指定的优化参数进行目标函数的最小化 [x,fval] = fminbnd(...) 返回最优解x处的目标函数值fval。 [x,fval,exitflag] = fminbnd(...) 在优化计算结束之时返回exitflag值，描述函数计算的退出条件 [x,fval,exitflag,output] = fminbnd(...) 在优化计算结束之时返回返回结构变量output 命令分析 fminbnd只能解决设计变量为实变量的最优化问题，所求解最优化问题的目标函数必须是连续的，且fminbnd给出的可能只是目标函数的局部最优解。 当最优化问题的解位于区间边界附近时，fminbnd算法可能收敛的很慢，此时使用fmincon函数求解问题时的计算速度更快，计算精度更高，fmincon的用法我们将在之后讲解。 一维搜索的MATLAB求解 例1 求解一维搜索问题 [x,fval,exitflag,output] = fminbnd(@sin,