西南科技大学网络教育系列课程

1、5. 5. 优优 化化 设设 计计5.3 西南科技大学网络教育系列课程西南科技大学网络教育系列课程西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.1 确定搜索区间的方法进退法实际问题数学模型数值计算方法程序设计上机计算求出结果 数值解法数值解法：利用计算机通过反复迭代计：利用计算机通过反复迭代计算，求得实际问题的近似值。算，求得实际问题的近似值。西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.1 确定搜索区间的方法进退法 下降迭代算法中在搜索方向下降迭代算法中在搜索方向S(k)上寻求最优步上寻求最优步长长ak时通常采用一维搜索法。时通常采用一维搜索法。 一维搜索

2、法一维搜索法就是一元函数极小化的数值迭代就是一元函数极小化的数值迭代算法，其求解过程称算法，其求解过程称一维搜索一维搜索。 一维搜索问题指目标函数为一维搜索问题指目标函数为单变量的非线性单变量的非线性规划问题规划问题。又称线性搜索问题。其模型为：。又称线性搜索问题。其模型为：t为实数为实数(t)min0 t(t)minmax0 tt 或或一般一维搜索问题一般一维搜索问题有效一维搜索问题有效一维搜索问题西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.1 确定搜索区间的方法进退法 一维搜索问题的算法分类：一维搜索问题的算法分类： 1 1）精确一维搜索（最优一维搜索）精确一维搜索（最

3、优一维搜索） 2 2）非精确一维搜索（可接受一维搜索）非精确一维搜索（可接受一维搜索）1、进退法确定搜索区间的方法、进退法确定搜索区间的方法 在函数的任一单谷区间上必存在一个在函数的任一单谷区间上必存在一个极小点极小点，而且在极小点的而且在极小点的左侧左侧，函数呈，函数呈下降趋势下降趋势，在极小，在极小点的点的右侧函数呈上升趋势右侧函数呈上升趋势。 若已知方向若已知方向S(k)上的三点上的三点x1x2x3及其函数及其函数值值f(x1)、f(x2)和和f(x3)，便可通过比较三个函数值的，便可通过比较三个函数值的大小估计出极小点所在的位置，如图大小估计出极小点所在的位置，如图5.11所示。所示。

4、西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.1 确定搜索区间的方法进退法图图5.15.11 1 极小点的估计极小点的估计西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.1 确定搜索区间的方法进退法2、进退法的定义、进退法的定义 在某一方向上按一定方式逐次产生一些探测点，在某一方向上按一定方式逐次产生一些探测点，并比较这些探测点上函数值的大小，就可以找出函并比较这些探测点上函数值的大小，就可以找出函数值呈数值呈“大大-小小-大大”变化的三个相邻点，其中两端变化的三个相邻点，其中两端点所确定的闭区间必定包含着极小点，这样的区间点所确定的闭区间必定包含着极小点，这

5、样的区间称为称为初始区间，记作初始区间，记作a,b。这种寻找初始区间的方。这种寻找初始区间的方法称为法称为进退法进退法。 x* x1 x2 b西南科技大学网络教育系列课程西南科技大学网络教育系列课程 若对任意若对任意x1 ,x2, x1 (x*); 2) 若若x2 x* ，则，则(x*) 0.5西南科技大学网络教育系列课程西南科技大学网络教育系列课程1.4160 xx2x12)、第二轮：、第二轮：x2=1.146, x1=0.7082131. 0)(0611. 0)(21xxx2-0=1.1460.53)、第三轮：、第三轮：x1=0.438, x2=0.7082082. 0)(0611. 0)

