四、 全局最优与正性问题<BR>全局最优问题和正性问题是等价的。所谓正性问题是指如下问题:<BR>[正性问题]:<BR>判断是否对任意的x满足g(x)>=0,都有f(x)>=0成立。显然,如果正性问题能够判定,那么因为全局最优问题等价于,对于全局最优的t=f(x^*),其中x^*使全局最优解,有<BR>t-f(x)>=0,对任意的x满足g(x)>=0<BR>所以全局最优问题与正性问题等价。<BR>已经被Richardson证明,对于一般的函数类f(x)和g(x),该正性问题是不可<BR>解的。所谓不可解,就是无法作出判定。因此,对函数f(x),g(x)作出限定是有必要的。<BR>如果把f(x),g(x)限定在多项式函数,那么很多结果已经在代数几何中得到。Hilbert提出的23个著名问题中的Hilbert’s17th problem就是判定是否对任意的多项式f(x)>=0,对于任意的x属于R^n,f(x)都是可以表示成有限多个有理多项式的平方的和。<BR>Hilbert’s 17th problem已经由Artin在1927年的出否定的解决。他证明,对于在实数空间R^n上恒非负的多项式f(x),它可以表示成为有限个有理多项式的平方和,但是可以举出反例不可以表示为多项式的平方和。<BR>但是对以更广泛的问题f(x)>=0,\forall x:g(x)>=0这样的判定问题,其中g(x)是多项式函数,现在仍然有很多问题需要研究。如果g(x)十多项式向量函数,那么区域F={x|g(x)>0}就称为半代数集。因此一般的正性问题可以叙述如下:<BR>[正性问题]:<BR>判定,是否对任意的满足g(x)>=0的x,都可以推出f(x)>=eps?<BR>目前对该正性问题已经有不少结果。如Hilbert’s Positivstellensitz.,Schugmzen’s Positivstellensitz,Putinar’s Positivstellensitz,等等结果。但是已经证明,虽然正性问题能够判定,但是计算量却是关于变量x的维数n以及1/eps的指数。显然,这样的计算量是非常巨大的。<BR>用代数几何中的这些结果到最优化中,最近有若干研究。有两个人比较有代表性,他们是Parrilo和Lassarre。但是可以看到,用这样的方法求解多项式全局最优化,只能限于一些低维问题。<BR>和正性问题相关的有半无限最优化问题以及半无限最优化问题的特例robust最优化问题。这些问题都归结成正性问题。半无限最优化问题形式如下:<BR>min c^Tx<BR>s.t. f(x,s)>=0,\forall s属于U<BR>其中U是一个确定性的集合。显然,求解这类问题的关键在于能否判定对于任意的s属于U,都有f(x,s)>=0。或者说,满足该问题的x是否可以解析地描述出来。一般来说,这样的问题需要指数时间的计算量。<BR><BR>五、 全局最优化、组合最优化与计算复杂性<BR>组合最优化在实际中有广泛的应用。大部分实际的最优化问题都归结成组合最优化问题。组合最优化考虑如下问题<BR>min f(x)<BR>s.t. x属于F<BR>其中F是一个离散点集。<BR>组合最优化只是全局最优化的特例。自从Cook1972年提出NP理论,衡量计算复杂性就有了标准。已经证明了相当大一类组合最优化问题是NP困难的问题和NP完全的问题。而这些问题有等价于一些全局最优化问题。因此,计算复杂性的概念就被引入了全局最优化。<BR>所谓P问题,就是可以被关于问题本身的参数,如维数,约束个数等的多项式时间内求解的问题。NP问题就是对于一个给定的点,能多项式时间内判定它是否给定问题的解的问题。NP包含P是以显然的事实。但是P是否也包含NP,就是一个非常困难的问题。目前这个问题被列为全世界7大数学难题之首。<BR>有一类NP问题,它们之间相互等价,求解其中一个问题就求解了全部问题。大部分组合组优化问题属于此类。这类问题称为NP完全问题类。单个问题就称为NP完全问题。一般相信,这类问题不存在多项式时间算法。<BR>由于全局最优化包含了组合最优化,因此也可以用计算复杂性的概念到全局最优化上面。能多项式时间求解的问题是容易的,不能多项式时间内求解的问题是困难的。目前这已经成了判断算法好坏的一个标准。<BR><BR>六、 全局最优化与积分<BR>我们看到,求解全局最优化关键是利用全局信息。全局信息,就是能够描述函数整体性质的信息。导数、梯度、Hessian矩阵等等,都是局部信息。利用全局信息的方法,一个是水平集,一个是积分。利用水平集,如积分水平集方法,就是其中的代表。水平集的概念我们上面已经介绍过了,这里就不多说。这种方法最终归结到计算近似积分上。另外的一个方法,是直接计算积分。目前的一个结果是,如果给定一个点,判断它是否一个全局最优点,只要判断一个积分函数是否存在零点就够了。详细地说,给定x^*,考虑<BR>global min f(x)<BR>s.t. x属于[0,1]^n<BR>其中[0,1]^n表示n维空间上的一个箱子。<BR>通过构造辅助函数<BR>g(t)=int_{x属于[0,1]^n}e^{t(f(x^*)-f(x))}dx<BR>那么,可以证明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的全局最优。<BR>利用上述方法的时候要计算高维积分。而这仍然是一个困难问题。求高维积分一般采用的是概率方法。但这样就无法得到一个确定性的误差,这样,就不知道在计算积分的时候损失了多少。从这个意义上说来,我们无法采用上述方法来求解全局最优。但是,有一种基于数论的一致分布的方法来求高维积分,而且误差是确定性的。这样,就可以利用它来计算近似全局最优解。<BR>目前,探索积分与全局最优、利用积分来求解全局最优的方法和理论还很缺乏,有必要也有潜力大力发展。<BR><BR>七、 从哲学观点看全局最优<BR>从能量守恒原理来看,物质运动都趋于使维持物质的能量最小这个方向发展。如肥皂泡在收缩过程中形成的曲面要使曲面面积最小,从而使支撑该曲面的能量最小;又如原子为了自身的稳定,总是释放能量,让电子轨道向低能级跃迁;其他,无论是生物学、进化论,还是天体演化,等等,都表明了这一原理的合理性,即使不敢说正确性。而耗散理论的观点也在这方面说明了这一点。<BR>物质运动既然趋向低能和稳定结构,那么,一般来说,不存在普遍的完美的解决方案,使得即可以解决问题,而解决的手段又漂亮的无懈可击。因为如果这样,就意味着解决方案处于高能状态,而这是不稳定的。只要条件稍微改变,旧有可能引致该解决方案发生质的变化,由完美变成不完美。完美的存在是高能耗的,不稳定的,其存在当且仅当在很严格的条件满足。如就最优化来说,人们目前能自豪地宣称能够找到全局最优的问题,也就是自己实现能判定出来的局部最优唯一的问题类----甚至对这样的问题,如果要用计算复杂性理论来度量的话,也还有一些问题不能够多项式时间求解。人类能作用的范围太小了。<BR>既然完美的活的需要高代价,那么寻找全局最优有必要向两个方向发展。第一个方向是保证能够求得全局最优,另外一个是能尽可能快地求得相对好的解。目前的研究状态就是这样的。前者导致了启发式算法、随机算法的热烈研究,而后者则导致了近似算法的研究。显然,我们也希望,在进行寻找全局最优的时候,不必要用各种准则来限制研究方法。“黑猫白猫,抓到老鼠的是好猫”。<BR>有时候我们常常通过外界映照,来推知自身所处的位置。如通过观察其他动物来推知人类本身所处于世界中的位置,通过别人的行为推知自己行为的合理性。对世界观察,并用数学同构的观点来认知世界,也许不失为拓广知识的一种方法。.但是这些对于无知觉的算法来说,都统统失效。智能算法,如能记录搜索过程,自适应调整搜索方向的算法,也许值得研究。<BR>但无论如何,我们处于一种尴尬的境地,一方面,我们需要全局最优,一方面,我们对大部分问题无能为力。也许这恰好是人类几千年来挣扎着发展的历史。<BR><BR>八、 对生活的建议<BR>对别人的生活提出忠告是一件很冒险的事情。因为任何人不见得比别人好得更多---如果单纯从人在世界所处的位置来看。所以这里只是提出建议。<BR>在惆怅现在找对象还是将来找对象,现在找了,万一将来遇到更好的怎么办的朋友,建议赶快找一个对自己好,自己也相对喜欢的身边人。好没有穷尽,任任何时候也不能判断自己的选择是否最优,既然如此,不如赶快动手,别丢失了你现在最大的那颗麦穗。<BR>对勇于立志,要成大事业但是不知道干那个好,感觉什么都能做的朋友,不如从现在做起,从眼前做起,把当前要做的事情做好,同时也要智能地观察和调整自己的路。也许这样,才是这个人生的最优解。<BR>对研究感到失望,诚如若干年前我陷入的疑惑的朋友,不如先判断那种方法能有一些改进,然后就埋头进去苦干。人类的发展需要前赴后继的努力,能给大厦添砖加瓦就相当不错了。毕竟人能力有大小,做好本分也是值得尊重的。<BR>对决策影响到很多人、但是手中的权力无监督的朋友,请遇事情反复思量。一种决策很难达到最优,永远不要武断地认为自己已经找到最佳的解决途径了。不妨多不耻下问,也许至少能够改善决策,提高效果。 <BR> |