最优化方法归纳总结

《最优化方法归纳总结》由会员分享，可在线阅读，更多相关《最优化方法归纳总结（23页珍藏版）》请在金锄头文库上搜索。

1、最优化方法归纳总结最优化方法归纳总结篇一：最优化方法综述最优化方法综述1.引论1.1应用介绍 最优化理论与算法是一个重要的数学分支，它所研 究的问题是讨论在众多的方案中什么样的方案最优以及怎样找出最 优方案。这类问题普遍存在。例如，工程设计中怎样选择设计参数， 使得设计方案满足设计要求，又能降低成本；资源分配中，怎样分配 有限资源，使得分配方案既能满足各方面的基本要求，又能获得好的 经济效益；生产评价安排中，选择怎样的计划方案才能提高产值和利 润；原料配比问题中，怎样确定各种成分的比例，才能提高质量，降 低成本；城建规划中，怎样安排工厂、机关、学校、商店、医院、住 户和其他单位的合理布局，才能

2、方便群众，有利于城市各行各业的发 展；农田规划中，怎样安排各种农作物的合理布局，才能保持高产稳 产，发挥地区优势；军事指挥中，怎样确定最佳作战方案，才能有效 地消灭敌人，保存自己，有利于战争的全局；在人类活动的各个领域 中，诸如此类，不胜枚举。最优化这一数学分支，正是为这些问题的 解决，提供理论基础和求解方法，它是一门应用广泛、实用性强的学 科。1.2优化的问题的基本概念 工程设计问题一般都可以用数学模型 来描述，即转化为数学模型。优化设计的数学模型通常包括设计变量、 目标函数和约束条件。三个基本要素。设计变量的个数决定了设计空 间的维数。确定设计变量的原则是：在满足设计基本要求的前提下，将那

3、些对设计目标影响交大的而 参数选为设计变量，而将那些对设计目标影响不大的参数作为设计变 量，并根据具体情况，赋以定值，以减少设计变量的个数。用来评价 和追求最优化设计方案的函数就称为目标函数，目标函数的一般表达 式为f?x?f?x1,x2,?xn?。优化设计的目的，就是要求所选择的设 计变量使目标函数达到最佳值。所谓最佳值就是极大值或极小值。在 设计空间中，虽然有无数个设计点，即可能的设计方案，但是一般工 程实际问题对设计变量的取值总是有一些限制的，这些限制条件显然 是设计变量的函数，一般称之为优化设计问题的约束条件或约束函数。在优化设计问题中，约束条件有两种表现形式，一种是不等式约束， 其一

4、般表达式为：gu?x?0,?u?1,2,?m?，另一种是等式约束，即 hv(x)?0,(v?1,2,?p?n)。由设计变量、目标函数和约束条件三个基 本要素所组成的工程优化设计数学模型所表达的意思是：在满足一定的约束以偶案件下，寻求一组设计变量，使得目标函 数取得极小值或极大值。在设计空间中，每一个不等式约束条件都 把设计空间划分成两部分，一部分是满足不等式约束条件的，另一部 分是不满足约束条件的，两部分的分界面就是g(x)?0所形成的曲面， 称为约束面。在二维设计空间中约束面是一条曲线或直线，在三维设 计空间中则是一个曲面或超曲面。一个优化设计问题的所有不等式约 束的边界将组成一个复合约束边

5、界。满足约束条件的区域称为可行域， 而不满足约束条件的区域称为非可行域。可行域内的点称为可行点。1.3分类：(最优化方法归纳总结)若工程优化设计问题的数学模型中只有 目标函数而没有约束条件，则称之为无约束优化问题。无约束优化问 题的目标函数如果是一元函数，则称之为一维优化问题，他的求解方 法称之为一维搜索方法。对于约束优化问题，课按其目标函数和约束 函数的特性，分为线性规划问题和非线性规划问题。如果目标函数和 所有的约束函数都是线性函数，则称之为线性规划问题；否则称之为 非线性规划问题。对于目标函数是二次函数而约束函数都是线性函数 这一类问题，一般称之为二次规划问题。另外，还有整数规划、几何

