4.1 共轭方向法及其改进在线视频

同学们好

我是天津大学电气自动化与信息工程学院的老师

杨挺

今天我们来学习第四章无约束优化方法

数学模型

minf(X)

没有约束

方法含义

第一

解决工程中无约束优化问题

第二

我们通过学习这个方法

是我们后续的约束优化方法的一个基础

即将约束优化问题可以转化为无约束的优化问题

来进行求解

迭代公式

同样是我们之前所讲的

X(k+1)等于Xk加上αkSk

我们这里边的下一次迭代的点

通过上一次迭代的点和一个正确的方向和合适的步长

来进行搜索

我们还是步步搜索

步步逼近

最后逼近我们这里边的极值点

使每一次都会让f(X(k+1))小于f(X(k))

那么这里边呢我们方法呢可以分为两大类

第一类是直接法

只利用目标函数和目标函数的值而不去求导

比如说我们这里的坐标轮换法或者Powell法

或者是单纯形法

第二类是间接法

就或者称为解析法

利用目标函数值以及梯度

或者是海森矩阵我们的一阶导或者二阶导

来进行求解

那么所代表性的方法有包括梯度法

共轭梯度法

牛顿法或者是DFP法

那么对于直接法来说呢

它的优点呢是适用性广

可靠性高

但是呢它的收敛速度呢一般呢是比间接法要低

那么间接法呢收敛速度呢比直接法要高

但是间接法呢会用到了函数的梯度

或者是海森矩阵这样的一些函数的性状

所以它的计算呢可能会更复杂

我们首先来看一个基本的概念

共轭方向

什么是共轭方向呢

在整个优化搜索中

我们说了共轭方向的概念起着重要作用

一些有效的方法都是以共轭方向为搜索方向

而形成的

看一个例子

这是一个函数的等值线

这是我们的X*

那么我们说了

在这里边呢随便取一点X0

那么我随便找一个方向S1

X0找一个方向S1

那么这里边我总能跟这个等值线

有一个等值线相切

对不对

因为我们是正圆

那么对于这个切点处呢

实际上我们是切点处

我去做这个S1的一个什么

垂直线

那既然是跟它相切的话

那这个S1应该就是它的什么

切线 对不对

做切线做法线

既然是正圆那这个法线是不是一定指向X*

再看一个图

更一般情况我们说了

在X*点处

它等线呈现为椭圆或椭球素

这是我们的X*

一样随便取点X0

取X0以后呢随便找一个方向S1

那一样你也肯定可以找到一个等值线跟它相切的

这是X1同样再找一个X0

我同样沿着S1方向

我一定还能找到另外一个同心椭圆

然后呢找它相切这一点

我们的X2 X1X2连线的这个方向

S2方向是指向X*的

S1与S2是共轭方向

我们先给大家一个感性认识

这是说S1S2是共轭方向

我们下面来看看到底什么是共轭方向

共轭方向定义

对于二次函数

我们给到二次函数

f(X)等于1/2XAX加上BT转置X加C

我们这里什么

因为是二次函数吗

是多维的

不像上一章我们讲的是一维的

我们既然多维的话

那么X一定是一个列向量

那么它既然是列向量的话

你就不能写X的平方了

是不是

两个列向量不能相乘

对吧

乘出来没什么东西

所以必须什么

左乘一个右乘一个

X 找到这一个方向

随便找一个方向S0这个方向

找到一个合适的步长

a0S0

那我就有X1

那我怎么样找到这个X1找一个合适的S1这方向

让S1方向就能够从X1直接指向X*

我们来看一看

既然这个方向是正确的话

那只要找到合适的步长

a1就可以去指向X*了

迭代第一步X0用a0S0

做第一步找到了X1

那么X1呢我们只要找到什么

合适的方向S1和合适的步长X1

就能下一步找到X*就两步

所以说这个方向S1很重要

只要找那个好的方向

S1就能找到对应的X*

那到底这个S0和S1有什么关系呢

能让我们这么快速的去找到X*

那我说既然是这样的话

那我现在求S1 和a1

好那我就什么

X*就等于什么

X1加上α1S1

那有这么公式以后

我们看一下

首先需要对于这个函数的梯度

∇f(X)等于AX加B 那因此说呢

∇f(X*)等于AX1加B让它等于0

因为你的X*是极值点

