无约束优化方法-直接方法（Powell与改进Powell）

在坐标轮换法中，可知其收敛速度慢，且受到等值线的形状的影像。原因可归结为其搜索方向总是平行于坐标轴，不适应函数的变换情况。针对这样的问题，共轭方向可以较好解决。

那什么叫共轭方向呢？

共轭方向

这里，我们设 $\boldsymbol A$ 为 $n\times n$ 的对称正定矩阵，如果有两个 $n$ 维向量 $\boldsymbol s_1$ 和 $\boldsymbol s_2$ 满足 $\boldsymbol s_1^T\boldsymbol A\boldsymbol s_2 = 0$ ，则 $\boldsymbol s_1$ 和 $\boldsymbol s_2$ 是关于 $\boldsymbol A$ 是共轭的。很明显，当 $\boldsymbol A = \boldsymbol I$ 时，两向量是正交的，说明正交是共轭的特例。如果一组方向向量两两都关于 $\boldsymbol A$ 共轭，那么这一组向量可称为共轭方向向量。

共轭方向有一个重要性质，就是对于正定二次函数 $f(\boldsymbol x)= c+\boldsymbol b^T\boldsymbol x+1/2\boldsymbol x^T\boldsymbol A\boldsymbol x$ ，从任意初始点开始出发，一次沿关于 $\boldsymbol A$ 共轭方向 $\boldsymbol s_i(i=1,2,...,n)$ 进行一维搜索，至多 $n$ 步可以收敛到极小点。这个是可以证明的。这里我们给出简单理解，比如对于坐标轮换法，如果椭圆簇的长短轴和坐标方向一致，迭代 $n$ 步可以收敛到极小值，共轭方向相当于作用于 $\boldsymbol x$ ，使得 $f(\boldsymbol x)$ 在新的坐标系下和坐标方向一致。可见共轭方向方法重点就在于共轭方向的构建上。一种简单的构建的方式是求 $\boldsymbol A$ 的特征向量，但是对于大规模的优化问题，特征向量求解很耗时。还有一种采用改进的Gram-Schmidt正交方法得到共轭方向，然而这种方法也很耗时，且需要存储整个向量。基于这些问题，Powell提出了加速的方法。

Powell方法

Powell与1964年提出方向加速法，也是一种共轭方向法，针对的问题也是考虑正定二次函数的无约束最优化问题。Powell方法主要有三部分构成，即基本搜索、加速搜索和调整搜索方向。

基本搜索：包括从基点出发沿着已知的 $n$ 个线性无关的搜索方向进行一维搜索,确定一个新的基点;
加速搜索：指这将第一轮起点和新确定的基点相连构成新的方向，进行一维搜索使得函数值下降；
调整搜索：将这一轮方向组的第一个方向去掉,新的方向补充在最后构成新的方向组，进行下一轮迭代。

图1 Powell方法示意图

如图2所示，针对坐标轮换方法中提到几个问题，Powell方法收敛速度更快。对于具有脊线的问题也能得到优解。然而Powell方法对于维度 $n<20$ 的能得到满意的结果，高维度的优化问题并不合适，其次不用说对于高维的复杂函数，就是对于二次函数，Powell方法也可能无效。因为算法中，没有衡量过后续的 $n$ 个搜索方向是否变成线性相关。一旦搜索方向存在相关关系，就不能形成共轭方向，从而构不成 $n$ 维空间，导致后续的迭代在降维的空间中进行，发生退化，得不到极小值点。为此Powell又进行了改进。

图2 Powell方法实例

Algorithm 1 Powell方法

function [x_min,f_min] = ConjugateDirectionMethod(func,x0,options)
%Powell
if nargin<3
    options.tol = 1e-12;
    options.iterNum = 1000;
    options.bracketMethod = '';
    options.linearSrcMethod = '';
    options.plot2.Flag = 0;
    options.plot2.x = [];
    options.plot2.y = [];
    options.plot2.z = [];  
end
tol = options.tol;
iterNum = options.iterNum;

plot2 = options.plot2;
if length(x0)~=2
    plot2.Flag = 0;
end

x_min = x0;
f_min = func(x0);

E = eye(length(x0));
%E = [1,0;-1,1];
xk = x0; 