6、(12xxb-x1=1.146-0.4380.51.8540 x x2x1西南科技大学网络教育系列课程西南科技大学网络教育系列课程4)、第四轮：、第四轮：x2=0.876, x1=0.7080798. 0)(0611. 0)(21xxb-x1=1.146-0.7080.5输出：输出：x*=x2=0.876为最优解，最优值为为最优解，最优值为-0.07980 1.416xx1x2西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.3 Newton法法0)()(),(min xfxfxf二次可微，其中考虑Newton法基本思想：法基本思想：用探索点用探索点xk处的二阶处的二阶Taylo

7、r展开式近似代替目展开式近似代替目标函数，以展开式的最小点为新的探索点。标函数，以展开式的最小点为新的探索点。2)(21)()()(kkkkkxxxfxxxfxfxg 展开式：:,0)(求导得的点的最小点即导数为xg)()(1kkkkxfxfxx 西南科技大学网络教育系列课程西南科技大学网络教育系列课程解题步骤：解题步骤：给定初始点给定初始点x1和精度和精度 是是是是停止，输出停止，输出x10)(1 xf是是否否停止，解题失败停止，解题失败)()(1112xfxfxx 计算否否停止，输出停止，输出x2否否 1xf12xx西南科技大学网络教育系列课程西南科技大学网络教育系列课程 5.3.4 二次

8、插值法二次插值法叫截断误差叫插值结点插值法插值条件使被插函数近似代替插值函数用简单函数望希只知离散数据求知存在实际中问题提出)()()(,)()(,)()(:).2 .1 .0( )(, ,)(:.1xPxfxRxxPxfxfxPnixfyxfyiiiii)( )(或多项式插值代数插值多项式函数或者三角插值三角函数通常取xP西南科技大学网络教育系列课程西南科技大学网络教育系列课程 二次插值法二次插值法又称又称抛物线法抛物线法，它是以目标函数，它是以目标函数的的二次插值函数的极小点二次插值函数的极小点作为新的中间插入点，作为新的中间插入点，进行区间缩小的一维搜索算法。进行区间缩小的一维搜索算法。

9、 用用f(x)在在2 或或3 个点的函数值或导数值，构造个点的函数值或导数值，构造2 次或次或3次多项式作为次多项式作为f(x)的近似值，以这多项式的近似值，以这多项式的极小点为新的迭代点。的极小点为新的迭代点。 3点点2次，次，2点点2次，次，4点点3次，次，3点点3次，次，2点点3次次等等 以以3点点2次为例：次为例： 取取x 1，x 2，x3，求出，求出f(x1)， f(x2)， f(x3) 5.3.4 二次插值法二次插值法西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.4 二次插值法 设二次插值多项式：设二次插值多项式： f(x) =a0+a1x +a2x2 f(x1)

10、 = a0+a1x1 +a2x12 f(x2 )= a0 +a1x2 +a2x22 f(x3) = a0 +a1x3 +a2x32 解得解得a1 a2 1332212131323212xxxxxxxfxxxfxxxfxxa 1332212221223221133221xxxxxxxfxxxfxxxfxxa212aaxp西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.4 二次插值法 13131xxxfxfc 21322212232213322113322121xfxxxfxxxfxxxfxxxfxxxfxxxp21315 . 0ccxxxp 32112122xxcxxxfxfc西

11、南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.4 二次插值法f2fp的新搜索区间的新搜索区间西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.4 二次插值法2、特点：、特点： 1）二次插值法的中间插入点包含了函数）二次插值法的中间插入点包含了函数在在三个点上的函数值信息三个点上的函数值信息，因此这样的插入点，因此这样的插入点比较接近函数的极小值。比较接近函数的极小值。 2）二次插值法以）二次插值法以两个中间插入点的距离两个中间插入点的距离充分小作为收敛准则充分小作为收敛准则，即当，即当 成立时，成立时，把把 作为此次一维搜索的极小点。作为此次一维搜索的极小点。 二

12、次插值法的计算程序如下图二次插值法的计算程序如下图:2xxppx西南科技大学网络教育系列课程西南科技大学网络教育系列课程西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.4 二次插值法 例例2.用用二次插值法二次插值法求函数求函数 的极的极小点，给定小点，给定 解：解：1）确定初始区间：）确定初始区间： 由于由于 ，应加大步长继续向前探测，应加大步长继续向前探测， 由于由于 ，可知初始区间已经找到，可知初始区间已经找到， 即即243)(3xxxf2 . 0, 1, 00hx2)(,01101xffxx1)(, 1102212xffhxx21ff 18)(, 23323xffhxx

13、32ff 2,0西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.4 二次插值法2）用二次插值法逼近极小点）用二次插值法逼近极小点 记此初始区间内的相邻三点及其函数值依次为：记此初始区间内的相邻三点及其函数值依次为： 将它们代入式，得插值函数的极小点，即新的将它们代入式，得插值函数的极小点，即新的插入点及其函数值：插入点及其函数值： 由于，由于， 故新区间故新区间18, 1, 2, 2, 1, 0321321fffxxx292. 0,555. 0ppfx22,xxffpp1 , 0,2xaba西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.4 二次插值法由于，由于

14、，故应继续作第二次插值计算。故应继续作第二次插值计算。在新的区间内，相邻三点及其函数值依次为：在新的区间内，相邻三点及其函数值依次为：将它们代入式，得将它们代入式，得由于，由于，新区间新区间2.0445.0555.012pxx1,292. 0, 2, 1,555. 0, 0321321fffxxx243. 0,607. 0ppfx22,xxffpp1 ,555. 0,2bxba西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.4 二次插值法由于，由于，故一维搜索到此结束，极小点和极小值为：故一维搜索到此结束，极小点和极小值为：2 . 0052. 0607. 0555. 02pxx

15、243. 0,607. 0*fxxp5. 5. 优优 化化 设设 计计5.4 西南科技大学网络教育系列课程西南科技大学网络教育系列课程西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4 多维优化方法是进行多变量优化设计的数值多维优化方法是进行多变量优化设计的数值迭代法。它包括了迭代法。它包括了无约束优化方法和约束优化方无约束优化方法和约束优化方法法两种。两种。1、无约束优化问题的一般形式：、无约束优化问题的一般形式： 求解设计变量：求解设计变量：X=x1,x2,xnT,XRn 满足目标函数满足目标函数minf(X)的无约束最优化解的无约束最优化解X*和和最优化函数最优化函数minf

16、 (X *)。2、无约束优化的分类、无约束优化的分类 根据根据搜索方向搜索方向的不同构成形式，可分类以下的不同构成形式，可分类以下两类：两类：西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4 1）导数法导数法：利用目标函数的一阶和二阶导：利用目标函数的一阶和二阶导数信息构成搜索方向的算法，称为导数法，如数信息构成搜索方向的算法，称为导数法，如梯梯度法和共轭梯度法度法和共轭梯度法。 注注：其收敛性和收敛速度都是比较好的。：其收敛性和收敛速度都是比较好的。 2）模式法模式法：通过几个已知点上函数值的比：通过几个已知点上函数值的比较构造搜索方向的算法。如较构造搜索方向的算法。如鲍威尔法

17、鲍威尔法。 对于对于较复杂的目标函数优化较复杂的目标函数优化是有利的。是有利的。3、约束优化方法、约束优化方法 minf(X) s.t. gu(X)0 (u=1,2,m) hv(X)=0 (v=1,2,pn)西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4 根据处理条件的不同，约束优化方法分为根据处理条件的不同，约束优化方法分为直直接法和间接法接法和间接法两类。两类。 直接法是指直接法是指在迭代过程中逐点考察约束，并在迭代过程中逐点考察约束，并使迭代点始终局限于可行域之内的算法。如使迭代点始终局限于可行域之内的算法。如可行可行方向法和复合法方向法和复合法。 间接法是指间接法是指把

18、约束条件引入目标函，将约束把约束条件引入目标函，将约束优化问题转化为无约束问题求解的算法。如优化问题转化为无约束问题求解的算法。如惩罚惩罚函数法函数法。西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4.1 梯度法1 定义定义 什么方向是函数下降最快的方向呢？答案是什么方向是函数下降最快的方向呢？答案是负梯度方向。负梯度方向。 梯度法又称梯度法又称最速下降法最速下降法，是无约束优化方，是无约束优化方法中间接法的一种。其基本原理：法中间接法的一种。其基本原理：是将一个多维是将一个多维无约束优化问题转化为一系列沿目标函数负梯度无约束优化问题转化为一系列沿目标函数负梯度方向进行一维搜索寻

19、优的一种方法方向进行一维搜索寻优的一种方法，即是在每一，即是在每一迭代点迭代点 ，选取搜索方向，选取搜索方向 为负梯度方向：为负梯度方向： )(kX)()()(kkXfS)(kS西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4.1 梯度法 再沿再沿 进行一维搜索，以确定步长因子进行一维搜索，以确定步长因子 ，找到新的设计点找到新的设计点 按照上述迭代公式进行若干次一维搜索，每按照上述迭代公式进行若干次一维搜索，每次迭代的初始点取上次迭代的终点，即可使迭代点次迭代的初始点取上次迭代的终点，即可使迭代点逐渐逼近目标函数的极小点。逐渐逼近目标函数的极小点。)()()1(kkkkSXX)