我们说极值点的梯度等于0

所以说∇f(X*)等于AX1加上Aα1S1加B

把X*带进去整理一下

AX1加B不就是我的∇f(X1)

X1点处的梯度吗

那好了

我这样的话

我两边都乘以S0

变成S0∇f(X1)再加上a1S0转置AS1等于0

都乘以一个转置

保证这里边的矩阵都是可乘的

这是我的什么

-∇f(X1) 那么这样

因为S0与∇f(X1)是正交的

而且是什么

a1不等于0

S0转置乘以a乘以S应该是等于0的

所以说S0转置AS1是等于0的

设A为n乘以n阶的实对称正定阵

如果有两个n维非零向量S1与S2

若满足S1乘以A乘以S2等于0

那么我们称这两个向量S1与S2

是关于A的共轭的方向

如果说非零向量组S1S2和Sk满足

任意两个都满足Si转置乘以A乘以Sj等于0

那么我们说向量组S1S2到Sk

是关于矩阵A的共轭向量

我们的海森矩阵就是一个n乘以n阶的

而且是一个实对称正定阵

那么同样对于实对称正定阵

还有什么特殊的 单位阵

那么对于单位阵A等于I的时候

S1转置乘以A乘以S2等于0

A即使不等于单位阵

那么我S2经过矩阵A的一个转换变成S2'

等于A乘S2与S1是正交的

所以说正交是共轭的一个特例

共轭是正交的一个推广

看一个例子

已知S1等于3,0

S2等于2，-6

A等于6，2，2，3

问S1S2关于A是否共轭的 判断一下

S1S2是不关于A共轭的

这怎么做

根据定义是不是就可以了

很简单

就是S1转置乘以A乘以S2看是不是等于0

如果等于0就可以了

那就是什么

3,0然后呢是6，2，2，3乘以2，-6

乘起来等于0

那就是满足共轭条件S1S2是关于A共轭的

多问一步

又找了两个方向

A不变还是6，2，2，3

找到S1S2这两个

问你这时候S1S2是不是关于A

是不是也是共轭的

我们再算一算S1S2

S1转置乘以AS2等于0,3 6,2,2,3

-3,2乘起来

0,3 14,0乘起来等于0

也是共轭的

所以说什么

关于矩阵A的共轭向量S1和S2并不是唯一的

共轭方向的性质

我们这里简单的介绍一下

对于它的这个数学证明

同学们可以去参考相关的书籍

去看一下数学证明

设A为n乘n阶的实对称正定阵

如果S1S2到Sn为关于矩阵A共轭的

n个非零向量组

则这一向量组是什么

是线性无关的

这是它的第一个性质

推论 在n维空间中相互共轭的非零向量个数

不会超过n个

第二 设向量Si是一组线性无关的非零向量

则可构造出n个非零向量Si i等于1,2,n

满足什么呢

S2转置ASj等于0

即共轭向量由线性无关向量构成

推论可由坐标轴方向来构造共轭向量

X轴一定表示不了Y轴

Y轴一定表示不了X轴

第三

如果S1S2Sn为关于矩阵A共轭的

n个非零向量

则对于正定的二次函数

f(X)等于1/2的X转置AX加上B转置X加C

从任意一点X0出发

依次沿Si方向进行一维搜索

至多n次便可收敛到极小点X*

所以说呢二次共轭的这个方向呢具有二次收敛性

它有二阶的收敛速度

我们来看看看算法收敛性

也就是说如果说limX(k+1)减去X*

比上Xk减去X*的β倍取它的这个摩

是等于一个在0到1之间的一个小的数的话

如果存在β大于零

则上式是成立的话

第一个

如果当β等于1的时候

我们认为算法具有线性的收敛性

或具有线性的收敛速度

如果β是等于2的话

我们称它为具有二阶的或者二次的收敛速度

那么如果β是在1和2之间

算法具有超线性的收敛性

这是我们说的算法的收敛性的定义

那么以二维正定的二次函数为例

在第k轮迭代时候

X0k随便找一个X2

然后呢找S1找到合适的α1S1

找到合适这一点X1k然后在这一点再进行迭代

沿着S2方向进行迭代时候呢

α2S2证回X2 我们说什么

跟我们刚才最开始讲的共轭方向时候一样

连接S0和S2

