关于无约束最优化问题的信赖域解法

关于无约束最优化问题的信赖域解法一、引言无约束优化问题是实际工程中最常见的问题之一。这类问题虽然形式比较简单，但是对于某些大规模的或者非线性很强的问题，求解它们仍然是有相当难度的。无约束问题的算法大致分成两类：一类在计算过程中要用到目标函数的导数，另一类则只要求目标函数值。本文中所讲述的信赖域法，与牛顿法、最速下降法、共轭梯度法一样，同属于第一类方法。二、信赖域法的主要内容2.1信赖域法的基本思想虽然信赖域法与最速下降法等同属于一大类，但是在基本思想上还是有所不同。其他几种方法的基本策略是：给定点x(k)后，定义搜索方向d(k),再从x(k)出发沿d(k)作一维搜索，信赖域法则不然，下面重点阐述一下其基本思想：首先给定一个所谓的“信赖域半径”作为位移长度的上界，并以当前迭代点为中心以此“上界”为半径确定一个称之为“信赖域”的闭球区域。然后,通过求解这个区域内的“信赖域子问题”(目标函数的二次近似模型)的最优点来确定“候选位移”。若候选位移能使目标函数值有充分的下降量,则接受该候选位移作为新的位移,并保持或扩大信赖域半径,继续新的迭代。否则,说明二次模型与目标函数的近似度不够理想,需要缩小信赖域半径，再通过求解新的信赖域内的子问题得到新的候选位移。如此重复下去，直到满足迭代终止条件。2.2信赖域法的数学分析考虑无约束问题：min(),nfxxR(2-1)将f(x)在给定点x(k)展开，取二次近似可得：()()()()2()()1()()()()()()()2kkTkkTkTkfxfxfxxxxxfxxx(2-2)记d=x-x(k)，得到二次模型()()2()1()()()()2kkTTkkdfxfxddfxd(2-3)为了在x(k)附近用()kd近似f(x(k)+d)，限定d的取值，令||d||≤rk，rk是给定的常数，称为信赖域半径，这样求函数f(x)的极小点归结为解一系列子问题()()2()1min()()()()2..defkkTTkkkdfxfxddfxdstdr(2-4)若d(k)是2-1式的最优解，则存在乘子.0，使得：2()()()()1()()2()()()0()()0kkkkkTkkkfxdfxddddr(2-5)记作:1()()2()kTkdd(2-6)得到d(k)为最优解的必要条件2()()()()()()()()()00kkkkkkkkfxddfxdrdr(2-7)设2()()kfxI可逆，由式2-7可得，()2()1()(())()kkkdfxIfx(2-8)由上述条件易知，式2-7的解d(k)与信赖域半径rk取值有关，如果rk充分大，的值有可能很小，从而d(k)与牛顿法中的牛顿方向接近，即()2()1()()()kkkdfxfx(2-9)如果rk趋近于0，则可得：()()1()kkdfx由此可知，当信赖域半径rk由小到大逐渐增大时，d(k)在最速下降方向与牛顿方向之间连续变化。得出式2-4的最优解d(k)后，点x(k)+d(k)能否作为式2-1的近似解，还要根据()kd逼近f(x)是否成功来确定。如果函数值实际下降量与预测下降量之比()()()()()()()()()kkkkkkkfxfxdfxd太小，就认为不成功，后继点仍取x(k)；若比较大，则逼近成功，令x(k+1)=x(k)+d(k)。信赖域方法计算步骤如下：1)给定可行点x（1），信赖域半径r1,参数01(一般取=0.25，=0.75)，精度要求，置k=12)计算f(x(k)),()()kfx.若()()kfx，则停止计算，得解x(k)；否则计算2()()kfx3)求解子问题()()2()1min()()()()2..defkkTTkkkdfxfxddfxdstdr得到子问题的最优解并令()()()()()()()()()kkkkkkkfxfxdfxd4)如果k，令x(k+1)；如果k，令x(k+1)=x(k)+d(k)5)修改rk。如果k，令rk+1=12kr；如果k，令rk+1=kr；如果k，令rk+1=2kr6)置k=k+1，转步骤(2)。总的来说，其步骤可由图2-1来表示。开始选取初试点，信赖域半径计算子问题rk接近1x(k+1)=x(k)+d(k)TF2.3信赖域法的收敛问题在一定条件下，信赖域方法具有全局收敛性。查阅相关资料，定理如下：设f(x)是nR上的实函数，x（1）是给定的初始点，(1)|()()Sxfxfx是有界闭集，(),()fxfx和2()fx在.S上连续，用信赖域方法求的序列｛x(k)｝,则()lim||()||0kkfx三、运用信赖域法求解具体问题考虑无约束问题4321122min()45fxxxxx取初点(1)00x，信赖域半径r1=1，取=0.25，=0.75.用信赖域法求解过程：1)将初值代入目标函数求得函数值f(x(1))=5，目标函数的梯度(1)0()4fx，Hesse矩阵2(1)20()02fx2)求解子问题(1)(1)2(1)11min()()()()2..1defTTdfxfxddfxdstd即为求解221212min()54..||||1ddddstd可得最优解(1)(1)1(1)201ddd，函数值(1)(1)()2fxd3)可得11，逼近成功，令(2)(1)(1)01xxd，2122rr4)进行二次迭代，函数值为2，(2)0()2fx，2(2)20()02fx5)求解子问题2222122212min()22..4ddddstdd可得最优解(2)(2)1(2)201ddd，(2)(2)()0fxd，(2)2()1d6)可得22，令(3)(2)(2)02xxd，3224rr7)计算得(3)(3)(3)00()1,(),02fxfxx是最优解