. .项目一 一维搜索算法(一)[实验目的]编写加步探索法、对分法、Newton 法的程序。
[实验准备]1.掌握一维收搜索中搜索区间的加步探索法的思想及迭代步骤; 2.掌握对分法的思想及迭代步骤;3.掌握Newton 法的思想及迭代步骤。
[实验容及步骤]编程解决以下问题:1.用加步探索法确定一维最优化问题12)(min 30+-=≥t t t t ϕ的搜索区间,要求选取2,1,000===αh t .加步探索法算法的计算步骤:(1)选取初始点])0[)(0[max 00t t t ,或,∈⊂∞+∈,计算)(00t ϕϕ=.给出初始步长0>h ,加步系数1α>,令0=k 。
(2) 比较目标函数值.令k k k h t t +=+1,计算 )(11++=k k t ϕϕ,若k k ϕϕ<+1,转(3),否则转(4)。
(3) 加大探索步长.令k k h h α=+1,同时,令,k t t =,1+=k k t t 1k k =+,转(2)。
(4) 反向探索.若0=k ,转换探索方向,令,k k h h -=1+=k t t ,转(2)。
否则,停止迭代,令11min{}max{}k k a t t b t t ++==,,,。
加步探索法算法的计算框图. .程序清单加步探索法算法程序见附录1实验结果运行结果为:2.用对分法求解)2()(min +=t t t ϕ,已知初始单谷区间]5,3[],[-=b a ,要求按精度3.0=ε,001.0=ε分别计算.对分法迭代的计算步骤:(1)确定初始搜索区间],[b a ,要求'()0'()0a b ϕϕ<>,。
(2) 计算],[b a 的中点)(21b ac +=. (3) 若0)(<'c ϕ,则c a = ,转(4);若0)(='c ϕ,则c t =*,转(5);若0)(>'c ϕ,则c b = ,转(4).(4) 若ε<-||b a ,则)(21*b a t +=,转(5);否则转(2)... (5) 打印*t ,结束对分法的计算框图程序清单对分法程序见附录2实验结果运行结果为:3.用Newton 法求解12)(min 3+-=t t t ϕ,已知初始单谷区间]1,0[],[=b a ,要求精度01.0=ε.Newton 法的计算步骤(1) 确定初始搜索区间],[b a ,要求 '()0'()0a b ϕϕ<>, (2) 选定0t (3) 计算000'()/"()t t t t ϕϕ=-. . (4) 若 ε≥-||0t t ,则t t =0,转(3);否则转(5). (5) 打印()t t ϕ, ,结束.Newton 法的计算框图程序清单Newton 法程序见附录3实验结果运行结果为:项目二 一维搜索算法(二)[实验目的]编写黄金分割法、抛物线插值法的程序。
.. [实验准备]1.掌握黄金分割法的思想及迭代步骤; 2.掌握抛物线插值法的思想及迭代步骤。
[实验容及步骤]编程解决以下问题: 1.用黄金分割法求解)2()(min +=t t t ϕ, 已知初始单谷区间]5,3[],[-=b a ,要求精度001.0=ε.黄金分割法迭代步骤:(1) 确定)(t ϕ的初始搜索区间][b a ,. (2) 计算)(382.02a b a t -+= (3) 计算)(618.01a b a t -+=(4) 若ε<-||21t t ,则打印221*t t t +=,结束;否则转(5). (5) 判别是否满足21ϕϕ≤:若满足,则置12122ϕϕ===,,t t t a 然后转(3);否则,置)()(22221211t a b t t t t b ϕϕβαϕϕ=-+====,,,,然后转(4). 黄金分割法的计算框图:. .程序清单黄金分割法程序见附录4实验结果运行结果为:2.用抛物线插值法求解3728)(min 23+--=x x x x f ,已知初始单谷区间001.0]20[][==ε,,,b a .抛物线插值法的计算步骤:(1) )()(0t t ϕϕ<,所以相对0t 来说t 是好点,故划掉区间],[20t t ,保留],[01t t 为新区间,故置)()(0202t t t t ϕϕ==,,)()(00t t t t ϕϕ==,,1t 保持不变;(2) )()(0t t ϕϕ>,所以相对t 来说0t 是好点,故划掉区间],[1t t ,保留],[2t t 为新区间,故置)()(11t t t t ϕϕ==,,0t 与2t 保持不变;程序清单抛物线插值法程序见附录5. . 实验结果运行结果为:项目三 常用无约束最优化方法(一)[实验目的]编写最速下降法、Newton 法(修正Newton 法)的程序。
[实验准备]1.掌握最速下降法的思想及迭代步骤。
2.掌握Newton 法的思想及迭代步骤; 3.掌握修正Newton 法的思想及迭代步骤。
[实验容及步骤]编程解决以下问题: 1.用最速下降法求22120min ()25[22]0.01T f X x x X ε=+==,,,.最速下降法计算步骤 (1)0,0)(,)0(=>k X 令精度容许误差取初始点ε(2))()()(k k X f p-∇=计算(3)0)()(4,,?否则转取若是迭代终止检验k k X X p =≤*ε (4)))(()(min :)()()()(0一维搜索求最优步长k k k k k k p X f p Xf λλλλ+=+≥)()()1(2,1:,转令令+=+=+k k p X X k k k k λ最速下降法的计算框图..程序清单最速下降法程序见附录6实验结果运行结果为:2.用Newton 法求22121212min ()60104f X x x x x x x =--++-,.. 初始点0[00]0.01TX ε==,,.Newton 法的计算步骤 (1)给定初始点(0)x ,及精度0ε>,令0k =;(2)若()()k f X ε∇≤,停止,极小点为()k x ,否则转步骤(3);(3)计算12()()k f X -⎡⎤∇⎣⎦,令1()()()()()k k k s H X f X -⎡⎤=-∇⎣⎦;令(1)()()k k k xx s +=+,1k k =+,转步骤(2)。
程序清单Newton 法程序见附录7实验结果 运行结果为:3.用修正Newton 求221212min ()4(1)2(1)10f X x x x x =++-+++,初始点0[00]0.01T X ε==,,.修正Newton 的计算步骤 (1)给定初始点(0)x ,及精度0ε>,令0k =; (2)若()()k f X ε∇≤,停止,极小点为()k x,否则转步骤(3);(3)计算12()()k f X -⎡⎤∇⎣⎦,令1()()()()()k k k s H X f X -⎡⎤=-∇⎣⎦;(4)用一维搜索法求α,使得()()()()()()min ()k k k k k f X S f X S ααα≥+=+,令(1)()()()k k k k X X S α+=+,1k k =+,转步骤(2)。
程序清单..修正Newton 程序见附录8实验结果运行结果为:项目四 常用无约束最优化方法(二)实验目的编写共轭梯度法、变尺度法(DFP 法和BFGS 法)程序。
实验准备1.掌握共轭方向法的思路及迭代过程; 2.掌握共轭梯度法的思想及迭代步骤;3.掌握DFP 法和BFGS 法的思想及迭代步骤。
实验容及步骤编程解决以下问题:1. 用共轭梯度法求得)4min(2221x x +,取初始点TX ]11[0,=,01.0=ε.共轭梯度法算法步骤 (1) 给定初始点(0)x,及精度0ε>;(2) 若(0)()f x ε∇≤,停止,极小值点为(0)x,否则转步骤(3);. . (3) 取(0)(0)()pf x =-∇,且置0k =;(4) 用一维搜索法求k t ,使得()()()()()()min k k k k k t f x t p f x tp ≥+=+,令,(1)()()k k k k x x t p +=+,转步骤5;(5) 若(1)()k f x ε+∇≤,停止,极小值点为(1)k x+,否则转步骤(6);(6) 若1k n +=,令(0)()n x x =,转步骤(3),否则转步骤(7);(7) 令(1)(1)()()k k k k p f x p λ++=-∇+,2(1)2()()()k k k f x f x λ+∇=∇,置1k k =+,转步骤(4)。
程序清单共轭梯度法程序见附录9实验结果运行结果为:2. 用共轭梯度法求221212min ()2f X x x x x =+-,自定初始点,01.0=ε.程序清单共轭梯度法程序见附录9..实验结果运行结果为:3.用DFP 法求2212min ()4(5)(6)f X x x =-+-,初始点01.0]98[0==ε,,TX .DFP 法的具体迭代步骤如下: (1)给定初始点,迭代精度,维数n(2)置0→k ,单位矩阵I →,计算。
(3)计算搜索方向 (4)进行一维搜索求,使得迭代新点(5)检验是否满足迭代终止条件‖‖≤?若满足,停止迭代,输出最优解,;否则进行下一步。
(6)检查迭代次数,若k=n ,则置,转向步骤(2);若k<n ,则进行下一步。
(7)计算:。
然后,置k+1→k,转向步骤(3)。
DFP法的计算框图程序清单DFP法程序见附录10实验结果运行结果为:... . 项目五 常用约束最优化方法[实验目的]编写外点罚函数法、外点罚函数法的程序。
[实验准备]1.掌握外点罚函数法的思想及迭代步骤; 2.掌握点罚函数法的思想及迭代步骤。
[实验容及步骤]编程解决以下问题:1.用外点罚函数法编程计算⎩⎨⎧=-+=≥=+-=,,,01)(0ln )(..)(min 2112121x x X h x X g t s x x X f精度510-=ε.外点法的计算步骤:(1)给定初始点x (0),初始罚因子)1(λ,放大系数c>1;允许误差e>0,设置k=1;(2)以x (k-1)作为搜索初始点,求解无约束规划问题)()(m in x P x f λ+,令x (k)为所求极小点。
(3)当e xP k <)()(λ,则停止计算,得到点x (k);否则,令)()1(k k c λλ=+,返回(2)执行。
程序清单外点罚函数法程序见附录11实验结果实验结果为运行结果为:..2.用点罚函数法编程计算⎩⎨⎧≥≥-⎥⎦⎤⎢⎣⎡++.,,001..)1(31min 21231x x t s x x初始点取为TX ]43[0,=,初始障碍因子取101=u ,缩小系数取1.0=c .点罚步骤:(1) 给定初始点S x ∈)0(,允许误差e>0,障碍参数)1(γ,缩小系数)1,0(∈b ,置k=1;(2) 以)1(-k x 为初始点,求解下列规划问题:Sx t s x B x f k ∈+..)()(min )(γ,令)(k x 为所求极小点(3) 如果e x B k k <)()()(γ,则停止计算,得到结果)(k x ,(4) 否则令)()1(k k b γγ=+,置k=k+1,返回(2)。