《第3章优化设计--现代设计方法教学课件.ppt》由会员分享，可在线阅读，更多相关《第3章优化设计--现代设计方法教学课件.ppt（113页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、优化设计主要讲述内容一.一.优化设计概述优化设计概述二.二.优化数学模型优化数学模型三.三.优化设计的数学基础优化设计的数学基础四.四.一维搜索方法一维搜索方法五.五.无约束优化方法无约束优化方法六.六.约束优化方法约束优化方法第一节 优化设计概述v定义：在现代计算机广泛应用的基础上发展起来的一项新技术，是根据最优化原理和方法综合各方面的因素，以人机配合方式或“自动探索”方式，在计算机上进行的自动或半自动设计，以选出现有工程条件下的最佳设计方案的一种现代设计方法。v设计原则：最优设计v设计手段：电子计算机和计算程序v设计方法：最优化数学方法第一节 优化设计概述v机械优化设计在给定的载荷或环境条
2、件下，在对机械产品的性态、几何尺寸关系或其他因素的限制（约束）范围内，选取设计变量，建立目标函数并使其获得最优值的一种新的设计方法。设计变量、目标函数和约束条件三者在设计空间（以设计变量为坐标轴组成的实空间）的几何表示中构成设计问题。第一节 优化设计概述v优化设计与传统设计的比较 机械的传统设计方法机械的传统设计方法:基于手工劳动或简易计算工具基于手工劳动或简易计算工具,低效低效,一般只能获得一个可行的设计方案。一般只能获得一个可行的设计方案。机械的优化设计方法：机械的优化设计方法：基于计算机的应用，从实际基于计算机的应用，从实际问题中抽象出数学模型问题中抽象出数学模型;选择合适的优化方法求解
3、选择合适的优化方法求解数学模型。以人机配合或自动搜索方式进行，能从数学模型。以人机配合或自动搜索方式进行，能从“所有的所有的”可行方案中找出可行方案中找出“最优的最优的”设计方案。设计方案。第一节 优化设计方法概述v优化设计方法的发展是适于生产建设、计划管理、科学实验和战争的需要发展起来的。是适于生产建设、计划管理、科学实验和战争的需要发展起来的。1 1）二二十十世世纪纪三三十十年年代代.前前苏苏联联 根根据据生生产产组组织织和和计计划划管管理理的的需需要要提提出出线线性性规规划划问问题题.在在第第二二次次世世界界大大战战期期间间出出于于战战争争运运输输需需要要，提提出出线线性性规规划划问题的
4、解法；问题的解法；2 2）二二十十世世纪纪五五十十年年代代末末.H.W.Kuhn H.W.Kuhn&A.W.TuckerA.W.Tucker提提出出非非线线性性规规划划的的基基本本定定理理,奠奠定定了了非非线线性性规规划划的的理理论论基基础础.其求解方法在六十年代获得飞速发展其求解方法在六十年代获得飞速发展;第一节 优化设计概述3)3)二二十十世世纪纪六六十十年年代代.美美数数学学家家 R.J.Duffin R.J.Duffin 提提出出了了几几何何规规划划,可可把把高高度度非非线线性性的的问问题题转转化化为为具具有有线线性性约约束束的的问题来求解问题来求解,使计算大为简化使计算大为简化;4)
5、4)动态规划动态规划由由 R.Bellman R.Bellman 创立创立,可解与时间有关的最优可解与时间有关的最优化问题化问题;5)5)混合离散规划混合离散规划是二十世纪八十年代提出的是二十世纪八十年代提出的,目前仍在发目前仍在发展过程中。展过程中。v优化设计方法的发展第一节 优化设计概述*最最优优化化方方法法用用于于机机械械设设计计是是从从二二十十世世纪纪六六十十年年代代开开始始的的,较较早早的的成成果果主主要要反反映映在在机机构构的的优优化化设设计计方方面面,现现已已广广泛泛用用于机械零部件设计和机械系统的优化设计于机械零部件设计和机械系统的优化设计.v优化设计方法的发展第二节 优化数学
6、模型解解:设货箱的长、宽、高分别为设货箱的长、宽、高分别为 ，该问题可表示为该问题可表示为：求求 使使 达到最小达到最小 满足于满足于其解为其解为：该问题可表示为该问题可表示为求求使使满足于满足于解：由解：由 有有2.设计一曲柄摇杆机构设计一曲柄摇杆机构.已知已知:要求要求:使使 达到最大达到最大.第二节 优化数学模型二二.优化数学模型优化数学模型 完整的规格化的数学模型包含三要素：设计变量，目标函数，约束函数。由于数学模型构成不同，可以分为：无约束优化有约束优化线性规划非线性规划第二节 优化数学模型二二.优化数学模型优化数学模型 第二节 优化数学模型三三.设计变量设计变量 v在设计中需进行优
7、选的独立的待求参数；在设计中需进行优选的独立的待求参数；v)设计常量设计常量预先已给定的参数；预先已给定的参数；v)设计方案设计方案由设计常量和设计变量组成。由设计常量和设计变量组成。v)维维 数数设计变量的个数设计变量的个数n.通常通常,设计自由度设计自由度 ,越能获得理想的结果越能获得理想的结果,但求解难度但求解难度 .第二节 优化数学模型三三.设计变量设计变量 2)2)设计空间设计空间设计点的集合（设计点的集合（维实欧氏空间维实欧氏空间 ）。）。当设计点连续时当设计点连续时,为直线为直线;为平面为平面;为立体空间为立体空间;为超越空间为超越空间.第二节 优化数学模型四四.目标函数目标函数
8、 最最好好的的性性能能;最最小小的的重重量量;最最紧紧凑凑的的外外形形;最小的生产成本最小的生产成本;最大的经济效益等最大的经济效益等.-对极大化问题可取原函数的负值对极大化问题可取原函数的负值常处理为极小化形式常处理为极小化形式;单目标和多目标单目标和多目标；常用指标常用指标:数学模型中用来评价设计方案优劣的函数式（又称评价函数数学模型中用来评价设计方案优劣的函数式（又称评价函数):):第二节 优化数学模型四四.目标函数目标函数 在无约束极小点处，等值线一般收缩一个点在无约束极小点处，等值线一般收缩一个点。如如:目标函数的等值线目标函数的等值线（面面）能使目标函数取某一定值能使目标函数取某一
9、定值的所有设计点的集合的所有设计点的集合;第二节 优化数学模型五五.约束函数约束函数 对设计变量的取值范围加以限制的条件；对设计变量的取值范围加以限制的条件；为使问题有解，须使为使问题有解，须使(1)(1)按约束的数学形式分按约束的数学形式分 不等式约束：不等式约束：等式约束：等式约束：第二节 优化数学模型五五.约束函数约束函数 对设计变量的取值范围加以限制的条件；对设计变量的取值范围加以限制的条件；-由需满足的某种性能条件而导出的约束由需满足的某种性能条件而导出的约束(如如强度条件、刚度条件、曲柄存在条件等）。强度条件、刚度条件、曲柄存在条件等）。-对某个设计变量直接给出取值范围对某个设计变
10、量直接给出取值范围:边界约束边界约束性能约束性能约束(2)(2)按约束的作用分按约束的作用分*此外，也有将约束分成此外，也有将约束分成显约束显约束和和隐约束隐约束的。的。第二节 优化数学模型五五.约束函数约束函数 满足满足 的约束为起作用约束的约束为起作用约束,否则为否则为不起作用不起作用的约束的约束.(.(等式等式约束一定是起作用约束约束一定是起作用约束)起作用的约束与不起作用的约束起作用的约束与不起作用的约束约束边界上的可行点为边界点约束边界上的可行点为边界点,其余可行点为内点其余可行点为内点.)边界点边界点与与内点内点D D内的设计点为可行点内的设计点为可行点,否则为否则为不可行点不可行
11、点.*)可行点与不可行点可行点与不可行点第二节 优化数学模型六六.优化数学模型的求解优化数学模型的求解 优化设计工作包括两部分内容：优化设计工作包括两部分内容：将设计问题的物理模型转化为数学模型；将设计问题的物理模型转化为数学模型；用适当的最优化方法求解数学模型。用适当的最优化方法求解数学模型。1)1)解析法解析法-对简单的无约束问题及等式约束问题对简单的无约束问题及等式约束问题;2)2)图解法图解法-对简单的低维问题对简单的低维问题;3)3)数值迭代法数值迭代法-利用计算机按某种逻辑方式反复利用计算机按某种逻辑方式反复运算运算,是是最基本的最基本的方法。方法。第二节 优化数学模型六六.优化数
12、学模型的求解优化数学模型的求解 产生点列产生点列:使得使得:当满足终止迭代条件时当满足终止迭代条件时,便认为达到了最优点便认为达到了最优点.迭代过程迭代过程3)3)数值迭代法数值迭代法-利用计算机按某种利用计算机按某种逻辑方式反复运算逻辑方式反复运算,是是最基本的最基本的方法。方法。第二节 优化数学模型六六.优化数学模型的求解优化数学模型的求解 1.初始点初始点:2.搜索方向搜索方向:3.步长步长:4.是否终止迭代是否终止迭代.）需解决的问题需解决的问题：-后三个问题是每次迭代都要解决的问题后三个问题是每次迭代都要解决的问题第二节 优化数学模型六六.优化数学模型的求解优化数学模型的求解 ）算法
13、的收敛性、收敛速度和收敛准则算法的收敛性、收敛速度和收敛准则：算法的收敛性算法的收敛性第二节 优化数学模型六六.优化数学模型的求解优化数学模型的求解 ）算法的收敛性、收敛速度和收敛准则算法的收敛性、收敛速度和收敛准则：算法的收敛准则算法的收敛准则 点距准则点距准则第二节 优化数学模型六六.优化数学模型的求解优化数学模型的求解 ）算法的收敛性、收敛速度和收敛准则算法的收敛性、收敛速度和收敛准则：算法的收敛准则算法的收敛准则 目标函数下降量准则目标函数下降量准则相对下降量准则相对下降量准则绝对下降量准则绝对下降量准则第二节 优化数学模型六六.优化数学模型的求解优化数学模型的求解 ）算法的收敛性、收
14、敛速度和收敛准则算法的收敛性、收敛速度和收敛准则：算法的收敛准则算法的收敛准则 梯度准则梯度准则第二节 优化数学模型六六.优化数学模型的求解优化数学模型的求解 ）算法的收敛性、收敛速度和收敛准则算法的收敛性、收敛速度和收敛准则：算法的收敛准则算法的收敛准则 梯度准则梯度准则以上各准则单独使用时并非十分可靠，有时需几种准则联用。以上各准则单独使用时并非十分可靠，有时需几种准则联用。第三节 优化设计的数学基础一一.函数的泰勒展开式函数的泰勒展开式 一元函数的一元函数的Taylor Taylor 展开式展开式*在实际计算中在实际计算中,常取前三项常取前三项(二次函数二次函数)来近似原函数来近似原函数
15、:第三节 优化设计的数学基础一一.函数的泰勒展开式函数的泰勒展开式 多元函数的多元函数的Taylor Taylor 展开式展开式第三节 优化设计的数学基础一一.函数的泰勒展开式函数的泰勒展开式 多元函数的多元函数的Taylor Taylor 展开式展开式梯度梯度海赛海赛(Hessian)(Hessian)矩阵矩阵第三节 优化设计的数学基础故故解：解：例：将函数例：将函数 写成在点写成在点 处泰勒展开式的矩阵形式。处泰勒展开式的矩阵形式。第三节 优化设计的数学基础二二.二次其次矩阵二次其次矩阵 系数矩阵系数矩阵第三节 优化设计的数学基础二二.二次其次矩阵二次其次矩阵 *矩阵矩阵A A为正定的充要
16、条件为正定的充要条件-A A的各阶主子式均大于零的各阶主子式均大于零。如如 为正定，则必有为正定，则必有：第三节 优化设计的数学基础三三.方向导数方向导数 函数沿指定方向函数沿指定方向 的平均变化率的极限的平均变化率的极限。第三节 优化设计的数学基础三三.方向导数方向导数 第三节 优化设计的数学基础三三.方向导数方向导数 第三节 优化设计的数学基础三三.梯度梯度 令令单位矢量单位矢量于是于是第三节 优化设计的数学基础三三.梯度梯度 从上式可得出如下结论：从上式可得出如下结论：最优点最优点*最速下降只是局部性质最速下降只是局部性质.4 4）在与梯度垂直的方向（等值线的切）在与梯度垂直的方向（等值
17、线的切线方向）上，函数的变化率为零。线方向）上，函数的变化率为零。2 2）梯梯度度的的模模是是最最大大的的方方向向导导数数,负梯度方向是函数的最速下降方向；负梯度方向是函数的最速下降方向；1 1）方向导数是梯度在指定方向上的投影；）方向导数是梯度在指定方向上的投影；3 3）最最速速下下降降方方向向为为等等值值线线（面面）的法线方向；的法线方向；第三节 优化设计的数学基础四四.共轭方向共轭方向 *几何意义几何意义:经过线性变换经过线性变换A A后成了与后成了与 正交的向量正交的向量.例：例：设设A A为为n*nn*n阶正定对称矩阵阶正定对称矩阵，是两个是两个n n维维向量向量，若存在若存在则称则
18、称 对对A A共轭共轭。第三节 优化设计的数学基础四四.共轭方向共轭方向 *这种性质称为这种性质称为有限步收敛性有限步收敛性（亦称（亦称二次收敛性二次收敛性）（2 2）从任意选定的初始点出发，只要依次沿从任意选定的初始点出发，只要依次沿n n个共轭方向进个共轭方向进行一维搜索，一轮后便可达到行一维搜索，一轮后便可达到n n元正定二次函数的极小点。元正定二次函数的极小点。（1 1）若矢量系若矢量系 彼此对正定对称矩阵彼此对正定对称矩阵A A共轭共轭，则它们组则它们组成线性无关的矢量系成线性无关的矢量系；共轭方向的性质第三节 优化设计的数学基础四四.共轭方向共轭方向 正定二元二次函数的性质（1 1
19、）正正定定二二元元二二次次函函数数的的等等值值线线是是一一族族同同心心椭椭圆圆，其其中中心坐标就是该函数的极小点。心坐标就是该函数的极小点。（2 2）过同心椭圆族的中心作任意直线与椭圆族中任意两）过同心椭圆族的中心作任意直线与椭圆族中任意两椭圆相交，再过两交点所作相应椭圆的切线必相互平行。椭圆相交，再过两交点所作相应椭圆的切线必相互平行。逆命题逆命题:设两平行线与同心椭圆族中两椭圆分别相切于设两平行线与同心椭圆族中两椭圆分别相切于 点点,则过则过 的直线必通过椭圆族的中心的直线必通过椭圆族的中心。第三节 优化设计的数学基础四四.共轭方向共轭方向 构成共轭方向的方法设设 为平行于为平行于 的两条
20、直线的两条直线，则过这两直线则过这两直线上正定上正定 n n元二次元二次目标函数的极小点目标函数的极小点 的向量的向量 和和 对对HessionHession矩矩阵阵A A共轭共轭。再从再从 出发出发，沿沿 搜索得搜索得 2）取初始点取初始点 ，沿沿 方向搜索方向搜索 解解：1）例例：对于目标函数对于目标函数 ，给定给定 ，试试求出与求出与 共轭的方向共轭的方向 ，并求出目标函数的极小点并求出目标函数的极小点。第三节 优化设计的数学基础五五.函数的凸性函数的凸性 X XX X2 2X X1 1凸集凸集非凸集非凸集凹集凹集*若若X X是是X X1 1和和X X2 2连线上的点，则有连线上的点，则
21、有 凸凸集集-若若任任意意两两点点 ，对对于于 ，恒恒有有 。第三节 优化设计的数学基础五五.函数的凸性函数的凸性 凸函数凸函数设设f(X)f(X)为定义在为定义在 R Rn n 内一个凸集内一个凸集D D上的上的函数函数，若对于若对于 及及D D上的任意两点上的任意两点X X1 1,X,X2 2,恒恒有有 第三节 优化设计的数学基础五五.函数的凸性函数的凸性 为凸函数的充要条件是对于任意的为凸函数的充要条件是对于任意的(D(D为凸集为凸集),),凸函数的判定第三节 优化设计的数学基础六六.优化问题存在极值的条件优化问题存在极值的条件 梯度为零向量梯度为零向量海赛矩阵正定海赛矩阵正定多元函数具
22、有极小值的充要条件多元函数具有极小值的充要条件一元函数具有极小值的充要条件一元函数具有极小值的充要条件第三节 优化设计的数学基础六六.优化问题存在极值的条件优化问题存在极值的条件 （2）对于对于整个可行域整个可行域，恒有恒有 ，则则X X*为全局极小点为全局极小点；（1）对于对于X X*在可行域中的在可行域中的一个邻域一个邻域，恒恒有有 ，则则X X*为局部极小点为局部极小点；局部极小点与全局极小点局部极小点与全局极小点第四节 一维搜索方法一一.一维问题是多维问题的基础一维问题是多维问题的基础如：如：*在上次迭代中已求得在上次迭代中已求得，由某种逻辑方式由某种逻辑方式（如负梯度方向如负梯度方向
23、、共轭共轭方向等方向等）给定给定，每次迭代可归结为以每次迭代可归结为以 为变量的一维问题为变量的一维问题。则则当当第四节 一维搜索方法二二.的确定方法的确定方法上例中，上例中，2 2）取最优步长：）取最优步长：上例中，上例中，-能使目标函数值下降的步长能使目标函数值下降的步长；1 1）取下降步长（任意步长）：）取下降步长（任意步长）：第四节 一维搜索方法三三.一维搜索的步骤一维搜索的步骤2 2）将含最优点的区间不断缩小）将含最优点的区间不断缩小1 1）确定一个包含最优点的初始搜索区间确定一个包含最优点的初始搜索区间特点：特点：高高-低低-高高*区间缩短率区间缩短率：当该区间的长度小于预先给定的
24、一个很小的正数当该区间的长度小于预先给定的一个很小的正数 ，则可认为该区间中的某点则可认为该区间中的某点(如中点如中点)是最优点是最优点。第四节 一维搜索方法四四.确定初始区间的进退算法确定初始区间的进退算法前进计算前进计算后退计算后退计算试探后作前进或后退计算试探后作前进或后退计算。第四节 一维搜索方法四四.确定初始区间的进退算法确定初始区间的进退算法h=hh=h0 0y y1 1=f(x=f(x1 1)、x x2 2=x=x1 1+h+h、y y2 2=f(x=f(x2 2)给定给定x x1 1、h h0 0y y1 1yy2 2y y22y y3 3是是h=2hh=2hx x3 3=x=
25、x2 2+h+h、y y3 3=f(x=f(x3 3)结束结束否否h=-hh=-hx x3 3=x=x1 1y y3 3=y=y1 1a=xa=x1 1、b=xb=x3 3是是x x1 1=x=x2 2y y1 1=y=y2 2x x2 2=x=x3 3y y2 2=y=y3 3是是a=xa=x3 3、b=xb=x1 1否否h0h0否否初始进退距初始进退距计算程序框图khx1 y1x2 y2x3 y310.10.20 90.1 8.2030.3 6.68120.40.1 8.2030.3 6.6810.7 4.42930.80.3 6.6810.7 4.4291.5 7.125第四节 一维搜索
26、方法五五.格点法格点法 ab 先将搜索区间先将搜索区间分成若干等分，计分成若干等分，计算出当中的算出当中的n n个等分个等分点的目标函数值。点的目标函数值。再通过比较再通过比较,找出其找出其中的最小点，则该中的最小点，则该点的两个邻近点围点的两个邻近点围成缩短了的新区间。成缩短了的新区间。1）基本思路）基本思路第四节 一维搜索方法五五.格点法格点法2）每轮迭代区间的缩短率）每轮迭代区间的缩短率思路简单，编程容易，宜于离散型优化问题；思路简单，编程容易，宜于离散型优化问题；计算量大，不宜用于高维优化问题。计算量大，不宜用于高维优化问题。3）特点）特点第四节 一维搜索方法六六.黄金分割法黄金分割法
27、1）基本思路）基本思路为预先给定的误差限为预先给定的误差限。缩短区间的总次数缩短区间的总次数 将区间按一定的比例缩小，且正常迭代时每缩短将区间按一定的比例缩小，且正常迭代时每缩短一次区间只需计算一次函数值一次区间只需计算一次函数值。令令得得：其正根为其正根为：证证：*关于关于 的证明的证明关于缩小区间总次数的证明关于缩小区间总次数的证明即即证：证：第四节 一维搜索方法六六.黄金分割法黄金分割法2）迭代步骤）迭代步骤给定给定否否否否是是是是止止*也可采用迭代次也可采用迭代次数是否大于或等于数是否大于或等于 k k 作终止准则。作终止准则。第四节 一维搜索方法七七.二次插值法二次插值法1）基本思路
28、）基本思路原函原函数数用三点二次用三点二次插值多项式插值多项式来逼近原函来逼近原函数。数。第四节 一维搜索方法求出求出a a、b b后得后得求系求系数数a a和和b b求驻点求驻点插值多项式：插值多项式：区间的缩短区间的缩短x4=0.5(x1+x2)f4=f(x4)x1=x4f1=f4x3=x2f3=f2x2=x4f2=f4x1=xpf1=fpx3=x2f3=f2x2=xpf2=fpx1=x2f1=f2x2=xpf2=fpx3=xpf3=fp是是否否输出输出二次插值法缩小区间流程图二次插值法缩小区间流程图输入输入xpx2f4f2f2fpxp0 x*=xp,f*=fpx*=x2,f*=f2否否给
29、定给定 x1、x3、否否否否是是结结 束束是是是是是是第五节 无约束优化方法一一.解法分类解法分类1 1）直接法）直接法 其搜索方向直接取定或由计算目标函其搜索方向直接取定或由计算目标函数值所得的信息来确定；数值所得的信息来确定；2 2）间接法）间接法（解析法）（解析法）确定搜索方向时用到一阶或（和）二确定搜索方向时用到一阶或（和）二阶导数的方法。阶导数的方法。第五节 无约束优化方法二二.坐标轮换法坐标轮换法 坐标轮换法又称为坐标轮换法又称为“变量轮换法变量轮换法”，“交替法交替法”或或“降维法降维法”。是一种不需要求函数导数，直接探。是一种不需要求函数导数，直接探索目标函数最优解的方法。索目
30、标函数最优解的方法。每次仅对多元函数的一个变量沿其坐标轴进每次仅对多元函数的一个变量沿其坐标轴进行一维探索，其余各变量均固定不动，并依次行一维探索，其余各变量均固定不动，并依次轮换进行一维探索的坐标轴，完成第一轮探索轮换进行一维探索的坐标轴，完成第一轮探索后再重新进行第二轮探索，直到找到目标函数后再重新进行第二轮探索，直到找到目标函数在全域上的最小点为止。在全域上的最小点为止。基本思路第五节 无约束优化方法二二.坐标轮换法坐标轮换法迭代公式第五节 无约束优化方法二二.坐标轮换法坐标轮换法步长选取方法1)随机选择随机选择 值的方法值的方法 此方法每次选择值此方法每次选择值 时，需满足下式：时，需
31、满足下式：由于这种方法是轮流沿由于这种方法是轮流沿n个设计变量的坐标轴方向前个设计变量的坐标轴方向前进，所以此方法有时路程过于迂回曲折，因此它不是进，所以此方法有时路程过于迂回曲折，因此它不是快速探索的方法。快速探索的方法。第五节 无约束优化方法二二.坐标轮换法坐标轮换法步长选取方法2)加速步长法加速步长法 此方法先规定沿此方法先规定沿 方向的初始实验步方向的初始实验步 ，确，确定步长定步长 的正负，当沿坐标轴正方向探索能使目的正负，当沿坐标轴正方向探索能使目标函数值减小时，则取正值，否则应取负值。标函数值减小时，则取正值，否则应取负值。再取步长再取步长 计算并判断计算并判断 。当步长不宜延伸
32、而宜缩小时，亦可缩小，也当步长不宜延伸而宜缩小时，亦可缩小，也是一直到函数达到最小值为止。是一直到函数达到最小值为止。加速步长法流程图给定给定得出得出TTFTFTTFFFT结束结束第五节 无约束优化方法二二.坐标轮换法坐标轮换法步长选取方法3)最优步长法最优步长法 最优步长法是利用一维探索方方，如黄金分割最优步长法是利用一维探索方方，如黄金分割法或二次插值法，来确定最优步长值。法或二次插值法，来确定最优步长值。在第在第k轮探索的第轮探索的第i次迭代中其步长为：次迭代中其步长为：第五节 无约束优化方法二二.坐标轮换法坐标轮换法坐标轮换法特点1 1）编程简单，容易掌握；）编程简单，容易掌握；2 2
33、）收收敛敛速速度度通通常常较较低低（其其有有效效性性取取决决于于目目标函数的性态标函数的性态），仅适于低维的情况。），仅适于低维的情况。如如:(:(1)1)等值线为椭圆等值线为椭圆,且长短轴分别平行于坐标轴时且长短轴分别平行于坐标轴时-高效高效(2(2)等值线为如图脊线时等值线为如图脊线时-无效无效(3(3)一般情况一般情况-低效低效第五节 无约束优化方法三三.最速下降法最速下降法基本思路 最速下降法是以负梯度方向作为下降方向的极小化算法，又称梯度法，是1874年法国科学家Cauchy提出的，最速下降法是无约束最优化中最简单的方法。柯西（Cauchy，Augustin Louis 1789-1
34、857），出生于巴黎，在数学领域，有很高的建树和造诣。很多数学的定理和公式也都以他的名字来称呼，如柯西不等式、柯西积分公式.第五节 无约束优化方法三三.最速下降法最速下降法迭代公式(1)(1)梯度方向是目标函数上升最快的方向，负梯度梯度方向是目标函数上升最快的方向，负梯度方向则是最速下降方向方向则是最速下降方向(2)(2)步长为了使目标函数值沿搜索方向能获得最大步长为了使目标函数值沿搜索方向能获得最大的下降值。的下降值。步长步长计算程序框图给给 定定 X0,X(K)=X0K=K+1是是否否结结 束束 K:=0第五节 无约束优化方法三三.最速下降法最速下降法算法特点（1 1）在最速下降法中，相邻
35、两个迭代点上的函数梯度相互）在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。迭代点向函数极小点靠近的过程，走的是曲折路线。垂直。迭代点向函数极小点靠近的过程，走的是曲折路线。这一次的搜索方向与前一次的搜索方向相互垂直，形成这一次的搜索方向与前一次的搜索方向相互垂直，形成“之之”字形的锯齿现象。字形的锯齿现象。（2 2）在远离极小点的位置，每次迭代可使函数值有较多的）在远离极小点的位置，每次迭代可使函数值有较多的下降。可是在接近极小点的位置，由于锯齿现象使每次迭代下降。可是在接近极小点的位置，由于锯齿现象使每次迭代行进的距离缩短，因而收敛速度减慢。行进的距离缩短，因而收敛速度减慢。第五节 无
36、约束优化方法四四.牛顿法（牛顿法（Newton-RaphsonNewton-Raphson，二阶梯度法），二阶梯度法）基本思路 牛顿法就是一种收敛速度很的方法，其基本思牛顿法就是一种收敛速度很的方法，其基本思路是利用二次曲线来逐点近似原目标函数，以二路是利用二次曲线来逐点近似原目标函数，以二次曲线的极小点来近似原目标函数的极小值点并次曲线的极小点来近似原目标函数的极小值点并逐渐逼近该点。逐渐逼近该点。第五节 无约束优化方法四四.牛顿法（牛顿法（Newton-RaphsonNewton-Raphson，二阶梯度法），二阶梯度法）基本思路具体做法：利用二次函数（二具体做法：利用二次函数（二次曲线）
37、次曲线），来逐点去近似，来逐点去近似或逼近原目标函数或逼近原目标函数 ，然后，然后求出二次函数的最小点求出二次函数的最小点 ，作为对元目标函数求优的下一作为对元目标函数求优的下一个迭代点个迭代点 ，通过若干，通过若干次的迭代，使迭代点逐步逼近次的迭代，使迭代点逐步逼近元目标函数的极小值点（如右元目标函数的极小值点（如右图）。图）。第五节 无约束优化方法公式推导 取原目标函数在各迭代点附近展开的泰勒二次多项取原目标函数在各迭代点附近展开的泰勒二次多项式，作为每次迭代计算时用以逼近目标函数的函数的函式，作为每次迭代计算时用以逼近目标函数的函数的函数表达式。数表达式。令式中的令式中的Hessian矩
38、阵矩阵 =，上式可以改写为：，上式可以改写为：第五节 无约束优化方法公式推导 当当 时可求得二次曲线时可求得二次曲线 的极值点，且当的极值点，且当在该处的在该处的Hessian矩阵为正定时有极小点。矩阵为正定时有极小点。由上式得：由上式得：由于由于 是二次函数，故是二次函数，故 是线性函数。是线性函数。令令 ，得到：，得到：第五节 无约束优化方法公式推导若若 为可逆矩阵，将上式两边左乘以为可逆矩阵，将上式两边左乘以整理之后得：整理之后得：当目标函数当目标函数 是二次函数时，牛顿法变得很简单有是二次函数时，牛顿法变得很简单有效，这时效，这时 是一个常数矩阵，所逼近的二次曲线就变是一个常数矩阵，所
39、逼近的二次曲线就变成精确表达式，而利用上式做一次迭代计算所求得的成精确表达式，而利用上式做一次迭代计算所求得的X就是就是最优点。但在一般情况下，最优点。但在一般情况下，不一定就是二次函数，则不不一定就是二次函数，则不能一步求出极小值点，即极小点不在能一步求出极小值点，即极小点不在 方向上，但由于在方向上，但由于在 点附近函数点附近函数 与与 是近似是近似的，所以这个方向可以作为近似方向，可以用上式求出的点的，所以这个方向可以作为近似方向，可以用上式求出的点X作为一个逼近点作为一个逼近点 ，这时上式既可以改写成牛顿法的，这时上式既可以改写成牛顿法的一般迭代公式：一般迭代公式：第五节 无约束优化方
40、法牛顿方向例题：例题：试用牛顿法球目标函数试用牛顿法球目标函数 的极小值点。的极小值点。解：解：取取 有有其逆矩阵为：其逆矩阵为：则：则：即为最小点，因为目标函数为二次函数，即为最小点，因为目标函数为二次函数，所以迭代一次就可以达到极值点所以迭代一次就可以达到极值点。前面已经说到，牛顿法对初始点的选择要求较高，即前面已经说到，牛顿法对初始点的选择要求较高，即使目标函数使目标函数 不是二次函数，当初始点选得好时，例如不是二次函数，当初始点选得好时，例如满足出事误差满足出事误差 时，也会很快收敛，但是如果时，也会很快收敛，但是如果不能满足不能满足 时就不能保证有比较好的收敛性。时就不能保证有比较好
41、的收敛性。初始点选择不当有时也会导致收敛到鞍点或不收敛，基于这初始点选择不当有时也会导致收敛到鞍点或不收敛，基于这种原因，对古典牛顿法要做些修改种原因，对古典牛顿法要做些修改修正牛顿法。修正牛顿法。牛顿修正法的方法是：由牛顿修正法的方法是：由 求求 时不是直接用时不是直接用原来的迭代公式计算，而是沿着原来的迭代公式计算，而是沿着 点处的牛顿方点处的牛顿方向进行一维探索，将该方向上的最优点作为向进行一维探索，将该方向上的最优点作为 。于是牛顿迭代公式可以写为：。于是牛顿迭代公式可以写为：令令第五节 无约束优化方法式中探索步长 为：这种修正牛顿法通常又称为广义牛顿法，计算量大，这种修正牛顿法通常又
42、称为广义牛顿法，计算量大，但是具有收敛快的优点，当初始点选择不当时，这种探索但是具有收敛快的优点，当初始点选择不当时，这种探索方法也会成功，（以牺牲计算量的代价得到了初始点的选方法也会成功，（以牺牲计算量的代价得到了初始点的选择任意性，因为在最开始并不是每次初始点都选择的恰当，择任意性，因为在最开始并不是每次初始点都选择的恰当，从而使设计变得简化）其迭代步骤如下：从而使设计变得简化）其迭代步骤如下：第五节 无约束优化方法（1）给定初始点）给定初始点 ，允许误差，允许误差 令令（2）计算）计算（3）检验是否满足）检验是否满足 ，若满足则迭代停止，若满足则迭代停止，否则进行步骤（否则进行步骤（4）
43、（4）令）令第五节 无约束优化方法（5）从）从 出发沿牛顿方向出发沿牛顿方向 进行一维探索：进行一维探索：（6）令）令转步骤（转步骤（2）第五节 无约束优化方法第五节 无约束优化方法 牛顿法及修正牛顿法的缺点是需要计算二阶偏导数和牛顿法及修正牛顿法的缺点是需要计算二阶偏导数和矩阵，特别是还需要求逆矩阵，计算繁琐，当目标函数矩阵，特别是还需要求逆矩阵，计算繁琐，当目标函数的维数的维数n n较高时，计算量和储存量都以较高时，计算量和储存量都以n n的平方比例增加。的平方比例增加。因此，当目标函数的变量较多且次数较高时，一般不用因此，当目标函数的变量较多且次数较高时，一般不用这种方法。此外，特别是当
44、这种方法。此外，特别是当HessianHessian矩阵是奇异矩阵时，矩阵是奇异矩阵时，其逆矩阵不存在，使得不收敛，此方法也不能用。其逆矩阵不存在，使得不收敛，此方法也不能用。牛顿法对初始点要求严格，修正牛顿法对初始点的牛顿法对初始点要求严格，修正牛顿法对初始点的要求不严格，具有二次收敛性，最优要求不严格，具有二次收敛性，最优 点附近的收敛速点附近的收敛速度极快。对于正定二次函数的寻优、迭代一次即可达到度极快。对于正定二次函数的寻优、迭代一次即可达到极小值点。极小值点。方法特点五五.共轭梯度法共轭梯度法 共轭梯度法是共轭方向法的一种，在该方法中每一共轭梯度法是共轭方向法的一种，在该方法中每一个
45、共轭向量是依赖于迭代点处的负梯度而构造出来的，个共轭向量是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。所以称作共轭梯度法。共轭梯度法最早是由共轭梯度法最早是由HestenesHestenes和和StiefleStiefle（19521952）提）提出来的，用于解正定系数矩阵的线性方程组，在这个出来的，用于解正定系数矩阵的线性方程组，在这个基础上，基础上，FletcherFletcher和和ReevesReeves（19641964）首先提出了解非）首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度
46、和二次终止性等优要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用与实际问题中。点，现在共轭梯度法已经广泛地应用与实际问题中。第五节 无约束优化方法第五节 无约束优化方法五五.共轭梯度法共轭梯度法基本思路 每轮搜索方向为一组共轭方向每轮搜索方向为一组共轭方向,但第一方向为负梯度方向但第一方向为负梯度方向.目标函数在极值点附近的等值线方程为（以二元函数为例）：当函数有极小值存在时需满足：根据解析几何可知满足上式条件时等值线方程为近似椭圆族。几何特性如果非零向量组如果非零向量组S1，S2，S3,SK中的任意两个向量中的任意两个向量关于关于n阶实对称矩阵阶实对称矩阵A是共
47、轭的，即满足式是共轭的，即满足式 SiTASj=0 ij i，j=1,2，k则称向量组则称向量组S1，S2，S3,SK关于矩阵关于矩阵A是共轭的。是共轭的。设A为nn阶实对称正定矩阵，而S1，S2为在n维欧氏空间En中的两个非零向量，如果满足式 S1TAS2=0则称向量S1与S2关于实对称正定矩阵A是共轭的，或简称S1与S2关于A共轭。凡是满足上式的向量S1和S2称为具有A共轭方向。数学基础考虑二次函数考虑二次函数点出发，沿点出发，沿G的某一共轭方向的某一共轭方向作一维搜索，到达作一维搜索，到达 点点，即，即数学推导共轭方向与梯度之间的关系 而在而在分别为分别为点处的梯度点处的梯度所以有所以有
48、若若 和和 对对G是共轭的，则有是共轭的，则有利用式（利用式（4-1）对两端前乘）对两端前乘 ，即得，即得（4-1 ）这就是共轭方向与梯度之间的关系。此式表明沿这就是共轭方向与梯度之间的关系。此式表明沿方向进行一维搜索，其终点与点的梯度之差与的共轭方向进行一维搜索，其终点与点的梯度之差与的共轭方向正交。共轭梯度法就是利用这个性质做到不计算方向正交。共轭梯度法就是利用这个性质做到不计算矩阵矩阵G就能就能 求得共轭方向的。求得共轭方向的。图一图一 共轭梯度法的几何说明共轭梯度法的几何说明 第二方向：第二方向：第一方向：第一方向：*可表示为两个负梯度方向的线性组合可表示为两个负梯度方向的线性组合。图
49、二图二.共轭方向的构成共轭方向的构成公式推导，以后新方向均按下述迭代公式产生以后新方向均按下述迭代公式产生：因而因而，因为因为（A A是是二次函数的二次函数的Hessian Hessian 矩阵矩阵）二次函数二次函数其梯度为其梯度为故有故有故有故有又又（正交正交）刘刘惟惟信信用用数数学学归归纳纳法法对对此此法法的的共共轭轭性性作作出出过过证明。证明。是是是是否否否否K n给给 定定 X0,n,K=1,X(K)=X0S(K)=-F(X(K)从从X(K)始始，沿沿S(K)进行一维搜索得进行一维搜索得X(K+1)K=K+1计算计算结结 束束重置负梯度方向重置负梯度方向程序框图 1.1.为共轭方向法为
50、共轭方向法,具有二次收敛性具有二次收敛性;2.2.共轭梯度法是一个典型的共轭方向法，它的每一共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向个搜索方向是互相共轭的，而这些搜索方向d d仅仅仅仅是负梯度方向与上一次迭代的搜索方向的组合，因是负梯度方向与上一次迭代的搜索方向的组合，因此，计算方便算法简单此，计算方便算法简单,编程容易编程容易,存储量小存储量小;3.3.需用到一阶导数。需用到一阶导数。算法特点一一.等式约束问题的拉格朗日乘子法等式约束问题的拉格朗日乘子法1.1.拉格朗日乘子法简介拉格朗日乘子法简介2.2.拉格朗日乘子拉格朗日乘子拉格朗日乘子法是一种将约