我们就可以来找到一个共轭方向S

我们从S0沿着一个方向S1

找到合适步长α1S1

然后呢找到Xk然后呢再去做

找到X2k

连接X0和X2就可以找到一个X*

我们来看一看

由于S等于S2k减去X0k那我们画一画

我们把坐标原点标出来

坐标原点零

然后呢是S0S2

那么S应该是什么

那就是S2方向减去S0方向

那么实际上我就想证明什么

想证明S与S2是共轭就可以了

我们看看怎么证明

因为二次函数f(X)1/2X的转置乘以A乘以X加上B转置乘以X加C

它的梯度是AX加B

在X2k点处呢∇f(X2)等于AX2加B

在X0的梯度等于∇f(Xk)等于AX0K加B

这其实跟我们刚才证明是思路是一样的

那么我们两边同样都是左乘S2

S2转置乘以∇f(X2k)S2转置乘以∇f(X0k)

X2这个f(X2)是正交的

所以说这个是等于0的

这个也是等于0的

减一下

完了以后

变成了S2转置A这个式子

刚好就是S2转置乘以A乘以S是等于0的

所以说什么

证明了我这里边的S与S2是共轭的

满足共轭条件

同理可推广到n维 n维沿n的线性无关的方向

进行一维搜索

X0k与Xnk连线的向量即为产生的共轭向量

Powell科学家呢他提出了共轭方向法以及

改进的方法

我们看看共轭方向法

是这个基本概念是什么

第一基本思想

找线性无关的那最基本的最简单线性无关是什么

以坐标轴方向为基础产生的共轭方向

以共轭方向作为所有方向

反复迭代逼近X*

那就是什么

我以坐标轴为基本的产生共轭方向

然后呢我进行迭代

迭代步骤

第一在给定的初始点X0

轮数k k等于1

X0k等于X0 精度ε

令什么呢

坐标轴方向Xik等于ei ei等于什么呢

固定其他维的坐标轴

这维解放出来

其他轴都等于0

然后呢如此这样循环

i是维数

解放第i维

固定其它的n-1维 然后呢在第i维上去搜索

那么具体方法呢就是

输入n乘以n阶的单位阵

迭代步骤

进行一轮一维搜索以后

X0k呢是对应的是α1

通过α1k和S1k呢变成S1k然后呢

再进行方向二α2和S2这个方向呢

做X2k一直这样延续下去

到αnkSnk一步一步一步进行了n步

进行了n步以后呢到这一轮的最后一个Xnk

那么连接X0与Xnk呢构造出
第一个共轭方向S(n+1)k

那么S(n+1)k的方向呢实际上

就是Xnk减去X0k

实际上画个图呢很简单

画个图就是这样子的

原点

这是我的X0k

然后呢这是我的Xnk我X0k和Xnk连线呢

就是我的新的方向S(n+1)k

从Snk出发

沿着S(n+1)k呢进行一维搜索

得到这一轮的终止点X(n+1)k

实际上也是下一轮开始的起始点

就是完成一轮的一维搜索

如果说X(n+1)k减去X0k小于等于ε的时候

那么则X*呢就等于X(n+1)k

否则呢淘汰S1k增加S(n+1)k

构成(n+1)k轮的新的搜索方向

看个动画演示就是这样的

上一次方向是S1S2S3S4Sk

最初的第一次什么

就是坐标轴嘛X1轴X2轴X3轴X4轴到Xk轴

然后呢做一轮以后呢会产生一个新的方向

然后呢我去除第一个老的方向

把新的方法增加下来

就变成一个新的这一轮

还保证是n个方向

如此这样的反复一个一个增加一个新的

去掉一个老的

如此这样的反复呢去构造这样的方向

那么每一次这个方向呢就是共轭方向的话

那么说如果说你的函数慢慢接近于二次型的话

那么它的速度会提升上去

通式呢就是S(k+1)等于S(i+1)k

第六 X(n+1)k给到X0(k+1) 什么意思

我上一轮的第k轮结束的那个终止点就是

我k+1轮的初始点

利用k等于k+1

然后返回

如此这样迭代

这就是我们的共轭方向法

那么这里边呢对于坐标轴这样的轮换法

或共轭方向法出现一个问题

什么问题

我们看一下

假如说这是三个

X1X2和X3这三维的

X*在这里

