最优化方法综述

1最优化方法综述21.引论1.1应用介绍最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多的方案中什么样的方案最优以及怎样找出最优方案。这类问题普遍存在。例如，工程设计中怎样选择设计参数，使得设计方案满足设计要求，又能降低成本；资源分配中，怎样分配有限资源，使得分配方案既能满足各方面的基本要求，又能获得好的经济效益；生产评价安排中，选择怎样的计划方案才能提高产值和利润；原料配比问题中，怎样确定各种成分的比例，才能提高质量，降低成本；城建规划中，怎样安排工厂、机关、学校、商店、医院、住户和其他单位的合理布局，才能方便群众，有利于城市各行各业的发展；农田规划中，怎样安排各种农作物的合理布局，才能保持高产稳产，发挥地区优势；军事指挥中，怎样确定最佳作战方案，才能有效地消灭敌人，保存自己，有利于战争的全局；在人类活动的各个领域中，诸如此类，不胜枚举。最优化这一数学分支，正是为这些问题的解决，提供理论基础和求解方法，它是一门应用广泛、实用性强的学科。1.2优化的问题的基本概念工程设计问题一般都可以用数学模型来描述，即转化为数学模型。优化设计的数学模型通常包括设计变量、目标函数和约束条件。三个基本要素。设计变量的个数决定了设计空间的维数。确定设计变量的原则是：在满足设计基本要求的前提下，将那些对设计目标影响3交大的而参数选为设计变量，而将那些对设计目标影响不大的参数作为设计变量，并根据具体情况，赋以定值，以减少设计变量的个数。用来评价和追求最优化设计方案的函数就称为目标函数，目标函数的一般表达式为nxxxfxf,,21。优化设计的目的，就是要求所选择的设计变量使目标函数达到最佳值。所谓最佳值就是极大值或极小值。在设计空间中，虽然有无数个设计点，即可能的设计方案，但是一般工程实际问题对设计变量的取值总是有一些限制的，这些限制条件显然是设计变量的函数，一般称之为优化设计问题的约束条件或约束函数。在优化设计问题中，约束条件有两种表现形式，一种是不等式约束，其一般表达式为：muxgu,2,1,0，另一种是等式约束，即()0,(1,2,)vhxvpn。由设计变量、目标函数和约束条件三个基本要素所组成的工程优化设计数学模型所表达的意思是：在满足一定的约束以偶案件下，寻求一组设计变量，使得目标函数取得极小值或极大值。在设计空间中，每一个不等式约束条件都把设计空间划分成两部分，一部分是满足不等式约束条件的，另一部分是不满足约束条件的，两部分的分界面就是g()0x所形成的曲面，称为约束面。在二维设计空间中约束面是一条曲线或直线，在三维设计空间中则是一个曲面或超曲面。一个优化设计问题的所有不等式约束的边界将组成一个复合约束边界。满足约束条件的区域称为可行域，而不满足约束条件的区域称为非可行域。可行域内的点称为可行点。1.3分类：4若工程优化设计问题的数学模型中只有目标函数而没有约束条件，则称之为无约束优化问题。无约束优化问题的目标函数如果是一元函数，，则称之为一维优化问题，他的求解方法称之为一维搜索方法。对于约束优化问题，课按其目标函数和约束函数的特性，分为线性规划问题和非线性规划问题。如果目标函数和所有的约束函数都是线性函数，则称之为线性规划问题；否则称之为非线性规划问题。对于目标函数是二次函数而约束函数都是线性函数这一类问题，一般称之为二次规划问题。另外，还有整数规划、几何规划和多目标规划等。线性规划和非线性规划是数学规划中欧偶那个的两个重要的分支，在工程实际问题中均得到了广泛的应用。1.4凸函数、凸规划：工程优化设计问题大多是非线性规划问题，其数学本质是多元非线性函数求极值问题，如果函数在整个区域有两个或两个以上的极值点，则称每一个极值点为局部极值点。在整个可行域中，比较所有的局部极值点，可得到一个最小或最大的局部极值点，称为全局极值点。但基于数学规划的工程优化设计方法一般只能求得为题的局部极值点，只有当函数具有凸性的情况下，局部极值点才是全域极值点。对于一元函数来说，在某区间内，如果函数的曲线是下凸的，即在刺区间内，一元函数曲线上任意两点间相连的弦线，总不会位于这两点间函数曲线的下面，则称此一元函数具有凸性，或称此函数为凸函数；反之，若函数曲线上任意两点间相连的弦线，总不会位于这两点间的函数曲线的上面，则称此函数具有下凸性，或称此函数为凹函数。5如果约束优化问题min(),..0(1,2,,)nufxxRstgum中的目标函数()fx是凸函数，所有的不等式约束也都是凸函数，则称此约束优化问题为凸规划。凸规划具有一个重要特性，这就是：凸规划的局部极小值一定是全域极小值。对于凸规划问题，只要求出一个局部极小值，它就是全域极小值。所以，优化理论与方法常限于讨论凸规划问题，故称为凸规划理论。应强调指出的是。实际工程优化问题往往不是凸规划问题。所以，采用常用的优化方法，求得的最优解往往是局部最优解。凸规划的可行域是凸集。2.线性规划问题：2.1线性规划的标准形式线性规划即目标函数和约束函数都是线性的约束最优化问题。线性规划在理论和计算方法上都很成熟。他在工程管理和经济管理中，应用都和广泛。它的解法在理论上和方法上都很成熟。虽然大多数工程设计是非线性的，但是也有采用线性逼近方法求解非线性问题的。此外，线性规划方法还常被用作解决非线性问题的子问题的工具，如在可行方向法中可行方向的寻求就是采用线性规划方法。当然，对于真正的线性优化问题，线性规划方法就更有用了。线性规划的标准形式：61122111112112211min..0nnnnnnmmnnmncxcxcxstaxaxbaxaxbaxaxbxn为线性规划的维数，m为线性规划的阶数，一般mn。任何其他形式的线性规划均可化为标准形式，并可借助标准形式的求解方法求解。2.1.1一般形式化成标准形式的方法：⑴如果目标函数为极大化，则可转化为极小化，因为在同样的约束条件下，kxmaxz与min（-z）有相同的最优解，故以后常限于讨论极小化的情况。⑵在约束条件中，如果有不等式约束：1122iiinniaxaxaxb则可加上新的变量0nix，把他们全变为等式约束，即1122iiinnniiaxaxaxxb如果有不等式约束1122iiinniaxaxaxb则可以减去新的变量nix，把他们全部变为等是约束，即1122iiinnniiaxaxaxxb以上这些引进来的新变量叫做松弛变量，松弛变量并不出现在目标函数中，也不影响问题的解。因此可把所有的约束条件化为统一的7等式形式。⑶当在某些问题中，实际情况并不要求某一变量kx为非负时，可另,kkkxUV，其中，0,0kkUV，并将其带入目标函数和约束方程中去。2.1.2线性规划的几个基本概念⑴可行解凡同时满足标准形式中目标函数和约束条件的任何一个解12,,,nxxxx，称为线性问题的可行解。所有可行解的集合称为可行域。⑵基本解另标准形式中某（n-m）个变量等于零，如果剩余的m个变量构成的m个线性方程有唯一的解，则称由此得到的n个变量的解为基本解。⑶基本可行解凡满足非负条件(1,2,,)ixjn的基本解为基本可行解，即既是基本解又是可行解。⑷最优解满足目标函数的可行解是线性规划的最优解（即目标函数达到最小值的可行解叫最优解）。当一个线性规划的值无穷大时，则称这样的线性规划是无界的。⑸基本变量和非基本变量基本可行解中大于零的分量称为基本变量，其余变量称为非基本变量。基本变量和非基本变量是相对于基本可行解来说的。⑹基向量与基基本变量所对应的系数称为基向量。线性规划有如下两个基本性质：⑴线性规划可行解的集合构成一个凸集，且这个凸集是凸多面8体。它的每一个定点对应一个基本可行解。⑵线性规划的最优解如果存在，必然在凸集的某个顶点上达到。2.2解线性规划的单纯形法：求解思路：单纯形法是从一个初始基本可行解(0)x出发，寻找使目标函数有较大下降的一个新的基本可行解(1)x代替原来的基本可行解，如此完成一个迭代。经过判断，如果没达到最优点，则继续迭代下去。基本可行解的个数是有限的，所以经过有限次迭代，一定能达到最优解。采用单纯形法求解线性规划，主要解决以下三个问题：⑴如何确定基本可行解；⑵如何由一个基本可行解迭代出另一个基本可行解，并使目函数值获得较大的下降方向；⑶如何判断一个基本可行解是否为最优解。3.无约束优化方法无约束优化问题的一般数学表达式为min()fxnxR求解这类问题的方法，称为无约束优化方法。若()fx为一元函数，求解这类为题的无约束优化方法称为一维搜索方法。求解优化问题的迭代算法是按迭代格式(1)()()kkkxxs求解的，即从已知点()kx出发，沿给定的方向()ks搜索，以得到目标函数沿()ks方向的极小点，其实质是求的一个最优步长因子k使9(1)()()()()()()min()kkkkkkkfxfxsfxs()kx和()ks是已确定的，所以上述表达式所表达的问题就是以为设计变量的一维优化为题，因而一维搜索方法是优化方法的基础。一维搜索方法有：分数法、黄金分割法、二次插值法和三次插值法。多元函数的无约束优化方法，可按其确定搜索方向所使用的信息和方法的不同氛围两大类。一类方法是需要利用函数的一阶偏导数甚至是二阶偏导数都早搜索方向，如梯度法、牛顿法、变尺度法和共轭梯度法等。这种方法计算量大，但收敛较快，一般称之为解析法。另一种方法是仅利用迭代点的函数值来构造搜索方向，如坐标轮换法、模式搜索法、方向加速法和单纯形法。只需要计算函数值，无需求导，这类方法有突出的优越性，一般称之为直接法。3.1牛顿法牛顿法基本思想：求()fx的极小值时，先将它在点()kx附近作泰勒展开，取二次近似函数值，再求出这个二次函数的极小点，并一该极小点作为原目标函数的极小点x的一次近似值；若此值不满足精度要求，则可以此近似值作为下一次迭代的初始点，仿照上面的做法，求出二次近似值；照此方法迭代下去，直至所求出的近似极小点满足精度要求为止。牛顿迭代法的公式是：(1)()()1()[()]()kkkkxxHxfx牛顿法所采用的搜索方向为()()1()[()]()kkksHxfx其中()()kHx是海色矩阵，步长因子1k。3.2共轭方向法10共轭方向的概念是在研究二次函数()0.5TTfxxGxbxc（3.1）时提出的，就是首先以3.1式的二次函数为目标给出有关算法，然后再推广到一般的目标函数中去。3.2.1共轭方向的性质共轭方向有如下三个性质：性质1若非零向量系011,,,mddd是对共轭的，则这m个向量是线性无关的。性质2在n维空间中互相共轭的非零向量的个数不超过n。性质3从任意初始点(0)x出发，顺次沿n个G的共轭方向011,,,mddd进行一维搜索，最多经过n次迭代就可以找到上式所表示的二次函数()fx极小点x，此性质表明这种迭代方法具有二次收敛性。3.2.2Powell共轭方向法Powell法是一种求解无约束优化问题的较为有效的方法。其基本原理是：首先采用坐标轮换法进行第一轮迭代，然后以第一轮迭代的最末一个极小点和初始点，构成一个新的方向，并以此新的方向作为最末一个方向，而去掉第一个方向，得到第二轮迭代的n个方向。仿此进行下去，直至求得问题的极小值。3.3不精确的一维搜索用于多维NLP计算过程中，其基本思想是：从()kx出发，沿()ks方向，移动一定的距离k，求(1)()()kkkkxxs使(1)()kfx有足够的下降。3.4变尺度法（DFP法）11其基本思想是利用牛顿法的迭代公式，然而并不直接计算()1[()]kHx，而是用一个对称正定矩阵(k)A近似的代替()1[()]kHx。(k)A在迭代过程中，不断改进，最后逼近()1[()]kHx。变尺度法的迭代公式为(1)()()()()kkkkkxxAfx其中(1)()()()()kkkkxxAfx()()()