3.1 3.1 3.1 3.1 搜索算法结构搜索算法结构搜索算法结构搜索算法结构一、下降算法模型一、下降算法模型 考虑(考虑(fs)常用一种线性搜索的方式来求解:迭代中从常用一种线性搜索的方式来求解:迭代中从一点出发沿一点出发沿下降可行方向下降可行方向找一个新的、性找一个新的、性质有改善的点。质有改善的点。迭代计算:其中 为第 次迭代的搜索方向,为沿 搜索的最佳步长因子(通常也称作最佳步长)。min f(x)s.t.xS第三章第三章 常用的一维搜索方法常用的一维搜索方法可行方向:设可行方向:设 S,dRn,d0,若存在若存在 ,使,使 ,称,称d 为为 点的点的可行方向。可行方向。同时满足上述两个性质的方向称同时满足上述两个性质的方向称下降可行方向下降可行方向。下降方向下降方向 :设设 S,d Rn,d0,若存在若存在 ,使,使 ,称,称d 为为 在在 点的下降方向。点的下降方向。l模型算法模型算法线性搜索求线性搜索求 ,新点新点使使x(k+1)S初始初始x(1)S,k=1对对x(k)点选择下降点选择下降可行方向可行方向d(k)是否满足停机条件?是否满足停机条件?停停k=k+1yesn