数学建模社区-数学中国

标题: 浅谈全局最优 [打印本页]

作者: huaer 时间: 2010-2-28 10:49
标题: 浅谈全局最优

一、从爬山谈起
每个人都会迷路。但是也许很少有人会对迷路这种现象思考甚多。原因很简单，一个人对周围的环境不熟悉，自然就可能迷路。而且，越是生疏的地方，迷路的可能就越大。如果是自己非常熟悉的地盘，也许闭着眼睛也不会迷路。
但其实迷路只是一种现象，却非本质。对人们来说，迷路不是偶然的，而是必然的。是否迷路，迷路的程度多少，完全取决于当事人对周围环境的信息的了解程度。比如，从一个地方A到另外一个地方B，其中有N条岔道，其中只有一条连接A和B；假设当局者对从A到B一无所知，那么，他要花多少时间才能到达目的地呢？答案是，当局者也许一辈子也找不到从A去B的路----如果他不在探索的时候记录信息的话。我说的意思是，如果当局者在寻找这条唯一的道路的时候，不能记录他以前的探索结果，不能记录这N条路的特征，那么，当局这就可能永远也找不到正确的从A到B的道路。
这是一件令人伤心的事实。但毕竟，很幸运的是，我们是人，毕竟能够发挥主观能动性，在寻找这条道路的时候可以记录信息，从而在搜索N次以后，终于可以找到从A到B的路。但是在另外一些情况中，我们可能连这样的乐观都没有。比如，假设有人让某人在一座山脉中寻找一个海拔最低的山谷，但是这个山脉有多少山谷，怎样到达这些山谷，我们根本不知道。在这样的情况下，假设该人能够记录他搜索的历史信息，，那么他要花时间才能够断言他找到的是海拔最低的山谷呢？答案是，无穷时间。我的意思是，该人一辈子都不能够断言他找到的是最低的山谷。
相似的情形在社会生活中很多领域出现。一件困惑人们千百年之久的事情就是，怎样才能找到最适合自己的对象？是否真的存在自己的那根肋骨？是否真的有对自己最好的人？我们可以悲观的说，人们是不可能找到最适合自己的对象的，也不存在自己的那根肋骨，不存在对自己最好的人。所有的这些我们都不知道，因为我们不能够一一了解存在的人类个体，不能亲身体验。这样的一个事实的结果是这样的一个忠告：惜取眼前人。正如苏格拉底让他的学生们所做的，在摘麦穗的时候，自己觉得最大了的就摘。别老是想着摘最大的，否则可能结果恰恰相反。
这些问题就是全局最优的问题。这些问题涉及到社会生活的方方面面。因此，对这种问题作一个探讨是有必要的，也可能在某些方面能够改进人们的某些观念。比如，一个让喜欢**的人们惋惜不已的问题是，人类为什么要一夫一妻，为什么不能够多取几个老婆，这样，至少也能让我们多亲芳泽，不至于私下里经常流着口水？我们将会看到，解释是哲学层面的，但是诠释确是非常合理。

二、局部最优和全局最优
既然我们要考察全局最优的问题，那么一个必然要设计的概念就是局部最优。什么是全局最优，什么是局部最优呢？这样的解释可能比较容易理解：假设当事人在一定的范围内寻找一个解决方案，使得当事人期望的目标达到最大或者最小。如果一个方案使得当事人的目标得以实现，就称该方案为全局最优方案，而目标就称为全局最优的目标。假设一个方案虽然不能让当事人的目标达到全局最优，但是在一个小范围内，已经没有其他的方案比这个方案更好了，那么就成该方案为局部最优。用数学语言可以如下描述：
设f(x)是当事人的目标函数，F是当事人的选择范围。我们希望找到使得f(x)最小的x。如果有一个x^*使得f(x^*)<=f(x),对任意的x属于F都成立，就称x^*使全局最优的。不然，如果存在一个集合E包含在F中，x^*属于E，使得f(x^*)<=f(x),对任意的x属于E都成立，就称x^*是局部最优的。
求解全局最优的问题就称为全局最优化问题。由以上阐述可以看到，一个全局极小问题可以描述如下
global min f(x)
s.t. x 属于 F
其中F={x|g(x)>=0}，g(x)是一个向量函数。
假设f(x),g(x)都是曲线，那么全局最优解就是让f(x)在g(x)>=0限定的区域F内达到最低点的点。

