最优化心得范文.doc

最优化心得范文 浅谈对最优化原理与方法的学习摘要众所周知，最优化问题具有普遍性、实用性和趣味性。 不仅在工农业生产、经济管理、交通建设等方面应用广泛，而且在日常生活中也经常遇到。 本文给出了一个运输问题的数学模型，对最优化原理的理论算法进行了；同时本文也浅谈了一下理论算法和实际问题计算上的差异，最后给出了对最优化的一些展望。 关键词最优化；学习感想；数学模型；算法差异最优化问题无处不在，它不仅仅是关系到工农业生产、国家建设的大问题，也可能关系我们每天的日常生活。 只要存在着选择，并涉及资源利用，就一定存在最优化问题。 它可以很“高深”，比如在工程建设中的电力系统无功优化问题，比如国防建设中的导弹的轨迹优化问题；也可以很“生活”，比如我们可以研究同学在内大教室、图书馆、实验室和几个食堂之间的最优路径问题。 它们有着共同的特点，就是很实际，并且很有趣。 我们不仅要能够发现这些问题，还要善于将这些问题进行数学化抽象建立数学模型，而且还要能够设计出相应算法，使得我们能够更加方便、简洁地给出每个模型的优化解或者是近似最优解。 一、实际问题建模针对实际的工业生产和日常生活中遇到的最优化问题，我们首先就是要能够将其转化成为数学模型，为求解打下基础。 建立模型一般有这样几个步骤首先是提出问题并收集相关数据、资料；其次，利用数学知识建立一个数学模型，确定变量、目标函数以及约束条件；最后，利用数学理论计算出该模型的最优解，将之放回到实际问题中进行检验和实施，利用反馈信息再调整模型。 例如运输问题在某一地区，有某种物资需要从m个生产地运往n个销售地。 如果每个产地的供应量、每个销地的需求量以及产地到销地的单位运费都是已知的，那么将这种物资从各个产地调运到各个销地，调运的方案可以很多。 应如何组织调运，才能使总运费或运输量最小，就称为运输问题。 对于运输问题，我们可以按照如下思路建立数学模型假设产地设某种物资有m个产地，n个需求地，各产地的产量、各销地的销量以及各产地至各销地的单位运价如下ijc第i个产地到第j个销地的单位运价；ia第i个产地的产量；jb第j个销地的需求量；ijx第i个产地运往第j个销地的物资数量。 其中，1,2.;1,2.im jn?。 当产销平衡时，我们可以得到如下的线性规划模型（P），而对于产销不平衡问题，及供大于求和供不应求问题时，我们只需要在产销平衡的模型基础上将约束条件适当地进行调整就可以得到。 比如当供大于求时将第一组约束条件修改为 （1），供不应求时将第二组条件修改为 （2）即可。 11j=1?i=1?min.s t1,2,.i()P1,2,.j01,2,.,i1,2,.nmijijjinijimijjijc xxamxbnxmjn?j=1?1,2,.inijixam? （1）i=1?1,2,.jmijjxbn? （2）当然，在实际的运输过程中还会附加其他一些条件，比如说要求某产地到某销地的运输量不能多于（或少于）指定量，这就需要增加约束条件。 二、理论问题求解方法由于优化问题是多种多样的，因而建立的模型也是类型很多的，既有线性规划、非线性规划、整数规划，也有动态规划、图论等。 正是由于模型的多样性，使得我们在求解不同的模型时，所用的方法也是不尽相同的。 2.1连续型优化问题数学模型为描述最优化的目标函数()f x，然后求使得()nD DR?f x最小的*x点min()f x()x? （1）无约束优化问题除了解析解法，其数值解法主要包括线性规划的经典解法单纯形搜索法；对偶单纯形法；内点算法（大型）。 整数规划的经典解法割平面法；分支定界法等；非线性规划的经典解法最速下降法；Newton法；拟Newton法(主要是DFP和BFGS算法)；共轭梯度法；信赖域法等。 （2）约束优化问题的解析方法主要是Lagrange法；数值解法包括惩罚函数法（外罚函数法、内障碍罚函数方法）；广义Lagrange乘子法；内点法（大型问题）等。 2.2组合优化问题经典的组合优化问题有旅行商问题（TSP）、加工调度问题、背包问题、装箱问题、图着色问题、聚类问题等。 这些问题描述非常简单，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，其中有一类所谓的“NP-完全问题”，至今未发现有效算法，目前只能采用多项式界的近似算法求出组合优化问题的良好近似解。 一般我们关心的不是最优解的存在性和唯一性，而是如何找到有效的算法求得一个最优解，如何衡量算法的优劣、有效与无效等问题。 2.3智能优化问题智能优化是近年来发展起来的多种智能优化算法。 包括遗传算法、禁忌搜索算法、模拟退火算法和蚁群优化算法，粒子群优化算法等。 这些算法不需要构造精确的数学搜索方向，不需要进行繁杂的一维搜索，而是通过大量简单的信息传播和演变方法以一定的概率在整个求解空间中探索最优解。 这些算法具有全局性、自适应、离散化等特点。 这些算法大大丰富了现代优化技术，也为那些传统优化技术难以处理的优化问题提供了切实可行的解决方案。 三、实际问题与理论问题的差别理论问题和实际问题的差异是我们在应用时不可回避的一个现实。 数学的研究人员注重的是理论的研究，一般很少接触实际问题的数值计算及相关问题，而理论的研究是为了实际应用服务的，在现实当中需要数学的时候，恰恰又都无法避免数值计算问题，于是，理论和实践之间多了一条裂痕。 在我和物理系教师的接触过程中，他们提到了数值计算与相对理论计算的差异问题。 比较典型的问题是局部优化算法的可靠性。 对于一切基于一维搜索的方法，当一维搜索在理论上绝对可行的时候，在现实计算中出现理论外结果的情况几乎可说是大量存在的，特别对于某些专门的测试函数。 目标函数的数量级太大，梯度函数的数量级太小，舍入误差等等，都可能使一维搜索失败、结果不可靠甚至异常退出，为防止这些不符合理论要求的情况出现，又需增加运算负责检查矫正，最终也很难完全避免。 信赖域的方法同样存在着数值计算中的不可靠，甚至在小尺度时，实验中比基于一维搜索的方法有时更加不可靠。 又比如特征值计算问题，当使用eigs函数而Hessian阵数值的数量级太大时，就会发生异常返回。 再比如，在各种出现数值大小比较的地方，都存在着数值计算带来的问题和隐患，比如判定Hessian阵正定，理论上只需最小特征值大于0，可是，万一由于数值的原因这个最小特征值在计算机中是负的，就会得出错误的结果。 相等判断更是如此，一切“xA?”对double变量都因舍入误差的存在是不可靠的，只能用xAe?来判定，那么e怎么取，又构成新的问题。 最后，像最速下降法这样理论上对正定二次函数一定收敛的算法，当特征值分布分散、问题维数很高的时候，实际是不可行的，根本达不到现实中的精度要求。 总之，计算机参与到最优化的计算之中，在大力推动数学的发展和应用的同时，也引出了许许多多新的问题，理论和工具的结合，本身产生了大量理论问题，这是任何一个从事科学工程领域工作的人都必须有所认识的。 四、对最优化问题的展望我认为，抽象地讲，解最优化问题的过程，就是获取目标函数一条全局信息的过程，这个需要获取的全局信息，就是某点的函数值最小。 因为说某点函数值“最小”，其实是说某点函数值“比其它所有点的函数值都小”，包含了该点函数值对所有点函数值的大小比较关系，这当然是全局性的。 而最优化问题的主要矛盾就是，问题的解所包含的信息是全局性的，但为求取这个解所能采集到的可利用信息是局部的甚至单点的，且采集次数是有限的。 比如求一点函数值，只能得单点信息。 又比如水平集方法之所以不好用，就是因为它每一步都要求算法获得水平集测度这种全局信息。 正是这个根本矛盾，导致了最优点搜索、确认上的困难。 因为对于可微函数，从解析式中的有限次信息采集如求单点梯度就可获得一个有限领域内可利用的局部信息。 对于全局优化问题，我们却没有这样的手段。 也就是说，通过局部信息的有限次累计，得到全局信息。 其实比较各种局部优化算法就可有这样的体会，理论上好的算法，往往就是能在各次获取单点信息的过程中实现一种信息累积使得算法掌握的信息越来越能钩织出局部信息。 出于这样的认识，我认为，要实现一种好的全局优化算法，可以在两个地方下功夫一是如何从解析式与约束中通过少的信息采样挖掘出更大范围、更大信息量的信息；二是，如何逐步有效累积信息把前面挖掘的信息汇成全局信