应用数学系列讲座--最优化理论与方法

2024年2月20日发(作者：)

应用数学系列讲座---最优化理论与方法

肖 伟

Part 1 最优化发展的历史背景

最优化亦称数学规划，她追求一种尽善尽美之道，此乃人类贪婪之本性、追求极致之欲念。可以说，最优化首先是这种理念，然后才是一种方法。她是人类追求完美的一种最佳决策理念与方法。

1．问题

在人类的生活、科学研究、工程、经济、工业、军事等领域都会遇到许多最优化问题：

（1）运输问题。生产厂家要将自己的产品运输到用户，如何运输既能满足用户需求，又能花费最少？

（2）金融投资问题。如何设计比较好的证券组合或投资项目组合，以便在可接受的风险限度内获得最大的投资回报？

（3）产业结构调整、人员优化组合、多种商品的生产计划与调度等资源分配问题。如何分配有效的资源以便在特定的空间与时间内谋求最大的经济效益？

（4）工程设计问题。在工程设计中如何选择适当的参数使得工程方案既满足实际需要，又能够降低工程造价？

（5）曲面选择问题。如何设计汽车、飞机、宇宙飞船的最佳外形，既保证其运动的稳定性，又减少运动阻力，甚至满足隐身要求？

（6）飞行器的最优轨迹问题。导弹防御系统的开发与部署的有效性实际上就是能否在敌方导弹到达己方某一重要区域之前，对飞行目标的轨迹进行准确跟踪和预测，并且引导拦截器将其摧毁？

（7）过程控制问题。如何控制一个化学过程或者机械装置，既优化其性能，又满足鲁棒性要求？

2．背景

最优化作为一门学科，孕育于20世纪30年代，诞生于20世纪40年代第二次世界大战弥漫的硝烟中，以线性规划模型（美国空军军力规划问题、运输问题、资源分配问题等）和单纯行算法的出现为标志。因此，最优化的历史，早期也就是线性规划的历史。作为最优化理念与方法，无论国内，还是国外，都可以追溯到很久以前。

1637年，Fermat发表了“求极大和极小的方法”，文中包含了Fermat定理结论。

1684年，Newton和Leibniz发明的微积分为求解一大类单变量极值问题提供了通用工具。当年Leibniz发表的第一篇微分学论文被定名为“一种求极大与极小值和求切线的新方法”。后来，Euler，Poincare，Hilbert将Fermat定理推广到多变量、无穷个变量、特定条件的极值问题。

1826年，Fourier的工作涉及到后来发展线性规划的核心理论，线性不等式组的研究。

1847年，Cauchy研究了函数值沿着什么方向下降最快问题，这就是现在的无约束最优化的最速下降法。

1939年，前苏联，Kantorovich出版了著作《生产组织与计划中的数学方法》，建立了线性规划模型，用来解决下料问题和运输问题。标志线性规划的诞生。遗憾地是他的努力在当时的俄罗斯并没有重视（直到Dantzig）。

1947年以前，Koopmans给出了古典经济学理论的线性规划分析结构，并进行了与经济学有关的研究。

1947年，Dantzig正式提出了线性规划数学模型，并发展了有效解决线性规划的单纯行方法，并沿用至今。当时他是联邦空军审计部地一名数学顾问，开发了一个数学工具，用来制定军队的训练、部署、后勤保障的方案。由于空军的计划问题可以用一个不等式组来描述，他就将论文题目定为“线性结构的规划”（programming in a linear structure）。

1948年夏天，美国的Koopmans和Dantzig参观兰德公司期间提出了线性规划这一名称，直到今天。

1949年，Koopmans在美国芝加哥组织了数学规划第一次会议，主编了《生产与分配的活动分析》（Activity analysis of production and allocation），这对数学规划的发展产生过重大影响。

说明：1975年10月14日，瑞典皇家科学院将Nobel经济学奖颁给了ovich和ns。原因是他们创造了线性规划方法，并成功地应用于经济学领域，为经济学的发展做出了卓越贡献。其实，我们知道g是线性规划之父，应该获得Nobel奖，而不是Kantorovich和Koopmans。可惜他的单纯行方法太数学化，无法获得Nobel奖。

1972年，Klee和Minty证明，单纯行算法不是求解线性规划问题的优良算法，于是人们自然问，线性规划是否存在优良算法？

1979年，Khachiyan肯定地回答了上面的问题，提出了求解线性规划的椭球法，她避免了单纯行法的最坏情形下的指数时间算法。

1984年，美国AT&T贝尔实验室的Karmarkar提出了求解线性规划的多项式时间内点法，她避免了Khachiyan椭球算法的不可操作性，同时也是多项式时间算法。至今依然是线性规划的研究热点。但它已经不是单纯行法了。

在中国，运筹优化的思想也经常被使用。

战国时期，田忌赛马，就属于最优化中的对策论。

古代和中世纪，中国学者在天文历法研究中曾涉及到天体运动的不均匀性和相关的极值问题。例如，1280年，郭守敬在《授时历》中，涉及“月离迟疾”（月亮运行的最快点和最慢点）以及月亮白赤道与太阳黄赤道交点距离的极值（“极数”）的计算。

二十四节气中“夏至”与“冬至”实际上是描述一年中太阳光直射点南北移动的一种极端状况。

Part 2 最优化的内涵

最优化问题的一般数学表达形式为

minF(x)f1(x),f2(x),,ft(x)ci(x)0,i1,2,,m,

s.t.cj(x)0,jm1,,m.这里F(x)f1(x),f2(x),,ft(x)为目标函数族，xx1,x2,,xn为决策变量，

T

这里RnxRn/ci(x)0,cj(x)0,i1,2,,m,jm1,,m为可行域。根据决策目标量t、决策变量个数n、可行域将最优化问题分类如下。

1．根据目标函数个数最优化问题可分为单目标（t=1）和多目标（t>1）最优化问题。

2．根据决策变量个数可分为一维最优化（n=1）和多维最优化（n>1）问题。

3．根据可行域可分为无约束最优化（Rn）和约束最优化（Rn）问题。

于是将上述三种情况结合起来就可以将最优化问题正确分类。由于多目标最优化通常要转化为单目标最优化，所以只需研究一般单目标最优化问题minf(x)或

xminf(x)ci(x)0,i1,2,,me,(1)

s.t.cj(x)0,jme1,,m.因此，问题单目标最优化可简单分类如下（多目标平行）：

f(x)和有约束1）根据有无约束条件最优化问题分为无约束最优化问题minnxR最优化问题。

2）根据有无不等式约束，最优化分为等式约束问题（只有等式约束）、不等式约束问题（只有不等式约束）、混合约束问题（等式与不等式约束都存在）。

3）根据函数的线性性可见最优化分类为：线性规划（目标函数与约数函数都是线性函数）、非线性规划（目标函数和约数函数至少有一个是非线性函数）、二次规划（目标函数是二次函数，约数函数是线性函数）。

4）根据凸性划分：凸规划（目标函数为凸函数，可行域为非空闭凸集）、非凸规划。

5）根据可行域Rn内点的个数划分：离散最优化（可行域为有限个点）、整数规划（变量取整数的离散最优化）、混合整数规划（部分变量取整数，部分变量连续变化的离散最优化）、连续最优化（可行域为连通区域）。

6）根据可微性划分：光滑最优化问题（目标函数和约数函数都是光滑函数）、非光滑最优化问题（目标和约束函数至少有一个非光滑）。

7）根据最优化问题有关信息的确定性划分：确定最优化问题（前面的一般最优化）、模糊最优化（目标函数或约数函数具有模糊性）、灰色最优化（函数具有灰色性）、随机最优化（函数具有随机性）。

Part 3 最优化的结构

最优化理论与方法实际上只有如下五方面的内容：解的存在性及其存在条件、算法、算法的收敛性、算法的收敛阶（速度）、数值计算。

1．存在性及存在条件

向所有数学问题一样，我们首先关心的是解的存在性及其存在的条件，然后再用某种方法将解找出来。下面只陈述光滑函数的条件。

如果f(x*)minf(x)，则称x*为f(x)的全局最优解。如果存在x*的领域Nx使得对xN满足f(x*)f(x)，则称x*为局部最优解。

对约束问题（1）引入Lagrange函数：L(x,)f(x)ici(x*)；记指标i1m*集Ix*处的线性化零约束方向集定义为i/iI,*i0，在**。

G(x*,*)d/d0,dTci(x*)0,iEI,dTci(x*)0,iI*I

A．必要条件

1）无约束问题的一阶必要条件：f(x*)0。

2）无约束问题的二阶必要条件：f(x*)0且2f(x*)0。

3）有约束问题的一阶必要条件（库恩-塔克条件）：xL(x*,*)0或f(x*)i*ci(x*)0。

i1m4）有约束的二阶必要条件：对满足约束规格的x*有dT2xxL(x*,*)d0。

B．充分条件

1）无约束问题的二阶充分条件：f(x*)0且2f(x*)正定。

*是对应的Lagrange2）有约束问题的二阶充分条件：设x*为（1）的K-T点，乘子，dT2xxL(x*,*)d0,dG(x*,*)。

2．算法的构造设计

当知道最优化问题的解存在时，我们通常通过迭代方法求其最优解。当然迭代方法找出的是局部最优解。迭代法的基本思想为：给定初始点x0Rn，按照某种规则产生点列xk满足：点列有限时，最后一个点是最优解；当点列无限时，其极限点为最优解。

一个好算法应该具备的典型特征：迭代点列xk能稳定地接近局部极小点x*的领域，并收敛于x*。当给定某种收殓准则时，迭代终止。一般证明迭代点列xk的聚点为局部极小点。

对于最优化问题（1）的求解，主要是通过迭代格式。假设第k次迭代点为xk，第k次搜索方向为dk，第k次步长因子为k，则第k次迭代格式为

xk1xkkdk(2)

从上面的（2）式可以看出，设计算法时，实际上需要确定两个问题，迭代方向dk和步长因子k。然而步长因子容易设计规则，关键是迭代方向dk的确定。从最优化问题解的必要条件知，搜索方向dk是目标函数f(x)的下降方向，即

f(xk)Tdk0或

(3)

f(xk1)fxkkdkf(xk)所以，最优化的基本结构如下：

Step 1：选择初始点x0；

(4)

Step 2 ：确定满足条件（3）或（4）的搜索方向dk；

Step 3：根据迭代法则（2）产生新点xk1；

Step 4：给定某种终止条件，查看xk1是否满足。如果满足，则停止，xk1作为最优解x*的近似解。否则重复上面的步骤。

算法迭代的终止条件可有如下几种（设为预先给定精度，p为某种给定范数，x*为最优点）：

（1）f(xn)f(x*)（2）f(xn1)f(xn)（3）(5)

(6)

(7)；

(8)

(9)

f(xn1)f(xn)|f(xn)|p（4）xnx*（5）xn1xn（6）xn1xnxnppp(10)

（7）f(xn)p(11)

说明：

1．利用终止准则（5）与（8），显然是最适合的，但计算中无法知道最优点x*。因此，通常采用其余形式。

2．（6）和（9）对一些收敛较快的算法很实用，但有些情况不适合。

3．有时xn1xn或f(xn1)f(xn)是小的，但是对应的f(xn1)f(xn)或极小点x*远离当前迭代点xn。此时同时使用（6）与（9）xn1xn却是很大，合适。

4．如果xn或者f(xn)，采用（7）与（10）。

5．有一阶导数，且收敛速度不太快，采用（11）。

6．有时候，临界点是鞍点，单独使用（11）不适合，可结合（7）与（10）。

3．算法的收敛性

构造算法，通过迭代获得序列xn。最关心的是算法的收敛性甚至收敛速度。收敛性指

limxnx*np0(12)

即在给定的某种范数意义下收敛。从理论上讲，构造一个算法，至少要求其收敛。否则，算法失去意义。事实上，有些算法太复杂，我们甚至无法证明其收敛性，但是在实际中依然在使用，也显示了有效性。数学所关心的问题与实际有些差距（某些时候）。

4．算法的收敛速度

算法的收敛快慢对其应用效果作用太大，我们经常关心一个算法的收敛速度。这也是衡量一个算法好坏的标准。虽然现在计算机速度非常快，但是对于复杂问题依然不能满足，因此算法的收敛速度较为重要。

对算法的收敛速度通常有两种刻划方式Q-收敛阶、R-收敛阶。

如果存在实数0及常数q（与迭代次数n无关），使得

xn1x*plimq(13)

nxnx*p则称算法产生的迭代点列xn具有Q阶收敛速度。特别是，

（1）当1,q0时，迭代点列xn称为具有Q-线性收敛阶；

（2）当12,q0，或者1,q0时，迭代点列xn称为具有Q-超线性收敛阶；

（3）当2时，迭代点列xn称为具有Q-二次收敛阶。

另一种是R-收敛阶的定义，

limsupxnx*1/n,如果q1pnRq1/qnlimsupxnx*p,如果q1n(14)

特别是，

（1） 如果R10，则称迭代点列xn是R-超线性收敛阶；

（2） 如果0R11，则称迭代点列xn是R-线性收敛阶；

（3） 如果R11，则称迭代点列xn是R-次线性收敛阶；

（4） 如果R20，则称迭代点列xn是R-超平方收敛阶；

（5） 如果0R21，则称迭代点列xn是R-平方收敛阶；

（6） 如果R21，则称迭代点列xn是R-次平方收敛阶。

一般我们都用（13），而不是（14）去刻画收敛速度。

5．数值计算

数值计算不能以严格的数学证明保证算法具有良好的性态，但却能验证算法的有效性与实用性，也能表明算法的可接受特性。数值计算的必要性：

（1）算法的收敛性和收敛速度不能保证该方法一定有好的结果；