三、全局最优的解法
要考察如何求解全局最优问题，先从几何观点来审视这个问题是有好处的。假如在一个斜坡上放一个球，如果摩擦力适当小，那么球将会往更低的地方跑。从物理上我们知道，在一个斜角为v的斜坡上，物体的下滑力，如果忽略摩擦力，当为mgsin v。设斜坡斜率为K，则有
(sin v)^2+(cos v)^2=1, sin v/ cost v= K
由此可得
sin v =K/(1+K^2)^{1/2}
根据牛顿定律，可得
mds/dt =mg sin t=m K/(1+K^2)^{1/2}=>
ds/dt=K/(1+K^2)^{1/2}
其中s是沿着斜坡运动的速度，所以ds/dt就是沿着斜坡运动的加速度。
我们来看物体在平行地面（即可设为x轴）运动的加速度是多少。根据矢量分解的平行四边形法则，该加速度应该为
dx/dt=ds/dt * cos v=K/(1+K^2)^{1/2}* 1/(1+K^2)^{1/2}=K/(1+K^2)
现在考虑球放在曲线f(x)上在点x处的加速度。由于在该点的梯度为 abla f(x),故可类似推得：
dx(t)/dt=- abla f(x)/(1+|| abla f(x)||^2)
其中||.||表示 abla f(x)这个向量的范数。如向量a的范数为||a||=(a^Ta)^{1/2}。
注意到- abla f(x)是一个向量，而1+|| abla f(x)||^2是一个数，所以方程
dx(t)/dt=- abla f(x)/(1+|| abla f(x)||^2)就表示沿着 abla f(x)下降的运动方程。更进一步，我们可以略掉1+|| abla f(x)||^2，而直接考虑：
dx(t)/dt=- abla f(x) （A）
对t进行离散，并用差分离散该方程，就可以得到诸如最速下降法（或者称为下山法），牛顿法之类的局部最优的求解方法，如，一阶离散，可得：
x_{k+1}-x_k=- abla f(x_k)*(t_{k+1}-t_k)
这就是最速下降法。
如对方程（A）先对t求导数，即
d^2x(t)/dt^2=- abla^2 f(x)*d x(t)/dt=- abla^2f(x)* abla f(x) (B)
由此可得牛顿法。
注意到当 abla=0的时候，上述方程(A),(B)都处于稳定状态了，这时候球打到最低点，这时候就不能下降了。
由上面可以看到，要求的一个局部最优还是很容易的。只要求系统(A),(B)的稳定点就可以了。
但是求解全局最优就没有那么幸福了。因为这个时候我们根本就无法判断一个点是否全局最优。即使我们能够找到很多局部最优，我们也不能断言我们已经找到全局最优----除非函数f(x)只有一个局部最优。这是一个悲剧。
一种很直接的想法是通过局部最优来求解全局最优。这又分为几种方法。一种十多取几个初始点，求得多个局部最优，然后比较这些局部最优，取其最好的。这种方法就叫做随机算法。这种算法很直接，缺点也很明显---我们无法判断我们是否达到了全局最优。因为很多局部最优只是一个简单的罗列，而没有任何实质性的改进。
另外一种想法几何直观也很明显。这种方法希望在达到一个局部最优以后，能够跳出该局部最优，然后继续搜索，达到另外一个更好的局部最优点。这种方法包括填充函数法和隧道函数法。这样看起来，如果这种想法真正的能实现，那么，就能够实现全局最优了。因为假设f(x)在F的局部最优有限，通过该方法，一直找下去，总是能够达到全局最优。但是很不幸，这些方法是无法实现真正的跳出已经求得的局部极小的。填充函数法通过构造一个新的辅助函数，把局部极小变成极大，然后对该点进行随机扰动（或者是确定性的扰动），再利用经过扰动以后的点为初始点进行搜索，寻找该辅助函数的局部极小点，该局部极小点是原来函数f(x)的更好的局部极小点或者至少和原来一样好。问题就是出在对原局部极小点进行扰动上。该扰动是没有目的的，因而很盲目。而且，该扰动的方案有无穷多种，每种方案可能导致不同的结果，而在实际计算中又无法全部实现这些方案。如对x是一维变量，对局部极小点的扰动就有两种方案，对x是n维变量的情况，对局部极小点的扰动有无穷多种方案。而且，利用扰动以后的点求得的辅助函数的局部最优可能根本就使原来的局部最优点，或者在一些计算以后回到该局部最优点，从而形成循环。这样就意味着我们无法判断利用辅助函数搜索到的点是全局最优点。相似的情况发生在隧道函数上。隧道函数是通过一个辅助函数到达另外一个点上，该点在另外一个更好的局部最优点的吸收域中。它的本质方法是水平集法。隧道函数的缺点就在于构造隧道函数求另外一个点的时候，同样存在无穷多个搜索方向，因而也无法保证最终求得的局部最优为全局最优。
积分水平集方法是另外一个求解全局最优化的方法。该方法的本质是这样的：如果找到了一个可行点x^*属于F，如果能够构造水平集E={x|f(x)<=f(x^*),x属于F}。在该区域中搜索，求得新的局部最优，一次迭代，就能够求得全局最优。构造水平集是一件困难的工作。为此，研究者们采用随机投点的方法来近似构造该水平集，并用f(x)<=f(x^*)该评判准则来剔除大于f(x^*)的点。这样，近似构造水平集就取决于随机所投的点。为了获得在F上全局最优，就需要投无穷多个点。随着投点的越来越多，计算量也越来越大。因此，从理论上来说，积分水平集方法能够求得全局最优，但是从计算角度来看，需要耗费非常多的计算量。
有朋友可能会问，既然如此，为什么不对
min f(x)
s.t. f(x)
其中eps是一个很小的正数，这样一个问题来求解呢？这样不是在水平集E上求解么？但是，根据笔者用计算软件计算的经验，这样的问题始终还是停留在原来的局部最优点x^*，没有什么改进。背后的机理如何，现在还不清楚。
最直观的方法是分割区域F来求解全局最优。这样就有区域分割算法、单纯分割算法等等方法。显然，区域分割方法为了求得全局最优，需要大量的计算量。
启发式算法，包括遗传算法、神经网络算法、蚁群算法等等，都不能保证求得全局最优。而且计算量相当巨大。
就目前来说，除了对某些特殊的全局最优问题能够有效求解，对于一般的问题，目前还没有有效的手段来求解。

