網頁

星期一, 9月 22, 2014

劉剛獲提名首屆貝爾實驗室獎

轉載:

 好消息,我要获大奖了!

 作者:刘刚   2014-09-20 09:06:52 [Reads:396]   返回共舞台首页 

本文网址:http://jasmine-action.blogspot.com/2014/09/blog-post_20.html

我已经被提名首届贝尔实验室奖。目前正在进行第二阶段工作,在这个阶段,贝尔实验室将出资出人,帮助我完善我开发的优化计算系统。年底发奖。

我在线性规划以及经济学领域中的几篇论文不久将被学术界认可。将来还会获得更多的奖。

对于懂得线性和非线性规划的人不难看出我的算法对数学领域的贡献。当前线性规划的最佳算法是单行算法(Simplex)和内点算法(Interior Point)。这两个算法被誉为100年来10个最佳算法之中。内点算法的收敛速度是N^5.5. 而我给出的新算法的收敛速度是N^2。通常,将这种算法的收敛速度能提高0.5次方,都能算作是一场革命。我的算法一下提高了3.5次方!

根据我现有的几个发明,我已经开发了一些软件,这些软件将能够取代IBM的一些最赚钱的软件系统。IBM的Cplex系统每年能够赚取几十亿美金,这些软件将会被我的软件取代。

有兴趣的人,不妨到下列网站试用我的软件:

http://quatratic.com

这个网站只是暂时网站。我将同贝尔实验室一道发展建立新网站,并通过更新硬件系统,进一步加速我们的运算速度。届时可望再提高速度一万倍。

还有一个坏消息。我又被毒评给封名了。等将来赚大钱了,看我如何去对付毒评。

随后简单介绍一下我的这个软件的商业价值和应用领域。

目前进行线性规划优化计算的系统是IBM的Cplex以及Gurubi公司的计算系统,对非线性规划的计算系统是斯坦福大学开发达MINOS。这些系统的单一用户的使用权是$8000,有的高达$35,000. 也就是说,如果你要使用这个系统,你每年至少要缴纳$8000. 这比微软的所有软件都加起来还要昂贵。

这类优化问题广泛应用于各个行业,比如电讯行业的光纤网络设计,航空工业的线路规划,金融业的模型优化和模拟计算,在军事上有更多的应用。

举一个例子来说,我曾经为一些电讯公司进行光纤网络设计,这包括北方电讯的光纤网络,奥地利的光纤网络,Level3 的光纤网络。这些光纤网络通常都要投资几十亿美元。通过优化设计,能够节省投资50%。也就是说,我们几个人帮助它们进行优化设计,就能节省投资上亿美元。这些公司当然愿意为我们的优化设计支付上千万美元的报酬。而这种优化设计,就是要通过求解线性规划问题。我当年就是使用CPLEX进行计算。使用CPLEX现有的方法进行计算,我们通常要计算几个礼拜甚至是更长时间才能给出最佳解。我现在开放的软件,就能将解决这类问题的速度由原来的几周时间提高到几分钟内。这是我们的软件的优势。

另外,最主要的是,一旦我们的软件被认定为是当今优化问题的最快软件,那些电讯公司及航空公司就会将它们的那些大项目交给我们去进行优化设计。这些项目通常都是几十亿美元的预算。光是优化设计,就应该能够赚取上千万美元。

下面是一个有包含有两个变量、7个限制条件的三次方优化问题。



上图的左侧给出这个问题的数学表达式,右侧的图形给出这个问题的可能取值区域(Feasible Region). 从图中看,这个问题的最佳解是图中的红圈圈出的那一点。也就是

x0 = 0.90740
x1 = 0.63236


上面的问题可通过使用我们的软件加以解决。我们首先将上述数学公式写出下面的输入文件:

Max: x0 ;
subject to
lower bound for all: 0;
upper bound for all: 1;
Subject To
C1:x0x0x0 + x1x1x1>=1;
C2:x0x0 +x1x1 -2x0>=0;
C3:x0x0 +x1x1 -2x1>=0;
end

将上面的内容存入一个文件,再将此文件上传到 quatratic.com. 随后按照网站上给出的方式求解此问题,就会得到该问题的最佳解。

这个问题很简单,可以通过笔算加以解决。可以用这种简单问题来验证我们的程序。通常,我们的程序是用来解决有很多个变量的问题,比如,可能会有上百万个变量的问题。


应用:习近平包包子的最佳方案



我过去曾经以习近平包包子为例,来解释如何给出习近平包包子的最佳方案。现在,我们就再次以此为例,来使用我们的软件解决这个问题。

我们假设习近平和彭丽媛夫妇分工合作来包包子。二人是一个擀皮,一个包包子。假设在一个小时时间里习近平能够擀皮60个,包20个包子,而彭丽媛能够擀皮40个,包50个包子。假设习近平夫妇的目标是要在一个小时有最大的成品包子产出,就是说要包出尽可能多的包子,又使得包子皮没有过剩也没有短缺,那么,习近平和彭丽媛包包子的最佳方案是什么?就是说,应该让谁擀皮,又让谁去包包子?

这个习近平包包子的问题就是一个线性优化问题。我们首先可以列成下面的数学方程式。

我们将习近平花在包包子上的时间百分比为未知数x,那么,他花在擀皮上的时间就自然是(1-x)。

我们将彭丽媛花在包包子上的时间百分比为未知数y,那么,他花在擀皮上的时间就自然是(1-y)。

这二人合作的擀皮总量为 60(1-x) + 40(1-y).

这二人合作的包包子总量为 20x + 50y.

根据要求,我们需要擀皮总量等于包包子总量,也就是:
20x + 50y = 60(1-x) + 40(1-y).

这就是我们的限制条件之一。其它限制条件还应该有:

0 <= x <= 1;
0 <= y <= 1;

在满足这些限制条件下,我们希望习近平夫妇的包包子产量最大化,那就是要:

maximize: 20x + 50y.

将上述问题适当化简后,习近平包包子的优化方案问题可归结为如下的线性规划问题:

maximize: 20x + 50y.
subject to:
80x + 90y <= 100;
0 <= x <= 1;
0 <= y <= 1;

这个问题就能够使用我们的软件求出最佳解。按照我们软件输入文件的要求,上述问题可列为下面的输入文件格式:

maximize: 20x0 + 50x1;
subject to
upper bound for all: 1;
lower bound for all: 0;
C1: 80x0 + 90x1 <= 100;
end


我们将其存为文件 XiJinpingDumpling.txt. 用我们的软件给出的最佳方案是:

Optimal Objective (包子最大产出量): 52.25;

x0 = 0.125;
x1 = 1;

换成原先的变量就是:
x = 0.125;
y = 1;

这也就是说,习近平若想得到最大生产效率,应该是让习近平花12.5% 的时间来包包子,剩下的 87.5% 的时间去擀包子皮。而彭丽媛用全部时间去包包子。这是最佳方案。这个最佳方案能够使得习近平夫妇在一个小时里能够包出52.25 个包子。任何其它方案都不会比这个方案更好,或者包出的包子数量少,或者是出现包子皮过剩或短缺。

我们这里只是以习近平包包子为例,来说明如何优化投入产出。同样的,现实生活中的很多问题都可化为优化问题。比如说,习近平应该如何管理他的几个常委,应该如何安排这些常委的日常工作,甚至是如何管理这个国家,都能够化成优化问题,并用我们的软件求得最佳方案。

 跟帖:返回共舞台首页 

沒有留言: