最优化方法综述.doc

最优化方法综述 1.引论1.1应用介绍最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多的方案中什么样的方案最优以及怎样找出最优方案。这类问题普遍存在。例如，工程设计中怎样选择设计参数，使得设计方案满足设计要求，又能降低成本；资源分配中，怎样分配有限资源，使得分配方案既能满足各方面的基本要求，又能获得好的经济效益；生产评价安排中，选择怎样的计划方案才能提高产值和利润；原料配比问题中，怎样确定各种成分的比例，才能提高质量，降低成本；城建规划中，怎样安排工厂、机关、学校、商店、医院、住户和其他单位的合理布局，才能方便群众，有利于城市各行各业的发展；农田规划中，怎样安排各种农作物的合理布局，才能保持高产稳产，发挥地区优势；军事指挥中，怎样确定最佳作战方案，才能有效地消灭敌人，保存自己，有利于战争的全局；在人类活动的各个领域中，诸如此类，不胜枚举。最优化这一数学分支，正是为这些问题的解决，提供理论基础和求解方法，它是一门应用广泛、实用性强的学科。1.2优化的问题的基本概念工程设计问题一般都可以用数学模型来描述，即转化为数学模型。优化设计的数学模型通常包括设计变量、目标函数和约束条件。三个基本要素。设计变量的个数决定了设计空间的维数。确定设计变量的原则是：在满足设计基本要求的前提下，将那些对设计目标影响交大的而参数选为设计变量，而将那些对设计目标影响不大的参数作为设计变量，并根据具体情况，赋以定值，以减少设计变量的个数。用来评价和追求最优化设计方案的函数就称为目标函数，目标函数的一般表达式为。优化设计的目的，就是要求所选择的设计变量使目标函数达到最佳值。所谓最佳值就是极大值或极小值。在设计空间中，虽然有无数个设计点，即可能的设计方案，但是一般工程实际问题对设计变量的取值总是有一些限制的，这些限制条件显然是设计变量的函数，一般称之为优化设计问题的约束条件或约束函数。在优化设计问题中，约束条件有两种表现形式，一种是不等式约束，其一般表达式为： ，另一种是等式约束，即。由设计变量、目标函数和约束条件三个基本要素所组成的工程优化设计数学模型所表达的意思是：在满足一定的约束以偶案件下，寻求一组设计变量，使得目标函数取得极小值或极大值。在设计空间中，每一个不等式约束条件都把设计空间划分成两部分，一部分是满足不等式约束条件的，另一部分是不满足约束条件的，两部分的分界面就是所形成的曲面，称为约束面。在二维设计空间中约束面是一条曲线或直线，在三维设计空间中则是一个曲面或超曲面。一个优化设计问题的所有不等式约束的边界将组成一个复合约束边界。满足约束条件的区域称为可行域，而不满足约束条件的区域称为非可行域。可行域内的点称为可行点。1.3分类：若工程优化设计问题的数学模型中只有目标函数而没有约束条件，则称之为无约束优化问题。无约束优化问题的目标函数如果是一元函数，则称之为一维优化问题，他的求解方法称之为一维搜索方法。对于约束优化问题，课按其目标函数和约束函数的特性，分为线性规划问题和非线性规划问题。如果目标函数和所有的约束函数都是线性函数，则称之为线性规划问题；否则称之为非线性规划问题。对于目标函数是二次函数而约束函数都是线性函数这一类问题，一般称之为二次规划问题。另外，还有整数规划、几何规划和多目标规划等。线性规划和非线性规划是数学规划中欧偶那个的两个重要的分支，在工程实际问题中均得到了广泛的应用。1.4凸函数、凸规划：工程优化设计问题大多是非线性规划问题，其数学本质是多元非线性函数求极值问题，如果函数在整个区域有两个或两个以上的极值点，则称每一个极值点为局部极值点。在整个可行域中，比较所有的局部极值点，可得到一个最小或最大的局部极值点，称为全局极值点。但基于数学规划的工程优化设计方法一般只能求得为题的局部极值点，只有当函数具有凸性的情况下，局部极值点才是全域极值点。对于一元函数来说，在某区间内，如果函数的曲线是下凸的，即在刺区间内，一元函数曲线上任意两点间相连的弦线，总不会位于这两点间函数曲线的下面，则称此一元函数具有凸性，或称此函数为凸函数；反之，若函数曲线上任意两点间相连的弦线，总不会位于这两点间的函数曲线的上面，则称此函数具有下凸性，或称此函数为凹函数。如果约束优化问题中的目标函数是凸函数，所有的不等式约束也都是凸函数，则称此约束优化问题为凸规划。凸规划具有一个重要特性，这就是：凸规划的局部极小值一定是全域极小值。对于凸规划问题，只要求出一个局部极小值，它就是全域极小值。所以，优化理论与方法常限于讨论凸规划问题，故称为凸规划理论。应强调指出的是。实际工程优化问题往往不是凸规划问题。所以，采用常用的优化方法，求得的最优解往往是局部最优解。凸规划的可行域是凸集。2.线性规划问题：2.1线性规划的标准形式线性规划即目标函数和约束函数都是线性的约束最优化问题。线性规划在理论和计算方法上都很成熟。他在工程管理和经济管理中，应用都和广泛。它的解法在理论上和方法上都很成熟。虽然大多数工程设计是非线性的，但是也有采用线性逼近方法求解非线性问题的。此外，线性规划方法还常被用作解决非线性问题的子问题的工具，如在可行方向法中可行方向的寻求就是采用线性规划方法。当然，对于真正的线性优化问题，线性规划方法就更有用了。线性规划的标准形式： n为线性规划的维数，m为线性规划的阶数，一般mn。任何其他形式的线性规划均可化为标准形式，并可借助标准形式的求解方法求解。2.1.1一般形式化成标准形式的方法： 如果目标函数为极大化，则可转化为极小化，因为在同样的约束条件下，max z与min（-z）有相同的最优解，故以后常限于讨论极小化的情况。 在约束条件中，如果有不等式约束： 则可加上新的变量，把他们全变为等式约束，即如果有不等式约束则可以减去新的变量，把他们全部变为等是约束，即以上这些引进来的新变量叫做松弛变量，松弛变量并不出现在目标函数中，也不影响问题的解。因此可把所有的约束条件化为统一的等式形式。 当在某些问题中，实际情况并不要求某一变量为非负时，可另，其中，并将其带入目标函数和约束方程中去。2.1.2线性规划的几个基本概念 可行解 凡同时满足标准形式中目标函数和约束条件的任何一个解，称为线性问题的可行解。所有可行解的集合称为可行域。 基本解 另标准形式中某（n-m）个变量等于零，如果剩余的m个变量构成的m个线性方程有唯一的解，则称由此得到的n个变量的解为基本解。 基本可行解 凡满足非负条件的基本解为基本可行解，即既是基本解又是可行解。 最优解 满足目标函数的可行解是线性规划的最优解（即目标函数达到最小值的可行解叫最优解）。当一个线性规划的值无穷大时，则称这样的线性规划是无界的。基本变量和非基本变量 基本可行解中大于零的分量称为基本变量，其余变量称为非基本变量。基本变量和非基本变量是相对于基本可行解来说的。 基向量与基 基本变量所对应的系数称为基向量。线性规划有如下两个基本性质： 线性规划可行解的集合构成一个凸集，且这个凸集是凸多面体。它的每一个定点对应一个基本可行解。 线性规划的最优解如果存在，必然在凸集的某个顶点上达到。2.2解线性规划的单纯形法：求解思路：单纯形法是从一个初始基本可行解出发，寻找使目标函数有较大下降的一个新的基本可行解代替原来的基本可行解，如此完成一个迭代。经过判断，如果没达到最优点，则继续迭代下去。基本可行解的个数是有限的，所以经过有限次迭代，一定能达到最优解。采用单纯形法求解线性规划，主要解决以下三个问题： 如何确定基本可行解； 如何由一个基本可行解迭代出另一个基本可行解，并使目函数值获得较大的下降方向；如何判断一个基本可行解是否为最优解。3. 无约束优化方法无约束优化问题的一般数学表达式为 求解这类问题的方法，称为无约束优化方法。若为一元函数，求解这类为题的无约束优化方法称为一维搜索方法。求解优化问题的迭代算法是按迭代格式 求解的，即从已知点出发，沿给定的方向搜索，以得到目标函数沿方向的极小点，其实质是求的一个最优步长因子使 和是已确定的，所以上述表达式所表达的问题就是以为设计变量的一维优化为题，因而一维搜索方法是优化方法的基础。一维搜索方法有：分数法、黄金分割法、二次插值法和三次插值法。多元函数的无约束优化方法，可按其确定搜索方向所使用的信息和方法的不同氛围两大类。一类方法是需要利用函数的一阶偏导数甚至是二阶偏导数都早搜索方向，如梯度法、牛顿法、变尺度法和共轭梯度法等。这种方法计算量大，但收敛较快，一般称之为解析法。另一种方法是仅利用迭代点的函数值来构造搜索方向，如坐标轮换法、模式搜索法、方向加速法和单纯形法。只需要计算函数值，无需求导，这类方法有突出的优越性，一般称之为直接法。3.1牛顿法 牛顿法基本思想：求的极小值时，先将它在点附近作泰勒展开，取二次近似函数值，再求出这个二次函数的极小点，并一该极小点作为原目标函数的极小点x的一次近似值；若此值不满足精度要求，则可以此近似值作为下一次迭代的初始点，仿照上面的做法，求出二次近似值；照此方法迭代下去，直至所求出的近似极小点满足精度要求为止。牛顿迭代法的公式是： 牛顿法所采用的搜索方向为 其中是海色矩阵，步长因子。3.2 共轭方向法共轭方向的概念是在研究二次函数 （3.1）时提出的，就是首先以3.1式的二次函数为目标给出有关算法，然后再推广到一般的目标函数中去。3.2.1 共轭方向的性质 共轭方向有如下三个性质：性质1 若非零向量系是对共轭的，则这m个向量是线性无关的。性质2 在n维空间中互相共轭的非零向量的个数不超过n。性质3 从任意初始点出发，顺次沿n个G的共轭方向进行一维搜索，最多经过n次迭代就可以找到上式所表示的二次函数极小点，此性质表明这种迭代方法具有二次收敛性。3.2.2 Powell共轭方向法Powell法是一种求解无约束优化问题的较为有效的方法。其基本原理是：首先采用坐标轮换法进行第一轮迭代，然后以第一轮迭代的最末一个极小点和初始点，构成一个新的方向，并以此新的方向作为最末一个方向，而去掉第一个方向，得到第二轮迭代的n个方向。仿此进行下去，直至求得问题的极小值。3.3 不精确的一维搜索用于多维NLP计算过程中，其基本思想是：从出发，沿方向，移动一定的距离，求使有足够的下降。3.4 变尺度法（DFP法）其基本思想是利用牛顿法的迭代公式，然而并不直接计算，而是用一个对称正定矩阵近似的代替。在迭代过程中，不断改进，最后逼近。变尺度法的迭代公式为其中为变尺度法 的搜索方向；为变尺度矩阵，在迭代过程中逐次形成并不断修正。变尺度法的特点：变尺度法在最初的几步迭代，与梯度法类似，函数值的下降是较快的而在最后的几步迭代，变尺度法与牛顿法相近，可较快的收敛到极小点。因而变尺度法就克服了梯度法收敛慢的缺点，但却保留了梯度法在最初几步，函数值下降快的优点；同时，变尺度法避免了计算海色矩阵及其逆矩阵，克服了牛顿法计算量大的缺点，但却有较快的收敛速度。4.约束优化问题工程优化设计问题绝大多数属于约束非线性优化问题，它的一般数学表达式为 其中 、都假定具有连续偏导数。求解这类问题的方法称为约束优化方法。 起作用约束：若在极小点附近，不等式约束变成了等式约束，则该约束条件显然是起作用约束，约束极值点必然存在于这些起作用约束条件的极值上。不起作用约束：在实际的工程优化设计问题中，多数的不等式约束条件在极值点是不起作用的，因而，在某种条件下是可以忽略的。Kuhn-Tucker条件 ：对于一般约束优化问题 如果是上述优化问题的最优解，则有 满足以上两式的点为KuhnTucker点。4.1 惩罚函数法惩罚函数法是一种用来求解约束优化问题的间接方法。基本思想是：将一个有约束的问题转化为一系列的无约束的优化问题来求解。其根据惩罚项的不同函数形式，分为外罚函数法、内罚函数法和混合函数法。外罚函数法：其主要在特点是是惩罚函数定义在可行域的外部，从而在求解系列无约束优化问题的过程中，从可行域的外部逐渐逼近原约束优化问题的最优解。 内罚函数法：内罚函数法只可用来求解不等式约束优化问题，而不能求解等式约束优化问题。其主要特点是将惩罚函数定义在可行域的内部，这样在求解内罚函数的序列无约束优化问题的过程中，所求得的系列无约束优化问题的解总是可行解，从而从可行域的内部逐渐逼近原约束优化问题的解。混合罚函数法：混合罚函数法的基本思想是：当初始点给出后，对等式约束和不能满足的那些不等式约束，用外函数法，而对所满足的那些不等式约束，则用内函数法。4.2 乘子法广义乘子法既可以解决线性优化问题，也可以解决非线性优化问题，广义乘子法所采取的基本策略与广义乘子法没有太大的不同，二者都是在原约束优化问题的基础上，构造一系列无约束优化问题，并以这一系列无约束优化问题的解去逼近原约束优化问题的解，所不同的是，广义乘子法不像外罚函数法那样直接构造原约束优化问题的外罚函数作为无约束优化子问题，而是先构造原问题的的外罚函数代替原问题的目标函数，得到一个增广极值问题，然后再构造增广极值问题的拉格朗日函数作为原问题的无约束优化子问题，并以此系列无约束优化子问题的解去逼近原约束优化子问题的解。理论和实践证明，采用这样的广义乘子法时，只需要在罚因子充分大而无需趋近于无穷的情况下，调节拉格朗日乘子便可以逐次逼近原约束优化问题的解。4.3 Rosen梯度投影法定义：设p为n阶矩阵，若，则称p为投影矩阵。考虑问题 其中是可微函数，A为矩阵，E为矩阵。 梯度投影法的基本思想仍然是从可行点出发，沿可行方向进行搜索。当迭代出发点在可行域内部时，沿负梯度方向进行搜索。当迭代出发点在某些约束的边界上时，将该点处的负梯度投影到M的零空间，M是以起作用约束或部分起作用约束的梯度行为构造成的矩阵。4.4 二次规划二次规划是非线性规划中的一种特殊情形，它的目标函数是二次实函数，约束是线性的。二次规划法的基本原理是将原问题转化为一系列二次规划子问题。求解子间题，得到本次迭代的搜索方向，沿搜索方向寻优，最终逼近问题的最优点，因此这种方法又称序列二次规划法。另外，算法是利用拟牛顿法(变尺度法)来近似构造海赛矩阵，以建立二次规划子问题，故又可称约束变尺度法，这种方法被认为是目前最先进的非线性规划计算方法。5.模糊优化方法最优化问题一直是模糊理论应用最为广泛的领域之一。自从Bellman和Zadeh在20世纪70年代初期对这一研究作出开创性工作以来，其主要研究集中在一般意义下的理论研究、模糊线性规划、多目标模糊规划、以及模糊规划理论在随机规划及许多实际问题中的应用。主要的研究方法是利用模糊集的a截集或确定模糊集的隶属函数将模糊规划问题转化为经典的规划问题来解决。模糊优化方法与普通优化方法的要求相同，仍然是寻求一个控制方案（即一组设计变量），满足给定的约束条件，并使目标函数为最优值，区别仅在于其中包含有模糊因素。普通优化可以归结为求解一个普通数学规划问题，模糊规划则可归结为求解一个模糊数学规划问题。包含控制变量、目标函数和约束条件，但其中控制变量、目标函数和约束条件可能都是模糊的，也可能某一方面是模糊的而其它方面是清晰的。例如模糊约束的优化设计问题中模糊因素是包含在约束条件（如几何约束、性能约束和人文约束等）中的。求解模糊数学规划问题的基本思想是把模糊优化转化为非模糊优化即普通优化问题。方法可分为两类：一类是给出模糊解（fuzzysolution）；另一类是给出一个特定的清晰解（crispsolution）。必须指出，上述解法都是对于模糊线性规划（fuzzylinearprogramming）提出的。然而大多数实际工程问题是由非线形模糊规划（fuzzynonlinearprogramming）加以描述的。于是有人提出了水平截集法、限界搜索法和最大水平法等，并取得了一些可喜的成果。15