第三章 无约束最优化方法 本章内容及教学安排 第一节 概述
第二节 迭代终止原则
第三节 常用的一维搜索方法 第四节 梯度法 第五节 牛顿法 第六节 共轭方向法 第七节 变尺度法 第八节 坐标轮换法 第九节 鲍威尔方法
第一节 概述
优化问题可分为
无约束优化问题 有约束优化问题
无约束最优化问题求解基于古典极值理论的一种数值迭代方法，主要用来求解非线性规划问题 迭代法的基本思想：
所以迭代法要解决三个问题 1、如何选择搜索方向 2、如何确定步长
3、如何确定最优点（终止迭代） 第二节 迭代终止准则 1）XK?1?XK??
?2?XK?1?XK???（XK?1i?XKi）??i?1?f(XK?1)?fX(K?)?n1/2??
2）
f(XK?1)?fX(K) or ??f(XK)3）?f(X(K?1))??
第三节 常用的一维搜索方法
本节主要解决的是如何确定最优步长的问题。
从初始点X(0)出发，以一定的步长沿某一个方向，可以找到一个新的迭代点，其公式如下：
X(1)?X(0)??0S0X(2)?X(1)??1S1 X(K?1)?X(K)??kSk现在假设SK已经确定，需要确定的是步长?k，就把求多维目标函数的极小值这个多维算过程中，当起步点和方向问题，变成求一个变量即步长的最优值的一维问题了。即
minf(X(K?1))?minf(X(K)??kSk)?minf(?K)
由此可见，最佳步长?K*由一维搜索方法来确定 求?k*，使得f(?(K))?f(X(K)??(K)S(K))?min 一、一维搜索区间的确定
区间[a,b]应满足
f(a)?f(?*)?f(b)
a??*?b
进退法确定搜索区间 区间的特点：两边翘。 方法的思想；
1）先明确函数在某一初始点的走势，是上升还是下降，若是下降，则最小点在该点的右边，若是上升，则最小点在函数的左边。
2）根据最小点在该初始点的位置，确定搜索的方向：上升则后退，下降则前进
3）只到函数的走势出现逆转，将最小值包含在区间中。
具体算法
1)给定初始点x0和初始步长h
2）从任意点x0出发，以x1?x0，x2?x1?h计算f(x1)和f(x2)
3）比较f(x1)和f(x2)，若f(x1)?f(x2)（F1>F2），函数下降，转（4）(5)做前进算法；若f(x1)?f(x2)（F1 （4）当f(x1)?f(x2)时（前进），极小点在x1点的右方，应加大步长作前进运算。取h?2h，计算x3?x2?h和f(x3)?f(x3)； (5)比较F2和F3。①当F3＞F2时，则满足F1＞F2＜F3，即x1，x2，x3三点函数值形成“高一低一高”的情况，函数极小点必在区间[x1，x3]内。令a＝x1，b＝x3，初始搜索区间[a,b]确定；②当F3 （6）当f(x1)?f(x2)（后退），由图3—4(b)知极小点在F1的左方，应作后退运算。取h??h/4，作符号置换，Z＝x1，x1＝x2，x2=x3及W＝F1、F1＝F2，F1＝W。取x3?x2?h；计算F3?f(x3)。 (7) 比较F2和F3。①当F3＞F2时，函数极值点在区间[x3，x1]内。令a＝x3，b＝x1，输出初始搜索区间[a,b]；②当F3 （注意：（6），（7）为（后退算法）） 进退算法确定单峰区间的计算框图 进退算法确定单峰区间的计算框图如图3—5所示。