如梯度法和共轭梯度法

5.优化设计5.3一维搜索的优化方法西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.1确定搜索区间的方法—进退法实际问题数学模型数值计算方法程序设计上机计算求出结果数值解法：利用计算机通过反复迭代计算，求得实际问题的近似值。西南科技大学网络教育系列课程5.3.1确定搜索区间的方法—进退法下降迭代算法中在搜索方向S(k)上寻求最优步长ak时通常采用一维搜索法。一维搜索法就是一元函数极小化的数值迭代算法，其求解过程称一维搜索。一维搜索问题指目标函数为单变量的非线性规划问题。又称线性搜索问题。其模型为：t为实数(t)min0t(t)minmax0tt或一般一维搜索问题有效一维搜索问题西南科技大学网络教育系列课程5.3.1确定搜索区间的方法—进退法一维搜索问题的算法分类：1）精确一维搜索（最优一维搜索）2）非精确一维搜索（可接受一维搜索）1、进退法确定搜索区间的方法在函数的任一单谷区间上必存在一个极小点，而且在极小点的左侧，函数呈下降趋势，在极小点的右侧函数呈上升趋势。若已知方向S(k)上的三点x1＜x2＜x3及其函数值f(x1)、f(x2)和f(x3)，便可通过比较三个函数值的大小估计出极小点所在的位置，如图5.11所示。西南科技大学网络教育系列课程5.3.1确定搜索区间的方法—进退法图5.11极小点的估计西南科技大学网络教育系列课程5.3.1确定搜索区间的方法—进退法2、进退法的定义在某一方向上按一定方式逐次产生一些探测点，并比较这些探测点上函数值的大小，就可以找出函数值呈“大-小-大”变化的三个相邻点，其中两端点所确定的闭区间必定包含着极小点，这样的区间称为初始区间，记作[a,b]。这种寻找初始区间的方法称为进退法。αx*x1x2b西南科技大学网络教育系列课程若对任意x1,x2,α≤x1x2≤b满足：1)若x1≤x*，则φ(x1)φ(x*);2)若x2≥x*，则φ(x*)φ(x2).则称φ(x)在[α,b]上强单峰。若只有当x1≠x*，x2≠x*时，上述1),2)式才成立，则称φ(x)在[α,b]上单峰。αx1x*x2b强单峰αx*b单峰西南科技大学网络教育系列课程其具体的程序见右图：西南科技大学网络教育系列课程5.3.1确定搜索区间的方法—进退法一维搜索法：就是一元函数极小化的数值迭代算法，其求解过程称一维搜索。一维搜索法是构成非线性优化方法的基本算法，因为多元函数的迭代解法可归结为在一系列逐步产生的下降方向上的一维搜索。一维搜索法一般分两步：1）确定初始搜索区间，该区间应是包括一维函数极小点在内的单峰区间；2）在搜索区间内寻找极小点。ba,ba,西南科技大学网络教育系列课程1、定义黄金分割法：又称0.618法，是一种通过不断缩小区间得到极小点的一维搜索算法。问题：凸函数是不是单谷函数？严格凸函数是不是单谷函数？单谷函数是不是凸函数？上的单谷函数为称上严格递增且在上严格递减在使得函数如果],[)(,],[,],[)(],,[baxbxxaxbax的单谷区间。称为)(],[xba单谷函数上唯一的极小点。在为显然此时],[)(baxx5.3.2黄金分割法西南科技大学网络教育系列课程搜索法求解：(t)min0t(t)minmax0tt或2、基本过程：给出[a,b],使得x*在[a,b]中。[a,b]称为搜索区间。迭代缩短[a,b]的长度。当[a,b]的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。西南科技大学网络教育系列课程假定：已经确定了单谷区间[a,b]xx0minxxxmax0min)(minxbxa)(1x)(2xx)(1x)(2xxx1x2ababx1x2新搜索区间为[a,x2]新搜索区间为[x1,b]西南科技大学网络教育系列课程区间缩小比例的确定：区间缩短比例为(x2-a)/(b-a)缩短比例为(b-x1)/(b-a)缩短比例满足：每次插入搜索点使得两个区间[a,x2]和[x1,b]相等；每次迭代都以相等的比例缩小区间。618.0215缩短比例0.618法)(1x)(2x)(1x)(2xx1x2ababx1x2西南科技大学网络教育系列课程确定[a,b],计算探索点x1=a+0.382(b-a)x2=a+0.618(b-a)0.618法解题步骤：)()(21xx是否ax2是停止，输出x1否以[a,x2]为新的搜索区间1xb是停止，输出x2否以[x1,b]为新的搜索区间西南科技大学网络教育系列课程5.3.2黄金分割法例1：用黄金分割法求的初始区间，设初始点，初始步长。解：用进退法确定初始区间：比较，因作前进运算：107)(2aaaf00a1h10)(,01101affaa4)(,12212affhaa21ff西南科技大学网络教育系列课程5.3.2黄金分割法因，再作前进运算：故初始搜索区间为：212h4,12121ffaa0,23232ffaa2)(,43323affhaa32ff422h0,22121ffaa2,43232ffaa18)(,83323affhaa8,2,,31aaba西南科技大学网络教育系列课程例2：5.0],3,0[12)(min30精度其中单谷区间求解xxxx解：x1x2)(1x)(2x30x1)、第一轮：x1=1.146,x2=1.8546648.3)(,2131.0)(21xxx2-00.5西南科技大学网络教育系列课程1.4160xx2x12)、第二轮：x2=1.146,x1=0.7082131.0)(0611.0)(21xxx2-0=1.1460.53)、第三轮：x1=0.438,x2=0.7082082.0)(0611.0)(12xxb-x1=1.146-0.4380.51.8540xx2x1西南科技大学网络教育系列课程4)、第四轮：x2=0.876,x1=0.7080798.0)(0611.0)(21xxb-x1=1.146-0.7080.5输出：x*=x2=0.876为最优解，最优值为-0.079801.416xx1x2西南科技大学网络教育系列课程5.3.3Newton法0)()(),(minxfxfxf二次可微，其中考虑Newton法基本思想：用探索点xk处的二阶Taylor展开式近似代替目标函数，以展开式的最小点为新的探索点。2))((21))(()()(kkkkkxxxfxxxfxfxg展开式：:,0)(求导得的点的最小点即导数为xg)()(1kkkkxfxfxx西南科技大学网络教育系列课程解题步骤：给定初始点x1和精度是是停止，输出x10)(1xf是否停止，解题失败)()(1112xfxfxx计算否停止，输出x2否1xf12xx西南科技大学网络教育系列课程5.3.4二次插值法叫截断误差叫插值结点插值法插值条件使被插函数近似代替插值函数用简单函数望希只知离散数据求知存在实际中问题提出)()()(,)()(,)()(:).....2.1.0()(,,)(:.1xPxfxRxxPxfxfxPnixfyxfyiiiii)()(或多项式插值代数插值多项式函数或者三角插值三角函数通常取xP西南科技大学网络教育系列课程1、定义：二次插值法又称抛物线法，它是以目标函数的二次插值函数的极小点作为新的中间插入点，进行区间缩小的一维搜索算法。用f(x)在2或3个点的函数值或导数值，构造2次或3次多项式作为f(x)的近似值，以这多项式的极小点为新的迭代点。3点2次，2点2次，4点3次，3点3次，2点3次等以3点2次为例：取x1，x2，x3，求出f(x1)，f(x2)，f(x3)5.3.4二次插值法西南科技大学网络教育系列课程5.3.4二次插值法设二次插值多项式：f(x)=a0+a1x+a2x2f(x1)=a0+a1x1+a2x12f(x2)=a0+a1x2+a2x22f(x3)=a0+a1x3+a2x32解得a1a21332212131323212xxxxxxxfxxxfxxxfxxa1332212221223221133221xxxxxxxfxxxfxxxfxxa212aaxp西南科技大学网络教育系列课程5.3.4二次插值法13131xxxfxfc21322212232213322113322121xfxxxfxxxfxxxfxxxfxxxfxxxp21315.0ccxxxp32112122xxcxxxfxfc西南科技大学网络教育系列课程5.3.4二次插值法f2fp的新搜索区间f2fp的新搜索区间西南科技大学网络教育系列课程5.3.4二次插值法2、特点：1）二次插值法的中间插入点包含了函数在三个点上的函数值信息，因此这样的插入点比较接近函数的极小值。2）二次插值法以两个中间插入点的距离充分小作为收敛准则，即当成立时，把作为此次一维搜索的极小点。二次插值法的计算程序如下图:2xxppx西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.3.4二次插值法例2.用二次插值法求函数的极小点，给定解：1）确定初始区间：由于，应加大步长继续向前探测，由于，可知初始区间已经找到，即243)(3xxxf2.0,1,00hx2)(,01101xffxx1)(,1102212xffhxx21ff18)(,23323xffhxx32ff2,0西南科技大学网络教育系列课程5.3.4二次插值法2）用二次插值法逼近极小点记此初始区间内的相邻三点及其函数值依次为：将它们代入式，得插值函数的极小点，即新的插入点及其函数值：由于，故新区间18,1,2,2,1,0321321fffxxx292.0,555.0ppfx22,xxffpp1,0,,2xaba西南科技大学网络教育系列课程5.3.4二次插值法由于，故应继续作第二次插值计算。在新的区间内，相邻三点及其函数值依次为：将它们代入式，得由于，新区间2.0445.0555.012pxx1,292.0,2,1,555.0,0321321fffxxx243.0,607.0ppfx22,xxffpp1,555.0,,2bxba西南科技大学网络教育系列课程5.3.4二次插值法由于，故一维搜索到此结束，极小点和极小值为：2.0052.0607.0555.02pxx243.0,607.0**fxxp5.优化设计5.4多维优化方法西南科技大学网络教育系列课程西南科技大学网络教育系列课程5.4多维优化方法多维优化方法是进行多变量优化设计的数值迭代法。它包括了无约束优化方法和约束优化方法两种。1、无约束优化问题的一般形式：求解设计变量：X=[x1,x2,…,xn]T,X∈Rn满足目标函数minf(X)的无约束最优化解X*和最优化函数minf(X*)。2、无约束优化的分类根据搜索方向的不同构成形式，可分类以下两类：西南科技大学网络教育系列课程5.4多维优化方法1）导数法：利用目标函数的一阶和二阶导数信息构成搜索方向的算法，称为导数法，如梯度法和共轭梯度法。注：其收敛性和收敛速度都是比较好的。2）模式法：通过几个已知点上函数值的比较构造搜索方向的算法。如鲍威尔法。对于较复杂的目标函数优化是有利的。3、约束优化方