直线搜索问题课件

条件条件：已知：已知 和可行下降方向和可行下降方向精确搜索精确搜索：求解单变量优化问题：求解单变量优化问题非精确搜索非精确搜索：找到一个：找到一个 满足满足由于由于 是下降方向，所以是下降方向，所以精确搜索的基本途经精确搜索的基本途经2）逐步压缩区间）逐步压缩区间1）确定初始区间）确定初始区间用试探法确定一个单谷区间用试探法确定一个单谷区间可用步长加倍或减倍的方法可用步长加倍或减倍的方法按照一定规则在上述区间内选点，通过计算按照一定规则在上述区间内选点，通过计算并比较这些点上的函数值逐步缩小包含局部并比较这些点上的函数值逐步缩小包含局部最优解的区间只至区间长度小于给定阈值最优解的区间只至区间长度小于给定阈值区间压缩原理区间压缩原理已知闭区间已知闭区间 是单谷区间，在其内部任取两点是单谷区间，在其内部任取两点 ，计算，计算 ，如果，如果 ，局，局部最优解在区间部最优解在区间 ，否则局部最优解在区间，否则局部最优解在区间 ，两种情况均能压缩区间，两种情况均能压缩区间第一种情况第一种情况第二种情况第二种情况每计算一个函数值能将区间压缩一个固定比值每计算一个函数值能将区间压缩一个固定比值为实现上述想法，必须为实现上述想法，必须精确搜索的精确搜索的0.618 法的原理法的原理基本想法：基本想法：满足第四个方程满足第四个方程在单谷区间在单谷区间 搜索局部最优解的搜索局部最优解的0.618法法1）确定误差阈值）确定误差阈值 及满足及满足 的的2）令）令3）对于）对于 依次完成以下运算依次完成以下运算c）比较）比较 和和 的大小确定的大小确定a）令）令b）计算）计算 和和 中未知的数值中未知的数值4）取所求局部最优解为）取所求局部最优解为（只需算一个）（只需算一个）斐波那契（斐波那契（Fibonacci）法）法（最优选点方法）（最优选点方法）用用 表示某个区间长度，通过计算表示某个区间长度，通过计算 点函数值能点函数值能将该区间压缩为一个单位长度，但任何大于将该区间压缩为一个单位长度，但任何大于 的区的区间长度都不能保证做到这一点间长度都不能保证做到这一点由于不计算函数值和只计算一点的函数值都不能由于不计算函数值和只计算一点的函数值都不能压缩区间，所以压缩区间，所以当当 时，由于两个分点可以任意接近中点，如时，由于两个分点可以任意接近中点，如下面的下面的 和和 所示，所以能将两个单位的区间压所示，所以能将两个单位的区间压缩为一个单位的区间，即缩为一个单位的区间，即前三个数的关系前三个数的关系一般情况下，一般情况下，必须满足下图所示关系必须满足下图所示关系结论结论：（斐波那契数列）（斐波那契数列）如何确定分点数如何确定分点数？假设初始区间是假设初始区间是 ，容许误差是，容许误差是 将将 视为一个单位的长度，则在视为一个单位的长度，则在 中一共有中一共有个单位长度，只要取个单位长度，只要取 为满足为满足的最小整数，通过计算的最小整数，通过计算 个分点的函数值，一个分点的函数值，一定能将包含最优解的区间压缩为不大于一个单定能将包含最优解的区间压缩为不大于一个单位的长度，即小于或等于位的长度，即小于或等于在单谷区间在单谷区间 搜索局部最优解的斐波那契法搜索局部最优解的斐波那契法1）确定误差阈值）确定误差阈值 以及满足以及满足 的的2）令）令3）对于）对于 依次完成以下运算依次完成以下运算c）比较）比较 和和 的大小确定的大小确定a）令）令b）计算）计算 和和 中未知的数值中未知的数值4）取所求局部最优解为）取所求局部最优解为（只需算一个）（只需算一个）0.618法和斐波那契法的关系法和斐波那契法的关系由由可得可得在上面右式令在上面右式令 并定义并定义可得可得解二次方程得正数解解二次方程得正数解所以所以0.618法实际上就是用斐波那契法中分数数列法实际上就是用斐波那契法中分数数列的极限代替每个分数值所得到的方法的极限代替每个分数值所得到的方法 等价于等价于利用导数的精确搜索算法（区间对分法）利用导数的精确搜索算法（区间对分法）如右图，单谷区间如右图，单谷区间 一定一定满足满足 取取 ，若，若 ，将区间压缩为将区间压缩为 ，否则将，否则将区间压缩为区间压缩为 这种方法区间压缩比等于这种方法区间压缩比等于 ，比仅计算函数值的最，比仅计算函数值的最好方法斐波那契法好，实际效果取决于导数计算量好方法斐波那契法好，实际效果取决于导数计算量利用二阶导数的精确搜索算法（利用二阶导数的精确搜索算法（Newton法）法）如上左图，在如上左图，在 点用切线近似点用切线近似 ，求该切线的零点，求该切线的零点切线方程：切线方程：再在再在 点重复上述过程点重复上述过程如上所示如上所示单谷区间单谷区间一定收敛一定收敛Goldstein法原理法原理基本想法：基本想法：不能太小不能太小不能太大不能太大对于上图，合格的对于上图，合格的 属于区间属于区间 或或非精确搜索的非精确搜索的Goldstein法法令令 ，选定，选定 令令 ；若；若 ，停止；，停止；若若 ，令，令 ；另一种情况；另一种情况 令令令令 ，回到第二步迭代，回到第二步迭代 （压缩比（压缩比0.5）无约束优化问题无约束优化问题基本算法（基本算法（下降方向法下降方向法）：）：1）任取）任取 2）如果在）如果在 处找不到下降方向，停止，否则，确定处找不到下降方向，停止，否则，确定 处的下降方向处的下降方向3）直线搜索确定）直线搜索确定 满足满足 4）用）用 替换替换 ，回到，回到 2）继续迭代）继续迭代无约束优化问题无约束优化问题实现算法的关键：实现算法的关键：如何确定下降方向如何确定下降方向？梯度梯度Hesse矩阵矩阵给定方向的二阶泰勒展开给定方向的二阶泰勒展开下降方向的充分条件下降方向的充分条件 下降方向的必要条件下降方向的必要条件 最速下降方向最速下降方向负梯度方向负梯度方向注意：注意：采用不同的范数可得到不同的最速下降方向采用不同的范数可得到不同的最速下降方向如如（牛顿方向牛顿方向）负梯度方向的几何意义负梯度方向的几何意义的等位线法的等位线法负梯度方向负梯度方向下降方向下降方向下降方向下降方向切平面切平面负梯度方向和切平面垂直负梯度方向和切平面垂直梯度下降法梯度下降法1）任取）任取 ，设定充分小的正数，设定充分小的正数2）若）若 ，停止，否则令停止，否则令3）直线搜索确定）直线搜索确定 满足满足 4）用）用 替换替换 ，回到，回到 2）继续迭代）继续迭代精确搜索得到的点和搜索方向之间的关系精确搜索得到的点和搜索方向之间的关系设设 是在是在 处沿下降方向处沿下降方向 进行精确搜索所进行精确搜索所得到的点，即得到的点，即 ，其中，其中 是优化问题是优化问题由由可得可得即即所得到的点的梯度和所采用的搜索方向垂直所得到的点的梯度和所采用的搜索方向垂直的最优解，应有的最优解，应有负梯度方向的特点负梯度方向的特点即即沿负梯度方向精确搜索前进时，相邻两点的梯沿负梯度方向精确搜索前进时，相邻两点的梯度互相垂直度互相垂直设设 是在是在 处沿负梯度方向处沿负梯度方向 进行进行一维搜索能得到的最好的点，由前面的结果可知一维搜索能得到的最好的点，由前面的结果可知负梯度方向的缺陷负梯度方向的缺陷最优解最优解梯度下降法是沿锯齿状路线前进，接近最优解梯度下降法是沿锯齿状路线前进，接近最优解时一维搜索效率很低，前进速度很慢时一维搜索效率很低，前进速度很慢最优解最优解最优方向最优方向克服负梯度方向缺陷的途径克服负梯度方向缺陷的途径用适当的用适当的正定矩阵正定矩阵（尺度矩阵）乘负梯度方向，其（尺度矩阵）乘负梯度方向，其作用是对后者进行适当的旋转，以获得更好的方向作用是对后者进行适当的旋转，以获得更好的方向令令正定二次函数的最优方向正定二次函数的最优方向最优方向：最优方向：正定二次函数的牛顿方向正定二次函数的牛顿方向1）任取）任取 ，设定充分小的正数，设定充分小的正数2）若）若 ，停止，否则令，停止，否则令3）直线搜索确定）直线搜索确定 满足满足 4）用）用 替换替换 ，回到，回到 2）继续迭代）继续迭代阻尼牛顿法（广义牛顿法）阻尼牛顿法（广义牛顿法）阻尼牛顿法的缺陷阻尼牛顿法的缺陷1）每步迭代要计算）每步迭代要计算 ，计算量大，计算量大2）可能不存在可能不存在3）可能不正定，可能不正定，不是下降方向不是下降方向共轭方向法原理之一共轭方向法原理之一共轭方向定义：共轭方向定义：对称矩阵，对称矩阵，非零向量，非零向量，若若 ，称，称 为为 共轭方向共轭方向共轭方向线性无关性（定理共轭方向线性无关性（定理4.4.5，121页）页）若若 互为互为 的共轭方向，则它们线性无关的共轭方向，则它们线性无关理由：理由：共轭方向法原理之二共轭方向法原理之二共轭方向二次函数有限终止性（定理共轭方向二次函数有限终止性（定理4.4.6，121页）页）结论：结论：条件：条件：，为为 的共轭方向的共轭方向 是任意的出发点是任意的出发点 由下述直线搜索依次确定由下述直线搜索依次确定 理由：理由：共轭方向法原理之三共轭方向法原理之三用用Gram-Schmidt 正交化方法顺序生成正交化方法顺序生成 共轭方向共轭方向 利用利用 共轭性确定下面方程组中所有待定系数共轭性确定下面方程组中所有待定系数例如：例如：解前面方程组最终可得解前面方程组最终可得其中其中为了应用于一般性的非线性函数，需要消除为了应用于一般性的非线性函数，需要消除 消除消除 的基本途经：的基本途经：由于由于 ，上式已经可以应用于一般性函数，再利，上式已经可以应用于一般性函数，再利用梯度和共轭方向的关系，可进一步简化系数表达式用梯度和共轭方向的关系，可进一步简化系数表达式（共轭方向法原理之二的理由）（共轭方向法原理之二的理由）共轭梯度法（共轭梯度法（Fletcher-Reeves）1）任取）任取 ，令，令2）如果）如果 ，停止计算，停止计算3）如果）如果 等于等于0或整数，令或整数，令5）用）用 替换替换 ，回到，回到2）继续迭代）继续迭代4）进行精确搜索获得）进行精确搜索获得否则令否则令 ，其中，其中共轭梯度法（共轭梯度法（Polak-Ribiere）1）任取）任取 ，令，令2）如果）如果 ，停止计算，停止计算3）如果）如果 等于等于0或整数，令或整数，令5）用）用 替换替换 ，回到，回到2）继续迭代）继续迭代4）进行精确搜索获得）进行精确搜索获得否则令否则令 ，其中，其中共轭梯度法（共轭梯度法（Beale-Sorenson）1）任取）任取 ，令，令2）如果）如果 ，停止计算，停止计算3）如果）如果 等于等于0或整数，令或整数，令5）用）用 替换替换 ，回到，回到2）继续迭代）继续迭代4）进行精确搜索获得）进行精确搜索获得否则令否则令 ，其中，其中关于共轭梯度法的结论关于共轭梯度法的结论1）共轭梯度法是下降算法）共轭梯度法是下降算法如果从相同的初始点出发，三种共轭梯度法前进如果从相同的初始点出发，三种共轭梯度法前进的轨迹完全相同，即每一步一维搜索得到的点均的轨迹完全相同，即每一步一维搜索得到的点均相同，并且，经过相同，并且，经过 次精确的一维搜索后一定找次精确的一维搜索后一定找到最优解，即到最优解，即意义：对一般非线性函数在最优解附近快速收敛意义：对一般非线性函数在最优解附近快速收敛2）对于正定二次目标函数）对于正定二次目标函数ACBACBCABACB三种基于梯度的搜索方向的比较三种基于梯度的搜索方向的比较计算量计算量效率效率鲁棒性鲁棒性解附近解附近远离解远离解负梯度负梯度共轭梯度共轭梯度牛顿方向牛顿方向