logo资料库

最优化方法及其应用.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：4.57M 资料格式：pdf 举报 版权申诉
第1页 / 共158页
第2页 / 共158页
第3页 / 共158页
第4页 / 共158页
第5页 / 共158页
第6页 / 共158页
第7页 / 共158页
第8页 / 共158页
资料共158页，剩余部分请下载后查看
    第一章 最优化问题总论 无论做任何一件事，人们总希望以最少的代价取得最大的效益，也就是力求最好，这就 是优化问题．最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学 科．例如，从甲地到乙地有公路、水路、铁路、航空四种走法，如果我们追求的目标是省钱， 那么只要比较一下这四种走法的票价，从中选择最便宜的那一种走法就达到目标．这是最简 单的最优化问题，实际优化问题一般都比较复杂． 概括地说，凡是追求最优目标的数学问题都属于最优化问题．作为最优化问题，一般要 有三个要素：第一是目标；第二是方案；第三是限制条件．而且目标应是方案的“函数”．如 果方案与时间无关，则该问题属于静态最优化问题；否则称为动态最优化问题． §1.1 最优化问题数学模型 最简单的最优化问题实际上在高等数学中已遇到，这就是所谓函数极值，我们习惯上又 称之为经典极值问题． 例 1.1 对边长为 a 的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽， 问如何剪法使水槽的容积最大？ 解 设剪去的正方形边长为 x，由题意易知，与此相应的水槽容积为 令 得两个驻点： ． ． ， 第一个驻点不合实际，这是因为剪去 4 个边长为 的正方形相当于将铁板全部剪去．现 在来判断第二个驻点是否为极大点． ∵ ∴ ， ， 是极大点． 因此，每个角剪去边长为 的正方形可使所制成的水槽容积最大． 例 1.2 求侧面积为常数 ，体积最大的长方体体积． 解 设长方体的长、宽、高分别为 体积为 ，则依题意知体积为 条件为 由拉格朗日乘数法，考虑函数 ， ． ， xxaxf2)2()(−=0)6)(2()2()2)(2(2)('2=−−=−+−−=xaxaxaxxaxfaxax6121==，2aaxf824)(''−=04)6(''−=aaf6ax=6a)0(62aazyx，，vxyzzyxfv==)(，，06)(2)(2=−++=axyxzyzzyx，，)6222()(2axyxzyzxyzzyxF−+++=，，
    由题意可知 应是正数，由此 ，将上面三个等式分别乘以 并利用条件 ，得到 比较以上三式可得 ， 从而 ．又侧面积固定的长方体的最大体积客观存在，因此侧面积固定的长方 体中以正方体体积最大，其最大值为 ． 例 1.3 某单位拟建一排四间的停车房，平面位置如图 1.1 所示．由于资金及材料的限 制，围墙和隔墙的总长度不能超过 40m，为使车房面积最大，应如何选择长、宽尺寸？ 解 设四间停车房长为 ，宽为 ．由题意可知面积为 ， ， ． 且变量 ， 应满足 x2 x1 图 1.1 ， 即求 以上三个例子，虽然简单，但是它代表了三种类型的最优化问题． 第一个例子代表无约束极值问题： 一 般 可 表 示 为 是定义在 上的可微函数． 或 ． 这 里 ， 求极值的方法是从如下含有 个未知数 的非线性方程组 2()02()02()0xyzFyzyzFxzzxFxyxy=++==++==++=，，，zyx，，0zyx，，23axyzxyz=++2222(3)02(3)02(3)0xyzayzxyzazxxyzaxy+−=+−=+−=，，．xyazxayza−=−=−222333azyx===3a1x2x2121)(xxxxf=，1x2x405221+xx1200xx，2121),(maxxxxxf=1212254000xxxx+，，．),,,(min21nxxxf),,,(max21nxxxf),,,(21nxxxfnRnnxxx,,,21
    中解出驻点，然后判定或验证这些驻点是不是极值点． 第二个例子代表具有等式约束的极值问题： 一般可表示为 该问题的求解通常采用拉格朗日乘数法，即把这个问题转化为求 的无约束极值问题． 第三个例子代表具有不等式约束的极值问题． 下面具体分析上述三种类型的最优化问题中按经典极值问题解法可能出现不能解决的 情况： （1）当变量个数增加且方程组又是非线性，求解此方程组只有在相当特殊情况下才能 人工解出．正因为如此，通常高等数学中的求极值问题的变量个数一般不超过三个． （2）当限制条件出现不等式，无论变量数多少，按经典极值方法求解根本无法解决． 直到本世纪 50 年代，最优化理论的建立以及电子计算机的迅速发展，才为求解各种最 优化问题提供了雄厚的基础和有效手段．不过最优化方法作为一门崭新的应用学科，有关理 论和方法还没有完善，有许多问题还有待解决，目前正处于迅速发展之中． 最优化问题的数学模型包含三个要素：变量（又称设计变量）、目标函数、约束条件． 一、变量 一个优化设计方案是用一组设计参数的最优组合来表示的．这些设计参数可概括地划分 为两类：一类是可以根据客观规律、具体条件、已有数据等预先给定的参数，统称为常量； 另一类是在优化过程中经过逐步调整，最后达到最优值的独立参数，称为变量．优化问题的 目的就是使各变量达到最优组合．变量的个数称为优化问题的维数．例如有 个变量 的 优 化 问 题 就 是 在 维 空 间 中 寻 优 ． 维 空 间 中 的 点 就代表优化问题中的一个方案．当变量为连续量时，称为连续变量； 若变量只能在离散量中取值，称为离散变量． 二、目标函数 反映变量间相互关系的数学表达式称为目标函数．其值的大小可以用来评价优化方案的 好坏．按照规范化的形式，一般把优化问题归结为求目标函数的极小化问题，换句话说，目 标函数值越小，优化方案越好．对于某些追求目标函数极大的问题，可以转化成求其负值最 小的问题，即 因此在本书的叙述中，一律把优化问题描述为目标函数的极小化问题，其一般形式为 ． 如果优化问题只有一个目标函数，称为单目标函数，如果优化问题同时追求多个目标，则该 ． 问题的目标函数称为多目标函数． 多目标优化问题的目标函数通常表示为 ===0)('0)('0)('21212121nxnxnxxxxfxxxfxxxfn，，，，，121212min()max()()0123()nnjnfxxxfxxxhxxxjmmn==，，，或，，，，，，，，，，，，．121212121()()()mnmnjjnjLxxxfxxxhxxx==−，，，；，，，，，，，，，nnxxx，，，21nnRnnRTnxxxX][21，，，=12max()max()min[()]nfXfxxxfX==−−，，，12min()min()nfXfxxx=，，，
    其中 ．这时的目标函数在目标空间中是一个 维矢量，所以又称之为 矢量优化问题（一般用 min 加一个前缀“ ”来表示矢量极小化）． 三、约束条件 变量间本身应该遵循的限制条件的数学表达式称为约束条件或约束函数． 约束条件按其表达式可分为不等式约束和等式约束两种，即 ， 上式中“s. t.”为 Subject to 的缩写，意即“满足于”或“受限于”．按约束条件的作用还可 将约束条件划分为起作用的约束（紧约束、有效约束）和不起作用的约束（松约束、消极约 束）．等式约束相当于空间里一条曲线（曲面或超曲面），点 X 必须为该曲线（曲面或超曲 面）上的一点，因而总是紧约束．有一个独立的等式约束，就可用代入法消去一个变量，使 优化问题降低一维．因此，数学模型中独立的等式约束个数应小于变量个数；如果相等，就 不是一个待定优化系统，而是一个没有优化余地的既定系统．不等式约束通常是以其边界 表现出约束作用的，它只限制点 X 必须落在允许的区域内（包括边 界上），因而不等式约束的个数与变量个数无关．不带约束条件的优化问题称为无约束最优 化问题；带约束条件的优化问题称为约束最优化问题． 四、带约束条件的优化问题数学模型表示形式 综上所述，全书所要讨论的问题是如下的（静态）最优化问题，其表示形式有三种： 第一种最优化问题表示形式为 第二种最优化问题表示形式为 第三种最优化问题表示形式为 （1.1） 其中 ． 上述三种表示形式中， 称为集约束．在所讨论的最优化问题中，集约束是无关紧 要的．这是因为一般 ，不然的话， 通常也可用不等式约束表达出来．因此今后一 般不再考虑集约束． 满足所有约束的点 称为容许点或可行点．容许点的集合称为容许集或可行域．可用 表示． 一般地，对于最优化问题（1.1）的求解，是指在可行域内找一点 ，使得目标函数 12min()[()()()]TmVFXfXfXfX−=，，，TnxxxX][21，，，=m−V()012..()012ijgXilsthXjm===，，，，，，，，，．)0)((0)(=XgXg或1212[]1212min()()012..()012()Tnnxxxinjnfxxxgxxxilsthxxxjmmn===，，，，，，，，，，，，，，，，，，，，，，．min()()012..()012()XijfXgXilsthXjmmn===，，，，，，，，，，．min()()0..()0XfGXstHX=，，，X11()[()()]()[()()]TTlmGXgXgXHXhXhX==，，，，，XnRX{|()012()012()}ijDXgXilhXjmmn====，，，，；，，，，*X)(Xf
    在该点取得极小值，即 这样的 称为问题（1.1）的最优点，也称极小点，而相应的目标函数值 称为最优 值；合起来， 称为最优解，但习惯上常把 本身称为最优解．最优点的各分 量和最优值必须是有限数． §1.2 最优化问题的算法 一、二维最优化问题的图解法 二维最优化问题具有鲜明的几何解释，这对于理解有关理论和掌握所述的方法是很有益 处的．下面讨论的二维最优化问题为 （一）约束集合 当约束函数为线性时，等式约束在 的坐标平面上为一条直线；不等式约束在 的坐标平面上为一半平面．当约束函数（例如 ）为非线性时，则等式约束条 件 在 的坐标平面上为一条曲线（如图 1.2 所示）．当约束函数（例如 ） 为 非 线 性 时 ， 则 不 等 式 约 束 在 的 坐 标 平 面 上 为 曲 线 把坐标平面分成两部分当中的一部分（如图 1.3 所示）． 图 1.2 图 1.3 综上所述，当把约束条件中的每一个等式所确定的曲线，以及每一个不等式所确定的部 分在 坐标平面上画出之后，它们相交的公共部分即为约束集合 D． 例 1.4 在 坐标平面上画出约束集合 ． 解 满足 的区域为以原点为圆心，半径为 1 的圆盘；满足 的 区域为第一象限中的扇形（如图 1.4 所示）． ***()min()()0..()0fXfXGXstHX==，，．*X)(*Xf))((**XfX，*X==.0)(210)(..)(min212121xxhlixxgtsxxfi，，，，，，，21xx，21xx，)(21xxh，0)(21=xxh，21xx，)(211xxg，0)(211xxg，21xx，0)(211=xxg，21xx，21xx，}001|],{[21222121+=xxxxxxDT，，12221+xx0021xx，
    （二）等高线 我们知道 在三维空间中表示一张曲面． （其中 为常数）在三维空间中表示平行于 平面的 一个平面，这个平面上任何一点的高度都等于常数 （如图 1.5 所示）． 图 1.4 图 1.5 现在，在三维空间中曲面 与平面 有一条交线 ．交线 在 平面 上的投影曲线是 ，可见曲线 上的点 到平面 的高度都等于常数 ，也即曲 线 上的 的函数值 都具有相同的值 ．当常数 取不同的值时，重复上面 的讨论，在 平面上得到一簇曲线——等高线．不难看出，等高线的形状完全由曲面 的形状所决定；反之，由等高线的形状也可以推测出曲面 的形 状．在以后的讨论中，不必具体画出曲面 的图形，只须在 平面上变动常 数 画出曲线簇 ． 例 1.5 在 坐标平面上画出目标函数 的等高线． 解 因为当取 时，曲线 表示是以原点为圆心，半径为 的圆．因此 等高线是一簇以原点为圆心的同心圆（如图 1.6 所示）． （三）几何意义及图解法 当在 坐标平面上分别画出约束集合 D 以及目标 函数 的等高线后，不难求出二维最优化问题的最 优解．下面举例说明． 例 1.6 用图解法求解二维最优化问题 图 1.6 解 由例 1.4 得到约束集合 D（如图 1.7 所示）．目标函数的等高线是以 为圆 心的同心圆，并且这簇同心圆的外圈比内圈的目标函数值大．因此，这一问题成为在约束集 合中找一点 ，使其落在半径最小的那个同心圆上．不难看出，问题的最优解 )(21xxft，=ct=c21xx，c)(21xxft，=ct=LL21xx，LLTxx][21，ct=cLTxx][21，)(21xxf，cc21xx，)(21xxft，=)(21xxft，=)(21xxft，=21xx，ccxxf=)(21，21xx，222121)(xxxxf+=，0ccxx=+2221c21xx，)(21xxf，2212221212min[(2)(2)]1..00xxxxstxx++++，，，．T]22[−−，Txx][21，
    ． 图 1.7 二、最优化问题的迭代解法 （一）迭代方法 在经典极值问题中，解析法虽然具有概念简明，计算精确等优点，但因只能适用于简单 或特殊问题的寻优，对于复杂的工程实际问题通常无能为力，所以极少使用． 最优化问题的迭代算法是指：从某一选定的初始点出发，根据目标函数、约束函数在该 点的某些信息，确定本次迭代的一个搜索方向和适当的步长，从而到达一个新点，用式子表 示即为 （1.2） 式中 代表前一次已取得的迭代点，在开始计算时为迭代初始点 ， 代表新的迭代 点， 代表第 次迭代计算的搜索方向， 代表第 次迭代计算的步长因子． 按照式（1.2）进行一系列迭代计算所根据的思想是所谓的“爬山法”，就是将寻求函数 极小点（无约束或约束极小点）的过程比喻为向“山”的顶峰攀登的过程，始终保持向“高” 的方向前进，直至达到“山顶”．当然“山顶”可以理解为目标函数的极大值，也可以理解 为极小值，前者称为上升算法，后者称为下降算法．这两种算法都有一个共同的特点，就是 每前进一步都应该使目标函数有所改善，同时还要为下一步移动的搜索方向提供有用的信 息．如果是下降算法，则序列迭代点的目标函数值必须满足下列关系 如果是求一个约束的极小点，则每一次迭代的新点 都应该在约束可行域内，即 ． 图 1.8 为迭代过程示意图． 由上面的迭代过程可知，在迭代过程中有两个规则需要确定：一个是搜索方向 的选 TTxxX]00[][21*，，==1012kkkkXXtPk+=+=，，，，kX0X1+kXkPkktk011()()()()kkfXfXfXfX+，，21XX012kXDk=，，，，kP
    取；一个是步长因子 的选取．一旦 和 的选取方法确定，则一种迭代算法就确定，即 不同的规则就对应不同的最优化方法． （二）收敛速度与计算终止准则 （1）收敛速度 作为一个算法，能够收敛于问题的最优解当然是必要８的，但仅收敛还不够，还必须能 以较快的速度收敛，这才是好的算法． 定义 1.1 设由算法 A 产生的迭代点列 在某种“||·||”的意义下收敛 图 1.8 于点 ，即 的常数 ，使得 ，若存在实数 及一个与迭代次数 无关 则称算法 A 产生的迭代点列 具有 阶收敛速度，或称算法 A 为 阶收敛的．特别地： ① 当 ② 当 时，称迭代点列 具有线性收敛速度或称算法 A 为线性收敛的． 时，或 时，称迭代点列 具有超线性收敛速度或 称算法 A 是超线性收敛． ③ 当 时，迭代点列 叫做具有二阶收敛速度或算法 A 是二阶收敛的． 一般认为，具有超线性收敛或二阶收敛的算法是较快速的算法． 例 1.7 设一算法 A 产生迭代点列 ，它收敛于点 ，试判定算法 A 的收 敛速度． 解 因为 ， 即取 所以算法 A 具有线性收敛速度． ． ktkPktkX*X0||||lim*=−→XXkk0k0q，qXXXXkkk=−−+→||||||||lim**1}{kX01=q，}{kX021q，0,1==q}{kX2=}{kX}1{kXk=0*=X1|01||011|lim=−−+→kkk01,1==q
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料