f_pre = func(xk);
f = f_pre+1e10;

if plot2.Flag == 1 
    figure,subplot(1,2,1),axis equal, hold on;
    contourf(plot2.x,plot2.y,plot2.z,30,'linestyle','-')
    colormap('jet');
    tempf =f_pre;
end

while(iterNum)
    x1k = xk;
    for i=1:1:length(x0) 
        d = E(:,i);
        lamdaFuncH = @(lamda)(func(xk+lamda.*d));
        [a,b,c] = bracketAdvanceBack(lamdaFuncH,0,0.01);
        lamda = GoldSection(lamdaFuncH,a,c,1e-12);
        xk1 = xk + lamda.*d;
        f =func(xk1);
        if plot2.Flag == 1 
            tempf = [tempf,f];
            subplot(1,2,1),plot([xk(1),xk1(1)],[xk(2),xk1(2)],'-o','LineWidth',2);
            subplot(1,2,2),plot(tempf,'-b.','LineWidth',2); grid on;
            axis([0,60,-10,func(x0)]);
            xlabel('Step');
            ylabel('Objective Function Value');
        end
        xk = xk1;
        iterNum = iterNum - 1;
    end
    
    d = xk-x1k;
    
    lamdaFuncH = @(lamda)(func(xk+lamda.*d));
    [a,b,c] = bracketAdvanceBack(lamdaFuncH,0,0.01);
    lamda = GoldSection(lamdaFuncH,a,c,1e-12);
    xk1 = xk + lamda.*d;
    f =func(xk1);
    if plot2.Flag == 1
        tempf = [tempf,f];
        subplot(1,2,1),plot([xk(1),xk1(1)],[xk(2),xk1(2)],'-o','LineWidth',2);
        subplot(1,2,2),plot(tempf,'-b.','LineWidth',2); grid on;
        axis([0,60,-10,func(x0)]);
        xlabel('Step');
        ylabel('Objective Function Value');
    end
    xk = xk1;
    iterNum = iterNum - 1;
    
    if abs(f-f_pre)<tol||iterNum == 0
            x_min = xk;
            f_min = f;
            break;
    else
        f_pre = f;
    end    
    
    E(:,1) = [];
    E = [E,d]
    
end

Powell改进方法

为了避免Powell方法中退化问题，Powell进行了改进。在构成的 $K+1$ 环基本方向组时，首先判断前一环的基本方向组是否需要更换;还要进一步判断前一环的原基本方向组中某一方向作为一维搜索函数值下降量最大,去掉该方向后再将新的方向步入最后。保证第 $K+1$ 环基本方向组时线性无关的并最接近共轭。

图3 Powell改进方法示意

具体步骤为：

给定初始点,选取 $n$ 个线性无关的方向组(初始为坐标单位向量);

从这一轮的初始点出发,顺次沿方向进行一维搜索,得到 $n$ 个点;

以最后一点为起点,沿最后一点和第一个点的连线方向移动,最后一点到第一个点的距离。这里就得到三点,即起点、终点和反射点,对应的坐标和函数值我们记作:
$F_0 = f(\boldsymbol x_0^k),F_2 = f(\boldsymbol x_n^𝑘),F_3 = f(\boldsymbol x_{n+1}^k)$

计算各中间点的函数值,以及下降量,求得下降量最大值 $\Delta_m$ 以及对应的方向 $\boldsymbol d_m$ ;

判断 $F_3<F_0$ 和 $(𝐹_0 − 2𝐹_2 + 𝐹_3)(𝐹_0 − 𝐹_2 − \Delta_m)^2 <$ $0.5\Delta_m(𝐹_0 − 𝐹_3)^2$ 来确定是否要对原方向组进行替换;

不满足条件,则下一轮迭代仍用原方向组,并以终点和反射点函数值小者最为下一轮的迭代始点;

满足条件,则将 $\boldsymbol d_m$ 去除,起点和终点的连线方向放入方向组的最后作为下一轮的迭代方向组,而下一轮迭代的起点为以终点为起点沿连线方向一维搜索的最优点。

判断终止条件,满足终止,反之进行下一轮迭代。

Algorithm 2 Powell改进方法

