tao函数

tao函数

-

2023年2月10日发(作者：司考教程)

目标函数极值求解的几种方法

题目：2

2

2

1

122minxx，取初始点Tx3,11，分别用最速下降法，牛顿法，

共轭梯度法编程实现。

一维搜索法：

迭代下降算法大都具有一个共同点，这就是得到点

kx后需要按某种规则确定一个方

向

kd，再从kx出发，沿方向kd在直线（或射线）上求目标函数的极小点，从而得到kx

的后继点

1kx，重复以上做法，直至求得问题的解，这里所谓求目标函数在直线上的极小

点，称为一维搜索。

一维搜索的方法很多，归纳起来大体可以分为两类，一类是试探法：采用这类方法，

需要按某种方式找试探点，通过一系列的试探点来确定极小点。另一类是函数逼近法或插

值法：这类方法是用某种较简单的曲线逼近本来的函数曲线，通过求逼近函数的极小点来

估计目标函数的极小点。本文采用的是第一类试探法中的黄金分割法。原理书上有详细叙

述，在这里介绍一下实现过程：

⑴置初始区间[

11

,ba]及精度要求L>0,计算试探点

1



和

1

，计算函数值

1

f和

1

f，

计算公式是：

1111

382.0aba，

1111

618.0aba。令k=1。

⑵若Lab

kk

则停止计算。否则，当

K

f>

k

f

时,转步骤⑶;当

K

f



k

f

时,

转步骤⑷。

⑶置

kk

a

1

,

kk

bb

1

,

kk



1

,

1111

618.0





kkkk

aba

,计算函数值

1k

f

,

转⑸。

⑷置

kk

aa

1

,

kk

b

1

,

kk



1

,

1111

382.0





kkkk

aba

,计算函数值

1k

f

,

转⑸。

⑸置k=k+1返回步骤⑵。

1.最速下降法

实现原理描述：在求目标函数极小值问题时,总希望从一点出发,选择一个目标函数值

下降最快的方向,以利于尽快达到极小点,正是基于这样一种愿望提出的最速下降法,并且

经过一系列理论推导研究可知,负梯度方向为最速下降方向。

最速下降法的迭代公式是

k

k

kkdxx1，其中

kd是从kx出发的搜索方向，这里

取在点

kx处最速下降方向，即kkxfd。

k



是从kx出发沿方向kd进行的一维搜索

步长，满足

kkk

k

kdxfdxf





0

min

。

实现步骤如下：

⑴给定初点

nRx1，允许误差

0，置k=1。

⑵计算搜索方向

kkxfd。

⑶若

kd

，则停止计算；否则，从kx出发，沿方向kd进行的一维搜索，求

k



，

使

kkk

k

kdxfdxf





0

min

。

⑷

k

k

kkdxx1，置k=k+1返回步骤⑵。

2.拟牛顿法

基本思想是用不包括二阶导数的矩阵近似牛顿法中的Hesse矩阵的逆矩阵，因构造近

似矩阵的方法不同，因而出现了不同的拟牛顿法。

牛顿法迭代公式：

k

k

kkdxx1，

kd是在点kx处的牛顿方向，

kkkxfxfd1

2，

k



是从kx出发沿牛顿方向kd进行搜索的最优步长。用不包括

二阶导数的矩阵

k

H近似取代牛顿法中的Hesse矩阵的逆矩阵1

2

kxf，

1k

H需满足拟牛

顿条件。

实现步骤：

⑴给定初点

1x，允许误差

0。

⑵置

n

IH

1

（单位矩阵），计算出在

1x处的梯度1

1

xfg，置k=1。

⑶令



kk

kgHd。

⑷从

kx出发沿方向kd搜索，求步长

k



，使它满足kkk

k

kdxfdxf





0

min

，

令

k

k

kkdxx1。

⑸检验是否满足收敛标准，若

1kyf，则停止迭代，得到点1



kxx，否则进

行步骤⑹。

⑹若k=n，令

11kxx，返回⑵；否则进行步骤⑺。

⑺令

1

1





k

k

xfg，kkkxxp1，



kk

kggq

1

，







k

k

Tk

k

Tkk

k

kTk

Tkk

kkqHq

HqqH

qp

pp

HH

1

，置k=k+1。返回⑶。

3.共轭梯度法

若

kddd,,,21是nR

中k个方向，它们两两关于A共轭，即满足

kjijiAddjTi,,1,;,0，称这组方向为A的k个共轭方向。共轭梯度法的基本思想

是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向

进行搜索，求出目标函数的极小点，根据共轭方向的基本性质这种方法具有二次终止性。

实现步骤如下：

⑴给定初点

1x，允许误差

0，置

11xy，11yfd，k=j=1。

⑵若

jyf

，则停止计算；否则，作一维搜索，求

j

，满足

jjj

j

jdyfdyf





0

min

，令

j

j

jjdyy1。

⑶若nj，则进行步骤⑷，否则进行步骤⑸

⑷令

j

j

jjdyfd11，其中



2

2

1

j

j

jyf

yf











，置j=j+1，转⑵。

⑸令

11nkyx，11kxy，11yfd，置j=1，k=k+1，转⑵。

