平凡无所谓,
平淡无所谓,
但求每天早晨能望见你,
这已经足够满足。
身边的一切如风,
而你让我有了根,
就让我爱你多些,
再多些,甚至满泻,
与你一生一世。
——畅宝宝的傻逼哥哥
过去使用最广泛的共轭方向法是由Powell提出来的,这个方法与共轭梯度法一样,开始也是来自凸二次问题,但是它也成功应用于非二次问题。
Powell法最显著的特征就是通过一系列线搜索生成共轭方向,所用的技术基于下面的定理:
定理1:如果凸二次问题
f(x)=a+xTb+12xTHx
在直线
x=xa+αda
与
x=xb+αdb
上分别对α最小化,得到的最小点分别为x∗a,x∗b,如图1所示。
如果db=da,那么向量x∗b−x∗a与da(或者db)共轭。
证明:如果f(xa+αda),f(xb+αdb)对α最小化,那么
df(xa+αda)dα=dTag(x∗a)=0df(xb+αdb)dα=dTbg(x∗b)=0(1a)(1b)
因为
g(x∗a)=b+Hx∗ag(x∗b)=b+Hx∗b(2a)(2b)
因为db=da,所以由等式1与2可得
dTaH(x∗b−x∗a)=0
因此,向量x∗b−x∗a与方向da(或者db)共轭,证毕。||
在Powell算法中,假设初始点为x00,n个线性无关方向为d01,d02,…,d0n,并且每次迭代执行一系列线搜索。虽然可以使用任意的线性无关方向集合,但是出于方便,我们使用坐标方向集。
![漫步最优化四十——Powell法(上) 漫步最优化四十——Powell法(上)](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzM2Ny9jNmViNjNlMTI4NjI1ODcxNzM3YzQ2NDY5YmNhNDQyZi5wbmc=)
图1
第一次迭代的时候,
f(x)从初始点
x00开始,在方向
d01,d02,…,d0n上最小化分别得到点
x01,x02,…,x0n,如图2所示,新的方向
d0(n+1)为
d0(n+1)=x0n−x0
且f(x)在这个方向上最小化得到新的点x0(n+1),然后更新方向集为
d11d12d1(n−1)d1n=d02=d03⋮=d0n=d0(n+1)(3)
第一次迭代的效果就是f(x)减少了Δf=f(x00)−f(x0(n+1))并且同时删除了d01加入了d0(n+1)。
第二次得带执行同样的过程,从点
x10=x0(n+1)
开始,f(x)在方向d11,d12,…,d1n上最小化分别得到点x11,x12,…,x1n,如图3所示,然后生成新的方向d1(n+1)
d1(n+1)=x1n−x10
f(x)在方向d1(n+1)上最小化得到点x1(n+1)。因为
d1n=d0(n+1)
所以d1(n+1)与dn共轭,因此我们令
d21d22d2(n−1)d2n=d12=d13⋮=d1n=d1(n+1)(4)
新的方向解将包含一对共轭方向,即d2(n−1),d2n。
用同样的方式执行上面的过程,每次迭代都会增加一个共轭方向。Powell法需要n(n+1)次线搜索,因为每次迭代包含(n+1)次线搜索,共需要n次迭代,Powell算法实现如下:
算法1:共轭梯度算法步骤1输入x00并初始化容忍误差ε令d01=[x01 0 ⋯ 0]Td02=[0 x02 ⋯ 0]T⋮d0n=[0 0 ⋯ x0n]T令k=0步骤2对于i=1从n求出αki,就是最小化f(xk(i−1)+αdki)的值α令xki=xk(i−1)+αkidki步骤3生成新方向dk(n+1)=xkn−xk0求出αk(n+1),就是最小化f(x0+αdk(n+1))的值α令xk(n+1)=xk0+αk(n+1)dk(n+1)计算fk(n+1)=f(xk(n+1))步骤4如果∥αk(n+1)dk(n+1)∥<ε,输出x∗=xk(n+1),f(x∗)=fk(n+1)算法结束步骤5更新方向d(k+1)1=dk2d(k+1)2=dk3⋮d(k+1)n=dk(n+1)令x(k+1)0=xk(n+1),k=k+1,令k=k+1然后回到步骤2
![漫步最优化四十——Powell法(上) 漫步最优化四十——Powell法(上)](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzc2MS9jNmE2ZDRhMDRjNjViMWE5MjVkZDMyZTllMzdlNmFkOS5wbmc=)
图2
![漫步最优化四十——Powell法(上) 漫步最优化四十——Powell法(上)](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzkwNi9lNTY0NjE5NGZhM2QzM2I0NzRmN2MxZTE5YzRlMWQ2YS5wbmc=)
图3