function [x_min,f_min] = PowellImprovedMethod(func,x0,options)
%Powell
if nargin<3
    options.tol = 1e-12;
    options.iterNum = 1000;
    options.bracketMethod = '';
    options.linearSrcMethod = '';
    options.plot2.Flag = 0;
    options.plot2.x = [];
    options.plot2.y = [];
    options.plot2.z = [];
end
tol = options.tol;
iterNum = options.iterNum;

plot2 = options.plot2;
if length(x0)~=2
    plot2.Flag = 0;
end

x_min = x0;
f_min = func(x0);

E = eye(length(x0));

xk = x0;

f_pre = func(xk);
f = f_pre+1e10;

if plot2.Flag == 1
    figure,subplot(1,2,1),axis equal, hold on;
    contourf(plot2.x,plot2.y,plot2.z,30,'linestyle','-')
    colormap('jet');
    tempf =f_pre;
end

while(iterNum)
    x1k = xk;
    deltaM_max = -inf;
    di = 1;
    for i=1:1:length(x0)
        d = E(:,i);
        lamdaFuncH = @(lamda)(func(xk+lamda.*d));
        [a,b,c] = bracketAdvanceBack(lamdaFuncH,0,0.01);
        lamda = GoldSection(lamdaFuncH,a,c,1e-12);
        xk1 = xk + lamda.*d;
        f =func(xk1);
        if plot2.Flag == 1
            tempf = [tempf,f];
            subplot(1,2,1),plot([xk(1),xk1(1)],[xk(2),xk1(2)],'-o','LineWidth',2);
            subplot(1,2,2),plot(tempf,'-b.','LineWidth',2); grid on;
            axis([0,60,-10,func(x0)]);
            xlabel('Step');
            ylabel('Objective Function Value');
        end
        
        deltaM = func(xk) - f;
        if deltaM_max<deltaM
            deltaM_max = deltaM;
            di = i;
        end
        xk = xk1;
        iterNum = iterNum - 1;
    end
    
    
    x2k = 2.*xk-x1k;
    f0 = f_pre;f2 = f;f3 = func(x2k);
    
    if (f3<f0&&(f0-2*f2+f3)*(f0-f2-deltaM_max)^2<0.5*deltaM_max*(f0-f3)^2 )
        d = xk-x1k;
        lamdaFuncH = @(lamda)(func(xk+lamda.*d));
        [a,b,c] = bracketAdvanceBack(lamdaFuncH,0,0.01);
        lamda = GoldSection(lamdaFuncH,a,c,1e-12);
        xk1 = xk + lamda.*d;
        f =func(xk1);
        E(:,di) = [];
        E = [E,d];
    else
        if f2<f3
            xk1 = xk;
            f =func(xk1);
        else
            xk1 = x2k;
            f =func(xk1);
        end
    end
    if plot2.Flag == 1
        tempf = [tempf,f];
        subplot(1,2,1),plot([xk(1),xk1(1)],[xk(2),xk1(2)],'-o','LineWidth',2);
        subplot(1,2,2),plot(tempf,'-b.','LineWidth',2); grid on;
        axis([0,60,-10,func(x0)]);
        xlabel('Step');
        ylabel('Objective Function Value');
    end
    xk = xk1;
    iterNum = iterNum - 1;
    
    if abs(f-f_pre)<tol||iterNum == 0
        x_min = xk;
        f_min = f;
        break;
    else
        f_pre = f;
    end
    E
end

Powell改进的方法虽然考虑了每轮的方向组的线性相关性，但是如果初始方向给的是单位坐标向量，很可能一直都是坐标方向向量，退化成坐标轮换法，对于存在脊线的优化问题，依然存在问题。

最后编辑于：2019.03.05 23:32:37

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 213,864评论 6赞 494
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,175评论 3赞 387
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 159,401评论 0赞 349
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,170评论 1赞 286
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,276评论 6赞 385
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,364评论 1赞 292
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,401评论 3赞 412
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,179评论 0赞 269
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,604评论 1赞 306
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,902评论 2赞 328
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,070评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,751评论 4赞 337
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,380评论 3赞 319
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,077评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,312评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,924评论 2赞 365
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,957评论 2赞 351

无约束优化方法-直接方法（Powell与改进Powell）

共轭方向

Powell方法

Powell改进方法

推荐阅读更多精彩内容