我刚刚发表的数学论文："T-递进法：线性和非线性规划的解析解"

原文网址：http://jasmine-action.blogspot.com/2014/03/t.html

我曾经贴出我的一篇数学论文的摘要。现在，该论文已经发表在“American Journal of Algorithm Research"。 见链接：

T-Forward Method: A Closed-Form Solution and Strongly Polynomial Time Approach for Convex Nonlinear Programming

http://article.sapub.org/pdf/10.5923.j.algorithms.20140301.01.pdf

下面的链接是我过去曾经发表过的一篇被引用数百次的论文：

A*Prune: An Algorithm for Finding K Shortest Paths Subject to Multiple Constraints
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.20.8011&rep=rep1&type=pdf

SPIDER: A Simple and Flexible Tool for Design and Provisioning of Protected Lightpaths in Optical Networks
http://cm.bell-labs.com/who/drew/pub/bltj-spider.pdf


我的这篇论文是用初中几何方法解决当今数学尖端难题。

看懂这篇论文主要要看懂下面几个公式


1. 公式（67）算出限制条件的根，这些根的最小值给出边界点。

2. 将上面算出的根代入到公式（46）或（47）中算出配分函数Phi。

3. 将上面的结果代入到公式（41）中算出边界点，再带入到公式（43）中算出法线方向。

4. 用公式（53）算出T递进方向。

5. 用公式（54）算出T递进出发点。

6. 将上面的结果代入到公式（56）中算出T-递进点。

7. 重复上面的计算K次，直到无路可走，即新的递进点同前一轮递进点相同时，就给出了最佳解。对于N<10000的线性规划问题来说，K=10通常就给出最佳解。

也就是说，公式（58）是解析解的最终表达式。但这里需要通过上面列出的几个公式算出一些参数。


这里有许多数学专家，比如平正教授，还有那位看好戏网友，樊公教授，等等。欢迎大家对我的这篇论文拍砖。

我还有四篇类似的论文将在近期内发表，这包括：

A Closed Form Solution for Convex Quadratic Programming.

A New Approach for Integer Programming.

Mathematic Formulation for Supply Function.

A New Model and Optimal Solution for Labor Assignment.


有人问我这种论文有什么用处？又有多大价值？我就不妨在这里简要回答一下。

首先，当年苏联将此线性规划解法冷冻8年，这足以说明线性规划问题在军事上的价值。其在军事上的价值，不亚于电报电讯及莫尔斯密码。

线性规划和非线性规划所解决的问题是最大值和最小值问题。它广泛应用于资源优化配置，利润产出最大化，投入支出最小化。所以，只要有投入产出的地方，有资源配置的地方，都可以应用线性规划和非线性规划，进行资源合理配置，使得利润最大化。可以说，各行各业，只要有人类生产的地方，线性和非线性规划就有不可估量的价值和作用。

我以前曾经发过一篇关于包饺子的例子，以及习近平包包子的例子，这些都是线性规划的简单应用。

那么，我所发明的新方法，对比现存的方法又有什么新的价值吗？我的方法新就新在其收敛速度。现有方法的最快速度是N的5次方。我的方法提高到N平方。很多人对这些问题没有什么概念，那我就举例说明一下。

线性规划所要解决的问题大多都含有很多个变量和限制条件，成千上万个变量数那是非常普通的。有时要上百万。假如我们用当前运算最快的电脑（CPU)，1GHz，就是说每秒钟能运算10的九次方，假设我们要解决一个有10，000个变数的线性规划问题。那么用当前最快的算法内点算法来求解这个问题，那就需要计算10000^5.5*ln(10000)*ln(ln(10000))=10^29，所需的计算机运算时间是：

10^(20-9)秒=10^20秒 = 6百万年

但是，如果使用我的新方法来计算，所需的计算机运算时间是：

10000^2*ln(10000) / 10^9 秒 = 1 秒！

目前，能够进行这种大规模（large scale）线性规划计算的必须通过几个著名公司生产的运算系统，那需要有大量的高速计算机在同时进行计算。生产这种运算系统最著名的是IBM的CPLEX，其它类似的运算系统（solver）还有CBC, FortMP, Gurobi, MINOS, IPOPT, SNOPT and KNITRO.等等等等。这些运算系统使用起来极其复杂，而且昂贵。如果你要求解一个大规模的线性规划问题，你首先要使用某种数学模型语言，比如AMPL。AMPL是我在贝尔实验室的同事David Gay 和 Brian Kernighan发明的。后者还是C语言和unix的发明者之一。使用AMPL不是免费的，你需要交使用license费。然后，你要将这个程序再送到一个solver如CPLEX去进行计算，使用CPLEX的费用就更高了。然后，你就回去睡觉，耐心等待，你根本就不知道这CPLEX何时能给你将结果反馈回来，少则几天，多则猴年马月。在这等待过程中，那是何等的折磨和煎熬。

因此，你要解决一个大规模线性规划问题，你首先应该是一个数学家，然后还应该是一个软件专家，你知道应该选用哪种语言来写出你的方程。你还要知道哪个solver能够解决你的问题。如果你是第一次使用这些软件，我保证你应该花上几个月的时间去掌握这些，然后，你还要去花钱购买这些需要的license。再去在你的电脑上去安装这些需要的连接软件。很多人和公司是不会花这么大功夫去求解他们的优化问题的。大多数公司都将他们的优化问题送给那些专业的公司去处理他们的优化问题。这是IBM目前赚钱的一个重要渠道之一。

如果使用我给出的方法，目前CPLEX要花几千年能够解出的问题，只需要几秒钟就能解决！那些含有百万千万变数的线性规划问题，是目前任何solver都无法解决的。但用我的新算法，也能用一台电脑在数小时内加以解决。


有了我的这个算法，许多原本无法解决的优化问题，现在都能够在一个微电脑上加以解决。那些原本要花上几年才能求解的问题，现在用几秒钟就能解决。而且不必送到那些大型电脑及联网电脑（grid）上去计算，在当地电脑就能求解。

可以说，如果我的新算法是正确的，那么，必将引发一场革命，这不仅是学术上的，而且是工业上的革命。