（2）计算过程中有舍入误差、系统误差等对计算结果的影响；

（3）算法往往对目标函数f(x)要加上某种不易验证的限制条件，实际计算时，这种条件可能不满足；

（4）理论上虽然不能证明算法有更快的收敛速度（如证明技术的限制），但是这不能意味着算法就不具有更高收敛阶。数值验证可以表明这种可能性的存在，从而为理论证明提出目标、猜想。

Part 4 最优化方法概述

最优化问题（1）的求解，就是在当前点xk通过找到的步长k和搜索方向dk，由（2）产生新的迭代点xk1。迭代的原则是对选择的某个评价函数(x)沿射线xkdk(0)有所下降，即

(xk1)(xkkdk)(xk)

1. 线性搜索策略

由于当前点xk和搜索方向dk已知，步长k就是通过关于的一元函数

(xkdk)来确定，所以问题称为一维搜索或者线性搜索。

线性搜索策略的好坏直接影响到最优化问题求解的收敛速度。线性搜索策略有两类：一是精确线性搜索，二是非精确线性搜索。

1.1 精确线性搜索

fxkkdkminfxkdk。若记()xkdk，则精确搜索为求0解一维优化问题min()。

01.2 非线性搜索策略之Goldstein准则

给定,,01（通常取0,1/2,1/2,1），选取步长k满足

fxkkdkfxkkf(xk)Tdkfxkkdkfxkkf(xk)Tdk(15)

(16)

其中（15）保证了目标函数f(x)有充分的下降，（16）保证了步长k不会取得太小。

1.3 非线性搜索策略之Wolfe准则

Goldstein准则的一个缺点是()的极小点可能不在可接受区间（15）与（16）之内。为了克服这项缺点，产生了Wolfe准则。

fxkkdkdkf(xk)TdkT(16*)

（16）与（16*）构成了Wolfe准则。

1.4 非线性搜索策略之Armijo准则

给定,,，其中(0,1),(0,1/2),0。令m0,1,2,，检验不等式

f(xk)fxkmdkmf(xk)Tdk(17)

是否成立。记使得上面不等式（17）成立的第一个m为mk，则令kmk。

2. 信赖域策略

重述迭代格式（2）为

xk1xkk

修正量k由信赖域方法确定。为简述信赖域方法，考察无约束优化问题

minf(x)nxR(18)

设xk为无约束问题（18）最优解x*的当前估计，则修正量k是通过适当大的参数k，求解下述信赖域子问题来确定

1minqk()f(xk)f(xk)TTBk2s.t.k

(19)其中，Bk或者是2f(xk)，或者是2f(xk)的某种近似，参数k为信赖域半径，其大小取决于二次模型qk()在点xk的以k为半径的邻域

Nxk,kx/xxkk

内对目标函数f(x)的拟合程度。记（19）的解为k，这种拟合程度可以通过比较f(x)在点xkk的实际下降量aredk和由拟合模型qk()确定的估计下降量predk来确定，这里

aredkf(xk)fxkk

1predkf(xk)qk(k)f(xk)TkkTBkk

2根据k的定义，显然predk0，令

Qkaredk/predk(19*)

如果Qk的值接近1，表明qk()在邻域Nxk,k内对f(x)的拟合程度较好，k可以保持不变或增大；如果Qk值接近于零或取负值，表明qk()在邻域Nxk,k内对f(x)的拟合程度不够理想，必须减小k的值，缩小邻域以改善拟合程度。

3. 评价函数

评价函数用于评价迭代过程的进展。对于无约束最优化问题，一般将目标函数选为评价函数。对于有约束优化问题，评价函数必须包含目标函数与约束条件的信息，以便迭代点既具有可行性，又具有下降性。对于约束问题，已经提出了许多评价函数，Frisch和Carroll提出的两种障碍函数，Zangwill提出的l1精确罚函数，Fletcher提出的可微精确罚函数等，例如可取罚函数为

p(x)ci(x)min0,ci(x)i1imemem(20)

其中1,1为待定常数，主要起到保持惩罚函数p(x)具有良好的特性如可微性可取2,2。由此构造评价函数

(x,)f(x)p(x)

其中0为罚因子。

4. 优化方法概述

对于无约束最优化问题，其求解方法可通过步长因子k和搜索方向dk的确定来概述求解方法。对于有约束问题还得加上评价函数的选择来界定求解方法。

4.1 无约束问题

通过信赖域策略的求解方法统称为信赖域法；通过线性策略，则主要以迭代方向来划分。

1）梯度法：dkf(xk)的迭代方法；

2）牛顿法：dk2f(xk)1f(xk)的迭代方法；

3）共轭梯度法：设GRnn，dk是G-共轭方向组，即Tdk,2,,k，用dk进行迭代的方法；

1Gdj0,j0,14）拟牛顿法：设ykf(xk1)f(xk)，kxk1xk，Bk正定（2f(xk)1的某种近似）满足拟牛顿条件Bk1kyk。则取dk1Bk1f(xk1)的迭代方法。

5）直接法：一般是直接沿着每个坐标轴进行一维搜索。

4.2 有约束问题

有约束问题的求解方法主要通过选择评价函数，转化为无约束最优化问题。

1）罚函数法：通过求评价函数(x,)的极小来代替原约束问题极小的方法，其中(x,)f(x)p(x)，p(x)为惩罚项，为惩罚因子。例如对优化问题（2）可取罚函数为（20）。

2）可行方向法：迭代点列可行，xk，迭代方向dk为可行下降方向，T即dkf(xk)0,dkFD(xk,)。

3）序列二次规划算法：将约束优化问题 转化为二次规划子问题进行求解。在当前点xk处选定正定矩阵Bk，求解二次规划子问题Qxk,Bk

1mindTf(xk)(xk)dTci(xk)0,iE{1,2,,me}

ci(xk)dTci(xk)0,iI{me1,,m}设Qxk,Bk的解为dk，则xk1xkdk。

4.3 非光滑函数最优化

对于最优化问题（2），如果目标函数和约数函数中至少有一个不可微，则称为非光滑最优化问题。这时需要引进广义梯度、广义方向导数、次梯度等概念，并用来求解非光滑最优化问题。例如求解非光滑最优化的次梯度方法，她实际上就是最速下降法的直接推广。

4.4 全局最优化

由于最优化问题的求解都是应用迭代法，所以求得的极小值都是目标函数的稳定点或者局部最优解。但是，对许多问题都有多个极值点。这样经典的最优解迭代方法就难于求出最优化问题的全局极值点。这就导致发展最优化问题全局解的方法。如果试图利用经典的迭代方法，就会导致两个困难。一是迭代中如何从一个极小值点跳到另一个更小的极小值点？二是如何判断当前的极小值点是全局极小值点？目前研究了许多方法解决第一个问题，但是第二个问题仍然比较困难，尚需进一步探讨。

全局最优化方法根据收敛性质分为两类：确定性方法和随机性方法。