4.实验结果

用以上三种方法通过Matlab编程得到实验数据。初始值

Tx3,11。迭代精度

sum(abs(x1-x).^2)<1e-4。

最速下降法拟牛顿法共轭梯度法

第一次迭代

结果

2x

第二次迭代

结果

3x

2.

1.

第三次迭代

结果

4x

2..

第四次迭代

结果

5x

实验结果分析：

由上表格可以看到最速下降法需要四次迭代实现所要求的精度，拟牛顿法和共轭梯度法需

要三次。

程序：

%精确一维搜索法的子函数,0.618（黄金分割）法,gold.m

%输入的变量x为初始迭代点是二维的向量,d为初始迭代方向是二维的向量

%输出变量是在[0,10]区间上使函数取得极小值点的步长因子

functionalfa=gold(x,d)

a=0;b=10;tao=0.618;

lanmda=a+(1-tao)*(b-a);

mu=a+tao*(b-a);alfa=lanmda;%初始化

f=((x(1)+alfa*d(1))-2)^2+2*(x(2)+alfa*d(2)-1)^2;%目标函数

m=f;alfa=mu;n=f;

while1

ifm>n

ifabs(lanmda-b)<1e-4

alfa=mu;return

else

a=lanmda;lanmda=mu;m=n;

mu=a+tao*(b-a);alfa=mu;

n=((x(1)+alfa*d(1))-2)^2+2*(x(2)+alfa*d(2)-1)^2;

end

else

ifabs(mu-a)<1e-4

alfa=lanmda;return

else

b=mu;mu=lanmda;n=m;

lanmda=a+(1-tao)*(b-a);alfa=lanmda;

m=((x(1)+alfa*d(1))-2)^2+2*(x(2)+alfa*d(2)-1)^2;

end

end

end

%梯度子函数，tidu.m,输入的变量为二维的向量，返回梯度在x处的数值向量

functiong=tidu(x)

%待求解的函数

f=(x(1)-2)^2+2*(x(2)-1)^2;

%求函数的梯度表达式

g=[2*(x(1)-2)4*(x(2)-1)];

x1=x(1);x2=x(2);

%最速下降法极小化函数的通用子函数zuisu.m

%输入变量为初始的迭代点，输出变量为极小值点

functionx0=zuisu(x)

%判断梯度范数是否满足计算精度1e-4的要求.是,标志变量设为1，输出结果;

%否,标志变量设为0

ifsum(abs(tidu(x)).^2)<1e-4

flag=1;x0=x;

else

flag=0;

end

%循环求解函数的极小点

whileflag==0

d=-tidu(x);a=gold(x,d);x=x+a*d

%判断梯度范数是否满足计算精度的要求.是,标志变量设为1，输出结果;

%否,标志变量设为0，继续迭代

ifsum(abs(tidu(x)).^2)<1e-4

flag=1;x0=x;

else

flag=0;

end

End

%拟牛顿法极小化函数的通用子函数，gonge.m

%输入变量为初始的迭代点，输出变量为极小值点

functionx0=ninewton(x)

%判断梯度范数是否满足计算精度的要求.是,标志变量设为1，输出结果;

%否,标志变量设为0，继续迭代

ifsum(abs(tidu(x)).^2)<1e-4

flag=1；x0=x;

else

flag=0;

end

%初始的H矩阵为单位矩阵

h0=eye(2);

%循环求解函数的极小点

whileflag==0

%计算新的迭代方向

d=-h0*tidu(x)';a=gold(x,d);

x1=(x'+a*h0*d)';s=x1-x;

y=tidu(x1)-tidu(x);v=s*y';

%校正H矩阵

h0=(eye(2)-s'*y./v)*h0*(eye(2)-y'*s./v)+s'*s./v;

%判断下一次和上一次迭代点之差是否满足计算精度的要求.是,标志变量设为1，输出

结果;否,标志变量设为0，继续迭代

ifsum(abs(x-x1).^2)<1e-4

flag=1;x0=x;

else

flag=0;

end

x=x1

end

%共轭剃度法极小化函数的通用子函数，gonge.m

%输入变量为初始的迭代点，输出变量为极小值点

functionx0=gonge(x)

%判断梯度范数是否满足计算精度的要求.是,标志变量设为1，输出结果;

%否,标志变量设为0，继续迭代

ifsum(abs(tidu(x)).^2)<1e-4

flag=1;x0=x;

else

flag=0;

end

%第一次的迭代方法为负梯度方向

d1=-tidu(x);a=gold(x,d1);x1=x+a*d1;

%循环求解函数的极小点

whileflag==0

g1=tidu(x);g2=tidu(x1);

%利用FR公式求解系数bata

bata=(g2*g2')/(g1*g1');

d2=-g2+bata*d1;

a=gold(x1,d2);

x=x1;

x1=x+a*d2

%判断下一次和上一次迭代点之差是否满足计算精度的要求.是,标志变量设为1，输出

结果;否,标志变量设为0，继续迭代

ifsum(abs(x1-x).^2)<1e-4

flag=1;x0=x1;

else

flag=0;

end

end