英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料

---

《数学与应用数学》专业

摘要: 本文提出一种基于枢轴的凸二次规划求解方法，并说明如何将其与参数技术结合起来，求解均值-方差组合选择问题

关键词: 凸二次规划，均值-方差组合选择模型，枢轴算法

1.介绍

求解凸二次规划(QP)有多种算法。最著名的是活动集方法，然而，由于这种方法的操作方式，很多人很难学习。本文提出了一种计算效率高、理解简捷的基于枢轴的凸QP求解方法。

QP的Karush-Kuhn-Tucker条件(KKT条件)是一个等式系统，其中除了互补条件外，所有的表达式都是线性等式或不等式。与Wolfe方法一样，我们在保持计算过程中的互补性条件的同时，通过一种旋转操作来求解线性部分。然而，由于KKT条件中删除了许多变量，用我们的方法计算的系统的大小要小得多。

1952年Harry Markowitz发表了具有里程碑意义的论文《投资组合选择》，其中投资组合选择问题被表述为具有非负变量的凸二次规划。已经快60年了。然而，大多数人仍然认为模型难以求解，很少有人通过计算有效投资组合来进行投资活动，以供参考。我们看到，每一本投资教科书都有一个图表来显示由两种相关系数不同的资产组成的投资组合。但是我们几乎看不到一本书有一个例子来展示三个人组成的投资组合在没有卖空的情况下，可以有更多的资产。我们将提出一个基于枢轴的算法和一个参数技术，以非常简单的形式解决马科维茨的投资组合选择模型。我们的参数技术最重要的优点是，通过旋转算法建立投资组合后，可以在线性时间内连续地获得不同收益水平下风险最小的投资组合。

本文其余部分组织如下。在第二节中，我们将介绍一个求解线性不等式系统的基于枢轴的算法，以及生成与不同右侧项相关的新基本解的参数技术。在第三节中，我们将介绍解决凸QP的基本概念和操作。在第四节中，我们将讨论如何求解马科维茨的均值-方差组合选择模型。为了简洁起见，省略了相关的定理和证明以及冗长的推理过程。具体请参考。

2.线性不等式系统

考虑一个线性不等式系统，其形式如下:

（2.1）

这里，和是一个标量，

算法中，以下概念是被使用的。一个极大线性无关向量的集合称为(2.1)的基。在基中的向量称为基向量，否则称为非基向量。与基向量相关的等式和不等式称为基本等式,非基本不等式。基本等式体系称为基本体系，其解集称为基本锥。对应于基本(内)等式的方程组的解，即基本锥的顶点，称为基本解。

几何上，我们的算法从一个基本锥开始,其顶点用表示。如果位于由每个不等式决定的超平面上，且位于由(2.1)的每个不等式所决定的半空间中，则它是整个系统的一个解。否则就存在一个不相等(或相等)，例如，因此被称为一个违反的不等式。如果半空间交点和基本锥是空的，则(2.1)没有解。否则投影到半空间的边界，其中取代一个基本不等式，构成一个新的基本锥。然后重复同样的过程。

从代数上讲，用一个非基本等式代替一个基本不等式可以通过以下的旋转操作来完成。

给定(2.1)的一组基，令，，和 分别为基本等式、基本不等式、非基本不等式和非基本等式的指标集。让成为基本的解决方案，即，。假设

（2.2）

如果为和，由(2.2)的第r个表达式得到

（2.3）

将其代入(2.2)的其他表达式中，得到

（2.4）

现在，我们有一个新的基本锥，其指标集是，相关的基本解表示为 (2.4)的右边乘以，即

（2.2）两边同时乘以，有

因此

把上面的表达式重写为

并且使，，

有

同样地，从(2.3)我们得到

或者

其中

上述操作过程称为旋转(操作)，称为主元(元素)。的行称为主行，列称为主列。我们说一个进入和一个离开，这两个向量的交换用定义。这个过程如表1和表2所示。

其中

对于表1, 叫做的偏差或者与相关的等式。如果

那么是系统(2.1)的解决方案。如果对于有些，被称为违背了不等式和到的距离

表1.最初的表。

	表2。旋转的结果。

线性不等式系统的计算步骤如下:

算法2.1.系统(2.1)的旋转算法。

步骤1.构造初始表。

如果(2.1)有一个形式为的不等式, 为初基本不等式;否则将代入(2.1)使是初始基本不等式，其中M是一个足够大的数，称为人工不等式，其系数向量称为人工向量。初始基本解是，其中或。初始的基本向量是n阶单位矩阵的第i行，。(2.1)的其他等式及其系数向量是非基本的，其相对于的偏差是。因此，我们有一个初始表，如表1所示。

步骤2.预处理。

让为等式的指标集，即, .。