6、规划和多目标规划等。线性规划和非线性规划是数学规划中欧偶那个 的两个重要的分支，在工程实际问题中均得到了广泛的应用。1.4凸函数、凸规划：工程优化设计问题大多是非线性规划问题，其数学本质是多元非 线性函数求极值问题，如果函数在整个区域有两个或两个以上的极值 点，则称每一个极值点为局部极值点。在整个可行域中，比较所有的 局部极值点，可得到一个最小或最大的局部极值点，称为全局极值点。 但基于数学规划的工程优化设计方法一般只能求得为题的局部极值 点，只有当函数具有凸性的情况下，局部极值点才是全域极值点。对 于一元函数来说，在某区间内，如果函数的曲线是下凸的，即在刺区 间内，一元函数曲线上任意两点间相

7、连的弦线，总不会位于这两点间 函数曲线的下面，则称此一元函数具有凸性，或称此函数为凸函数； 反之，若函数曲线上任意两点间相连的弦线，总不会位于这两点间的 函数曲线的上面，则称此函数具有下凸性，或称此函数为凹函数。如 果约束优化问题minf(x)x?R,s.t.gu?0(u?1,2,?,m)n中的目标函 数 f(x)是凸函数，所有的不等式约束也都是凸函数，则称此约束优化问 题为凸规划。凸规划具有一个重要特性，这就是：凸规划的局部极小值一定是全域极小值。对于凸规划问题，只要 求出一个局部极小值，它就是全域极小值。所以，优化理论与方法常 限于讨论凸规划问题，故称为凸规划理论。应强调指出的是。实际工

8、程优化问题往往不是凸规划问题。所以，采用常用的优化方法，求得 的最优解往往是局部最优解。凸规划的可行域是凸集。2.线性规划问题：2.1线性规划的标准形式 线性规划即目标函数和约束函数都是线 性的约束最优化问题。线性规划在理论和计算方法上都很成熟。他在 工程管理和经济管理中，应用都和广泛。它的解法在理论上和方法上 都很成熟。虽然大多数工程设计是非线性的，但是也有采用线性逼近 方法求解非线性问题的。此外，线性规划方法还常被用作解决非线性 问题的子问题的工具，如在可行方向法中可行方向的寻求就是采用线 性规划方法。当然，对于真正的线性优化问题，线性规划方法就更有 用了。线性规划的标准形式：最优化总结课

9、程论文(设计)题目最优化理论与方法小结学 生姓名学号院系专业系统科学指导教师二0一二年十一 月十日最优化课程小结由于我本科是学电气的，没有接触过运筹 学和最优化的知识，刚开始学习的两周很迷惑，后来在图书馆借了书 看，也问了其他同学，才能跟得上老师的步子.那我就总结一下这两个 月的学习，以及我对 最优化理论与方法 的认识.1. 运筹学的起源与方法首先学习的是运筹学，这也是我第一次听 说这个名词，刚开始以为是运输之类的问题.通过学习，我了解到运筹 学的广泛应用.在这里我简述一下.运筹学在商业活动与行政事务中 的早期应用可追溯到几个世纪以前，但是系统的运筹学理论源于第二 次世界大战期间.最初是英国军

10、方为了最大限度的利用已经十分短缺 的战争资源，召集了一批科学家与工程人员共同筹划作物资的分配问 题.英国军方的这一举动很快引起了美国军方的重视，类似的研究小 组在美国三军机构中相继成立，并开发出一套相对完整的新技术，用 以指导协约方面在战略上和战术上的各种军事行动.许多诺贝尔奖金 获得者都为运筹学的建立与发展做出过重要的贡献.运筹学理论和方 法建立在人类认识和人类活动的基础之上，反映了人类分析和处理事 务的思辨过程.因此运筹学既是一门科学，又是一门艺术.作为科学， 运筹学必须在科学方法论的指导下进行科学探索.其工作步骤包括：(1) 确定问题：目标,约束,变量和参数.(2) 建立模型：目标，约束

11、，变量和参数之间的关系.(3) 求解模型:最优解，有效解和满意解.(4) 解的检验:正确性，有效性和稳定性.(5) 解的控制:灵敏度分析.(6)解的实施:解释,培训和监测.作为 艺术，运筹学设计军侧着的社会环境,心理作用，主观意愿和工作经验 等多方面因素，而这些因素又大都具有模糊特征与动态性质.为了有 效的应用运筹学,前英国运筹学学会会长托姆林森提出以下原则：(1) 合伙原则:运筹学工作者与管理工作者相结合.(2) 催化原则:多学科协作，打破常规.(3) 渗透原则:跨部门,跨行业联合.(4) 独立原则:不受某人或者某部门的特殊政策所左右.(5) 宽容原则:广开思路，兼容并需.(6)平衡原则:平

