最优化方法实验报告(1)
最优化方法实验报告Numerical Linear Algebra And Its Applications
学生所在学院：理学院
学生所在班级：计算数学10-1
学生姓名：甘纯
指导教师：单锐
教务处
2013年5月
实验一
实验名称：熟悉matlab基本功能
实验时间: 2013年05月10日星期三实验成绩：
一、实验目的：
在本次实验中，通过亲临使用MATLAB，对该软件做一全面了解并掌握重点内容。
二、实验内容：
1. 全面了解MATLAB系统
2. 实验常用工具的具体操作和功能
实验二
实验名称：一维搜索方法的MATLAB实现
实验时间: 2013年05月10日星期三实验成绩：
一、实验目的：
通过上机利用Matlab数学软件进行一维搜索，并学会对具体问题进行分析。并且熟悉Matlab软件的实用方法，并且做到学习与使用并存，增加学习的实际动手性，不再让学习局限于书本和纸上，而是利用计算机学习来增加我们的学习兴趣。
二、实验背景：
(一）0.618法（黄金分割法），它是一种基于区间收缩的极小点搜索
算法，当用进退法确定搜索区间后，我们只知道极小点包含于搜索区间内，但是具体哪个点，无法得知。 1、算法原理
黄金分割法的思想很直接，既然极小点包含于搜索区间内，那么可以不断的缩小搜索区间，就可以使搜索区间的端点逼近到极小点。 2、算法步骤
用黄金分割法求无约束问题min (),f x x R ∈的基本步骤如下： （1）选定初始区间11[,]a b 及精度0ε>，计算试探点：
11110.382*()a b a λ=+-
11110.618*()a b a μ=+-。
（2）若k k b a ε-<，则停止计算。否则当()()k k f f λμ>时转步骤（3）。 当()()k k f f λμ≤转步骤（4）。 （3）置
11111110.382*()k k
k k k k k k k k a b b a b a λλμμ+++++++=??=??
=??=+-?转步骤（5）
（4）置
11111110.382*()k k k k k k k k k k a a b a b a μμλλ+++++++=??=??
=??=+-?转步骤（5）
（5）令1k k =+，转步骤（2）。 (二）斐波那契法： 1、算法原理
斐波那契法也是一种区间收缩算法，但是和黄金分割法不同的是，黄金分割法每次收缩只改变搜索区间的一个端点，而斐波那契法同时改变搜索区间的两个端点，是一种双向收缩法。 2、算法步骤
(1)选取初始数据，确定单峰区间],[00b a ，给出搜索精度0>δ，由
δ≤-n
F a
b 确定搜索次数n 。 (2) 00,,1b b a a k ===，计算最初两个搜索点，按（3）计算1t 和2t 。 (3) while 1- )(),(2211t f f t f f == if 21f f < ) ()() 1(;;1122a b k n F k n F a t t t t a ----+ === else ) ()() 1(;;2211b a k n F k n F b t t t t b ----+ === end 1+=k k en (4) 当进行至1-=n k 时， )(21 21b a t t += = 这就无法借比较函数值)(1t f 和)(2t f 的大小确定最终区间，为此，取 ?????? ? -++=+=))(21()(2112a b a t b a t ε 其中ε为任意小的数。在1t 和2t 这两点中，以函数值较小者为近似极小点，相应的函数值为近似极小值。并得最终区间],[1t a 或],[2b t 。 由上述分析可知，斐波那契法使用对称搜索的方法，逐步缩短所考察的区间，它能以尽量少的函数求值次数，达到预定的某一缩短率。 (三）三点二次插值法： 1、算法原理 该算法在搜索区间中不断用低次（通常不超过三次）插值多项式来近似目标函数，并逐步用插值多项式的极小点来逼近）（x ?的极小点，当函数具有比较好的解析性质时，插值方法比直接方法（如0.618或Fibonacci 法）效果更好。 2、算法步骤 (1)取初始点321ααα<<，计算3,2,1i i i ==），（α??并满足 )()()(321α?α?α?<>，置精度要求ε（迭代终止条件）。 (2 ) 计算[]0A 2A 213132321=-+-+-=，）（）（）（αα?αα?αα? ，则置22?α?αα==）（， 停止计算 (3)计算 A 32 2212212312322?αα?αα?ααα）（）（）（-+-+-= 若1αα<或)),((33ααααα?>则置22,??αα== 停止计算 (4)计算)(α??=，若εαα<-2停止计算（α作为极小点） (5)如果),(32ααα∈ 则 若,2??<则置：α?αα??αα====222121,,,否则置??αα==33,； 否则),(21ααα∈则 若,2??<则置：α?αα??αα====222323,,,否则置??αα==11,。 (6)转（2） 三、实验内容： 1. 0.618法的MATLAB 实现 2. Fibonacci 法的MATLAB 实现 3．二次插值法的MATLAB 实现 四、实验过程： 1．0.618法的函数： function [x,minf] = minHJ(f,a,b,eps) if nargin == 3 eps = 1.0e-6; end l = a + 0.382*(b-a); u = a + 0.618*(b-a); k=1; tol = b-a; while tol>eps && k<100000 fl = subs(f , findsym(f), l); fu = subs(f , findsym(f), u); if fl > fu a = l; l = u; u = a + 0.618*(b - a); else b = u; u = l; l = a + 0.382*(b-a); end k = k+1; tol = abs(b - a); end if k == 100000 disp('找不到最小值！'); x = NaN; minf = NaN; return; end x = (a+b)/2; minf = subs(f, findsym(f),x); 2．Fibonacci法的函数： function [x,minf] = minFBNQ(f,a,b,delta,eps) if nargin == 4 eps = 1.0e-6; end F = ones(2,1); N = (b-a)/eps; c = F(2) - N; n = 2; while c<0 n = n+1; F(n) = F(n-1) + F(n-2); c = F(n) - N; end l = a + F(n-2)*(b-a)/F(n); u = a + F(n-1)*(b-a)/F(n); k=1; while 1 fl = subs(f , findsym(f), l); fu = subs(f , findsym(f), u); if fl > fu a = l; l = u; u = a + F(n-k-1)*(b-a)/F(n-k); if (k == n - 3) break; else k = k+1; end else b = u; u = l; l = a + F(n-k-2)*(b-a)/F(n-k); if ( k == n-3 ) break; else k = k+1; end end end if k == 100000 disp('找不到最小值！'); x = NaN; minf = NaN; return; end u = l + delta; fl = subs(f , findsym(f), l); fu = subs(f , findsym(f), u); if fl > fu a = l; else b = l; end x = (a+b)/2; minf = subs(f , findsym(f), x); 3．二次插值法函数： function [min,minf]=minTP(a1,a2,a3,f,eps) if nargin==4 eps=10^(-2); end f1=subs(f,findsym(f),a1); f2=subs(f,findsym(f),a2); f3=subs(f,findsym(f),a3); if (f1 disp('输入三点不符合三点二次插值的要求'); end ax=((a2^2-a3^2)*f1+(a3^2-a1^2)*f2+(a1^2-a2^2)*f3)/(2*((a2-a3)*f1+(a3-a1)*f2+(a1-a2)*f3)); fax=subs(f,findsym(f),ax); while(abs(fax-f2)>eps) if ax>a2 if fax<=f2 a1=a2; a2=ax; f1=f2; f2=fax; else a3=ax; f3=fax; end else if fax<=f2 a3=a2; a2=ax; f3=f2; f2=fax; else a1=ax; f1=fax; end end ax=((a2^2-a3^2)*f1+(a3^2-a1^2)*f2+(a1^2-a2^2)*f3)/(2*((a2-a3)*f1+(a3-a1)*f2+(a1-a2)*f3)); fax=subs(f,findsym(f),ax); end min=ax; minf=subs(f,findsym(f),ax); format short; 五、实验结果(总结/方案) 黄金分割法求解极值实例。用黄金分割法求解下面函数的最小值： ]10,10[,52)(24-∈+--==t t t t t f 其中 在command window 中输入： >>syms t; f=t^4-t^2-2*t+5; [x,fx]=minHJ(f,-10,10) 结果为： x= 1.0000 fx= 3.0000 2．Fibonacci 法 Fibonacci 法求解极值实例。用Fibonacci 法求解下面函数的最小值： ]10,10[,52)(24-∈+--==t t t t t f 其中 在command window中输入： >>syms t; f=t^4-t^2-2*t+5; [x,fx]=minFBNQ(f,-10,10,0.05) 结果为： x= 1.0000 fx= 3.0000 3．二次插值法 在command window中输入： >> syms t; f=t^3-3*t+2; a1=0;a2=2;a3=3; [min,minf]=minTP(a1,a2,a3,f,0.0001) 结果为： min = 0.9983 minf = 8.9463e-006 最优化方法 课程设计报告班级：________________ 姓名： ______ 学号： __________ 成绩： 2017年 5月 21 日 目录 一、摘要 (1) 二、单纯形算法 (2) 1.1 单纯形算法的基本思路 (2) 1.2 算法流程图 (3) 1.3 用matlab编写源程序 (4) 二、黄金分割法 (7) 2.1 黄金分割法的基本思路 (7) 2.2 算法流程图 (8) 2.3 用matlab编写源程序 (9) 2.4 黄金分割法应用举例 (11) 三、最速下降法 (11) 3.1 最速下降法的基本思路 (11) 3.2 算法流程图 (13) 3.3 用matlab编写源程序 (13) 3.4 最速下降法应用举例 (13) 四、惩罚函数法 (17) 4.1 惩罚函数法的基本思路 (17) 4.2 算法流程图 (18) 4.3 用matlab编写源程序 (18) 4.4 惩罚函数法应用举例 (19) 五、自我总结 (20) 六、参考文献 (20) 一、摘要 运筹学是一门以人机系统的组织、管理为对象，应用数学和计算机等工具来研究各类有限资源的合理规划使用并提供优化决策方案的科学。通过对数据的调查、收集和统计分析，以及具体模型的建立。收集和统计上述拟定之模型所需要的各种基础数据，并最终将数据整理形成分析和解决问题的具体模型。 最优化理论和方法日益受到重视，已经渗透到生产、管理、商业、军事、决策等各个领域，而最优化模型与方法广泛应用于工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各个部门及各个领域。伴随着计算机技术的高速发展，最优化理论与方法的迅速进步为解决实际最优化问题的软件也在飞速发展。其中，MATLAB软件已经成为最优化领域应用最广的软件之一。有了MATLAB 这个强大的计算平台，既可以利用MATLAB优化工具箱（OptimizationToolbox）中的函数，又可以通过算法变成实现相应的最优化计算。 关键词：优化、线性规划、黄金分割法、最速下降法、惩罚函数法 《最优化方法》复习题(含答案) 附录5 《最优化方法》复习题 1、设n n A R ?∈是对称矩阵，,n b R c R ∈∈，求1()2 T T f x x Ax b x c =++在任意点x 处的梯度和Hesse 矩阵． 解 2(),()f x Ax b f x A ?=+?=． 2、设()()t f x td ?=+，其中:n f R R →二阶可导，,,n n x R d R t R ∈∈∈，试求()t ?''． 解 2()(),()()T T t f x td d t d f x td d ??'''=?+=?+． 3、设方向n d R ∈是函数()f x 在点x 处的下降方向，令 ()()()()() T T T T dd f x f x H I d f x f x f x ??=--???， 其中I 为单位矩阵，证明方向()p H f x =-?也是函数()f x 在点x 处的下降方向． 证明 由于方向d 是函数()f x 在点x 处的下降方向，因此()0T f x d ?<，从而 ()()()T T f x p f x H f x ?=-?? ()()()()()()()() T T T T T dd f x f x f x I f x d f x f x f x ??=-?--???? ()()()0T T f x f x f x d =-??+?<， 所以，方向p 是函数()f x 在点x 处的下降方向． 4、n S R ?是凸集的充分必要条件是12122,,,,,,,,m m m x x x S x x x ?≥?∈L L 的一切凸组合都属于S ． 证明 充分性显然．下证必要性．设S 是凸集，对m 用归纳法证明．当2m =时，由凸集的定义知结论成立，下面考虑1m k =+时的情形．令1 1k i i i x x λ+==∑， 其中,0,1,2,,1i i x S i k λ∈≥=+L ，且1 1 1k i i λ+==∑．不妨设11k λ+≠（不然1k x x S +=∈， 结论成立），记11 1k i i i k y x λλ=+=-∑ ，有111(1)k k k x y x λλ+++=-+， 最优化方法实验报告Numerical Linear Algebra And Its Applications 学生所在学院：理学院 学生所在班级：计算数学10-1 学生姓名：甘纯 指导教师：单锐 教务处 2013年5月 实验一 实验名称：熟悉matlab基本功能 实验时间: 2013年05月10日星期三实验成绩： 一、实验目的： 在本次实验中，通过亲临使用MATLAB，对该软件做一全面了解并掌握重点内容。 二、实验内容： 1. 全面了解MATLAB系统 2. 实验常用工具的具体操作和功能 实验二 实验名称：一维搜索方法的MATLAB实现 实验时间: 2013年05月10日星期三实验成绩： 一、实验目的： 通过上机利用Matlab数学软件进行一维搜索，并学会对具体问题进行分析。并且熟悉Matlab软件的实用方法，并且做到学习与使用并存，增加学习的实际动手性，不再让学习局限于书本和纸上，而是利用计算机学习来增加我们的学习兴趣。 二、实验背景： (一）0.618法（黄金分割法），它是一种基于区间收缩的极小点搜索 算法，当用进退法确定搜索区间后，我们只知道极小点包含于搜索区间内，但是具体哪个点，无法得知。 1、算法原理 黄金分割法的思想很直接，既然极小点包含于搜索区间内，那么可以不断的缩小搜索区间，就可以使搜索区间的端点逼近到极小点。 2、算法步骤 用黄金分割法求无约束问题min (),f x x R ∈的基本步骤如下： （1）选定初始区间11[,]a b 及精度0ε>，计算试探点： 11110.382*()a b a λ=+- 11110.618*()a b a μ=+-。 （2）若k k b a ε-<，则停止计算。否则当()()k k f f λμ>时转步骤（3）。 当()()k k f f λμ≤转步骤（4）。 （3）置 11111110.382*()k k k k k k k k k k a b b a b a λλμμ+++++++=??=?? =??=+-?转步骤（5） 《最优化方法与应用》 实验指导书 信息与计算科学系编制 1 实验目的 基于单纯形法求解线性规划问题，编写算法步骤，绘制算法流程图，编写单纯形法程序，并针对实例完成计算求解。 2实验要求 程序设计语言：C++ 输入：线性规划模型（包括线性规划模型的价值系数、系数矩阵、右侧常数等） 输出：线性规划问题的最优解及目标函数值 备注：可将线性规划模型先转化成标准形式，也可以在程序中将线性规划模型从一般形式转化成标准形式。 3实验数据 123()-5-4-6=Min f x x x x 121231212320 324423230,,0３-+≤??++≤??+≤??≥? x x x x x x st x x x x x 1 实验目的 基于线性搜索的对分法、Newton 切线法、黄金分割法、抛物线法等的原理及方法，编写算法步骤和算法流程图，编写程序求解一维最优化问题，并针对实例具体计算。 2实验要求 程序设计语言：C++ 输入：线性搜索模型（目标函数系数，搜索区间，误差限等） 输出：最优解及对应目标函数值 备注：可从对分法、Newton 切线法、黄金分割法、抛物线法中选择2种具体的算法进行算法编程。 3实验数据 2211 ()+-6(0.3)0.01(0.9)0.04 = -+-+Min f x x x 区间[0.3,1],ε=10-4 实验三 无约束最优化方法 1实验目的 了解最速下降法、牛顿法、共轭梯度法、DFP 法和BFGS 法等的基本原理及方法，掌握其迭代步骤和算法流程图，运用Matlab 软件求解无约束非线性多元函数的最小值问题。 2实验要求 程序设计语言：Matlab 针对实验数据，对比最速下降法、牛顿法、共轭梯度法、DFP 法和BFGS 法等算法，比较不同算法的计算速度和收敛特性。 3实验数据 Rosenbrock's function 222211()(100)+(1-)=-Min f x x x x 初始点x=[-1.9, 2]，,ε=10-4 学生科学实验效果最优化的基石实验报告设计 自然科学是以实验为基础的学科。实验是人们研究和认识自然的重要方法。因此，在自然科学的教学中，实验也是重要的教学方法之一。通过实验，不仅可以提供学生对科学现象的感性认识，更可以让学生获得初步的实验技能和观察分析问题的能力。 小学科学实验教学的设计是运用系统论的思想和方法，以学习理论、教学理论为基础，计划和安排实验教学的各个环节、要素，以实现教学效果最优化为目的的活动。通过多年来的实验教学实践与思考，我们可以让学生像科学家那样，亲历科学探究的过程，这有利于充分发挥学生的主体作用，让学生积极主动参与到观察、实验等学习活动中去，亲自感知实验所产生的各种现象和变化，提高自行获取知识的能力，而其中比较重要的一个环节就是学生实验报告的设计与记录。在学生实验的过程中，一份好的实验报告设计，就像是一盏明灯，能给学生指引实验的目标、方向，能提供给学生形成结论的分析数据，进而培养学生科学实验的基本素养，使学生的科学实验效果达到最优化。 一、观察实验报告的填写，有利于学生在实验中观察，进一步培养学生实验的责任心和有序观察能力。 教科版四下《油菜花开了》解剖花的实验中，我设计了如下实验报告，在教学中取得了很好的效果。 《解剖花》实验人 花的名称 实验方法：用镊子把花的各部分，从外向里一层层撕下，整齐排列并贴在相应的名称左边，数一数，填在相应的空格上。 个萼片 个花瓣 个雄蕊 个雌蕊 在班级（1）上课时我没有设计实验报告，就按照书本上的要求，先介绍解剖花的方法、花的结构，然后让学生按照书本要求独立解剖油菜花。在实验过程中，学生非常认真，且相当活跃，但检查结果时，学生雌雄蕊不分，萼片、花瓣不分，桌上、地上掉落的都是花瓣，实验效果之不佳显而易见。 后来，我根据班级（1）出现的情况，设计了如上实验报告，实验的效果就相当出色。在这个实验报告中，我并没有限制学生解剖何种花，但学生可以根据实验要求很清楚地完成解剖的任务。充分体现了以教师为主导、学生为主体的课堂教学思想；而且在实验的过程中，桌上有了这份实验报告，便时刻提醒着学生做实验究竟是何目的，做实验时必须仔细观察什么，做实验的观察步骤是什么。在解剖花的过程中，动作快的同学还可在老师的同意下，多取一两张实验报告单，多解剖几种花，因此既避免了学生在一旁闲着无所事事而打闹的局面，又进一步提高了这些学生的科学素质。至于个别有困难的学生，教师可在巡视的过程中 一维搜索方法的MATLAB 实现 姓名： 班级：信息与计算科学 学号： 实验时间: 2014/6/21 一、实验目的： 通过上机利用Matlab 数学软件进行一维搜索，并学会对具体问题进行分析。并且熟悉Matlab 软件的实用方法，并且做到学习与使用并存，增加学习的实际动手性，不再让学习局限于书本和纸上，而是利用计算机学习来增加我们的学习兴趣。 二、实验背景： 黄金分割法 它是一种基于区间收缩的极小点搜索算法，当用进退法确定搜索区间后，我们只知道极小点包含于搜索区间内，但是具体哪个点，无法得知。 1、算法原理 黄金分割法的思想很直接，既然极小点包含于搜索区间内，那么可以不断 的缩小搜索区间，就可以使搜索区间的端点逼近到极小点。 2、算法步骤 用黄金分割法求无约束问题min (),f x x R ∈的基本步骤如下： （1）选定初始区间11[,]a b 及精度0ε>，计算试探点： 11110.382*()a b a λ=+- 11110.618*()a b a μ=+-。 （2）若k k b a ε-<，则停止计算。否则当()()k k f f λμ>时转步骤（3）。 当 ()()k k f f λμ≤转步骤（4）。 （3） 11111110.382*()k k k k k k k k k k a b b a b a λλμμ+++++++=??=?? =??=+-?转步骤（5） （4） 转步骤（5） （5）令1k k =+，转步骤（2）。 算法的MATLAB 实现 function xmin=golden(f,a,b,e) k=0; x1=a+0.382*(b-a); x2=a+0.618*(b-a); while b-a>e f1=subs(f,x1); f2=subs(f,x2); if f1>f2 a=x1; x1=x2; f1=f2; x2=a+0.618*(b-a); else b=x2; x2=x1; f2=f1; x1=a+0.382*(b-a); end k=k+1; end xmin=(a+b)/2; fmin=subs(f,xmin) 项目一 一维搜索算法（一） [实验目的] 编写加步探索法、对分法、Newton 法的程序。 [实验准备] 1．掌握一维收搜索中搜索区间的加步探索法的思想及迭代步骤； 2．掌握对分法的思想及迭代步骤； 3．掌握Newton 法的思想及迭代步骤。 [实验容及步骤] 编程解决以下问题： 1．用加步探索法确定一维最优化问题 1 2)(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 的中点)(2 1 b a c +=． (3) 若0)(<'c ?，则c a = ，转(4)；若0)(='c ?，则c t =* ，转(5)；若0)(>'c ?，则c b = ，转(4)． (4) 若ε<-||b a ，则)(2 1* b a t +=，转(5)；否则转(2)． (5) 打印* t ，结束 对分法的计算框图 习题二包括题目：P36页5（1）（4） 5（4） 习题三 包括题目：P61页1(1)(2); 3; 5; 6; 14；15(1) 1(1)(2)的解如下 3题的解如下 5,6题 14题解如下 14. 设22121212()(6)(233)f x x x x x x x =+++---, 求点在(4,6)T -处的牛顿方向。 解：已知 (1) (4,6)T x =-，由题意得 121212212121212(6)2(233)(3)()2(6)2(233)(3)x x x x x x x f x x x x x x x x +++-----?? ?= ?+++-----?? ∴ (1)1344()56g f x -?? =?= ??? 21212122211212122(3)22(3)(3)2(233)()22(3)(3)2(233)22(3)x x x x x x x f x x x x x x x x +--+--------? ??= ? +--------+--?? ∴ (1)2(1)1656()()564G x f x --?? =?= ?-?? (1)1 1/8007/400()7/4001/200G x --?? = ?--?? ∴ (1)(1)11141/100()574/100d G x g -?? =-= ?-?? 15（1）解如下 15. 用DFP 方法求下列问题的极小点 （1）22 121212min 353x x x x x x ++++ 解：取 (0) (1,1)T x =，0H I =时，DFP 法的第一步与最速下降法相同 2112352()156x x f x x x ++???= ?++??， (0)(1,1)T x =，(0) 10()12f x ???= ??? (1)0.07800.2936x -??= ?-??， (1) 1.3760() 1.1516f x ???= ?-?? 以下作第二次迭代 (1)(0) 1 1.07801.2936x x δ-??=-= ?-??， (1)(0) 18.6240()()13.1516f x f x γ-??=?-?= ?-?? 0110 111011101 T T T T H H H H H γγδδδγγγ=+- . . 项目一 一维搜索算法（一） [实验目的] 编写加步探索法、对分法、Newton 法的程序。 [实验准备] 1．掌握一维收搜索中搜索区间的加步探索法的思想及迭代步骤； 2．掌握对分法的思想及迭代步骤； 3．掌握Newton 法的思想及迭代步骤。 [实验容及步骤] 编程解决以下问题： 1．用加步探索法确定一维最优化问题 1 2)(min 30 +-=≥t t t t ? 的搜索区间，要求选取2,1,000===αh t ． 加步探索法算法的计算步骤： (1)选取初始点])0[)(0[max 00t t t ，或，∈?∞+∈，计算)(00 t ??=．给出初始步长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 的中点)(2 1 b a c += ． (3) 若0)(<'c ?，则c a = ，转(4)；若0)(='c ?，则c t =* ，转(5)；若0)(>'c ?，则c b = ，转(4)． (4) 若ε<-||b a ，则)(2 1* b a t +=，转(5)；否则转(2)． 最优化方法 课程设计报告 班级：________________ 姓名： ______ 学号： __________ 成绩： 2017年 5月 21 日 目录 一、摘要 (1) 二、单纯形算法 (2) 1.1 单纯形算法的基本思路 (2) 1.2 算法流程图 (3) 1.3 用matlab编写源程序 (3) 二、黄金分割法 (7) 2.1 黄金分割法的基本思路 (7) 2.2 算法流程图 (8) 2.3 用matlab编写源程序 (9) 2.4 黄金分割法应用举例 (10) 三、最速下降法 (10) 3.1 最速下降法的基本思路 (10) 3.2 算法流程图 (12) 3.3 用matlab编写源程序 (12) 3.4 最速下降法应用举例 (13) 四、惩罚函数法 (16) 4.1 惩罚函数法的基本思路 (16) 4.2 算法流程图 (17) 4.3 用matlab编写源程序 (17) 4.4 惩罚函数法应用举例 (19) 五、自我总结 (19) 六、参考文献 (19) 一、摘要 运筹学是一门以人机系统的组织、管理为对象，应用数学和计算机等工具来研究各类有限资源的合理规划使用并提供优化决策方案的科学。通过对数据的调查、收集和统计分析，以及具体模型的建立。收集和统计上述拟定之模型所需要的各种基础数据，并最终将数据整理形成分析和解决问题的具体模型。 最优化理论和方法日益受到重视，已经渗透到生产、管理、商业、军事、决策等各个领域，而最优化模型与方法广泛应用于工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各个部门及各个领域。伴随着计算机技术的高速发展，最优化理论与方法的迅速进步为解决实际最优化问题的软件也在飞速发展。其中，MATLAB软件已经成为最优化领域应用最广的软件之一。有了MATLAB这个强大的计算平台，既可以利用MATLAB优化工具箱（OptimizationToolbox）中的函数，又可以通过算法变成实现相应的最优化计算。 关键词：优化、线性规划、黄金分割法、最速下降法、惩罚函数 法 盛年不重来，一日难再晨。及时宜自勉，岁月不 待人。 机械优化设计习题及参考答案 1-1.简述优化设计问题数学模型的表达形式。 答：优化问题的数学模型是实际优化设计问题的数学抽象。在明确设计变量、约束条件、目标函数之后，优化设计问题就可以表示成一般数学形式。求设计变量向量[]12T n x x x x =L 使 ()min f x → 且满足约束条件 ()0 (1,2,)k h x k l ==L ()0 (1,2,)j g x j m ≤=L 2-1.何谓函数的梯度？梯度对优化设计有何意义？ 答：二元函数f(x 1,x 2)在x 0点处的方向导数的表达式可以改写成下面的形式：??? ?????????????=??+??= ??2cos 1cos 212cos 21cos 1θθθθxo x f x f xo x f xo x f xo d f ρ 令xo T x f x f x f x f x f ?? ????????=????=?21]21[)0(， 则称它为函数f （x 1，x 2）在x 0点处的梯度。 （1）梯度方向是函数值变化最快方向，梯度模是函数变化率的最大值。 （2）梯度与切线方向d 垂直，从而推得梯度方向为等值面的法线方向。梯度)0(x f ?方向为函数变化率最大方向，也就是最速上升方向。负梯度-)0(x f ?方向为函数变化率最小方向，即最速下降方向。 2-2.求二元函数f （x 1，x 2）=2x 12+x 22-2x 1+x 2在T x ]0,0[0=处函数变化率最 大的方向和数值。 解：由于函数变化率最大的方向就是梯度的方向，这里用单位向量p 表示，函数变化率最大和数值时梯度的模)0(x f ?。求f （x1，x2）在x0点处的梯度方向和数值，计算如下： ()??? ???-=??????+-=???? ??????????=?120122214210x x x x f x f x f 2 221)0(??? ????+??? ????=?x f x f x f =5 ????? ???????-=??????-=??=5152512)0()0(x f x f p ? 2-3.试求目标函数()2 221212143,x x x x x x f +-=在点X 0=[1,0]T 处的最速下降 方向，并求沿着该方向移动一个单位长度后新点的目标函数值。 解：求目标函数的偏导数 212 21124,46x x x f x x x f +-=??-=?? 则函数在X 0=[1,0]T 处的最速下降方向是 ??????-=??????-+-=?????? ??????????-=-?=====462446)(0 121 210 1210 2121x x x x x x x x x f x f X f P 这个方向上的单位向量是： 13]2,3[4 )6(]4,6[T 22T -=+--==P P e 新点是 遗传算法实验报告 专业：自动化姓名：张俊峰学号：13351067 摘要：遗传算法，是基于达尔文进化理论发展起来的一种应用广泛、高效的随机搜索与优化方法。本实验利用遗传算法来实现求函数最大值的优化问题，其中的步骤包括初始化群体、个体评价、选择运算、交叉运算、变异运算、终止条件判断。该算法具有覆盖面大、减少进入局部最优解的风险、自主性等特点。此外，遗传算法不是采用确定性原则而是采用概率的变迁规则来指导搜索方向，具有动态自适应的优点。 关键词：串集最优化评估迭代变异 一：实验目的 熟悉和掌握遗传算法的运行机制和求解的基本方法。 遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻找所求问题的答案。其求解过程是个最优化的过程。一般遗传算法的主要步骤如下： （1）随机产生一个确定长度的特征字符串组成的初始种群。。 （2）对该字符春种群迭代地执行下面的步骤a和步骤b，直到满足停止准则为止： a计算种群中每个个体字符串的适应值； b应用复制、交叉和变异等遗传算子产生下一代种群。 （3）把在后代中表现的最好的个体字符串指定为遗传算法的执行结果，即为问题的一 个解。 二：实验要求 已知函数y=f（x 1,x 2 ,x 3 ,x 4 ）=1/(x 1 2+x 2 2+x 3 2+x 4 2+1),其中-5≤x 1 ,x 2 ,x 3 ,x 4 ≤5, 用遗传算法求y的最大值。三：实验环境 操作系统：Microsoft Windows 7 软件：Microsoft Visual studio 2010 四：实验原理与步骤 1、遗传算法的思想 生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程，第t代群体极为P（t），进过一代遗传和进化后，得到第t+1代群体，他们也是由多个个体组成的集合，记做P（t+1）。这个群体不断地经过遗传和进化操作，并且每次都按照有优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现性X将达到或接近于问题的最优解。 2、算法实现步骤 ①、产生初始种群：产生初始种群的方法通常有两种：一种是完全随机的方法产生的，适合于对问题的解无任何先验知识的情况；另一种是将某些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选择样本，t=0,随机产生n个个体形成一个初始群体P（t），该群体代表优化问题的一些可能解的集合； ②适应度评价函数：按编码规则，将群体P（t）中的每一个个体的基因码所对应的自变量取值代入目标函数，算出其函数值f，i=1,2,…,n,f越大，表示该个体有较高的适应度，更适合于f所定义的生存环境，适应度f为群体进化提供了依据； ③选择：按一定概率从群体P（t）中选出m个个体，作为双亲用于繁殖后代，产生新的个体加入下一个群体P（t+1）中。此处选用轮盘算法，也就是比例选择算法，个体被选择的概率与其适应度成正比。 ④交叉（重组）：对于选中的用于繁殖的每一个个体，选择一种交叉方法，产生新的个体；此处采取生成随机数决定交叉的个体与交叉的位置。 ⑤变异：以一定的概率Pm从群体P（t+1）中随机选择若干个个体，对于选中的个体随机选择某个位置，进行变异； ⑥对产生新一代的群体返回步骤③再进行评价，交叉、变异如此循环往复，使群体中个体的适应度和平均适应度不断提高，直至最优个体的适应度达到某一限值或最优个体的适应度和群体的平均适应度不再提高，则迭代过程收敛，算法结束。 五：实验结果 实验结果的显示取决于判断算法终止的条件，这里可以有两种选择：1、在程序中设定迭代的次数；2在程序中设定适应值。本实验是在程序中实验者输入需要迭代的次数来判断程序终结的。 习题二包括题目： P36页 5（1）（4） 5（4） 习题三 包括题目：P61页 1(1)(2); 3; 5; 6; 14；15(1) 1(1)(2)的解如下 3题的解如下 5,6题 14题解如下 14. 设22121212()(6)(233)f x x x x x x x =+++---, 求点在(4,6)T -处的牛顿方向。 解：已知 (1) (4,6)T x =-，由题意得 121212212121212(6)2(233)(3)()2(6)2(233)(3)x x x x x x x f x x x x x x x x +++-----?? ?= ?+++-----?? ∴ (1)1344()56g f x -?? =?= ??? 21212122211212122(3)22(3)(3)2(233)()22(3)(3)2(233)22(3)x x x x x x x f x x x x x x x x +--+--------? ??= ? +--------+--?? ∴ (1)2(1)1656()()564G x f x --?? =?= ?-?? (1)11/8007/400()7/4001/200G x --?? = ?--?? ∴ (1)(1)11141/100()574/100d G x g -?? =-= ?-?? 15（1）解如下 15. 用DFP 方法求下列问题的极小点 （1）22 121212min 353x x x x x x ++++ 解：取 (0) (1,1)T x =，0H I =时，DFP 法的第一步与最速下降法相同 2112352()156x x f x x x ++???= ? ++??， (0)(1,1)T x =，(0) 10()12f x ???= ??? (1)0.07800.2936x -??= ?-??， (1) 1.3760() 1.1516f x ???= ?-?? 以下作第二次迭代 (1)(0)1 1.07801.2936x x δ-??=-= ?-??， (1)(0) 18.6240()()13.1516f x f x γ-?? =?-?= ?-?? 《最优化方法》复习题 第一章 概述(包括凸规划) 一、 判断与填空题 1 )].([arg )(arg min max x f x f n n R x R x -=∈∈ √ 2 {}{}.:)(min :)(max n n R D x x f R D x x f ?∈-=? ∈ ? 3 设.:R R D f n →? 若n R x ∈*，对于一切n R x ∈恒有)()(x f x f ≤*，则称*x 为 最优化问题)(min x f D x ∈的全局最优解. ? 4 设.:R R D f n →? 若D x ∈*，存在*x 的某邻域)(* x N ε，使得对一切 )(*∈x N x ε恒有)()(x f x f <*，则称* x 为最优化问题)(min x f D x ∈的严格局部最 优解. ? 5 给定一个最优化问题，那么它的最优值是一个定值. √ 6 非空集合n R D ?为凸集当且仅当D 中任意两点连线段上任一点属于D . √ 7 非空集合n R D ?为凸集当且仅当D 中任意有限个点的凸组合仍属于D . √ 8 任意两个凸集的并集为凸集. ? 9 函数R R D f n →?:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √ 10 设R R D f n →?:为凸集D 上的可微凸函数，D x ∈* . 则对D x ∈?，有 ).()()()(* **-?≤-x x x f x f x f T ? 11 若)(x c 是凹函数，则}0)( {≥∈=x c R x D n 是凸集。 √ 12 设{}k x 为由求解)(min x f D x ∈的算法A 产生的迭代序列，假设算法A 为下降算法， 则对{} ,2,1,0∈?k ，恒有 )()(1k k x f x f ≤+ . 《最优化方法》课程设计指导书 一、课程设计目的与要求 1、提高分析问题、解决问题的能力，进一步巩固最优化方法的基本原理与方法。 2、熟悉应用MATLAB进行优化方法的设计。 二、课程设计要求 1、要充分认识课程设计对培养自己的重要性，认真做好设计前的各项准备工作。尤其是对编程软件的使用有基本的认识。 2、既要虚心接受老师的指导，又要充分发挥主观能动性。结合课题，独立思考，努力钻研，勤于实践，勇于创新。 3、独立按时完成规定的工作任务，不得弄虚作假，不准抄袭他人内容，否则成绩以不及格计。 4、在设计过程中，要严格要求自己，树立严肃、严密、严谨的科学态度，必须按时、按质、按量完成课程设计。 三、内容及学时分配 本设计包括四个小题目，全部设计时间一周，共16学时。 （一）单纯性算法的基本原理及思路（4学时） 设计目的和要求：通过本次设计应使学生掌握如何使用MATLAB软件进行单纯性算法求解线性规划，并学会对具体问题进行分析。 设计的内容： １、单纯性算法的基本思路 ２、算法流程图 ３、用matlab编写源程序 ４、单纯性算法应用举例 教学建议：初次使用MATLAB进行优化问题的实验，本次设计在全面了解软件系统基础之上，要让学生学习和熟悉一些MATLAB的基础用途，重点掌握优化工具箱函数选用的内容。 重点和难点： 优化工具箱函数选用。 （二）黄金分割法的MATLAB实现（4学时） 设计目的和要求：通过本次设计应使学生掌握如何使用MATLAB软件进行一维搜索，并学会对具体问题进行分析。 设计内容： １、0.618法的算法思路 ２、0.618法的MATLAB实现 ３、0.618法应用举例 教学建议： 本次实验是学生初次使用MATLAB进行优化问题的实验，本次实验就是要通过对一些具体问题的分析学会软件的操作并加深对理论知识的理解。 重点和难点： 具体问题的步长因子的确定，理解、掌握精度与效率的关系。 （三）最速下降法的MATLAB实现（4学时） 设计目的和要求：通过本次实验使学生进一步熟悉掌握使用MATLAB软件，并能利用该软件进行无约束最优化方法的计算。 设计内容： １、最速下降法的算法思路 ２、最速下降法的MATLAB实现 ３、最速下降法应用举例 教学建议： 本次实验就是要通过对一些具体问题的分析进一步熟悉软件的操作并加深对理论知识的理解。 重点和难点： 通过同一个具体问题用不同的方法解决的比较，加深理解恰当选用优化问题解决方法的重要性。 （四）罚函数法的MATLAB实现（4学时） 实验的目的和要求：通过本次实验使学生较为熟练使用MATLAB软件，并能利用该软件进行约束最优化方法的计算。 最优化方法(Matlab)实验报告 ——Fibonacci 法 一、实验目的： 用MATLAB 程序实现一维搜索中用Fibonacc 法求解一元单峰函数的极小值问题。二、实验原理： （一）、构造Fibonacci 数列：设数列{}k F ，满足条件： 1、011F F == 2、11 k k k F F F +-=+则称数列{}k F 为Fibonacci 数列。（二）、迭代过程： 首先由下面的迭代公式确定出迭代点： 1 1 1 (),1,...,1(),1,...,1n k k k k k n k n k k k k k n k F a b a k n F F u a b a k n F λ---+--+=+ -=-=+ -=-易验证，用上述迭代公式进行迭代时，第k 次迭代的区间长度缩短比率恰好为 1 n k n k F F --+。故可设迭代次数为n ，因此有11121211221111223231 ()()......()()n n n n n n n n n F F F F F F b a b a b a b a b a F F F F F F F ------= -=?-==?-=-若设精度为L ，则有第n 次迭代得区间长度111 ()n n n b a L b a L F -≤-≤，即 就是 111 ()n b a L F -≤，由此便可确定出迭代次数n 。 假设第k 次迭代时已确定出区间[,]k k a b 以及试探点,[,]k k k k u a b λ∈并且k k u λ<。计算试探点处的函数值，有以下两种可能：（1）若()()k k f f u λ>，则令 111111111,,()() () k k k k k k k k n k k k k k n k a b b f f F a b a F λλμλμμ++++--++++-=====+-计算1()k f μ+的值。（2）()()k k f f u λ≤，则令 111121111,,()() () k k k k k k k k n k k k k k n k a a b f f F a b a F μμλμλλ++++--++++-=====+-计算1()k f λ+的值。 又因为第一次迭代确定出了两个迭代点，以后每迭代一次，新增加一个迭代点，这样在迭代n-1后便计算完了n 个迭代点。因此第n 次迭代中，选用第n-1次的迭代点以及辨别常数δ构造n λ和n μ： 1 1n n n n λλμλδ --==+再用同样的方法进行判断：（1）、若()n f λ>()n f μ则令 1 n n n n a b b λ-==（2）、若()n f λ<=()n f μ则令 1n n n n a a b μ-==这样便可确定出最优解的存在区间[,]n n a b 。 计算方法实验报告 实验名称： 实验1 从函数表出发进行插值 1 引言 某个实际问题中，函数f (x)在区间[a,b]上存在且连续，但难以找到其表达式，只能通过实验和观测得到有限点上的函数表。有些情况虽然可以写出表达式，但结构复杂，使用不方便。所以希望构造简单函数P (x)作为f (x)的近似值。插值法是解决此类问题的一种方法。 设函数y=在插值区间[a,b]上连续，且在n+1个不同的插值节点a≤x 0,x 1,…,x n ≤b 上分别取值y 0,y 1,…,y n 。目的是要在一个性质优良、便于计算的插值函数类Φ中，求一简单函数P (x)，满足插值条件P (x i )=y i (i=0,1,…,n)，而在其他点x≠x i 上，作为f (x)近似值。求插值函数P (x)的方法称为插值法[1]。 2 实验目的和要求 运用Matlab 编写m 文件，定义三种插值函数，要求一次性输入整张函数表，并利用计算机选择在插值计算中所需的节点。分别通过分段线性插值、分段二次插值和全区间上拉格朗日插值计算f (0.15)，f (0.31)，f (0.47)的近似值。 3 算法原理与流程图 （1）原理 1.线性插值 当给定了n+1个点x 0 练习题一 1、建立优化模型应考虑哪些要素? 答：决策变量、目标函数和约束条件。 2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。 答：针对一般优化模型()()min () .. 0,1,2, 0,1, ,i j f x s t g x i m h x j p ≥===，讨论解的可行域D ，若存在一点*X D ∈，对于X D ?∈ 均有*()()f X f X ≤则称*X 为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代所得到的序列(1)(2)() ,, ,K X X X ，满足(1)()()()K K f X f X +≤，则迭代法收敛；收敛的停止准则有 (1)()k k x x ε+-<，(1)() () k k k x x x ε+-<，()()(1)()k k f x f x ε+-<， ()()() (1)()()k k k f x f x f x ε+-<，()()k f x ε?<等 等。 练习题二 1、某公司看中了例2.1中厂家所拥有的3种资源R 1、R 2、和R 3，欲出价收购（可能用于生产附加值更高的产品）。如果你是该公司的决策者，对这3种资源的收购报价是多少？（该问题称为例2.1的对偶问题）。 解：确定决策变量 对3种资源报价123,,y y y 作为本问题的决策变量。 确定目标函数 问题的目标很清楚——“收购价最小”。 确定约束条件 资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。 因此有如下线性规划问题：123min 170100150w y y y =++ 123123123 5210 ..23518,,0y y y s t y y y y y y ++≥??++≥??≥? *2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。 答：略。 3、用单纯形法求解下列线性规划问题： 附录5 《最优化方法》复习题 1、设n n A R ?∈是对称矩阵，,n b R c R ∈∈，求1()2 T T f x x Ax b x c =++在任意点x 处的梯度和Hesse 矩阵． 解 2(),()f x Ax b f x A ?=+?=． 2、设()()t f x td ?=+，其中:n f R R →二阶可导，,,n n x R d R t R ∈∈∈，试求()t ?''． 解 2()(),()()T T t f x td d t d f x td d ??'''=?+=?+． 3、设方向n d R ∈是函数()f x 在点x 处的下降方向，令 ()()()()() T T T T dd f x f x H I d f x f x f x ??=--???， 其中I 为单位矩阵，证明方向()p H f x =-?也是函数()f x 在点x 处的下降方向． 证明 由于方向d 是函数()f x 在点x 处的下降方向，因此()0T f x d ?<，从而 ()()()T T f x p f x H f x ?=-?? ()()()()()()()() T T T T T dd f x f x f x I f x d f x f x f x ??=-?--???? ()()()0T T f x f x f x d =-??+?<， 所以，方向p 是函数()f x 在点x 处的下降方向． 4、n S R ?是凸集的充分必要条件是12122,,,,,,,,m m m x x x S x x x ?≥?∈L L 的一切凸组合都属于S ． 证明 充分性显然．下证必要性．设S 是凸集，对m 用归纳法证明．当2m =时，由凸集的定义知结论成立，下面考虑1m k =+时的情形．令1 1k i i i x x λ+==∑， 其中,0,1,2,,1i i x S i k λ∈≥=+L ，且1 1 1k i i λ+==∑．不妨设11k λ+≠（不然1k x x S +=∈， 结论成立），记11 1k i i i k y x λλ=+=-∑ ，有111(1)k k k x y x λλ+++=-+，最优化实验报告
《最优化方法》复习题(含答案)
最优化方法实验报告(1)
《最优化方法与应用》实验指导书
学生科学实验效果最优化的基石实验报告设计
最优化方法(黄金分割与进退法)实验报告
最优化方法课程实验报告
最优化计算方法课后习题答案----高等教育出版社。施光燕
最优化方法课程实验报告
最优化实验报告
《机械优化设计》习题及答案1
遗传算法实验报告
最优化计算方法课后习题答案----高等教育出版社。施光燕
天津大学最优化方法复习题
最优化方法实验指导书
最优化算法实验报告(附Matlab程序)
计算方法实验报告习题1(浙大版)
最优化方法练习题答案修改建议版本删减版
《最优化方法》复习题(含答案)