确定性方法：区间方法、分支定界方法、填充函数方法、罚函数法、积分-水平集法、外逼近方法。

随机性方法：随机投点方法、遗传算法、模拟退火算法等。

Part 5 近代最优化的主要发展方向

对于最优化方法，除了考虑一般的最优化问题（1）以外，还经常研究二次规划问题

minQ(x)n1TxGxgTxcxbi,i1,2,,meaiTxbi,ime1,,m(21)

或者一般的无约束二次最优化问题

1TminQ(x)xGxgTxcnxR2 下面介绍一些最优化发展方向。

(21*)

1．拟牛顿法

假设当前迭代点为xk，则根据拟牛顿条件

Hk1ykk(21)

可确定Hesse逆近似Hk1，迭代方向取dkHkf(xk)，由此得到新的迭代点xk1xkkdk。这里Hk1是通过对Hk的修正得到，Hk1HkHk。这类方法统称为拟牛顿法。这类方法取决于Hk的构造，而Hk主要由已知的一些信息组成，如xj,j,f(xj),yj,Hj,j0,1,2,,k。

1）对称秩一修正公式

在构造Hk时，Hk满足RHk1；

2） DFP公式

Hk满足RHk2，选择适当参数满足等式HkauuTbTv,uv,vRn1,a,bR，由此确定出DFP公式

Hk1TkkTHkykykHk

HkTTkykykHkyk它首先是1959年Davidon提出的，1963年Fletcher和Powell发展完善。

3） BFGS公式

拟牛顿条件（21）中，Hk是通过对Hesse逆近似，因此可以直接近似Hesse阵得到一种对称的拟牛顿条件

Bk1kyk(21*)

1然后取迭代方向为dk1Bk1f(xk1)。利用（21）和（21*）中，Hk和Bk的对称性，就会得到与DFP公式对称的BFGS公式（交换Hk1Bk1，

kyk）B4） Broyden族

BFGSk1TykykBkkkTBk

BkTTykkkBkk由于DFP公式和BFGS公式都是对称秩二校正的拟牛顿公式，所以它们的

加权组合也具有同样的类型。考虑校正族

DFPBFGSHk1(1)Hk1Hk1(22)

其中是一个参数。公式（22）称为Broyden族校正。

5） Huang族

1970年，Huang提出一类比Broyden族更广泛的校正公式。在Broyden族中，矩阵Hk是对称的，满足拟牛顿条件（21）。而在Huang族中取消了对Hk的对称性限制，并且产生的矩阵满足比拟牛顿条件（21）更一般的条件

Hk1ykk(21**)

其中是一个参数。通过推导Huang族校正公式为

TTHk1HkkukHkykvk(23)

其中uk,vkRn，由下式给出

Tuka11ka12Hkyk,Tvka21ka22Hkyk

其中aij,i1,2,j1,2为常数，且满足

Tukyk,Tvkyk1

6）新拟牛顿公式

拟牛顿公式的拟牛顿条件（21）有个问题，就是只用到了梯度信息，而没有应用函数值的信息。于是[1]等提出了一类新的拟牛顿条件

ˆkBk1ky(21***)

。

ˆkyk3Akk ,Ak这里yf(xk1)f(xk)Tk2f(xk1)f(xk)k2白华[3]提出了更一般的公式。对行如（21***）中的右端项为

ˆkykAkk

y其中R。当取3时就是[1]，当取1时就是[2]。

2．大规模最优化问题

牛顿类方法对中小规模无约束最优化问题是一类最有效的求解方法。但由于求解过程中，需要存储一个nn阶矩阵，这对大规模无约束问题会因为计算机内存的限制无法使用。同时，在迭代的每一步构造搜索方向要解一个线性代数方程组，影响了算法的效率。因此，对于大规模问题，我们需要研究高效且具有较小存储量的算法。

对于大规模最优化问题的算法研究主要有这几方面：共轭梯度法；稀疏拟牛顿法；有限内存拟牛顿法；无记忆拟牛顿法等。

1）共轭梯度法

共轭梯度法一般首先讨论二次无约束优化问题（21*），这时的计算公式为

d0f(x0)

xk1xkkdkdf(x)dk1kkk1一般步长k由精确线性搜索确定

f(xk)Tdk

kTdkGdkFletcher-Reeves共轭梯度法（FR法）：kf(xk1)/f(xk)；

Polak-Ribiere-Polyak共轭梯度法（PRP）：k22f(xk1)f(xk)Tf(xk1)；

f(xk)Tf(xk)Dixon共轭梯度法：

kf(xk1)Tf(xk1)；

f(xk)TdkCrowder-Wolfe共轭梯度法：kf(xk1)f(xk)Tf(xk1)

f(xk1)f(xk)Tdk对于非二次函数最优化问题也常用FR法PRP法，但此时不再共轭，因为Hessian矩阵在变化。这就有所谓的重新开始共轭梯度法。一种是r(rn)步重新开始共轭梯度法，就是每经过r步就重新将迭代方向换为负梯度方向，即。

dr1f(xr1)。另一种就是三次重新开始共轭梯度法（参看[4]）2）稀疏拟牛顿法

对于某些无约束最优化问题，由于目标函数的特殊性，其二阶Hesse矩阵是稀疏矩阵。如果用通常的拟牛顿法构造逼近Hesse矩阵H(xk)的Bk，则Bk不具有H(xk)的稀疏结构，加大了存储量与计算量。因此，稀疏拟牛顿法就是构造Bk具有H(xk)的相同稀疏结构，然后应用拟牛顿法求解。例如有稀疏BFGS公式。但是，稀疏拟牛顿公式又失去了拟牛顿公式的一些特性如继承性。

3．信赖域法

对于信赖域问题，显然有两方面主要问题，1）如何构造逼近Hesse矩阵H(xk)的Bk？2）如何构造信赖域半径k？在给定Bk和k后，如何求解信赖域子问题

（19）？

对于第一个问题，采用不同的方式构造逼近矩阵Bk，产生不同的方法如用拟牛顿法构造。

对于第二个问题，在前面已经讲过，应用（19*）来确定信赖域半径的增大或者缩小。

对于第三个问题，信赖域子问题（19）的求解已经研究得比较清楚。其基本算法为

初始步：给定初始点x0,B0，令0f(x0)；

第k步：

1）给定xk,k，计算f(xk),Bk；

2）解信赖域模型（19），求出k；

3）计算f(xk1)f(xkk)和Qk（由（19*））；

4）如果Qk0.25，令k1k/4；

如果Qk0.75且kk，令k12k；

否则，置k1k；

5）如果Qk0.00，置xk1xk；否则置xk1xkk。

对于信赖域子问题（19）的求解，很大程度取决于采用的范数，即k（（19）式中的第二式）。

Levenberg-Marquardt[7、8]方法，如果采用l2范数。因为此时实际上是求解线性方程组

BkIf(xk)(24)

对于这方面求解的完善包含了许多人的工作，如More,Sorensen[5]，Hebden[6]。

双折线步方法，Powell[9]，Dennis and Mei[10]。