20、(kSk西南科技大学网络教育系列课程西南科技大学网络教育系列课程梯度法程序框图梯度法程序框图 西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4.1 梯度法2 梯度法的特点梯度法的特点 1）梯度法理论明确，程序简单，计算量和存储量）梯度法理论明确，程序简单，计算量和存储量较少，对初始点的要求不严格。较少，对初始点的要求不严格。 2）负梯度方向不是理想的搜索方向，梯度法也不）负梯度方向不是理想的搜索方向，梯度法也不是一种理想的方法，梯度法的是一种理想的方法，梯度法的收敛速度并不快收敛速度并不快。 这是因为最速下降方向仅仅是指某点的一个局部性这是因为最速下降方向仅仅是指某点的一个局部性

21、质，一旦离开这点，就不能保证仍是最速下降方向了。质，一旦离开这点，就不能保证仍是最速下降方向了。 3）梯度法的迭代全过程的搜索路线呈锯齿状。）梯度法的迭代全过程的搜索路线呈锯齿状。 由于梯度法的相邻两次搜索方向的正交性决定的，由于梯度法的相邻两次搜索方向的正交性决定的，如图如图5.14所示，故前几次迭代函数值下降较快，但以后所示，故前几次迭代函数值下降较快，但以后的迭代下降越来越慢。的迭代下降越来越慢。西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4.1 梯度法图图5.14 二维目标函数的梯度法搜索过程二维目标函数的梯度法搜索过程 西南科技大学网络教育系列课程西南科技大学网络教育

22、系列课程5.4.1 梯度法 所以，梯度法常与其它方法联合使用，即所以，梯度法常与其它方法联合使用，即在迭代的第一步或前几步使用，当接近极小点在迭代的第一步或前几步使用，当接近极小点时，改为用其它算法，以此加快收敛速度。时，改为用其它算法，以此加快收敛速度。 特点：特点：全局收敛，线性收敛，易产生扭摆全局收敛，线性收敛，易产生扭摆现象而造成早停现象而造成早停。西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4.1 梯度法例例1 用梯度法求下列无约束优化问题，已知用梯度法求下列无约束优化问题，已知函数函数X(0)=1 1T，0.1。 min 解：解：1）第一次迭代）第一次迭代 求求 令

23、令 则则 1212221422)(xxxxxXf ,42422)(2121xxxxXf24)() 0(Xf24)()0()0(XfS21412411) 0() 0() 0() 1 (SXX西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4.1 梯度法对这种简单的一元函数，可以直接用解析法对对这种简单的一元函数，可以直接用解析法对 求极小。令求极小。令 解得解得 因因 还应继续迭代计算。还应继续迭代计算。)()41 ( 4)21)(41 ( 2)21 ( 2)41 ()(22) 1 (Xf016)41 ( 4)21 ( 8)21 ( 8)41 ( 8)(,25.041,5 .02)1

24、(X5 . 5)() 1 (Xf,5)() 1 ( Xf西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4.1 梯度法 2)第二次迭代第二次迭代因因 解得解得 ,21)()1(Xf,21)1(S25 . 02215 . 02) 1 () 1 () 1 ()2(SXX)()2 ( 4)25 . 0)(2 ( 2)25 . 0 ( 2)2 ()(22) 2(Xf04)2 ( 4)25 . 0 ( 8)25 . 0 ( 8)2 ( 2)(, 5 . 0,5 . 15 . 2)2(X,75. 6)() 2(Xf,12)()2(Xf西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.

25、4.1 梯度法 因因 可知可知X(2)不是极小点，还应不是极小点，还应继续进行迭代。继续进行迭代。 最后得此问题的最优解为：最后得此问题的最优解为： ,5)()2( Xf8)(,24*XfXT西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4.2 共轭梯度法共轭方向的概念：共轭方向的概念： 设设H为一正定对称矩阵，若有一组非零向为一正定对称矩阵，若有一组非零向量量S1,S2,Sn满足满足 则称这组向量关于矩阵则称这组向量关于矩阵H共轭。共轭。 以正定二元二次函数为例。以正定二元二次函数为例。jiHSSjTi 0CXBAXXXfTT21)(21xxX西南科技大学网络教育系列课程西南科

26、技大学网络教育系列课程5.4.2 共轭梯度法 任选初始点任选初始点X(0)并沿某一下降方向并沿某一下降方向S(0)作一维作一维搜索，得搜索，得 由于梯度的迭代过程中，相邻的搜索方向由于梯度的迭代过程中，相邻的搜索方向相互垂直。可知相互垂直。可知 对函数对函数 f(X)求点求点X(1)的梯度的梯度 从点从点X(1)开始沿另一下降方向开始沿另一下降方向S(1)作一维搜作一维搜索，得索，得)0(0)0()1(SXXBHXXf)1()1()(0)()0()1(SXfT)1(1)1()2(SXXBHXXf)2()2()(西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4.2 共轭梯度法 欲使

27、欲使X(2)成为极小点，则必有成为极小点，则必有 将式将式 代入得代入得 展开得展开得 化简为化简为 左乘左乘 S(0)T，且且 得得0)()2()2(BHXXf)1(1)1()2(SXX0)()1(1)1(BSXH0)()1(1)1(HSBXH0)()1(1)1(HSXf0)1()0(HSST01西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4.2 共轭梯度法 这就是说，若要使第二个迭代点这就是说，若要使第二个迭代点X(2)成为该成为该正定二元二次函数的极小点，只要使两次一维正定二元二次函数的极小点，只要使两次一维搜索的搜索方向搜索的搜索方向S(0)和和S(1)关于函数的二阶导

28、数关于函数的二阶导数矩阵矩阵H为共轭就可以了。换句话说，如果能够为共轭就可以了。换句话说，如果能够找到以找到以H为共轭的两个向量，则无论从哪个初为共轭的两个向量，则无论从哪个初始点出发，依次沿这两个共轭方向作一维搜索，始点出发，依次沿这两个共轭方向作一维搜索，经两次迭代即可达到此正定二元二次函数的极经两次迭代即可达到此正定二元二次函数的极小点小点。西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4.2 共轭梯度法 对于一般函数，共轭方向具有以下性质：对于一般函数，共轭方向具有以下性质： （1）若）若 是以是以H共轭的共轭的n个向个向量，则对于正定二次函数从任意初始点出发，依量，则对

29、于正定二次函数从任意初始点出发，依次沿这次沿这n个方向进行一维搜索，最多个方向进行一维搜索，最多n次即可达到次即可达到极小点。极小点。 （2）从任意两个点）从任意两个点 和和 出发，分别沿出发，分别沿同一方向同一方向 进行一维搜索，得到两个一维极小进行一维搜索，得到两个一维极小点点 和和 ，则连接此两点构成的向量，则连接此两点构成的向量与原方向与原方向 关于该函数的二阶导数矩阵相共轭。关于该函数的二阶导数矩阵相共轭。niSi, 2 , 1)()0(1X)0(2X)0(S)1(1X)1(2X)1(2)1(1)1(XXS)0(S西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4.2 共

30、轭梯度法 共轭梯度方向的公式：共轭梯度方向的公式：)() 1() 1()(kkkkSXfS2)(2)1()()(kkkXfXf)()()1(kkkkSXX共轭梯度法程序见下图共轭梯度法程序见下图:西南科技大学网络教育系列课程西南科技大学网络教育系列课程图图5.14 共轭梯度法程序框图共轭梯度法程序框图 西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4.2 共轭梯度法例例2 用共轭梯度法求解例用共轭梯度法求解例1。解：解：1）第一次迭代沿负梯度方向搜索。）第一次迭代沿负梯度方向搜索。由例由例1得得X(0)=1 1T， 2）第二次迭代。求）第二次迭代。求 24)()0(Xf24)0(S,5 . 02) 1(X,21)() 1 ( Xf25. 0205)()(2)0(2)1(0XfXf5 . 122425. 021)()0(0) 1 () 1