四、全局最优与正性问题
全局最优问题和正性问题是等价的。所谓正性问题是指如下问题：
[正性问题]：
判断是否对任意的x满足g(x)>=0，都有f(x)>=0成立。显然，如果正性问题能够判定，那么因为全局最优问题等价于,对于全局最优的t=f(x^*)，其中x^*使全局最优解，有
t-f(x)>=0,对任意的x满足g(x)>=0
所以全局最优问题与正性问题等价。
已经被Richardson证明，对于一般的函数类f(x)和g(x)，该正性问题是不可
解的。所谓不可解，就是无法作出判定。因此，对函数f(x),g(x)作出限定是有必要的。
如果把f(x),g(x)限定在多项式函数，那么很多结果已经在代数几何中得到。Hilbert提出的23个著名问题中的Hilbert’s17th problem就是判定是否对任意的多项式f(x)>=0,对于任意的x属于R^n，f(x)都是可以表示成有限多个有理多项式的平方的和。
Hilbert’s 17th problem已经由Artin在1927年的出否定的解决。他证明，对于在实数空间R^n上恒非负的多项式f(x)，它可以表示成为有限个有理多项式的平方和，但是可以举出反例不可以表示为多项式的平方和。
但是对以更广泛的问题f(x)>=0, orall=0这样的判定问题，其中g(x)是多项式函数，现在仍然有很多问题需要研究。如果g(x)十多项式向量函数，那么区域F={x|g(x)>0}就称为半代数集。因此一般的正性问题可以叙述如下：
[正性问题]：
判定，是否对任意的满足g(x)>=0的x，都可以推出f(x)>=eps?
目前对该正性问题已经有不少结果。如Hilbert’s Positivstellensitz.，Schugmzen’s Positivstellensitz,Putinar’s Positivstellensitz,等等结果。但是已经证明，虽然正性问题能够判定，但是计算量却是关于变量x的维数n以及1/eps的指数。显然，这样的计算量是非常巨大的。
用代数几何中的这些结果到最优化中，最近有若干研究。有两个人比较有代表性，他们是Parrilo和Lassarre。但是可以看到，用这样的方法求解多项式全局最优化，只能限于一些低维问题。
和正性问题相关的有半无限最优化问题以及半无限最优化问题的特例robust最优化问题。这些问题都归结成正性问题。半无限最优化问题形式如下：
min c^Tx
s.t. f(x,s)>=0, orall s属于U
其中U是一个确定性的集合。显然，求解这类问题的关键在于能否判定对于任意的s属于U，都有f(x,s)>=0。或者说，满足该问题的x是否可以解析地描述出来。一般来说，这样的问题需要指数时间的计算量。