沿着X1轴做了一次

对吧 从这开始

沿着X1轴做到X1

然后呢搜索X1

沿着X2轴搜索到X2

然后呢沿着X3轴去搜索到X3

好了 沿着三个坐标轴搜索完一圈

这一轮不是搜索完了吗

然后呢我连接X0和X3不就产生一个新的方向

沿着这个方向找到一个合适的步长

就这一轮我结束那个点

连线 找到合适的步长S

做到最后那个α4S4到了X4的1

就是我这一轮结束了

这一轮结束这个点

就是下一轮初始点

就是X4（1）这个点 那下一步怎么办

是不是掉这个方向

对不对

删除哪个 删除第一个方向

那好了

我们来看一个

把这个我把它做得更直观一点

那么删除完以后

那我下一轮开始

第一步是不是沿着X2方向走了

沿着X2的方向一步

S3方向两步

然后再沿着这个方向是吧

你看这是123

下一次也是123

找到了S3

然后呢连接这一步的初始点和这一步的终止点

然后连接起来新的方向

再去找一下 找到新的点

就这样一步步反复

存在什么问题呢

你看 我们说了

在这里我们每一轮去找的时候的我们方向

应该是什么 线性无关的

但是第一次肯定线性无关

为什么

你沿着坐标轴

X1轴X2轴X3轴三个轴肯定是线性无关的

没有问题 是能做下去的

但是如果你找到这个S4这个点

找S4这个方向以后

如果说α1约等于0

这个非常小

这一步前进得非常小

而你下一步的时候呢

又是什么

淘汰是这个方向

那是不是下一步这个方向就相对什么

这个不起作用了

它不起作用意味着什么

就相当于这一点往前走

这个地方非常小

等于没走

没走的话 那相当于什么

是不是相当于是这个方向是由谁决定的

是不是就由这个方向和这个方向决定

这两方向决定了

由它俩决定是不是

它S4这个方向就跟S2和S3是线性相关了

你就把这方向去掉以后实际上变成什么了

三个方向 S2S3和S4这三个方向

而这三个方向S4又由它俩所构成

被什么 线性相关了

一旦线性相关

你的共轭方向法就失效了

没法进行下去

因为你线性相关的你没法进行下去了

所以会有这个问题

那么则构成什么

我们来看一个图

应该是 你的S4方向和它是线性相关的

S4什么线性相关

其实无非就是什么

它能由它俩表示 能够构成三角形

即S2S3S4是线性相关

那你的共轭方向就失效了

导致降维搜索

那么既然降维 那么你的什么

你的程序就停止了

就没有办法去搜索了

所以你的共轭方向法就失效了

那么正是由于这样的一个问题

Powell提出的叫做改进的或者是

修正的共轭方向法 我们称为是Powell法来纪念他

那么基本思想呢其实很简单

共轭方向法提出以后

Powell通过大量的实验发现有这样的问题

我只是来解决这个问题就OK了

那怎么办呢

基本思想

与上述未改进的共轭方向法基本的思想是相同的

不同点呢只有这么一点是什么

在k+1轮中呢是否选用新的方向

而删除老的方向

需要判断

并且呢要判断什么

到底删除哪一个老的方向

如果说你说首先我需要保留新的方向

我的新方向非常好 需要保留

那我就要删除老的方向

那么如果是要删除老的方向

那要判断 也不删除最开始那个

很机械总删除第一个

而是要看一看这里边哪个方向是要被删除的

所以说呢 第二步

不一定淘汰S1k

不一定淘汰上一轮的最初的方向

淘汰哪一个也要进行判断

目的 避免搜索方向是线性相关的

出现退化现象导致降维

就是避免这样的一个问题

第二 共轭方向Snk的选取与淘汰方向的判定

假设我的F1等于FX0k F2等于FXnk

F3等于FX(n+1)k

我做Δmk等于max的1到n

我两两相减到最大那个

然后呢我这里解释一下

再重新强调一下

X0k呢是第k轮的初始点

Xnk呢是第k轮的n次搜索的最小点

X(n+1)k呢是第k轮的X0关于Xk的一个映射点

X0 Xnk X(n+1)k 映射点

什么意思

沿着Sk S(n+1)k这个方向

X0关于它的一个映射

实际上就是它俩等长

等长 并且是沿这个方向的一个映射点

