4-2最优化分析方法

最优化方法-习题解答张彦斌计算机学院2014年10月20日Contents1第一章最优化理论基础-P13习题1(1)、2(3)(4)、3、412第二章线搜索算法-P27习题2、4、643第三章最速下降法和牛顿法P41习题1，2，374第四章共轭梯度法P51习题1，3，6(1)105第五章拟牛顿法P73-2126第六章信赖域方法P86-8147第七章非线性最小二乘问题P98-1，2，6188第八章最优性条件P112-1，2,5,6239第九章罚函数法P132，1-(1)、2-(1)、3-(3),62610第十一章二次规划习题11P178-1（1），5291第一章最优化理论基础-P13习题1(1)、2(3)(4)、3、4 1.验证下列各集合是凸集:(1)S={(x1,x2)|2x1+x2≥1,x1−2x2≥1};需要验证：根据凸集的定义，对任意的x(x1,x2),y(y1,y2)∈S及任意的实数λ∈[0,1],都有λx+(1−λ)y∈S.即,(λx1+(1−λ)y1,λx2+(1−λ)y2)∈S证：由x(x1,x2),y(y1,y2)∈S得到，{2x1+x2≥1,x1−2x2≥12y1+y2≥1,y1−2y2≥1(1)1把(1)中的两个式子对应的左右两部分分别乘以λ和1−λ,然后再相加，即得λ(2x1+x2)+(1−λ)(2y1+y2)≥1,λ(x1−2x2)+(1−λ)(y1−2y2)≥1(2)合并同类项，2(λx1+(1−λ)y1)+(λx2+(1−λ)y2)≥1,(λx1+(1−λ)y1)−2(λx2+(1−λ)y2)≥1(3)证毕.2.判断下列函数为凸（凹）函数或严格凸（凹）函数：(3)f(x)=x21−2x1x2+x22+2x1+3x2首先二阶导数连续可微，根据定理1.5，f在凸集上是（I）凸函数的充分必要条件是∇2f(x)对一切x为半正定；（II）严格凸函数的充分条件是∇2f(x)对一切x为正定。

学科教师辅导讲义知识梳理一、最优化问题在日常生活和生产中，我们经常会遇到下面的问题：完成一件事情，怎样合理安排才能做到用的时间最少，效果最佳。

这类问题在数学中称为统筹问题。

我们还会遇到“费用最省”、“面积最大”、“损耗最小”等等问题，这些问题往往可以从极端情况去探讨它的最大（小）值，这类问题在数学中称为极值问题。

以上的问题实际上都是“最优化问题”二、时间最优问题策略在进行最佳安排时，要考虑以下几个问题：（1）要做哪几件事；（2）做每件事需要的时间；（3）要弄清所做事的程序，即先做什么，后做什么，哪些事可以同时做。

在学习、生产和工作中，只有尽可能地节省时间、人力和物力，才能发挥出更大的效率。

典例分析考点一：烧水问题例1、明明早晨起来要完成以下几件事情：洗水壶1分钟，烧开水12分钟，把水灌入水瓶要2分钟，吃早点要8分钟，整理书包2分钟。

应该怎样安排时间最少？最少要几分钟？【解析】经验表明：能同时做的事尽量要同时去做，这样节省时间。

水壶不洗，不能烧开水，因而洗水壶不能和烧开水同时进行；而吃早点和整理书包可以和烧开水同时进行。

这一过程可用方框图表示：从图上可以看出，洗水壶要1分钟，接着烧开水要12分钟，在等水开的同时吃早点、整理书包，水开了就灌入水瓶，共需15分钟。

例2、妈妈让小明给客人烧水沏茶。

洗水壶需要1分钟，烧开水需要15分钟，洗茶壶需要1分钟，洗茶杯需要1分钟。

要让客人喝上茶，最少需要多少分钟？【解析】经验表明，能同时做的事，尽量同时做，这样可以节省时间。

水壶不洗，不能烧开水，因此，洗水壶和烧开水不能同时进行。

而洗茶壶、洗茶杯和拿茶叶与烧开水可以同时进行。

根据以上的分析，可以这样安排：先洗水壶用1分钟，接着烧开水用15分钟，同时洗茶壶、洗茶杯、拿茶叶，水开了就沏茶，共需要16分钟。

考点二：煎饼问题例1、贴烧饼的时候，第一面需要烘3分钟，第二面需要烘2分钟，而贴烧饼的架子上一次最多只能放2个烧饼。

最优化方法》课程教学大纲课程编号：100004英文名称：Optimizatio n Methods一、课程说明1. 课程类别理工科学位基础课程2. 适应专业及课程性质理、工、经、管类各专业，必修文、法类各专业，选修3. 课程目的（1 ）使学生掌握最优化问题的建模、无约束最优化及约束最优化问题的理论和各种算法;（2）使学生了解二次规划与线性分式规划的一些特殊算法；（3）提高学生应用数学理论与方法分析、解决实际问题的能力以及计算机应用能力。

4. 学分与学时学分2,学时405. 建议先修课程微积分、线性代数、Matlab语言6. 推荐教材或参考书目推荐教材：（1）《非线性最优化》（第一版）.谢政、李建平、汤泽滢主编.国防科技大学出版社.2003年.孙（第一版）参考文瑜、徐成贤、朱德通主编.高等教育出版社.2004年（2）《最优化方法》书目：（第一版）.胡适耕、施保昌主编.华中理工大学出版社.2000年（1）《最优化原理》（2）《运筹学》》（修订版）.《运筹学》教材编写组主编.清华大学出版社.1990年7. 教学方法与手段（1）教学方法：启发式（2）教学手段：多媒体演示、演讲与板书相结合8. 考核及成绩评定考核方式：考试成绩评定：考试课（1）平时成绩占20%形式有：考勤、课堂测验、作业完成情况（2）考试成绩占80%形式有：笔试（开卷）。

9. 课外自学要求（1）课前预习；（2）课后复习；（3）多上机实现各种常用优化算法。

二、课程教学基本内容及要求第一章最优化问题与数学预备知识基本内容：（1 ）最优化的概念；（2）经典最优化中两种类型的问题--无约束极值问题、具有等式约束的极值问题的求解方法；（3）最优化问题的模型及分类；（4）向量函数微分学的有关知识；5）最优化的基本术语。

基本要求：（1）理解最优化的概念；（2）掌握经典最优化中两种类型的问题--无约束极值问题、具有等式约束的极值问题的求解方法；（3）了解最优化问题的模型及分类；（4）掌握向量函数微分学的有关知识；（5）了解最优化的基本术语。

最优化问题2——集合点的选取在日常生活和生产中，我们会经常遇到一些事情需要进行合理、科学地安排，既要在指定时间内完成任务，又要考虑到精打细算，用最少的时间、人力、物力，发挥出最大的效率。

这就涉及这一章的知识“统筹问题”。

它包含的内容非常广泛，例如统筹安排问题、排队问题、最短路线问题、场地设置问题、物资调运问题、最省运费问题等等，每类问题都有特定的解法。

这些来源于生活的实际问题，正是启发同学们学数学、用数学最好的思维锻炼题目。

本节主要介绍两类典型的集合点选取问题：人员集合与物资集合人员集合：问题描述：多个人分散分布在一条线上，现在要使他们在某处集合，我们应该如何选取他们集合的位置，保证所有人走的路程和最短；解决方案：考虑总的人数为n，则有，n为奇数，设在(n+1)/2这个点；n为偶数，设在n/2或n/2+1这两个点中的任意一个或者两点之间的任意一个位置上。

物资集合：问题描述：现在各地有数量不等的物资，需要将它们集中到其中的某地，我们应该如何选取位置，保证运费最省；解决方案：1、计算物资总量；2、分析两端的量，找出来物资量较大的一端，如果大端大于等于总量的一半，则集中到大端；否则，大端集中到离它最近的不为零的位置。

本节主要介绍两类典型的集合点选取问题的解题思路，其推导验证过程会在之后的具体问题中再做如图，在街道上有A、B、C、D、E五栋居民楼，现在在某一居民楼处设立一个公交站，要想使居民到达车站的距离之和最短，车站应该设在哪栋居民楼处？1.1.如图，在街道上有A、B、C、D、E五栋居民楼，每栋楼的距离均为200米，每栋楼里每天都有20个人要坐车，现在设立一个公交站，要想使居民到达车站的距离之和最短，应该设在何处？、A、B、C、D2.2.如图，在街道上有A、B、C、D、E、F六栋居民楼，现在在某一居民楼处设立一个小超市，要想使居民到达超市的距离之和最短，超市应该设在哪栋居民楼处？、A、C、D、E3.3.现在有A、B、C、D、E、F、G、H八个人分别住在如图所示的八栋居民楼，八栋楼之间的距离都不一样，如图所示，现在这八个人某天相约在某栋居民楼碰头，要想使这八个人走的路程和最短，应该在哪栋居民楼下碰头？、A或H、B或G、C或F、D或E有1993名少先队员分散在一条公路上值勤宣传交通法规，问完成任务后应该在公路的什么地点集合，可以使他们从各自的宣传岗位沿公路走到集合地点的路程总和最小？1.1.有998名少先队员分散在一条公路上值勤宣传交通法规，问完成任务后应该在公路的什么地点集合，可以使他们从各自的宣传岗位沿公路走到集合地点的路程总和最小？、出发地点、在第一个学生所在的地点、在正中间两个学生所在的地点、在最后一名学生所在的地点2.2.在一条公路上每隔100千米，这条路上共有5个仓库，并且每个仓库都有10吨的货物，现在想把所有的货物集中存放在一个仓库里，如果每吨货物运输1公里需要1元运输费，那么最少要________元运费才行？集中到哪个仓库能使运费最省？（回答最省运费是多少元）3.3.有101只蚂蚁分别住在一条直线路上，现在他们需要集合起来开会，请问开会地点设在第_____只蚂蚁的家里才能使所有蚂蚁走的路程的总和最小？在一条公路上每隔100千米，有一个仓库(如图)共有5个仓库，一号仓库存有10吨货物，二号仓库有20吨货物，五号仓库存有40吨货物，其余两个仓库是空的．现在想把所有的货物集中存放在一个仓库里，如果每吨货物运输1公里需要1元运输费，那么最少要多少运费才行？1.1.在一条公路上每隔100千米有一个仓库(如图)，共有5个仓库，一号仓库存有30吨货物，二号仓库有20吨货物，五号仓库存有40吨货物，其余两个仓库是空的．现在想把所以的货物集中存放在一个仓库里，如果每吨货物运输1公里需要1元运输费，那么最少要_____元运费才行？2.2.一条直线公路上有5个村，现在几个村的居民要一起开会，每个村的要开会的人数如下图，请问将开会的地点设在哪个村，几个村的居民走的路程和最短？、一、二、三、四3.3.一条直街上有8栋楼，从左到右编号为1，2，3，4，5，6，7，8，相邻两楼的距离都是50米。

华东理工大学研究生《最优化方法》考试卷专业 ________ 班级 ________ 学号 ________ 姓名 ________ 成绩 ________2014年12月11日 一、简答题（40分，每小题4分）1．请写出最优化问题的一般模型形式。

2．试叙述局部最优解和全局最优解的定义。

3．请给出优化算法收敛速度的定义。

4．请给出优化算法的终止准则。

5．给出下降方向的定义和判别方法？ 6．简述下降迭代法的基本步骤。

7．何谓共轭方向？你知道由线性无关向量组构造共轭向量组的方法吗？ 8．最速下降法是最好的优化算法吗？为什么？ 9．何谓可行方向及如何判别？10．优化问题的最优解与可行下降方向有什么关系？二、（10分）试用最速下降法（梯度法）求解如下问题，初始点⎪⎪⎭⎫⎝⎛=110x ，只迭代一次，并判断迭代结果是否为最优解。

21222122)(min 2x x x x x f Rx -+=∈三、（10分）试叙述Powell 基本算法步骤或单纯形替换法的步骤，并简述其特点。

四、（10分）试用惩罚函数求解如下的优化问题8 ..)3()(min 2≥--=x t s x x f五、（10分）考虑下述线性规划问题1223 1832 ..233)(max 321321321321≥=++=+++-=x x x x x x x x x t s x x x x f ，，1．求出该问题的所有基本解，并指出哪些是基本可行解； 2．该问题是否有最优解？若有，请求出其最优解。

六、（10分）考虑问题010)3( 010)3( ..)(max 211323212≥≤---≤+-+=x x x x x x t s x x f ，1．写出上述问题的Kuhn —Tucker 条件。

2．这个问题的最优解满足Kuhn —Tucker 条件吗？为什么？七、（10分）已知某化工反应y 与因数x 和时间t 之间的依赖关系为xa t a ta x a y 43211+++=其中4321,,,a a a a 是待定参数，为确定这三个参数，实验测得有关y x t ,,的五组数据如下：1．试用最小二乘法建立确定参数4321,,,a a a a 的数学模型；2．对于列出的非线性最小二乘问题，你知道有哪些优化算法可求解该问题，并请给出求解该问题的修正Gauss-Newton 算法的迭代公式。

第四章 共轭梯度法§ 共轭方向法共轭方向法是无约束最优化问题的一类重要算法。

它一方面克服了最速下降法中，迭代点列呈锯齿形前进，收敛慢的缺点，同时又不像牛顿法中计算牛顿方向花费大量的工作量，尤其是共轭方向法具有所谓二次收敛性质，即当将其用于二次函数时，具有有限终止性质。

一、共轭方向概念 设G 是n n ⨯对称正定矩阵，1d ，2d 是n 维非零向量，假设120T d Gd = （）那么称1d ，2d 是G －共轭的。

类似地，设1,,m d d 是n R 中一组非零向量。

假设0T i j d Gd =()i j ≠ （）那么称向量组1,,m d d 是G －共轭的。

注：(1) 当G I =时，共轭性就变成正交性，故共轭是正交概念的推行。

(2) 若1,,m d d G －共轭，那么它们必线性无关。

二、共轭方向法共轭方向法确实是依照一组彼此共轭方向依次搜索。

模式算法：1）给出初始点0x ，计算00()g g x =，计算0d ，使000Td g <，:0k = （初始共轭方向）； 2）计算k α和1k x +，使得0()min ()k k k k k f x d f x d ααα≥+=+，令1k k k k x x d α+=+；3）计算1k d +，使10Tk j d Gd +=，0,1,,j k =，令:1k k =+，转2）。

三、共轭方向法的大体定理共轭方向法最重要的性质确实是：当算法用于正定二次函数时，能够在有限多次迭代后终止，取得最优解（固然要执行精准一维搜索）。

定理 关于正定二次函数，共轭方向法最多通过n 步精准搜索终止；且对每一个1i x +，都是()f x 在线性流形00,i j j j j x x x d αα=⎧⎫⎪⎪=+∀⎨⎬⎪⎪⎩⎭∑中的极小点。

证明：首先证明对所有的1i n ≤-，都有10T i j g d +=，0,1,,j i =（即每一个迭代点处的梯度与以前的搜索方向均正交）事实上，由于目标函数是二次函数，因此有()11k k k k k k g g G x x Gd α++-=-=1）当j i <时， ()1111iTTT i j j j k k j k j g d gd g g d +++=+=+-∑110iT T j j kkj k j gd dGd α+=+=+=∑2）当j i =时，由精准搜索性质知：10T i j g d +=综上所述，有 10T i j g d += (0,1,,)j i =。

最优化方法部分课后习题解答习题一1.一直优化问题的数学模型为：22121122123142min ()(3)(4)5()02()50..()0()0f x x xg x x x g x x x s t g x x g x x =−+−⎧=−−≥⎪⎪⎪=−−+≥⎨⎪=≥⎪=≥⎪⎩试用图解法求出：（1）无约束最优点，并求出最优值。

（2）约束最优点，并求出其最优值。

（3）如果加一个等式约束，其约束最优解是什么？12()0h x x x =−=解：（1）在无约束条件下，的可行域在整个平面上，不难看出，当=（3，4）()f x 120x x *x 时，取最小值，即，最优点为=（3，4）：且最优值为：=0()f x *x *()f x （2）在约束条件下，的可行域为图中阴影部分所示，此时，求该问题的最优点就是()f x 在约束集合即可行域中找一点，使其落在半径最小的同心圆上，显然，从图示中可12(,)x x 以看出，当时，所在的圆的半径最小。

*155(,)44x =()f x 其中：点为和的交点，令求解得到：1()g x 2()g x 1122125()02()50g x x x g x x x ⎧=−−=⎪⎨⎪=−−+=⎩1215454x x ⎧=⎪⎪⎨⎪=⎪⎩即最优点为：最优值为：=*155(,)44x =*()f x 658（3）.若增加一个等式约束，则由图可知，可行域为空集，即此时最优解不存在。

2.一个矩形无盖油箱的外部总面积限定为S，怎样设计可使油箱的容量最大？试列出这个优化问题的数学模型，并回答这属于几维的优化问题.解：列出这个优化问题的数学模型为：该优化问题属于三维的优化问题。

123122313123max ()220..00f x x x x x x x x x x S x s t x x =++≤⎧⎪>⎪⎨>⎪⎪>⎩32123sx y z v⎛⎞=====⎜⎟⎝⎠习题二3.计算一般二次函数的梯度。

小学四年级数学《最优化问题》专题分析：在日常生活和工作中，我们经常会遇到下雨的问题。

完成一件事情怎样合理安排才能做到用时最少，效果最好。

这类问题在数学中称为统筹问题，解决问题时，必须树立统筹思想，能同时做的事，尽量同时做。

有时，我们还会遇到求“费时最省”“面积最大”“损耗最小”等问题，这些问题往往可以从极端情况去探索它的最大（小）值。

在数学中称为极值问题。

统筹问题和极值问题实际上都属于最优化问题。

思考角度：1、用时最省：把两件或三件以上的事同时做。

2、费时最省：费时少者优先。

3、面积最大：图形越正，面积越大。

4、乘积最大：两数相差越小，乘积越大。

入门题：1、用一只平底锅煎饼，每次只能放两个，煎一个需要2分钟，规定每个饼的正反面各需1分钟。

问煎3个饼至少需要几分钟？2、妈妈让小明给客人捎水沏茶。

洗水壶需要1分钟，烧开水需要15分钟，洗茶壶需要1分钟，洗茶杯需要1分钟，拿茶叶需要2分钟，为了让客人早点喝上茶，你认为最合理的安排需要多少分钟？3、五（一）班赵明、孙勇、李佳三位同学到达学校卫生室等候校医治病。

赵明打针需要5分钟，孙勇包纱布需要3分钟，李佳点眼药水只需要1分钟，卫生室只有一位校医，问校医如何安排三位同学的治病次序，才能使三位同学留在卫生室的总时间最短？需要几分钟？4、用18厘米的铁丝围成各种长方形，要使长和宽的长度都是整厘米数，围成的长方形的面积最大是多少平方厘米？5、用3 ～～6这四个数字分别组成两个两位数，使这两个两位数的乘积最大。

练习题：1、烤面包时，第一面要烤2分钟，第二面只烤1分钟。

即烤一块面包共需3分钟，小丽用烤面包的架子，一次能放两块面包。

她每天早上要吃3块面包，至少需要几分钟？2、小虎早晨完成几件事：烧一壶开水需要10分钟，把开水灌进热水瓶里需要1分钟，取奶需要5分钟，整理书包需要4分钟，为了尽快完成这些事，怎样安排才能使用的时间最少？最少需要多少分钟？3、甲、乙、丙三人到商场批发部洽谈业务。