12、衡矛盾,平衡关 系.模型是运筹学研究客观现实的工具和手段.常见的模型有以下3种基本形式(1) 思维模型:研究者对于某种事物的想想或者概念性的描述，如公 司主管头脑中对公司未来市场的规划.这虽然不是一种精确，具体，可 见的形式,但通常是其他模型的渊源.(2) 物理模型:可以是一个与事物同等尺寸，或者被放大，或者被缩 小，或者被简化的几何模型，用以形象的表现和演示被研究的对象;也 可以是一些图标，用以说明事物的流程.(3) 数学模型:采用数学符号精确描述实际事物中的变动因素和因 素见的相互关系.构造模型是一种创造性劳动，成功的模型往往是科 学和艺术的结晶.建模的方法和思路有以下四种.(1) 直接分

13、析法:根据研究者对问题内在的机理的认识直接构造模 型，并利用已知的算法对问题求解与分析，如线性规划模型，动态规划 模型，排队模型，存储模型,决策与对策模型等.(2) 类比法:模仿类似问题的结构性质建立模型并进行类比分析.例 如，物理系统，化学系统，信息系统以及经济系统之间都有某些相同的 地方，因而可互相借鉴.(3) 统计分析法:尽管机理为名，但可根据历史资料或实验结果运用 统计分析方法建模.(4) 逻辑推理法:利用知识和经验对事物的变化过程进行逻辑推理 来构造模型.数学模型是3中常见模型中最抽象，最复杂的模型，它反 映的是事物的本质.数学模型的一般形式可以写为目标的评价准则 U=f(x,y,z

14、)约束条件g(x,y,z) =0式中:x为可控变量,y为已知参 数,z为不确定性因素.目标的评价准则一般要求达到最佳，适中，满 意等.准则可以使一个,也可以是多个.约束条件可以由多个,也可以 一个没有.如果g为等式，即为平衡条件.当模型中没有不确定因素是, 改模型称之为确定性模型.如果不确定性因素是随机因素，则气味随 机模型;如果是模糊因素，则为模糊模型;如果机油随机因素又有模糊 因素,则为模糊随机模型.在建立了问题的数学模型之后，如何求解 模型是运筹学的另一个关键所在.运筹学的进步有来与定量分析技术 的应用于发展，尤其是近年来计算机技术的迅速提高,各种管理决策 方面的应用性软件相继推出.这是

15、决策者得以借助计算机对复杂的实 际问题进行定量分析，大大该井了定量技术的有效性.2. 无约束最有化方法最优化问题无处不在。只要存在选择，并涉 及稀缺资源，就一定存在优化问题。可以很“高深”，比如前面提到 的电力系统无功优化问题，比如导弹的轨迹优化问题；也可以很“生 活”，比如有同学研究了在交大教室、图书馆、实验室和几个食堂之 间的最优路径问题，比如我曾经写过一篇恋爱中的博弈问题，又 比如有同学问周老师：“如何花费最少的时间获得相对较好的最优化课程分数？ ”但它 们有着共同的特点，就是很实际，并且很有趣。可以说，作为一个普 通的工学研究生，以往从没有接触过一门数学课程(除了那些最基本 的算术、几

16、何)，如此地贴近现实问题，立足现实问题，而最终亦指 向现实问题。在最优化理论系统中，除了可以感受到一般数学理论 的那种纯粹、抽象、透彻、简洁，也能感受一种无处不在的实用主义 价值观，“实用”、“好用”、“凑效”这些看起来不那么“数学” 的评价标准在这个领域中也有着相当的地位。而在各种“数学”、 “非数学”的标准之间的权衡取舍，本身就是一个多目标优化问题而 体现出某种对系统性思维的诉求。思考、研究这样的问题，即有用， 又有趣，令人快乐无穷。下面依次介绍我们所学的几种方法.2.1最速下降法基本原理(一)无约束问题的最优性条件无约束问题的最优解所要满足的必 要条件和充分条件是我们设计算法的依据，为此我们有以下几个定理。 定理1设f : Rn ?R1在点x ?Rn处可微。若存在p?Rn， 使?f (x)T p ?0则向量 p 是 f在点x处的下降方向。定