那就是这个向量

那么X(n+1)k呢就等于Sk加上Xnk减去X0k

很简单所以说呢

S(n+1)k呢把它括号打开

也就是二倍的S(n+1)k减去S0k等于它

那么ΔMk呢

就是第k轮n次一维搜索中的函数

FX值的最大缩减量 就是这样的一个值 ΔXk

Δik Δ(i+1)k 那Powell提出

如果说f3小于f1

并且呢f1加f3减去2倍的f2

乘以f1减f2

减去Δmk的平方呢是小于1/2ΔmkF1减F3的平方

如果说满足这两个式子

我们就选用你新构造出来这个方向

并且淘汰谁呢

淘汰与Δmk相应的方向Smk所构成(k+1)轮方向

就是说如果满足这个式子

那这两个问题我们都解决

第一个问题我们要这个新构成的方向

第二个问题我们淘汰谁

淘汰的方向就是与什么

你最大变化量那个Δmk相应的方向Smk

则最后构成的是(k+1)轮的迭代方向

那你说第k轮是SkS1kS2kS3k到Sm(k-1)到Smk等等

我们这边专门把这个东西提出来了

那你下一轮呢怎么办呢

不是淘汰这个了

是这样一个式子

那么怎么去对应呢

前面这几个都还保留

我只删除了这个

我把这个删除了

并不是每次都删除这个得很机械的

然后呢后边呢对应过来

并且呢保留什么

以前这个方向

同样构成第(k+1)轮n个方向

我们看一下通式

就这个公式

Si(k+1)等于Sik

i小于m 那么Si(k+1)等于Sik (i+1)k

i大于等于m 这是如果是满足

那么如果不满Powell条件

则我不变

我仍然用第k轮的迭代方向

作为第(k+1)的迭代方向

即不选用S(n+1)k同时我又不变

那我还是原来的

那我们看它的步骤

第一个

给定初始点X0

轮数k+1

X0k等于S0

精度 ε1和ε2

第二 令Sik等于ei

就是什么

我开始选的是坐标轴的方向

让ei等于0，1，然后到0

就是每一轮每一次呢我固定其他的选择

一个坐标轴的方向

第三 从X0k出发

分别沿Xik进行一轮一维搜索

依次求得极小点

Sik等于Sik加上αkSik等于它

计算Δmk等于max的fX(i-1)k减去FXik

找最大那个 得到相应的方向Smk的方向

第四 若Xnk减去X0k小于ε

或者说什么呢

点距准则

值差准则 对吧

如果是这样子的话

是不是就可以收敛了

那么则X*对应Xnk就收敛了

就结束了

否则转到下一步

构造共轭方向

连接X0k 第k轮的初始点和第k轮的终止点

构造出第一个共轭方向S(n+1)k

S(n+1)k等于Xnk减去X0k

求映射点X(n+1)k等于2倍的Xnk减去X0k

我们刚才讲的

找这个点以后呢计算什么

f1f2和f3

然后呢这f1f2f3干嘛用的

就是去做Powell的判定条件

对吧 然后若满足Powell判定条件满足它

则我们选用这个新的方向

剔除于ΔMk所对应的那个方向

转第六步

不满足则转第七步

如果不满足怎么办

仍然用原来的方向

第六步呢是满足的话

从Xnk出发

沿它做一维搜索得到极小值X

X等于Xnk加上αnk S(n+1)k

然后呢我令X0(k+1)等于X

然后呢进行方向的选取

删除一个第m个方向

增加一个方向

令k等于k+1

然后返回第三步

如果不选择这个方向

那么仍选用原来k个方向

第七步 就是说不满足Powell条件

则不选用S（n+1）k仍然用第k轮的搜索方向

Si(k+1)等于Sik

i等于1到n

如果f2小于f 3时

选取X0(k+1)等于Xnk

如果大于10呢

X0(k+1)等于Xn(k+1)k

然后呢进行下一轮

就k=k+1

轮数增加一位

然后呢返回第三步

这是我们的Powell法或者我们的共轭方向法

Powell法比共轭方法要复杂一点

就是避免了函数的降阶

避免了这个搜索降阶退化

那么这里边呢我给大家的步骤

那么程序框图以及例题

那我们在我们的书里面

我们教材里面有详细的讲解

同学们下面可以进行自学