无界折线法，Zhang and Xu[11]。

3．禁忌搜索算法

禁忌搜索算法是一个试图寻求全局最优解的算法。Glover[12,13]于1986年提出，进而形成一套完整算法[14，15]。

禁忌算法的特点是采用了禁忌技术，所谓禁忌就是禁止重复前面的工作。为了避免搜索点陷入局部最优，禁忌搜索算法用一个禁忌表纪录下已经到达过的局部最优点或达到局部最优的一些过程。在下次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点或过程，以次来跳出局部最优点。

禁忌算法充分体现了集中和扩散两个策略。集中策略体现在局部搜索，即从一点出发，在这点的邻域内寻求更好的解，以便找到局部最优解而结束。为了跳出局部最优解，扩散策略通过禁忌表的功能来实现，从而到达没有搜索过的点。

禁忌算法由两部分组成：局部搜索算法和禁忌搜索算法。

局部搜索算法：可由一般的最优算法组成。

禁忌搜索算法：

Step 1 给以禁忌表（tabu list）H，并选定一个初始解xnow；

Step 2 满足停止规则时，停止计算，输出结果；否则，在xnow的邻域Nxnow中选出满足不受禁忌的候选集Can_Nxnow；在Can_Nxnow中选一个评价值最佳的解xnext，置xnow:xnext；更新历史纪录H，重复Step 2。

4．模拟退火算法

模拟退火（simulated annealing）算法是一个以一定的概率选择邻域中的最佳状态。从理论上讲，它属于全局最优算法。模拟退火算法最早由Metropolis[16]在1953年提出了主要思想。Kirkpatrick[17]在1983年成功地应用到组合最优化问题。

假设解决如下组合最优化问题：

minf(x)

s.t.g(x)0,xD模拟退火算法：

Step 1 任选一个初始解x0，置xx0,k0,t0tmax；

Step 2 若在该温度达到内循环停止条件，则转到Step 3 ；否则，从邻域N(x)

中随机选一个y，计算ff(y)f(x)；如果f0，则xy,否则，如果expf/tkrandom(0,1)时，则xy；重复Step 2.

Step 3 置tk1dtk，k=k+1；如果满足停止条件，终止计算；否则，转到Step 2。

5．遗传算法

Holland 教授在20世纪70年代初期首先提出乐遗传算法（Genetic

algorithm）。1975年，Holland出版了第一本比较系统论述遗传算法的专著Adaptation in natural and artificial systems[18]。遗传算法主要借助了生物进化中“适者生存”的规律。

下面以计算无约束最优化问题介绍其算法。

Step 1 选择问题的一个编码，给出一个有N个染色体的初始群体POP(1)，t=1；

Step 2 对群体POP(t)中的每一个染色体popi(t)计算它的适应函数

fifitnesspopi(t)

Step 3 如果停止规则满足，则算法停止。否则，计算概率

pififj1N,i1,2,,N

j并以上面的概率分布从POP(t)中随机选择一些染色体构成一个种群

NewPOP(t1)popj(t)/j1,2,,N

Step 4 通过交配，得到一个有N个染色体的CrossPOP(t+1);

Step 5 以一个较小的概率p，使得染色体的一个基因发生变异，形成MutPOP(t+1)，t=t+1，一个新的群体POP(t)=MutPOP(t)；返回Step 2。

6．蚁群优化算法

蚁群优化算法（ant colony optimization algorithms）是一种分布式智能模拟算法。基本思想是模仿蚂蚁依赖信息素进行通信而显示出的社会行为。其最大特点是蚁群中的蚂蚁以“信息素”（pheromone）为媒介，间接异步地相互联系。蚂蚁在行动中，会在经过的地方留下称之为“信息素”的化学物质。这些化学物质被同一蚁群感受到，并作为一种信号影响后者的行动。具体表现在后到的蚂蚁选择有这些物质的路径的可能性比选择没有这些物质的可能性大得多，后到者留下的信息素会对原来的信息素进行加强，并循环下去。这样，经过蚂蚁越多的路径，后到蚂蚁选择这条路径的可能性就越大。由于在一定的时间内，越短的路径会被越多的蚂蚁访问，因儿积累的信息素也就越多，后到者访问的可能性越大。这个过程会持续到所有的蚂蚁都走最短的路径为止。

1992年，Dorigo[19]在他的博士论文中首先提出了一种全新的蚁群系统（ant

system）启发式算法，到现在逐步完善为一种最优化算法[20-21]。蚁群优化算法是一种随机的通用试探法，具有通用性和鲁棒性，是全局最优解方法。

例如，TSP问题（旅行商问题）。设G=(N,A)表示有n个城市的一个有向图，N1,2,,n，Ai,j/i,jN，城市间的距离Ddijnn，目标函数f(W)djk1jk,Wj1,j2,,jn1,2,,n为城市的一个排列。

k1n初始的蚁群优化算法就是求解上述TSP问题[22]。

1,2,,n，Ai,j/i,jN，城市Step 0 对n个城市的TSP问题，N间的距离Ddijnn为TSP图中的每一条弧i,j赋信息素痕迹初值ij(0)1/|A|，假设有m只蚂蚁在工作，所有的蚂蚁从同一城市i0出发，k=1。

当前最好解W1,2,,n。

Step 1 （外循环）如果满足算法的停止准则，停止计算，并输出计算得到的最好解。否则，让蚂蚁s从起点i0出发，用L(s)表示蚂蚁s行走的城市集合，初始L(s)为空集，1sm。

Step 2 （内循环）按蚂蚁1sm的顺序分别计算。当蚂蚁在城市i，如果L(s)N或l/(i,l)A,lL(s)i0，完成第s只蚂蚁的计算。否则，若L(s)N且Tl/(i,l)A,lL(s)i0，则以概率

ij(k1),jT(k1)pijillTjT0,(25)

到达j,L(s)L(s){j},i:j；如果L(s)N且Tl/(i,l)A,lL(s)i0则到达i0，L(s)L(s){i0},i:i0；重复Step 2。

Step 3 对1sm，若L(s)N，按L(s)中城市的顺序计算路径长度；若L(s)N，路径长度是一个充分大的数。比较m只蚂蚁中的路径长度，记走最短路径的蚂蚁为t，若f(L(t))f(W)，则W:L(t)。用式（26）对W路径上的弧信息素痕迹加强，对其他弧的信息素痕迹挥发，

1k_1ij(k1)k1/|W|,1k-1ij(k1)，ij(k)(i,j)为W的一条弧其他（26）

得到新的ij(k),k:k1，重复Step 1。

8．全局最优化问题

全局最优化（global optimization）研究非线性目标函数在某个特定区域上全局最优点的特征和计算方法。由于目标函数不是凸函数，约束区域不是凸区域，全局优化也称为非凸优化（nonconvex optimization）。

