最优化设计程序设计
- 格式：pdf
- 大小：868.34 KB
- 文档页数：17
最优化方法
实验报告
学生姓名： 学 班 号： 级：
魏 峰 201318050224 数学与应用数学 131802 2016 年 6 月 20 日
完成时间：
最优化方法上机实验报告
一、实验题目
共轭梯度法求解方程及方程组
二、实验目的
1.进一步熟悉理解掌握共轭梯度法解法思路，提高 matlab 编程能力 2.学习并撑握共轭梯度法的原理、方法及应用，并了解不同无约束优化方法的区 别、优缺点及特殊要求。 3.熟悉使用共轭梯度法求解无约束非线性规划问题的原理； 4.在掌握原理的基础上熟练运用此方法解决问题； 5.解决问题的同时分析问题，力求达到理论与实践的相统一；
最优化方法上机实验报告
由
( ) 0
得
1
从而有：
4 0 x 2 , f ( x 2 ) 8, f ( x 2 ) 2 0
因
f ( x 2 ) 0
收敛。
（3）程序
运行：打开 matlab,确定 conjugate_grad_2d.m 文件夹为当前目录。在命令窗中 输 入 ： f=conjugate_grad_2d([1,1],0.001) ， 选 择 不 同 的 初 始 点 坐 标 [0,0],[0,1],[1,0],和迭代精度 0.01，0.0001,进行运行时，需要多次调 用 conjugate_grad_2d 函数。 程序及说明：
搜索方向的构成问题乃是无约束优化方法的关键。 共轭梯度法是沿着共轭方向进行搜索，属于共轭方向法中的一种，该方法中 每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。 共轭梯度法作为一种 实用的迭代法，它主要有下面的优点： （1）算法中，系数矩阵Ａ的作用仅仅是用来由已知向量 P 产生向量 W=AP， 这不仅可充分利用Ａ的稀疏性，而且对某些提供矩阵Ａ较为困难而由 已知向量 P 产生向量 W=AP 又十分方便的应用问题是很有益的。 （2）不需要预先估计任何参数就可以计算，这一点不像 SOR 等； （3）每次迭代所需的计算，主要是向量之间的运算，便于并行化。
x1 1 p1 x1 p1 .
重复此步骤，得到一串
0 , 1 , 2 , 和 p0 , p1 , p2 , ，
称 pk 为搜索方向， k 为步长.一般情况下，先在 xk 点找下山方向 pk ，再在直线
x xk pk 上确定步长 k 使
pk 1 rk 1 k pk .
在实际计算中， 常将上述公式进一步简化，从而得到一个形式上更为简单而且对 称的计算公式.首先来简化 rk 1 的计算公式：
rk 1 b Axk 1 b A( xk k pk ) rk k Apk .
因为 Apk 在计算 k 是已经求出，所以计算 rk 1 时可以不必将 xk 1 代入方程计算， 而是从递推关系 rk 1 b k Apk 得到. 再来简化 k 和 k 的计算公式.此处需要用到关系式
用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方
1
最优化方法上机实验报告
法较适用于解决变量个数较少的（n ≤20）问题，一般情况下比间接法效率低。 间接法除要计算目标函数值外， 还要计算目标函数的梯度，有的还要计算其海赛 矩阵。
x k 1 x k k s k (k 0,1,2,)
1
k
rkT rk .
由此可得
rkT rk k T ,， pk Apk rkT1rk 1 k T . . rk rk
程序框图如下所示：
6
最优化方法上机实验报告
四、实验内容：
（1）问题描述 用共轭梯度法求二次函数
2 f ( x1 , x2 ) x12 2 x2 4 x1 2 x1 x2
内找出使函数 下降最快的方向作为新的下山方向 pk .考虑 在 2 上的限制：
, ( xk rk pk 1 )
( xk rk pk 1 )T A( xk rk pk 1 )
2bT ( xk rk pk 1 ) .
所确定的 即为所求步长 k ，即
k
步长确定后，即可算出
rkT pk . T pk Apk
xk 1 xk k pk .
此时，只要 rkT pk 0 ，就有
xk 1 xk xk k pk xk
3
最优化方法上机实验报告
计算 关于 , 的偏导得：
2 rkT Ark rkT Apk 1 rkT rk , T 2 rkT Apk 1 pk 1 Apk 1 ,
其中最后一式用到了 rkT pk 1 0 ，这可由 rk 的定义直接验证.令
2 2
5 0.25 20
2 d 1 f ( x1 ) 0d 0 1.5
代入目标函数
f ( x) (2 2 ) 2 2(0.5 1.5 ) 2 2(2 2 )(0.5 1.5 ) 4(2 2 ) ( )
7
5
最优化方法上机实验报告
rkT rk 1 rkT pk 1 rkT1 pk 0,
k 1, 2, .
从而可导出
rkT1 1
k
rkT1rk 1 , ，
T pk Apk
1
k
T pk rk rk 1
1
k
T pk rk
1
k
rkT rk k 1 pk 1
0，
即知 在 2 内有唯一的极 xk 0 rk 0 pk 1 ， x
其中 0 和 0 满足
0 rkT Ark 0 rkT Apk 1 rkT rk , T T 0 rk Apk 1 0 pk 1 Apk 1 0.
T 注：这样确定的 pk 满足 pk Apk 1 0 ，即 pk 与 pk 1 是相互共轭的.
总结上面的讨论，可得如下的计算公式：
rkT pk k T ， pk Apk
xk 1 xk k pk ， rk 1 b Axk 1 ，
k
rkT1 Apk ， T pk Apk
x1 x0 0 p0 ，
使得对所有实数 有
x0 0 p0 x0 p0 ，
2
最优化方法上机实验报告
即在这条直线上 x1 使 ( x) 达到极小.然后从 x1 出发，再确定一个下山的方向 p1 ， 沿着直 线 x x1 p1 再 跨 出 一 步 ， 即 找 到 1 使 得 x 在 x2 x1 1 p1 达 到 极 小 ：
function f=conjugate_grad_2d(x0,t) %用共轭梯度法求已知函数 f(x1,x2)=x1^2+2*x2^2-4*x1-2*x1*x2 的极值点 %已知初始点坐标：x0 %已知收敛精度：t %求得已知函数的极值：f x=x0; syms xi yi a; %定义自变量，步长为符号变量 f=xi^2+2*yi^2-4*xi-2*xi*yi; %创建符号表达式 f fx=diff(f,xi); %求表达式 f 对 xi 的一阶求导 fy=diff(f,yi); %求表达式 f 对 yi 的一阶求导 fx=subs(fx,{xi,yi},x0); %代入初始点坐标计算对 xi 的一阶求导实值 fy=subs(fy,{xi,yi},x0); %代入初始点坐标计算对 yi 的一阶求导实值 fi=[fx,fy]; %初始点梯度向量 count=0; %搜索次数初始为 0 while double(sqrt(fx^2+fy^2))>t %搜索精度不满足已知条件 s=-fi; %第一次搜索的方向为负梯度方向 if count<=0 s=-fi; else s=s1; end x=x+a*s; %进行一次搜索后的点坐标 f=subs(f,{xi,yi},x); %构造一元搜索的一元函数 φ(a) f1=diff(f); %对函数 φ(a)进行求导
为一维搜索最佳步长，应满足
f ( x1 ) min f ( x 0 d 0 ) min(40 2 20 3)
得：
0 0.25
2）第二次迭代
2 x1 0.5
1 f ( x 1 ) 2
0
f ( x 1 ) f ( x 0 )
0
r0T r0 , x1 x0 0 p0 , r1 b Ax0 . T p0 Ap0
对以后各步，例如第 k+1 步（k 1）,下山方向不再取 rk ，而是在过点由向量 rk 和
pk 1 所张成的二维平面
2 {x | x xk rk pk 1 , , R}
xk pk A xk pk 2bT xk pk
T
T 2 pk Apk 2 rkT pk xk ，
其中 rk b Apk .由一元函数极值存在的必要条件有
T f 2 pk Apk 2rkT pk 0
三、实验原理、基本理论
共轭梯度法为求解线性方程组而提出。后来，人们把这种方法用于求解无约 束最优化问题，使之成为一种重要的最优化方法。 共轭梯度法的基本思想是把共轭性与最速下降方法相结合， 利用已知点处的 梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。根据 共轭方向的基本性质，这种方法具有二次终止性。在各种优化算法中，共轭梯度 法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且 不需要任何外来参数。 无约束最优化方法的核心问题是选择搜索方向.在本次实验中,我们运用基于 共轭方向的一种算法—共轭梯度法 目前已研究出很多种无约束优化方法， 它们的主要不同点在于构造搜索方向 上的差别。 （1）间接法——要使用导数，如梯度法、 （阻尼）牛顿法、变尺度法、共轭梯度 法等。 （2）直接法——不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。
实验报告
学生姓名： 学 班 号： 级：
魏 峰 201318050224 数学与应用数学 131802 2016 年 6 月 20 日
完成时间：
最优化方法上机实验报告
一、实验题目
共轭梯度法求解方程及方程组
二、实验目的
1.进一步熟悉理解掌握共轭梯度法解法思路，提高 matlab 编程能力 2.学习并撑握共轭梯度法的原理、方法及应用，并了解不同无约束优化方法的区 别、优缺点及特殊要求。 3.熟悉使用共轭梯度法求解无约束非线性规划问题的原理； 4.在掌握原理的基础上熟练运用此方法解决问题； 5.解决问题的同时分析问题，力求达到理论与实践的相统一；
最优化方法上机实验报告
由
( ) 0
得
1
从而有：
4 0 x 2 , f ( x 2 ) 8, f ( x 2 ) 2 0
因
f ( x 2 ) 0
收敛。
（3）程序
运行：打开 matlab,确定 conjugate_grad_2d.m 文件夹为当前目录。在命令窗中 输 入 ： f=conjugate_grad_2d([1,1],0.001) ， 选 择 不 同 的 初 始 点 坐 标 [0,0],[0,1],[1,0],和迭代精度 0.01，0.0001,进行运行时，需要多次调 用 conjugate_grad_2d 函数。 程序及说明：
搜索方向的构成问题乃是无约束优化方法的关键。 共轭梯度法是沿着共轭方向进行搜索，属于共轭方向法中的一种，该方法中 每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。 共轭梯度法作为一种 实用的迭代法，它主要有下面的优点： （1）算法中，系数矩阵Ａ的作用仅仅是用来由已知向量 P 产生向量 W=AP， 这不仅可充分利用Ａ的稀疏性，而且对某些提供矩阵Ａ较为困难而由 已知向量 P 产生向量 W=AP 又十分方便的应用问题是很有益的。 （2）不需要预先估计任何参数就可以计算，这一点不像 SOR 等； （3）每次迭代所需的计算，主要是向量之间的运算，便于并行化。
x1 1 p1 x1 p1 .
重复此步骤，得到一串
0 , 1 , 2 , 和 p0 , p1 , p2 , ，
称 pk 为搜索方向， k 为步长.一般情况下，先在 xk 点找下山方向 pk ，再在直线
x xk pk 上确定步长 k 使
pk 1 rk 1 k pk .
在实际计算中， 常将上述公式进一步简化，从而得到一个形式上更为简单而且对 称的计算公式.首先来简化 rk 1 的计算公式：
rk 1 b Axk 1 b A( xk k pk ) rk k Apk .
因为 Apk 在计算 k 是已经求出，所以计算 rk 1 时可以不必将 xk 1 代入方程计算， 而是从递推关系 rk 1 b k Apk 得到. 再来简化 k 和 k 的计算公式.此处需要用到关系式
用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方
1
最优化方法上机实验报告
法较适用于解决变量个数较少的（n ≤20）问题，一般情况下比间接法效率低。 间接法除要计算目标函数值外， 还要计算目标函数的梯度，有的还要计算其海赛 矩阵。
x k 1 x k k s k (k 0,1,2,)
1
k
rkT rk .
由此可得
rkT rk k T ,， pk Apk rkT1rk 1 k T . . rk rk
程序框图如下所示：
6
最优化方法上机实验报告
四、实验内容：
（1）问题描述 用共轭梯度法求二次函数
2 f ( x1 , x2 ) x12 2 x2 4 x1 2 x1 x2
内找出使函数 下降最快的方向作为新的下山方向 pk .考虑 在 2 上的限制：
, ( xk rk pk 1 )
( xk rk pk 1 )T A( xk rk pk 1 )
2bT ( xk rk pk 1 ) .
所确定的 即为所求步长 k ，即
k
步长确定后，即可算出
rkT pk . T pk Apk
xk 1 xk k pk .
此时，只要 rkT pk 0 ，就有
xk 1 xk xk k pk xk
3
最优化方法上机实验报告
计算 关于 , 的偏导得：
2 rkT Ark rkT Apk 1 rkT rk , T 2 rkT Apk 1 pk 1 Apk 1 ,
其中最后一式用到了 rkT pk 1 0 ，这可由 rk 的定义直接验证.令
2 2
5 0.25 20
2 d 1 f ( x1 ) 0d 0 1.5
代入目标函数
f ( x) (2 2 ) 2 2(0.5 1.5 ) 2 2(2 2 )(0.5 1.5 ) 4(2 2 ) ( )
7
5
最优化方法上机实验报告
rkT rk 1 rkT pk 1 rkT1 pk 0,
k 1, 2, .
从而可导出
rkT1 1
k
rkT1rk 1 , ，
T pk Apk
1
k
T pk rk rk 1
1
k
T pk rk
1
k
rkT rk k 1 pk 1
0，
即知 在 2 内有唯一的极 xk 0 rk 0 pk 1 ， x
其中 0 和 0 满足
0 rkT Ark 0 rkT Apk 1 rkT rk , T T 0 rk Apk 1 0 pk 1 Apk 1 0.
T 注：这样确定的 pk 满足 pk Apk 1 0 ，即 pk 与 pk 1 是相互共轭的.
总结上面的讨论，可得如下的计算公式：
rkT pk k T ， pk Apk
xk 1 xk k pk ， rk 1 b Axk 1 ，
k
rkT1 Apk ， T pk Apk
x1 x0 0 p0 ，
使得对所有实数 有
x0 0 p0 x0 p0 ，
2
最优化方法上机实验报告
即在这条直线上 x1 使 ( x) 达到极小.然后从 x1 出发，再确定一个下山的方向 p1 ， 沿着直 线 x x1 p1 再 跨 出 一 步 ， 即 找 到 1 使 得 x 在 x2 x1 1 p1 达 到 极 小 ：
function f=conjugate_grad_2d(x0,t) %用共轭梯度法求已知函数 f(x1,x2)=x1^2+2*x2^2-4*x1-2*x1*x2 的极值点 %已知初始点坐标：x0 %已知收敛精度：t %求得已知函数的极值：f x=x0; syms xi yi a; %定义自变量，步长为符号变量 f=xi^2+2*yi^2-4*xi-2*xi*yi; %创建符号表达式 f fx=diff(f,xi); %求表达式 f 对 xi 的一阶求导 fy=diff(f,yi); %求表达式 f 对 yi 的一阶求导 fx=subs(fx,{xi,yi},x0); %代入初始点坐标计算对 xi 的一阶求导实值 fy=subs(fy,{xi,yi},x0); %代入初始点坐标计算对 yi 的一阶求导实值 fi=[fx,fy]; %初始点梯度向量 count=0; %搜索次数初始为 0 while double(sqrt(fx^2+fy^2))>t %搜索精度不满足已知条件 s=-fi; %第一次搜索的方向为负梯度方向 if count<=0 s=-fi; else s=s1; end x=x+a*s; %进行一次搜索后的点坐标 f=subs(f,{xi,yi},x); %构造一元搜索的一元函数 φ(a) f1=diff(f); %对函数 φ(a)进行求导
为一维搜索最佳步长，应满足
f ( x1 ) min f ( x 0 d 0 ) min(40 2 20 3)
得：
0 0.25
2）第二次迭代
2 x1 0.5
1 f ( x 1 ) 2
0
f ( x 1 ) f ( x 0 )
0
r0T r0 , x1 x0 0 p0 , r1 b Ax0 . T p0 Ap0
对以后各步，例如第 k+1 步（k 1）,下山方向不再取 rk ，而是在过点由向量 rk 和
pk 1 所张成的二维平面
2 {x | x xk rk pk 1 , , R}
xk pk A xk pk 2bT xk pk
T
T 2 pk Apk 2 rkT pk xk ，
其中 rk b Apk .由一元函数极值存在的必要条件有
T f 2 pk Apk 2rkT pk 0
三、实验原理、基本理论
共轭梯度法为求解线性方程组而提出。后来，人们把这种方法用于求解无约 束最优化问题，使之成为一种重要的最优化方法。 共轭梯度法的基本思想是把共轭性与最速下降方法相结合， 利用已知点处的 梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。根据 共轭方向的基本性质，这种方法具有二次终止性。在各种优化算法中，共轭梯度 法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且 不需要任何外来参数。 无约束最优化方法的核心问题是选择搜索方向.在本次实验中,我们运用基于 共轭方向的一种算法—共轭梯度法 目前已研究出很多种无约束优化方法， 它们的主要不同点在于构造搜索方向 上的差别。 （1）间接法——要使用导数，如梯度法、 （阻尼）牛顿法、变尺度法、共轭梯度 法等。 （2）直接法——不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。
