最速下降法课件

4.1非线性规划数学模型4.2凸函数和凸规划4.3一维搜索4.4无约束优化问题的解法第四章无约束最优化问题

第四节无约束优化问题的解法最速下降法Newton法拟Newton法共轭梯度法

第四章无约束最优化问题

一.最速下降法收敛性问题的基本概念最速下降法的迭代原理最速下降法的迭代步骤最速下降法的举例最速下降法的收敛结论

无约束问题4-41.收敛性问题的基本概念定义4-9若序列，对于，存在正整数当时，有，即则称收敛于，记为无约束问题4-4定义4-101.收敛性问题的基本概念若收敛于，且满足则p称为收敛于的阶。当p=1时，称为一阶收敛；当p=2时，称为二阶收敛；当时，称为超线性收敛；无约束问题4-4当时，当p=2

时，同阶无穷小若收敛于，且满足则p称为收敛于的阶。1.收敛性问题的基本概念定义4-10无约束问题4-4当时，当p=1

时，同阶无穷小若收敛于，且满足则p称为收敛于的阶。1.收敛性问题的基本概念定义4-10无约束问题4-4定义4-101.收敛性问题的基本概念若收敛于，且满足则p称为收敛于的阶。当p=1时，称为一阶收敛；当p=2时，称为二阶收敛；当时，称为超线性收敛；无约束问题4-4最速下降法Newton法拟Newton法定义4-12若某算法对于任意正定二次目标函数,从任意初始点出发,都能经过有限次迭代达到其极小点,则该算法称为具有二次终止性的算法或二次收敛算法.1.收敛性问题的基本概念结论：当Q为正定阵时，称f(X)为正定二次函数。正定二次函数有唯一全局极小点：无约束问题4-4一.最速下降法收敛性问题的基本概念最速下降法的迭代原理最速下降法的迭代步骤最速下降法的举例最速下降法的收敛结论

无约束问题4-4是X(k)处函数值下降最快的方向。当时，p(k)是f(X)在X(k)处的下降方向。函数f(X)在X(k)处的负梯度方向梯度的性质：2.迭代原理证明：结论：一元函数泰勒公式：无约束问题4-42.迭代原理最优步长无约束问题4-4最速下降法迭代原理：一维搜索找极小点：1)确定[0,1],精度0.12)用0.618法得到

040.53184无约束问题4-4最速下降法迭代原理：

无约束问题4-42.迭代原理最优步长最优步长无约束问题4-4线性收敛2.迭代原理最优步长最优步长得到一个点列：可以证明：无约束问题4-42.迭代原理证明：无约束问题4-4一.最速下降法收敛性问题的基本概念最速下降法的迭代原理最速下降法的迭代步骤最速下降法的举例最速下降法的收敛结论

无约束问题4-4无约束问题4-43.迭代步骤3.迭代步骤注释：(一阶必要条件)10停机准则：设连续(即f(X)连续可微)无约束问题4-4注释：3.迭代步骤一维搜索最优解的梯度与搜索方向正交20结论：证明：无约束问题4-4注释：最速下降法的任何两个相邻搜索方向正交(垂直)3.迭代步骤30结论：无约束问题4-4注释：3.迭代步骤40将一维搜索用于正定二次函数：则可以得到的表达式：无约束问题4-4证明：3.迭代步骤40将一维搜索用于正定二次函数：则可以得到的表达式：注释：该公式具有普遍性无约束问题4-4注释：3.迭代步骤40将一维搜索用于正定二次函数：则可以得到的表达式：无约束问题4-4注释：3.迭代步骤50将最速下降法用于正定二次函数：则可以得到的表达式：无约束问题4-4注释：3.迭代步骤50最速下降法，Newton法，拟Newton法，共轭梯度法的区别就是搜索方向p(k)取得不同。无约束问题4-4一.最速下降法收敛性问题的基本概念最速下降法的迭代原理最速下降法的迭代步骤最速下降法的举例最速下降法的收敛结论

无约束问题4-44.举例例4-10解：用最速下降法求的极小点，迭代两次。无约束问题4-44.举例例4-10解：用最速下降法求的极小点，迭代两次。无约束问题4-4解：1无约束问题4-4解：1无约束问题4-4解：2无约束问题4-4解：3（太大）继续迭代。最速下降法收敛速度很慢。注释：无约束问题4-4例4-10注释：本例的计算结果如图4-14(P156).迭代点在向极小点靠近的过程中形成一条锯齿折线,这种现象称为锯齿现象.这是由于最速下降法的任何两个相邻搜索方向正交.因此,从直观上可以看到,在远离极小点的地方,每次迭代可使目标函数值有较大的下降,但越接近极小点,由于锯齿现象,函数值下降速度显著变慢.优点：计算简单,存储量小.缺点：由于锯齿现象,迭代后期收敛速度变慢.4.举例用最速下降法求的极小点，迭代两次。无约束问题4-4一.最速下降法收敛性问题的基本概念最速下降法的迭代原理最速下降法的迭代步骤最速下降法的举例最速下降法的收敛结论

无约束问题4-45.最速下降法的收敛结论