第2章　全局优化的基本理论

2.1　优化问题简介

优化是个相对比较古老的课题^[39]，它所研究的问题是在众多备选方案中寻找最优方案。自20世纪以来，人们深入探讨和研究最优化的理论和方法。17世纪初期，英国科学家Newton和德国科学家Leibnitz发明的微积分其实就蕴含了优化的内容。而法国数学家Cauchy第一次采用梯度下降法解决无约束优化问题。后来处理约束优化问题又提出了Lagrange乘数法^[40—42]。今天看来，当时研究出的优化理论方法很多只能用来解决局部优化问题。同时由于缺乏统一的理论支撑，那时候的优化方法还仅仅是众多方法的简单结合。直到19世纪中期，一方面，许多复杂的优化问题在实际生产中需要解决，如复杂的高维的线性和非线性规划问题，就需要提出高效而实用、可程序化的优化算法；另一方面，随着泛函分析这门数学基础学科的发展，为研究最优化理论与方法奠定了坚实的理论根基。由于计算机的出现，学者开始将计算机用来解决实际优化问题，借助于计算机这个便捷的工具使设计的优化算法的实现更为简单方便，于是使优化逐渐转变为一门相对独立的学科，中国科学院院士、原中国运筹学会理事长袁亚湘教授的《最优化理论与方法》是研究优化理论与方法的经典著作^[43]，为优化研究理论和方法论奠定了基础。

近年来，中国运筹学会、中国系统工程学会、中国管理科学与工程学会、中国“双法”研究会等组织通过年度年会、专题论坛、分会论坛、科普讲座等形式对优化理论与思想在青年学者中传播，为优化理论与方法在不同领域的应用和发展做出了卓越的贡献，对学科交叉融合提供了重要的方法论支撑。

随着人类对自然界的不断探索，在认识世界和改造世界的过程中必然会遇到很多待解决的问题，当然这里面既有理论研究也有实际应用问题，在这两个领域涌现出更加复杂的现实问题需要我们解决，其中优化方面问题大多具有这样的特点：

（1）在可行域内目标函数具有很多个甚至无数个局部极值点。

（2）要解决的优化问题涉及许多本领域的专业知识，有时会存在要处理的优化问题的变量维数很高的情况，小的几十维，大的上千维，造成优化计算量急剧增加。

（3）要解决的问题本身可能是很复杂的，比如很多优化问题的目标函数是高度非线性的，有些函数从分析性质看是不可导、不连续的，某些形式下甚至函数本身抽象不出来，即不能解析地给出，我们只能通过一系列的实验数据点、特定的步骤、特殊方法和程序一步一步得以解决。

在我们要解决的实际优化问题中如果出现了上面提到的几个问题，要处理这样的优化问题就变得相当有难度了，只利用经典的局部优化理论与方法很难较好地解决问题。这时我们就要考虑从别的角度处理。

非传统的优化方法如雨后春笋般涌现出来，这其中包括利用生物智能设计的启发式优化方法，也包括算法之间的融合设计的新算法，这些新算法的特点是能充分地利用要解决问题的全局信息资源，有利于全局最优解的获得。如：

通过模拟自然界生物的遗传和变异实际过程而演绎得到遗传算法。

通过模拟物理中的退火过程而设计的模拟退火优化方法。

人工神经网络方法也是根据人们大脑处理问题时的特点而设计的智能优化方法。其中Hopfield网络发展比较成熟，可以用来成功地处理许多优化问题，特别是组合优化问题。

模拟有记忆的智能过程而得到的禁忌搜索优化方法。

模拟蚂蚁寻找食物时的最优路径而设计的蚁群优化方法。