资源描述:
《最优化方法课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、§1.5二维最优化问题的几何解释1理论分析二维最优化问题的目标函数z=f(x1,x2)表示三维空间R3中的曲面.在空间直角坐标系O-x1x2z中,平面z=c与曲面z=f(x1,x2)的交线在O-x1x2平面上的投影曲线为:取不同的c值得到不同的投影曲线,每一条投影曲线对应一个c值,称投影曲线为目标函数的等值线或等高线.234例在坐标平面上画出目标函数的等值线.解:因为当目标函数取常数时,曲线表示是以原点为圆心,半径为常数的圆.因此等值线是一族以原点为圆心的同心圆(如图所示)5理论分析求目标函数z=f(x1,x2)在可行域D上的极小点,是在与可行域D有交集的等值线中找出具有最小
2、值的等值线.也就是在可行域D上沿着f(x1,x2)的负梯度方向或某种下降方向上找取得最小值c的点.6例1.5.1解(1)画出可行域D;(2)目标函数的等值线是以点(1,2)为圆心的一族圆;(3)f(x1,x2)的梯度为7例1.5.1负梯度方向(下降方向)指向等值线圆心,所以等值线与可行域D的边界相切的点x*=(1/2,3/2)T是此问题的最优解,目标函数的最优值为1/2.8例1.5.2解如图所示,可行域只能是圆弧ABE,其中点A和点E是等值线–x1–x2+1=0和圆x12+x22-9=0的交点.注意到等值线是平行的抛物线,图中画出了几条目标函数的等值线.容易看出B点是最优点,
3、所以最优解是(0,-3)T,最优值为-3.9§1.6最优化问题的一般算法10迭代算法迭代算法选取一个初始可行点x0∈D,由这个初始可行点出发,依次产生一个可行点列:x1,x2,···,xk,···,记为{xk},使得某个xk恰好是问题的一个最优解,或者该点列收敛到问题的一个最优解x*.下降算法在迭代算法中一般要求f(xk+1)≤f(xk).11可行点列的产生在xk处求得一个方向pk(下降方向),在射线xk+apk(a>0)上求一点:xk+1=xk+akpk使得f(xk+1)≤f(xk).其中ak称为步长.定义1.6.1(下降方向)在点xk处,对于方向pk≠0,若存在实数b>0
4、,使得任意的a∈(0,b),有:f(xk+apk)0,使得对任意的a∈(0,b),有:xk+apk
5、∈D,则称pk为点xk处关于区域D的可行方向。对于D的内点(存在邻域包含于D),任意方向可行,对于边界点(任意邻域既有D的点也有不在D中的点),则有些方向可行,有些方向不可行.若下降方向关于域D可行,则称为可行下降方向.14最优化问题的算法的一般迭代格式给定初始点x0,令k=0.(1)确定xk处的可行下降方向pk;(2)确定步长ak,使得f(xk+akpk)6、0充分接近x*时,产生的点列才收敛于x*,则称该算法为具有局部收敛的算法.如果对任意的x0∈D,由算法产生的点列都收敛x*,则称该算法为具有全局收敛的算法.由于一般情况下最优解x*是未知的,所以只有具有全局收敛性的算法才有实用意义.但算法的局部收敛性分析,在理论上是重要的,因为它是全局收敛性分析的基础。16收敛速度定义1.6.3设序列{xk}收敛于x*,而且若0
7、止准则时,就停止迭代.常用的终止准则有:(1)或(2)或(3)(4)上面三种准则的组合.注:其中e>0是预先给定的.18