最优化理论与方法上机实验报告
- 格式：pdf
- 大小：952.82 KB
- 文档页数：25
4 / 25
最优化理论与方法上机报告
函数句柄和匿名函数的操作符均为@,匿名函数是函数句柄的一种特殊用法， 这里所得到的函数句柄变量不指向特定的函数（即不指向函数M文件中的函数 名），而是指向一个函数表达式（具体表达式）.在命令窗口中输入@func就是用 了函数句柄将其传给objf变量,而step=golden(@(x)objf(X0+x*d)，0，1， epsilon);则是通过匿名函数将函数传给golden程序,此两处的改变就大大提高 了程序的运行速度!
分为了三段， 比较 f ( x1 )与f ( x2 ) 的大小， 若 f ( x1 ) f x2 , 则 x* [ x1 , b], 去掉 [a, x1 ]; 若 f ( x1 ) f x2 , 则 x* [a, x2 ], 去掉 [ x2 , b] ，然后在余下的区间上根据对称原则再 计算一个对称点的函数值，再重复上述操作，直到满足精度. 1.2 实现及结果 采用 matlab 2011a 实现，命名为 golden，具体程序见附录 golden.m 文件. 该程序的使用方法， 请参见附录中golden.m文件中绿色部分， 下面给出程序 运行结果，其中目标函数为： f ( x) x12 x1 6 ，精度采用默认： 106 .
(a)采用默认精度
(b)精度为0.001 图 1-3-1 牛顿法运行结果
牛顿法收敛速度快，正如上图（a）所示，达到 106 精度只需 18 步，而最速 下降法却需要 366304 步，两者的收敛速度由此可见一斑，可谓有天壤之别！ 3.4 体会 由于牛顿法收敛速度快，且人工求目标函数的梯度、Hesse 矩阵，有时较为 繁杂，故算法实现时，实现了自动求梯度和 Hesse 矩阵，这样便在程序的易用性 和时间复杂度两者间得到了很好的折中.
1 / 25
最优化理论与运行结果
由 f ( x) x12 x1 6 ，求导得 f ( x) 2x1 1, 易知 x1 0.5 为其极小点，可见程 序正确.
2. 最速下降法
最速下降法是求解无约束优化问题最简单和最古老的方法之一， 时至今日已 不再具有实用性，但它是研究其它无约束优化算法的基础. 最速下降法适合解决下述优化问题：
2012 年最优化理论与 方法
上机报告
学院： 专业：
电子工程 智能科学与技术
文章详细介绍了使用 matlab 实现无约束和约束最优化问题的方法和程序，及使用 方法，包含黄金分割法、最速下降法、牛顿法、外点法、内点法，例子丰富.
最优化理论与方法上机报告
最优化理论与方法上机报告
虽然上机题仅有两个，但我又增加了一个，以验证程序的正确性！报告按照 优化方法：黄金分割法、最速下降法、牛顿法、外点法、内点法的顺序叙述，分 为两篇，第一篇为无约束优化，第二篇为约束优化.
数受到惩罚， M 越大，受到的惩罚越重，当 M 足够大时，要使 f ( x) 取得极小， 罚函数 P( x) 应充分小，从而 T ( x, M ) 的极小点充分逼近可行域 D，这样求解一般 约束优化问题就化为求解一系列无约束的优化问题
min T ( x, M ) .
1.2 算法 外点法的算法如下: Step1 取初始点 x0 R n , 容许误差 0
xR
1 ，惩罚因子 M 1 0 , r 1, 令 k:=1.
T ( x, M k ) f ( x) M k P( x) ， Step2 以 xk 1 为初始点求解子问题 min 设其极小点 n
为 xk . Step3 若 j (1 j m), 使 g j ( xk ) , 则令 M k 1 rM k , k k 1, 转 Step2,否则 停止迭代，取 x* xk . 1.3 实现及结果
3. 牛顿法
牛顿法也是一种经典的无约束优化方法，并且其收敛速度快， 具有自适应的 特点，至今仍受到人们的青睐. 3.1 思想 牛顿法的基本思想是用迭代点 xk 处的一阶导数（梯度）和二阶导数（Hesse 阵）对目标函数进行二次函数近似，然后把二次模型的极小点作为新的迭代点， 并不断重复这一过程，直至达到精度. 3.2 算法 牛顿法的算法如下: Step1 取初始点 x0 R n , 容许误差 0 Step2 计算 gk f ( xk ) . Step3 若 gk ，则停止迭代，取 x* xk ，否则，转下一步. Step4 计算 H k 2 f ( xk ), 并由 Hk d gk , 求得 dk Hk gk . Step5 令 xk 1 xk dk , k : k 1 , 转 Step2. 3.3 实现及结果 采用 matlab 2011a 实现，具体程序见附录 Newton.m 文件. 下面以上机题第一题为例介绍具体使用方法: 上机题1的优化目标函数为
0
1 ，令 k:=0.
Step5 令 xk 1 xk dk , k : k 1 , 转 Step2. 2.3 实现及结果 采用 matlab 2011a 实现，具体程序见附录 fast.m 文件. 下面以上机题第一题为例介绍具体使用方法: 上机题1的优化目标函数为
f ( x) ( x1 10 x2 )2 5( x3 x4 )2 ( x2 2 x3 )4 10( x1 x4 )4 ,
min f ( x) n
xR
其中 f ( x) 是 R n 上的连续可谓函数. 2.1 思想 无约束优化问题下降类算法的一般框架是， 用不同的方式确定搜索方向和搜 索步长，就得到不同的算法，最速下降法采用负梯度方向
dk f ( xk )
2 / 25
最优化理论与方法上机报告
作为搜索方向，由于该方向是函数值下降最快的方向，故称为最速下降法. 2.2 算法 最速下降法的算法如下: Step1 取初始点 x0 R n , 容许误差 0 Step2 计算 dk f ( xk ) . Step3 若 dk ，则停止迭代，取 x* xk ，否则，转下一步. Step4 求 k 0 ，使 f ( xk k dk ) min f ( xk dk ) .
P( x) [min{0, gi ( x)}]2 ,
i 1
m
和增广目标函数
T ( x, M ) f ( x) MP( x),
其 中 M 0 为 惩 罚 因 子 ， 不 难 发 现 当 xD 时 ， 即 x 为 可 行 点 时 ，
T ( x, M ) f ( x), 此时目标函数没有受到惩罚；当 x D 时，T ( x, M ) f ( x), 目标函
1 ，令 k:=0.
f ( x) ( x1 10 x2 )2 5( x3 x4 )2 ( x2 2 x3 )4 10( x1 x4 )4 ,
仍然使用最速下降法中建立的func.m文件,在命令窗口中输入(加粗部分)：
5 / 25
最优化理论与方法上机报告
X0=[1 2 3 4]’;Newton(@func,X0);即可按默认的精度 106 计算，若想改变精度， 如 103 则输入：Newton(@func,X0,0.001);对应的结果分别如下图的(a)、(b)所 示:
第一篇 无约束优化
1. 黄金分割法
黄金分割法又称 0.618 法，其基本思想是试探点函数值的比较，使包含极小 点的搜索区间不断缩小.该方法仅需计算函数值，适用范围广，使用方便.由于该 方法思想简单，在此不给出具体算法流程，仅介绍思想和 matlab 实现的程序. 1.1 思想
x1 a 0.382(b a) 在搜索区间 [a, b] 内插入点 x1 , x2 ，其中， ，把 [a, b] 区间 x2 a 0.618(b a)
3 / 25
最优化理论与方法上机报告
然后在命令窗口输入:X0=[1 2 3 4]’，再输入:fast(@func，gfunc，X0); 即可(加粗部分，X0为初始点，任意)，运行结果如下:
(a)精度较高时的情况
(b)精度较低时的情况
图 1-2-1 最速下降法运行结果
由于最速下降法收敛速度很缓慢，要达到较高精度，迭代的次数要很大，正 如上图(a)所示，当设置的精度较高时( 106 )，迭代了 50000 次也未达到，实际上 需要 366304 次才可以，给出的最优解为 x* 0.0049, 0.0005,0.0024,0.0024 .但
首先分别建立两个文件即目标函数文件func.m和对应梯度文件gfunc.m内容 分别如下: func.m文件 function f = func( x ) % ---------------最速下降法、牛顿法用-----------f=(x(1)+10*x(2))^2+5*(x(3)-x(4))^2+(x(2)-2*x(3))^4+10*(x(1)-x(4))^4; gfunc.m文件 function gf = gfunc( x ) %目标函数的梯度 gf=[2*(x(1)+10*x(2))+40*(x(1)-x(4))^3 20*(x(1)+10*x(2))+4*(x(2)-2*x(3))^3 10*(x(3)-x(4))-8*(x(2)-2*x(3))^3 -10*(x(3)-x(4))-40*(x(1)-x(4))^3];
T
精度不是很高时，得到的结果也是令人满意的，如图(b)所示. 2.4 体会 Matlab 的运算速度不太令人满意， 当然有时程序的运算速度是和算法及编程 实现者的水平密不可分的！ 在最速下降法的实现过程中，刚开始使用 subs 函数计算函数值和一般的函 数调用方式会大大降低程序的速度，几经修改后，得到了上面的程序，原来的程 序迭代 5000 次需要 30 分钟不只，改进后的程序仅需不到 10 秒的时间，即使是 要达到 106 的精度，也只需要 4 分钟，可见效果是相当可观的! 这其中， 应用了函数句柄和匿名函数，其实它们就是为了使 feval 及借助于 它的泛函指令工作更可靠；使“函数调用”像“变量调用”一样方便灵活；提高 函数调用速度，特别在反复调用情况下更显效率；提高软件重用性，扩大子函数 和私用函数的可调用范围；迅速获得同名重载函数的位置、类型信息.
最优化理论与方法上机报告
函数句柄和匿名函数的操作符均为@,匿名函数是函数句柄的一种特殊用法， 这里所得到的函数句柄变量不指向特定的函数（即不指向函数M文件中的函数 名），而是指向一个函数表达式（具体表达式）.在命令窗口中输入@func就是用 了函数句柄将其传给objf变量,而step=golden(@(x)objf(X0+x*d)，0，1， epsilon);则是通过匿名函数将函数传给golden程序,此两处的改变就大大提高 了程序的运行速度!
分为了三段， 比较 f ( x1 )与f ( x2 ) 的大小， 若 f ( x1 ) f x2 , 则 x* [ x1 , b], 去掉 [a, x1 ]; 若 f ( x1 ) f x2 , 则 x* [a, x2 ], 去掉 [ x2 , b] ，然后在余下的区间上根据对称原则再 计算一个对称点的函数值，再重复上述操作，直到满足精度. 1.2 实现及结果 采用 matlab 2011a 实现，命名为 golden，具体程序见附录 golden.m 文件. 该程序的使用方法， 请参见附录中golden.m文件中绿色部分， 下面给出程序 运行结果，其中目标函数为： f ( x) x12 x1 6 ，精度采用默认： 106 .
(a)采用默认精度
(b)精度为0.001 图 1-3-1 牛顿法运行结果
牛顿法收敛速度快，正如上图（a）所示，达到 106 精度只需 18 步，而最速 下降法却需要 366304 步，两者的收敛速度由此可见一斑，可谓有天壤之别！ 3.4 体会 由于牛顿法收敛速度快，且人工求目标函数的梯度、Hesse 矩阵，有时较为 繁杂，故算法实现时，实现了自动求梯度和 Hesse 矩阵，这样便在程序的易用性 和时间复杂度两者间得到了很好的折中.
1 / 25
最优化理论与运行结果
由 f ( x) x12 x1 6 ，求导得 f ( x) 2x1 1, 易知 x1 0.5 为其极小点，可见程 序正确.
2. 最速下降法
最速下降法是求解无约束优化问题最简单和最古老的方法之一， 时至今日已 不再具有实用性，但它是研究其它无约束优化算法的基础. 最速下降法适合解决下述优化问题：
2012 年最优化理论与 方法
上机报告
学院： 专业：
电子工程 智能科学与技术
文章详细介绍了使用 matlab 实现无约束和约束最优化问题的方法和程序，及使用 方法，包含黄金分割法、最速下降法、牛顿法、外点法、内点法，例子丰富.
最优化理论与方法上机报告
最优化理论与方法上机报告
虽然上机题仅有两个，但我又增加了一个，以验证程序的正确性！报告按照 优化方法：黄金分割法、最速下降法、牛顿法、外点法、内点法的顺序叙述，分 为两篇，第一篇为无约束优化，第二篇为约束优化.
数受到惩罚， M 越大，受到的惩罚越重，当 M 足够大时，要使 f ( x) 取得极小， 罚函数 P( x) 应充分小，从而 T ( x, M ) 的极小点充分逼近可行域 D，这样求解一般 约束优化问题就化为求解一系列无约束的优化问题
min T ( x, M ) .
1.2 算法 外点法的算法如下: Step1 取初始点 x0 R n , 容许误差 0
xR
1 ，惩罚因子 M 1 0 , r 1, 令 k:=1.
T ( x, M k ) f ( x) M k P( x) ， Step2 以 xk 1 为初始点求解子问题 min 设其极小点 n
为 xk . Step3 若 j (1 j m), 使 g j ( xk ) , 则令 M k 1 rM k , k k 1, 转 Step2,否则 停止迭代，取 x* xk . 1.3 实现及结果
3. 牛顿法
牛顿法也是一种经典的无约束优化方法，并且其收敛速度快， 具有自适应的 特点，至今仍受到人们的青睐. 3.1 思想 牛顿法的基本思想是用迭代点 xk 处的一阶导数（梯度）和二阶导数（Hesse 阵）对目标函数进行二次函数近似，然后把二次模型的极小点作为新的迭代点， 并不断重复这一过程，直至达到精度. 3.2 算法 牛顿法的算法如下: Step1 取初始点 x0 R n , 容许误差 0 Step2 计算 gk f ( xk ) . Step3 若 gk ，则停止迭代，取 x* xk ，否则，转下一步. Step4 计算 H k 2 f ( xk ), 并由 Hk d gk , 求得 dk Hk gk . Step5 令 xk 1 xk dk , k : k 1 , 转 Step2. 3.3 实现及结果 采用 matlab 2011a 实现，具体程序见附录 Newton.m 文件. 下面以上机题第一题为例介绍具体使用方法: 上机题1的优化目标函数为
0
1 ，令 k:=0.
Step5 令 xk 1 xk dk , k : k 1 , 转 Step2. 2.3 实现及结果 采用 matlab 2011a 实现，具体程序见附录 fast.m 文件. 下面以上机题第一题为例介绍具体使用方法: 上机题1的优化目标函数为
f ( x) ( x1 10 x2 )2 5( x3 x4 )2 ( x2 2 x3 )4 10( x1 x4 )4 ,
min f ( x) n
xR
其中 f ( x) 是 R n 上的连续可谓函数. 2.1 思想 无约束优化问题下降类算法的一般框架是， 用不同的方式确定搜索方向和搜 索步长，就得到不同的算法，最速下降法采用负梯度方向
dk f ( xk )
2 / 25
最优化理论与方法上机报告
作为搜索方向，由于该方向是函数值下降最快的方向，故称为最速下降法. 2.2 算法 最速下降法的算法如下: Step1 取初始点 x0 R n , 容许误差 0 Step2 计算 dk f ( xk ) . Step3 若 dk ，则停止迭代，取 x* xk ，否则，转下一步. Step4 求 k 0 ，使 f ( xk k dk ) min f ( xk dk ) .
P( x) [min{0, gi ( x)}]2 ,
i 1
m
和增广目标函数
T ( x, M ) f ( x) MP( x),
其 中 M 0 为 惩 罚 因 子 ， 不 难 发 现 当 xD 时 ， 即 x 为 可 行 点 时 ，
T ( x, M ) f ( x), 此时目标函数没有受到惩罚；当 x D 时，T ( x, M ) f ( x), 目标函
1 ，令 k:=0.
f ( x) ( x1 10 x2 )2 5( x3 x4 )2 ( x2 2 x3 )4 10( x1 x4 )4 ,
仍然使用最速下降法中建立的func.m文件,在命令窗口中输入(加粗部分)：
5 / 25
最优化理论与方法上机报告
X0=[1 2 3 4]’;Newton(@func,X0);即可按默认的精度 106 计算，若想改变精度， 如 103 则输入：Newton(@func,X0,0.001);对应的结果分别如下图的(a)、(b)所 示:
第一篇 无约束优化
1. 黄金分割法
黄金分割法又称 0.618 法，其基本思想是试探点函数值的比较，使包含极小 点的搜索区间不断缩小.该方法仅需计算函数值，适用范围广，使用方便.由于该 方法思想简单，在此不给出具体算法流程，仅介绍思想和 matlab 实现的程序. 1.1 思想
x1 a 0.382(b a) 在搜索区间 [a, b] 内插入点 x1 , x2 ，其中， ，把 [a, b] 区间 x2 a 0.618(b a)
3 / 25
最优化理论与方法上机报告
然后在命令窗口输入:X0=[1 2 3 4]’，再输入:fast(@func，gfunc，X0); 即可(加粗部分，X0为初始点，任意)，运行结果如下:
(a)精度较高时的情况
(b)精度较低时的情况
图 1-2-1 最速下降法运行结果
由于最速下降法收敛速度很缓慢，要达到较高精度，迭代的次数要很大，正 如上图(a)所示，当设置的精度较高时( 106 )，迭代了 50000 次也未达到，实际上 需要 366304 次才可以，给出的最优解为 x* 0.0049, 0.0005,0.0024,0.0024 .但
首先分别建立两个文件即目标函数文件func.m和对应梯度文件gfunc.m内容 分别如下: func.m文件 function f = func( x ) % ---------------最速下降法、牛顿法用-----------f=(x(1)+10*x(2))^2+5*(x(3)-x(4))^2+(x(2)-2*x(3))^4+10*(x(1)-x(4))^4; gfunc.m文件 function gf = gfunc( x ) %目标函数的梯度 gf=[2*(x(1)+10*x(2))+40*(x(1)-x(4))^3 20*(x(1)+10*x(2))+4*(x(2)-2*x(3))^3 10*(x(3)-x(4))-8*(x(2)-2*x(3))^3 -10*(x(3)-x(4))-40*(x(1)-x(4))^3];
T
精度不是很高时，得到的结果也是令人满意的，如图(b)所示. 2.4 体会 Matlab 的运算速度不太令人满意， 当然有时程序的运算速度是和算法及编程 实现者的水平密不可分的！ 在最速下降法的实现过程中，刚开始使用 subs 函数计算函数值和一般的函 数调用方式会大大降低程序的速度，几经修改后，得到了上面的程序，原来的程 序迭代 5000 次需要 30 分钟不只，改进后的程序仅需不到 10 秒的时间，即使是 要达到 106 的精度，也只需要 4 分钟，可见效果是相当可观的! 这其中， 应用了函数句柄和匿名函数，其实它们就是为了使 feval 及借助于 它的泛函指令工作更可靠；使“函数调用”像“变量调用”一样方便灵活；提高 函数调用速度，特别在反复调用情况下更显效率；提高软件重用性，扩大子函数 和私用函数的可调用范围；迅速获得同名重载函数的位置、类型信息.