1).如果，执行步骤3。否则，对于,如果的偏差是负的，正的或零，否则分别到2)，3)和4)。

2).如果的行中没有正元素,即对应于基本不等式(2.1)没有解;否则对其中一个正元素进行枢轴旋转，让并返回到1)。

3).如果的行中没有负元素,即对应于基本不等式(2.1)没有解;否则对其中一个负元素进行枢轴旋转，让并返回到1)。

4).如果的行中所有的元素使对应于基本不等式值为0，让并返回1);否则对其中一个非零元素进行枢轴旋转，令并返回1)。

步骤3.主要的迭代。

1).如果所有非基向量的偏差都是非负的，则当前的基解为(2.1)的解。

2).选择一个负偏差的非基向量进入基。如果基本不等式对应的输入向量的行中没有正元素，则(2.1)无解，否则对其中一个正元素进行枢轴旋转，返回1)。

注意，算法2.1的步骤1只是构造初始表的简化语句。事实上，如果(2.1)没有不等式但有对于有限集，可以作为初始基本不等式而不需要引入。

从算法2.1的步骤2和步骤3，我们可以看到基本等式永远不会离开基本系统。因为如果(2.1)有一个解，它必须满足所有等式。因此,一旦非基本等式进入基本系统，相应的列就可以消除。

有时，不等式系统中的不等式以的形式存在，尤其是，它的正式写法是和在我们的方法中。设是基本解，然后和的偏差为别为和，它们的和为。因为和是线性相关的，它们不能同时是基本的，如果其中一个是基本的，另一个的偏差是，因此可以忽略。如果和都是非基本的，它们可以在表中共享一行，因为和的表达式的系数基本向量的符号是相反的。

需要指出的是，即使基本的解没有明确地列在表中，它也可以很容易地从表中得到。设是基本解，得到如下。如果或者是基本的，或;否则等于这个不等式的偏差加上或。或者如果是基本的, ;否则等于减去的偏差。

选择向量进入或离开基有很多规则。我们将给出几个主要迭代阶段使用的方法。

对于给定的(2.1)基，令，和分别为基本等式、基本不等式和非基本不等式的指标集。让是当前的基本解决方案和

规则1.(最小偏差规则).在所有偏差为负的非基本向量中，选择向量有最小的偏差进入基。那就是如果，然后是进入的基。

规则2.(最大距离规则)。在所有偏差为负的非基本向量中，选择向量它的相关不等式离当前的基本解最远进入基。也就是说如果，然后是进入的基。

规则3.(沿边缘的最远距离规则)。在所有偏差为负的非基本向量中，选择向量它的相关不等式离当前基本解边缘最远进入基。也就是说如果，然后是进入的基。

规则4.(最小指标规则)。在所有偏差为负的非基本向量中，选择向量有进入基的最小指标;在所有离开基的基本向量中，选择向量有最小的离开基的指标。也就是说如果，然后进入基;如果，则离开基。

与Bland的反循环规则[9]一样，可以证明当使用最小指标规则求解(2.1)系统时，不会发生循环。

现在让我们考虑参数技术，通过改变一些基本等式的右边项，可以从当前表中得到一个新的基本解。

对于(2.1)的一个基，令和分别表示基本向量和非基本向量的指标集，为基本解。假设

两边同时乘以，因为，有

因此非基的偏差为

如果改为，的偏差就变成了

（2.5）

以上操作用表示。

通常我们只改变一个基本等式的右边，比如改变为对。那么的偏移就变成了

（2.6）

表明当一个基等式的右边增加了时,非基向量相对于新基解的偏差可以通过这个基的列乘以,然后将其添加到最后一列(偏差列)。

我们将使用来表示这样一个运算结果(2.6)。

3.凸二次规划

3.1基本概念和算法

考虑二次规划的形式：

（3.1）

其中，为半正定，，，和是实数。

让是与或相关的拉格朗日乘子，为与相关的拉格朗日乘子，为n阶单位矩阵的第i行。则(3.1)的KKT条件如下

因为

消除上述KKT条件下所有的，有

（3.2）

我们将通过算法2.1解决线性部分（3.2）的同时保持所有的互补条件。（3.2）有n m个变量，其中是自由的。为了开始计算，我们引入不等式

带入（3.2），等式（3.2）前n m个变量系数为

最后n m个不等式的系数用向量表示，也就是n m阶单位矩阵的第i行，。

在系统（3.2）：

被称为互补不等式，它们的系数向量被称为互补向量。

叫做拉格朗日向量。

称为约束向量，相关的不等式分别称为拉格朗日不等式和约束等式。

根据线性不等式系统基本解的定义，如果其中一个互补不等式是基本的，则满足相应的互补条件。因此，在计算过程中

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[266312]，资料为PDF文档或Word文档，PDF文档可免费转换为Word