编者按：马科维茨投资组合模型是一类很早期的二次规划模型，并在金融与优化等领域广泛为人所知。你知道早期的二次规划是怎么求解的吗？你是否知道马科维茨本人也提出过一类求解二次规划的临界线算法呢？
二次规划是非线性规划中的一类特殊的数学规划问题，在很多领域都有广泛的应用，例如投资组合、约束最小二乘问题的求解、序列二次规划在非线性优化问题中应用等。在过去的几十年里，二次规划已经广泛出现在运筹学、经济数学、管理科学、系统分析和组合优化学科中。二次规划（Quadratic Programming）这个名称的出现最早应该是在Robert Dorfman 的博士论文中（Dorfman （1951）），随后关于二次规划的理论与算法有了更加深入广泛的研究。
谈到二次规划，很多人都会提到一个典型的应用--投资组合，投资组合一个最重要的模型是均值方差模型，这个模型是1952年美国学者马科维茨提出的。
那么有多少人真的读过马科维茨1952发表的文章呢？有多少人知道马科维茨曾经也提出过一个求解二次规划的临界线算法Critical Line Algorithm (CLA) 呢？ 又有多少人知道CLA与沃尔夫的单纯形算法是等价的呢？
马科维茨在《Jounal of Finance》上发表了一篇划时代的文章，题目是“Portfolio Selection”，主张以收益率的方差作为风险的度量，并提出极小化风险为目标的资产组合选择模型，称为均值方差模型，这是一个凸二次规划。当时很多人认为此模型计算量很大，至少比同等规模的线性规划困难。 为了减少运算量，有的学者利用因子模型构造一个近似协方差矩阵进行计算（比如Sharpe的资本资产定价模CAPM）, 有的用线性变换产生一个二次项较少的目标函数，有的则干脆修改风险的定义，使用线性规划模型（比如用绝对偏差代替方差来度量风险）。
但非常有意思的是，马科维茨(1956) 设计的用于解决这类问题的二次规划算法--临界线算法(CLA)--在50多年后在数学规划文献中几乎没有得到关注。
正如威廉·夏普在马科维茨2000年版的《投资组合选择与资本市场的均值-方差分析》一书的前言中简洁地描述了当前的情况，他说:“马科维茨的投资组合模型受到了很多学者的广泛应用，但是很少有人阅读(至少是完全阅读) 他的工作。在他的这本书中，他说出了他的担忧，许多对这类问题感兴趣的学者显然从未发现他在书后面对基本原理的讨论”。(“Markowitz’s early works have suffered the fate of those of other pioneers: often cited, less often read (at least completely). Indeed, in this book he evidences his concern that “many scholars interested in such matters apparently never found [the discussion of fundamentals in the back of the 1959 book.]”)
也许第一个引用马科维茨二次规划论文的人是Philip Wolfe，他在关于二次规划的单纯形方法(Wolfe)的论文（Wolfe （1959））中写道:
“Markowitz...has suggested a method...for solving the ‘portfolio’ problem...The method described here exploits this ingenious idea, differing from the proposal of Markowitz (1956) in keeping to a linear programming format.”
在Guus Zoutendijk 的博士论文(Zoutendijk (1960)) “可行方向法”中，引用马科维茨的算法（Markowitz （1956）），认为它是属于“一些著名的二次规划方法”。随后Zoutendijk讨论了Beale, Frank and Wolfe和 Wolfe的工作，但没有讨论马科维茨的工作。后来，George Dantzig发表了一份技术报告（Dantzig（1961）），名称为：二次规划：沃尔夫-马科维茨算法的一个变种。承认了马科维茨的工作。但我想大多数人并没有真正的去读过马科维茨的CLA算法，在二次规划的早期历史中也很少有人提及过这个工作。
马科维茨的临界线算法与其他参数二次规划算法，特别是沃尔夫的单纯形法是等价的吗？关于算法等价性的研究，可以参考相关论文Best（1984）、Cottle和Djang（1979）、Goldfarb（1972）和Pang（1981）。Djang（1979）博士论文是本研究课题的重要来源。正如这些文章所揭示的，这个等价概念的本质是，如果两个迭代算法（给定相同的输入）生成相同的迭代序列，那么它们是等价的。需要补充的是，两个等效迭代算法不仅在解存在时以相同的解终止，而且在解不存在时提供一个明确的指示。
综上，在二次规划的形成年代， 马科维茨的临界线算法并没有引起广泛关注。然而，阅读马尔科维茨算法的原始版本（以及Barankin和Dorfman（1955年）、Barankin和Dorfman（1956年）、Barankin和Dorfman（1958年）的研究，确实激励了Philip Wolfe提出了二次规划的单纯形方法。他在文章提及（Wolfe（2008））：“如果没有Markowitz的论文，我关于二次规划单纯形方法的论文就不会被写出来。” Wolfe提出了一种算法，虽然在适当的问题上相当于Markowitz的算法，但在一般意义上，它确实吸引了很多对数学规划感兴趣的研究者。其中一个就是George Dantzig，他提出了“Wolfe-Markowitz算法的变体”，即Dantzig的算法（Dantzig（1961），Dantzig（1963））。
参考文献
[1] R. DORFMAN (1951). Application of Linear Programming to the Theory of the Firm. University of California Press, Berkeley.
[2] H. MARKOWITZ (1952). Portfolio selection, The Journal of Finance 7, 77–91.
[3] H. MARKOWITZ (1956). The optimization of a quadratic function subject to linear constraints. Naval Research Logistics Quarterly 3, 111–133.
[4] P. WOLFE (1959). The simplex method for quadratic programming, Econometrica 27, 382–398.
[5] G. ZOUTENDIJK (1960). Methods of Feasible Directions. Van Nostrand, New York.
[6] G.B. DANTZIG (1961). Quadratic programming: A variant of the Wolfe-Markowitz algorithms, Research Report 2, Operations Research Center, University of California, Berkeley.
[7] M.J. BEST (1984). Equivalence of some quadratic programming algorithms, Mathematical Programming 30, 71–87.
[8] R.W. COTTLE AND A. DJANG (1979). Algorithmic equivalence in quadratic programming I: A least-distance programming problem, Journal of Optimization Theory and Applications 28, 275–301.
[9] D. GOLDFARB (1972). Extensions of Newton’s method and simplex methods for quadratic programs, in (F.A. Lootsma, ed.) Numerical Methods for Numerical Optimization. Academic Press, New York, pp. 239–254.
[10] J-S. PANG (1981). An equivalence between two algorithms for quadratic programming, Mathematical Programming 20, 152–165.
[11] A. DJANG (1979). Algorithmic Equivalence in Quadratic Programming. PhD thesis, Department of Operations Research, Stanford University, Stanford, Calif.
[12] E.W. BARANKIN AND R. DORFMAN(1955). Toward quadratic programming, Report to the Logistics Branch, Office of Naval Research.
[13] E.W. BARANKIN AND R. DORFMAN (1956). A method for quadratic programming, Econometrica 24, 340.
[14] E. W. BARANKIN AND R. DORFMAN(1958). On quadratic programming, University of California Publications in Statistics 2:13, University of California Press, Berkeley, pp. 285–318.
[15] P. WOLFE (2008). Private communication.
[16] G.B. DANTZIG (1963). Linear Programming and Extensions. Princeton University Press, Princeton, N.J.
本文由西安交大金融优化组 徐凤敏 供稿
赌博平台
2019年3月12日