五、全局最优化、组合最优化与计算复杂性
组合最优化在实际中有广泛的应用。大部分实际的最优化问题都归结成组合最优化问题。组合最优化考虑如下问题
min f(x)
s.t. x属于F
其中F是一个离散点集。
组合最优化只是全局最优化的特例。自从Cook1972年提出NP理论，衡量计算复杂性就有了标准。已经证明了相当大一类组合最优化问题是NP困难的问题和NP完全的问题。而这些问题有等价于一些全局最优化问题。因此，计算复杂性的概念就被引入了全局最优化。
所谓P问题，就是可以被关于问题本身的参数，如维数，约束个数等的多项式时间内求解的问题。NP问题就是对于一个给定的点，能多项式时间内判定它是否给定问题的解的问题。NP包含P是以显然的事实。但是P是否也包含NP，就是一个非常困难的问题。目前这个问题被列为全世界7大数学难题之首。
有一类NP问题，它们之间相互等价，求解其中一个问题就求解了全部问题。大部分组合组优化问题属于此类。这类问题称为NP完全问题类。单个问题就称为NP完全问题。一般相信，这类问题不存在多项式时间算法。
由于全局最优化包含了组合最优化，因此也可以用计算复杂性的概念到全局最优化上面。能多项式时间求解的问题是容易的，不能多项式时间内求解的问题是困难的。目前这已经成了判断算法好坏的一个标准。

六、全局最优化与积分
我们看到，求解全局最优化关键是利用全局信息。全局信息，就是能够描述函数整体性质的信息。导数、梯度、Hessian矩阵等等，都是局部信息。利用全局信息的方法，一个是水平集，一个是积分。利用水平集，如积分水平集方法，就是其中的代表。水平集的概念我们上面已经介绍过了，这里就不多说。这种方法最终归结到计算近似积分上。另外的一个方法，是直接计算积分。目前的一个结果是，如果给定一个点，判断它是否一个全局最优点，只要判断一个积分函数是否存在零点就够了。详细地说，给定x^*，考虑
global min f(x)
s.t. x属于[0，1]^n
其中[0,1]^n表示n维空间上的一个箱子。
通过构造辅助函数
g(t)=int_{x属于[0,1]^n}e^{t(f(x^*)-f(x))}dx
那么，可以证明g(t)是凸函数，并且，如果x^*不是全局最优，那么g(t)存在一个0点解t^*，而且当t>t^*时，g(t)是增函数。而如果x^*使全局最优，那么对g(t)的近似0点t^*，当t>t^*时，g(t)是减函数。利用该方法，就可以判断x^*是否全局最优。这也同时建立了全局最优与积分的关系。而且，也可以构造算法，来求解f(x)在[0,1]^n的全局最优。
利用上述方法的时候要计算高维积分。而这仍然是一个困难问题。求高维积分一般采用的是概率方法。但这样就无法得到一个确定性的误差，这样，就不知道在计算积分的时候损失了多少。从这个意义上说来，我们无法采用上述方法来求解全局最优。但是，有一种基于数论的一致分布的方法来求高维积分，而且误差是确定性的。这样，就可以利用它来计算近似全局最优解。
目前，探索积分与全局最优、利用积分来求解全局最优的方法和理论还很缺乏，有必要也有潜力大力发展。