全局最优化开始于20世纪60年代，当时主要集中在线性或非线性规划的局部化数值算法方面。从20世纪70年代以来，全局优化获得迅速发展。如我国学者提出的填充函数法、积分水平集法、区间方法等在国际上产生了一定的影响。同时，我国学者在随机性不确定算法如遗传算法和模拟退火算法等方面也获得了较多的研究成果。

全局最优化问题的两大困难：如何从一个局部极小点跳到另一个函数值更小的局部极小点？如何判定当前的极小点是否为全局最优点？

全局最优化方法根据其收敛性分为两大类，确定性方法和随机性方法。

8.1 确定性方法

8.1.1. 区间方法

区间方法考虑优化问题minnf(x)，其中为闭区间。其基本思想是以区间xR分析为基础，按照区间算术运算规则，用区间变量代替点变量进行区间计算，并将分支定界和 Moore-Skelboe[23]算法相结合。Moore[24]首次提出区间全局优化概念。

区间算法可概括为五个步骤：定界、分枝、终止、删除、分裂，其中包括区间分裂规则、删除规则、以及区间选择规则。不同区间算法体现在这几种规则的不同处理手段上。

区间算法与常规算法（以点搜索方式产生近似点序列）相比，其突出优点是能在给定精度内求出问题的全部全局极小点。

这一算法的研究内容可参考[25]。

8.1.2. 分支定界法

分支定界法依然考虑问题minnf(x)，只是是紧集。其基本思想是通过把xR可行域逐渐剖分加细，同时构造最优解单调减少的上界序列和单调增加的下界序列。当上界和下界相等或者上界与下界的差满足误差要求时，迭代终止，获得全局最优解。根据剖分过程和上下界估计过程的选取不同，分支定界法大体分为两类。一类是把切平面过程与分支定界技术结合；另一类是使用目标函数逼近过程。

分支定界法被广泛地用在整数规划中，近年来一直是最优化领域的研究热点。分支定界法主要实现步骤可概括为分枝、定界、剪枝三个基本运算。不同的分支定界方法体现在这三个基本运算的不同处理手段上。这种算法的基本步骤可概括为：

Step 1 （初始化）选择可行域的初始松弛集合F满足F；初始可行点集合Q；上界。令P{F}，计算下界(F)minf(x),x，并令(F)。计算(F)的过程中，若有必要，可更新Q和。

Step 2 （分割）将F分割成有限个子集Fi,iI满足

FFi,iIintFiintFj,i,jI,ij,

令PPFFi。

iIStep 3 （剪枝）对每个iI，计算f在子集Fi上的下界(Fi)，满足

FiinffFi

利用在计算(Fi)的过程中所发现的所有可行点修正集合Q，同时按照合适的删

除规则，删除P中所有不包含最优解的Fi或Fi的一部分，剩余集合不妨仍记为P。

Step 4（定界）令minFi/FP,minf(x)/xQ。

Step 5（终止判断）若 （充分小的正数），则终止算法，否则从P中挑选合适的子集F,FP，转入Step 2。

8.1.3. 填充函数法

填充函数法由（葛仁溥）等[26-27]首先提出。这类方法一般假设f(x)在Rn上连续可微且满足强制性条件limf(x)，此时填充函数法所考虑的问xf(x)就退化为f(x)在某个有届闭集X上的全局优化问题。 题minnxR填充函数法由两个阶段组成，极小化和填充，这两个阶段交替进行直到找不到更好的局部极小点为止。其基本思想如下，首先在极小化阶段，采用经典的局部优化方法寻找f(x)的一个局部极小点x1，然后转入填充阶段。以当前极小点x1为基础构造一个填充函数p(x)，使得它有极大点x1，而且在任何比x1盆谷高的盆谷中没有极小点或鞍点。当在某个比x1盆谷低的盆谷中有一个极小点或鞍点x。然后以x作为初始点去极小化f(x)，并找到f(x)的一个新的极小点x2，使得f(x2)f(x1)。用x2代替x1，重复上述过程，直到找到全局最优点为止。

8.1.4. D.C.规划

在全局优化中许多强有力的方法是基于下面的D.C.规划问题

minf0(x)g0(x)(x)gi(x)0,i1,2,,m

xD其中D是Rn中的紧凸集，fi,gi,i1,2,,m是Rn中的凸函数。通常我们称表示为两个凸函数差的函数为D.C.函数。

由于Rn的紧凸集上的任意二次可微函数为D.C.函数。如果fi(x)i1为D.C.m函数，则ifi(x)iR、maxfi(x)、minfi(x)都是 D.C.函数。因此，有一i11im1imm大类函数是D.C.函数。

况且，下面的D.C.规划问题

minf(x)g(x)

xD可以转化为等价的凹极小化问题