七、从哲学观点看全局最优
从能量守恒原理来看，物质运动都趋于使维持物质的能量最小这个方向发展。如肥皂泡在收缩过程中形成的曲面要使曲面面积最小，从而使支撑该曲面的能量最小；又如原子为了自身的稳定，总是释放能量，让电子轨道向低能级跃迁；其他，无论是生物学、进化论，还是天体演化，等等，都表明了这一原理的合理性，即使不敢说正确性。而耗散理论的观点也在这方面说明了这一点。
物质运动既然趋向低能和稳定结构，那么，一般来说，不存在普遍的完美的解决方案，使得即可以解决问题，而解决的手段又漂亮的无懈可击。因为如果这样，就意味着解决方案处于高能状态，而这是不稳定的。只要条件稍微改变，旧有可能引致该解决方案发生质的变化，由完美变成不完美。完美的存在是高能耗的，不稳定的，其存在当且仅当在很严格的条件满足。如就最优化来说，人们目前能自豪地宣称能够找到全局最优的问题，也就是自己实现能判定出来的局部最优唯一的问题类----甚至对这样的问题，如果要用计算复杂性理论来度量的话，也还有一些问题不能够多项式时间求解。人类能作用的范围太小了。
既然完美的活的需要高代价，那么寻找全局最优有必要向两个方向发展。第一个方向是保证能够求得全局最优，另外一个是能尽可能快地求得相对好的解。目前的研究状态就是这样的。前者导致了启发式算法、随机算法的热烈研究，而后者则导致了近似算法的研究。显然，我们也希望，在进行寻找全局最优的时候，不必要用各种准则来**研究方法。“黑猫白猫，抓到老鼠的是好猫”。
有时候我们常常通过外界映照，来推知自身所处的位置。如通过观察其他动物来推知人类本身所处于世界中的位置，通过别人的行为推知自己行为的合理性。对世界观察，并用数学同构的观点来认知世界，也许不失为拓广知识的一种方法。.但是这些对于无知觉的算法来说，都统统失效。智能算法，如能记录搜索过程，自适应调整搜索方向的算法，也许值得研究。
但无论如何，我们处于一种尴尬的境地，一方面，我们需要全局最优，一方面，我们对大部分问题无能为力。也许这恰好是人类几千年来挣扎着发展的历史。

八、对生活的建议
对别人的生活提出忠告是一件很冒险的事情。因为任何人不见得比别人好得更多---如果单纯从人在世界所处的位置来看。所以这里只是提出建议。
在惆怅现在找对象还是将来找对象，现在找了，万一将来遇到更好的怎么办的朋友，建议赶快找一个对自己好，自己也相对喜欢的身边人。好没有穷尽，任任何时候也不能判断自己的选择是否最优，既然如此，不如赶快动手，别丢失了你现在最大的那颗麦穗。
对勇于立志，要成大事业但是不知道干那个好，感觉什么都能做的朋友，不如从现在做起，从眼前做起，把当前要做的事情做好，同时也要智能地观察和调整自己的路。也许这样，才是这个人生的最优解。
对研究感到失望，诚如若干年前我陷入的疑惑的朋友，不如先判断那种方法能有一些改进，然后就埋头进去苦干。人类的发展需要前赴后继的努力，能给大厦添砖加瓦就相当不错了。毕竟人能力有大小，做好本分也是值得尊重的。
对决策影响到很多人、但是手中的权力无监督的朋友，请遇事情反复思量。一种决策很难达到最优，永远不要武断地认为自己已经找到最佳的解决途径了。不妨多不耻下问，也许至少能够改善决策，提高效果。

作者: starbinbin 时间: 2010-2-28 11:31
写的很好！我来顶一下~~~~~~~~~~

作者: D-lin 时间: 2010-2-28 12:11
受教了 ~~~~~~~~~~~~~~~~~~~~~

作者: 厚积薄发 时间: 2010-2-28 13:16
是你写的吗？太拽了，各个层面都涉及到了

作者: huaer 时间: 2010-3-1 16:29
回复 4# 厚积薄发

是站在别人的肩上才成形的

作者: gssdzc 时间: 2010-6-18 19:04
感谢分享。。。。。。

作者: huaer 时间: 2010-8-4 15:53
回复 starbinbin 的帖子

谢谢，望指教！

作者: huaer 时间: 2010-8-4 15:54
回复 D-lin 的帖子

作者: huaer 时间: 2010-8-4 15:54
回复 gssdzc 的帖子

谢谢，望指教！

作者: weixinmaths 时间: 2011-6-22 16:00

作者: hbdkfk2 时间: 2012-8-19 11:13
谢谢分享！！！！！！！！！！！

作者: 别离 时间: 2013-9-8 15:54
写得好，厉害啊

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)