mintg(f(x)t0

xD这里D是Rn中的紧凸集，f,g是Rn中的凸函数。

对于凹极小化问题的求解，已经有一些算法，这些算法多数以分支定界技巧、割平面法、最优性条件和整数规划方法等为基础，如可参看文献[28]。

8.1.5.非凸二次规划

二次规划是人们研究较多的内容之一，因为很多规划可以在局部用二次规划逼近。二次规划是最简单的非线性规划，其特殊结构导致人们对它的研究兴趣。对于非凸二次规划，包含了多面凸集上非凸二次函数的最小化问题和带二次约束的二次规划问题。

1986年，[29]等研究了大规模可分凹二次规划问题。

1997年，, [30]利用D.C.优化算法和分支定界技术以及椭球技术分别对非负约束的二次规划问题和箱约束非凸二次规划提出乐有效的分支定界法。

1998年，, [31]利用线性化技术和割平面方法提出了一个有界[0，1]箱约束非凸二次规划问题的求解方法。

1999年，Yinyu Ye[32]给出了带有二次约束的界约束二次规划问题的近似算法和凸二次约束的二次规划问题的近似算法。

2000年，[33]利用拉格朗日松弛定界技术、椭球技术、D.C.优化技术、分支定界法对凸二次约束二次规划问题给出了一个有效的算法，并且可以解中大规模问题。

8.2 随机性方法

全局优化中最具挑战性的问题是对问题结构一无所知，即所谓的黑盒子最优化问题。这类问题就是紧集 S上的连续函数的全局最优化问题minf(x)。随机xS性方法比较适合这类问题的求解。

这些方法除了前面已经介绍的20世纪80年代以来发展起来的智能算法（启发式算法）如模拟退火算法、禁忌搜索法、遗传算法等以外，下面介绍三种有效的方法，两阶段方法、随机搜索方法和随机函数方法。

8.2.1 两阶段方法

两阶段方法包含一个全局阶段和一个局部阶段。在全局阶段，在可行域中随机地选取一些样点，并计算其对应的函数值。在局部阶段，对这些样点进行一些操作，即通过局部搜索产生一个候选的全局最优解。

大多数二阶段法可看作所谓的多重开始算法的变形。在全局阶段，通过可行域上的一致分布产生一些样本点。在局部阶段，对这些点应用局部搜索过程，产

生局部最优解，最好的局部最优解作为全局最优解。这些方法适用于具有较少局部最优解的问题。

在全局阶段，如果没有任何局部搜索，则称为纯随机搜索（PRS）算法。由这个算法产生的记录值序列（最好函数值序列）收敛到全局最优值的概率为1。

这类算法中比较有效的有下列两类算法。

1）Multi-Level-Single-Linkage（MLSL）算法[28]结合了聚点方法的计算效率和多重开始的理论特点。将局部搜索过程应用于每个样本点，除非另一个具有较好函数值的样本点位于某个事先选取的临界距离内。这种算法最小代价收敛的关键是临界距离的选取。对于大多数具有有限个局部最优解的全局优化问题。

2）随机循环算法。MLSL方法的主要局限性是当开始局部搜索的点位于边界附近时，理论结果不成立。而在高维时几乎所有的样本点都位于可行域的边界附近。另外算法还需要存储样点。

随机循环算法[34]，克服了这些弊端，这个算法每次迭代都在S上产生一致分布的点。算法如下：

Step 0 令k=0。

Step 1 由S上的一致分布产生样点xk1。

Step 2 从xk1处以概率Pkk(xk1)开始局部搜索，其中k(x)maxxyj:j1,2,,k,f(xj)f(x)。

Step 3 k=k+1，返回Step 1。

这里Pk是一族非减的可接受概率函数，其中Pk(0)0且Pk(x)1,x0。

8.2.2 随机搜索方法

随机搜索方法是一类根据某种概率或概率分布序列在可行域中产生点序列的算法。这些算法非常灵活，甚至可以应用于具有病态结构的优化问题，而对这些问题可以不要求有效的局部搜索方法。

这类方法中最基本的算法是PRS算法，更复杂的方法是及时修正样点分布算法，即修正搜索方法。其中纯修正搜索（PAS）为一种，它与PRS的不同在于对每次迭代进行强迫改进。而且随着维数的增加，逼近全局最优值所需迭代点的数量在PAS中是线性增加的，而在PRS中是指数增加的。

8.2.3 随机函数方法

随机函数方法已经被证明在求解传统的全局优化问题中不是有效的。其中一个主要原因是下一个候选点的估计本身就是一个全局优化问题，与原问题一样难求解。然而这种方法能够成功地应用于目标函数的估计代价较高的全局优化问题中[35]。

9．非光滑最优化问题

非光滑最优化问题指最优化问题（1）中，f(x),ci(x)i1,2,,m中至少有一个是非光滑函数（不可微函数）。这样，对于非光滑函数，我们必须引进比梯

度更弱的广义梯度等概念。

定义1 设X是一个Banach空间，是定义在X上的范数。函数f(x)满足

f(x)f(y)Kxy,x,yYX

则称f(x)在Y上满足Lipschitz条件。

定义2 如果f(x)在x附近是Lipschitz的，则对任何dX，定义f(x)在x处沿方向d的广义方向导数为

f0x,dlimsupyx,t0f(ytd)f(y)

t根据Hahn-Banach定理，存在线性范函使得对一切dX都有f0(x,d)(d)。显然为有界范函，必属于X的所有连续线性范函的共轭空间X*。通常用,d表示(d)。

定义3 设f(x)在x附近是Lipschitz的，称集合

X*/f0(x,d),d,dX

是f(x)在x处的广义梯度，记为f(x)。

共轭空间X*的范数*定义为

*sup,d/dX,d1

定理4 （非光滑优化的一阶必要条件）如果f(x)在x*处达到局部极值，且f(x)在x*附近是Lipschitz的，则必有

0f(x*)(27)

定理 5（非光滑优化的一阶充分条件）设f(x)在x*附近是凸的和Lipschitz的，且0f(x*)，则x*是f(x)的局部极小值。

定义6 设f(x)是定义在Banach空间的不可微函数，且满足Lipschitz条件，称所有满足（27）的x*为无约束问题minf(x)的稳定点。

xX对于非光滑优化问题，通常只讨论无约束问题minf(x)，下面给出一些算法。

xX9.1 次梯度方法

次梯度方法是最速下降法的直接推广，每次迭代利用gk作为搜索方向，这

里gk是任意次梯度。算法如下：

Step 1 给出初值x1Rn,k1；

Step 2 计算f(xk)，以及gkf(xk)；

Step 3 选取步长k0，令

xk1xkkgk/gk2

k=k+1，转Step 2。

9.2 捆集法

捆集法（bundle method）是从共轭次梯度法发展而得到的一类方法，它是下降算法。

共轭次梯度法由Wolfe[36]提出，在第k次迭代，有一个下标集合Ik1,2,,k，搜索方向由

dkikgi,gif(xk)iIk(28)

给出，其中ikiIk是通过求解子问题

2minigiiIk2(29)

s.t.i1,i0iIk(30)所得到的。现叙述算法。

Step 1 给出初值x1Rn,k1，计算g1f(x1)。选取0m2m11/2，0m31,0,0,I1{1}；

Step 2 由（28）—（30）计算dk，如果dk则停；

Step 3 计算ykxkkdk，使得

f(yk)f(xk)m2kdk22

或者

ykxkm3

成立；

Step 4 如果存在gk1f(xk)使得

Tgk1dkm1dk22

则令xk1yk，否则置xk1xk；

Step 5 令Ik1Ikk1Tk，其中Tki/xixk1,1ik；

Step 6 k=k+1，转Step 2。

Part 6 经典最优化问题实例

为了便于应用，下面给出一些经典的最优化问题，以供同学们参考。

例1 二维Shubert函数(I)[37-39]，

55f(x)jcos(j1)x1jjcos(j1)x2j

j1j1极小值点有760个，全局极小值点有18个，如

x*(5.4828,4.858),(7.7083,7.0835),

f*186.73

例2 Goldstein-Price函数[37、38]

2f(x)1x1x211914x13x1214x26x1x23x222302x13x21832x112x1248x236x1x227x2,

22x1,x22,极小值点有4个，全局极小值点有1个，如

x*0,1,f*3.0

例3 Brain函数[37]

5.15.01f(x)x22x12x16101cosx110,5x110,0x215

48极小值点有多个，全局极小值点有3个，如

2x*(9.424,2.474),(3.1415,2.274),(3.1415,12.274),

f*0.397887。

例4 二维Shubert函数（II）[37-39]

55f(x)jcos(j1)x1jjcos(j1)x2jj1j1

x20.80032,x11.425132210x1,x210,极小值点有760个，全局极小值点有1个，如

,f*186.73

x*1.42513,0.80032例5 Schwefel No. 3.7函数[39]

f(x)xi10,1xi1,

i1n当n=7时，极小值点有多个，全局极小值点有1个，如

x*=0，f*=0。

例6 [40]

f(x)jsin(j1)xj,10x10

j15极小值点有19个，全局极小值点有3个，如

x*6.774,0.4913,5.791,例7[40]

f*12.03

1f(x)sin,0.02x1,

x极小值点有8个，全局极小值点有8个，如

2x*,k1,2,,8,f*1

(4k1)例8（非光滑函数优化问题）[41]

1f(x)4x22.1x4x6|x|,x[1,1]

3x*0.21,

f*0.9。

Part 7 问题

1. 借助网络查找中国主要城市之间的航空价格，应用禁忌搜索算法，设计一条游遍这些主要城市的最少费用行程路线（最好包含一些主要城市）。

2. 应用蚁群优化算法求解上述TSP问题。

3. 如何寻求最优化问题的全局最优解是至今都没有解决的一个难题。经典的迭代方式所找出的解往往都是局部最优解。而现代的一些启发式智能算法又面临着难于判断局部最优解就是全局最优解。相对来说，从一个极小值点跳出找到另一个更小的极小值点，现代启发式算法做出了大量工作。问，你能否设计出一种算法跳出当前的极小值点？如何判断找到的点就是全局极小值点？可以从具体的一个优化问题出发，而不是一般的优化问题。可参看Part 6的范例。

4. 用一维的梯度法或者差分法计算例6或例7的局部与全局极值。

5．查找资料，寻找算法，求解非光滑优化问题例8。

6. 经典的迭代式算法寻求最优化问题的解时，拟牛顿及其改进方法是非常有效的算法。其中主要是涉及到目标函数f(x)的Hesse矩阵的近似或估计。你能否联系函数f(x)的性质，对其Hesse矩阵进行分类讨论，从而对相关算法进行分类总结？

参考文献

[1]J. Z. zhang, N. Y. Deng and L. H. Chen. A new quasi-Newton equation and related

methods for unconstrained optimization. Journal of Optimization Theory and

Application 102(1999) 147-167

[2]Xiao Yunhai and Ye Hun. A Modified BFGS Method with Global Convergence for

Unconstrained Optimization Problems. Guang xi Sciences 2003,10 (4) 253-257,261

[3]白华，南京理工大学理学院硕士论文，2006。

[4]徐成贤，陈志平，李乃成，近代优化方法，科学出版社。

[5]More J.J. and Sorensen D.C., Computing a trust region step, SIAM journal on

scientific and statistical computing, 4: 553-572,1981.

[6]Hebden M.D.,An algorithm for minimization using exact second derivatives.

Atomic energy research establishment report TP515,Harwell,England,1973.

[7]Levenberg K.,A method for the solution of certain nonlinear problems in least

squares, Quart. Appl. Math., 2:164-168,1944.

[8]Marquardt D.W., An algorithm for least squares estimation of nonlinear parameters,

SIAMJ. ,11:111-115,1963.

[9]M.J.D. Powell, A hybrid method for nonlinear equations, in: ,O.L.

Mangasarian and , eds, Nonlinear algebraic equations ( Gordon and Breach

science , London,1970),87-144.

[10] and , Two new unconstrained optimization algorithms

which use function and gradient values, J. Opt. Theory and Appl.,28:453-482,1979.

[11]Zhang J.Z. and Xu C.X., A class of indefinite dogleg path methods for

unconstrained minimization, SIAM J. on optimization, V9,646-667,1994.

[12]Glover F.,Future paths for integer programming and links to artificial intelligence,

Computers and operations research, 13: 533-549,1986.

[13]Glover F., Tabu search: Part I. ORSA Journal on computing, 1:190-206, 1989.

[14] Glover F., Tabu search: Part II. ORSA Journal on computing, 2:14-32, 1990.

[15]Maes J. McClain J. O. van Wassenhove L.N. Multilevel capacitated lotsizing

complexity and LP-based heuristics. Euro J of Opera. Res., 53:131-148,1991.

[16]Metropolis N, Rosenbluth A, Rosenbluth M et. al., Equation of state calculations

by fast computing machines. Journal of chemical physics, 21:1087-1092,1953.

[17]Kirkpatrick S, Gelatt Jr C.D., Vecchi M.P., Optimization by simulated annealing ,

science, 220:671-680,1983.

[18]Holland J.H., Adaptation in natural and artificial systems. MIT Press, 1975.

[19]Dorigo M., Optimization, learning and natural algorithms, PhD thesis,

Department of electronics, Politecnico di Milano, Italy, 1992.

[20]Parpine R.S., lopes H.S., Freitas A.A., Data mining with an ant colony

optimization algorithm, IEEE Transactions on evolutionary computing,

6:321-332,2002.

[21]Stützle T., Hoos H.H., MAX-MIN ant system, Future generation computing

system,16:889-914,2000.

[22]Gutjahr W.J., A graph-based ant system and its convergence, Future generation

computing system, 16:873-888,2000.

[23]Ratschek H., Rokne J., New computer methods for global optimization, Ellis

Horwood: Chichester, 1988.

[24]Moore R., Interval analysis, Englewood Cliffs NJ: Prentice-Hall, 1966.

[25]申培萍著，全局优化方法，科学出版社，2006。

[26]Ge R., A filled function method for finding a global minimizer of a several

variables, Mathematical programming, 35:191-204,1990.

[27]Ge R., Qin Y., The global convexized filled functions for global optimization,

Applied mathematics and computation,35:131-158,1990.

[28]R. Horst, os, , Introduction to global optimization, Kluwer

Academic publisher, 1995.

[29]Rosen J.B., Pardalos P.M., Global minimization of large-scale constrained

concave quadratic problems by separable programming. Math programming,

34:163-174,1986.

[30]Hoai L.T.,Tao P.D., Solving a class of linearly constrained indefinite quadratic

problem by D.C. algorithms, Journal of global optimization,11:253-285,1997.

[31]Yajima Y.T., Fujie T.Y., A polyhedral approach for nonconvex quadratic

programming problems with box constraints . Journal of global optimization,

13:151-170,1998.

[32]Ye Yinyu, Approximating quadratic programming with bound and quadratic

constraints, Math programming, 84:219-286,1999.

[33]Hoai L.T., An efficient algorithm for globally minimizing a quadratic function

under convex quadratic constraints. Math programming, 87:401-426, 2000.

[34]Locatelli M., Schone F., Random Linkage: a family of acceptance/rejection

algorithm for global optimization, Mathematical programming, 85(2):379-396,1999.

[35]Jones D.R., Schonlau M., Welch W.J., Efficient global optimization of expension

black-box functions. Journal of global optimization, 13(4):455-492,1998.

[36], A method of conjugate subgradients for minimizing nondifferentiable

functions, Math. Prog. Study, 3:145-173, 1975

[37]Casado L.G., Martinez J.A., Garcia I., Experiments with a new selection criterion

in a fast interval optimization algorithm, Journal of global optimization,

19:247-264,2001.

[38]Csendes T., New subinterval selection criteria for interval global optimization,

Journal of global optimization, 19: 307-327, 2001.

[39]Hansen E., Global optimization using interval analysisi, New York: Maacel

Dekker Inc., 1992.

[40]Ratez D., A nonsmooth global optimization technique using slopes: the

one-dimensional case, Journal of global optimization, 4:365-393, 1999.