单期投资组合选择问题的情景生成

最后，在第3.3.3节中，我们简要讨论了成员资格测试的计算问题。3.3.1可行区域的圆锥壳在投资组合问题中，可行区域通常由线性约束定义，即X={X∈ Rd:Ax≤ b} ，A∈ Rm×D b∈ Rm。也就是说，可行区域是有限个半空间的交点。众所周知，任何这样的交点都可以写成有限个点加上更多点的圆锥组合的凸包（例如参见[Zie08]中的定理1.2）。也就是说，存在x，xk∈ Rdy，伊尔∈ rdx={kXi=1λixi+lXj=1νjyj:λ，ν≥ 0，kXi=1λi=1}。（8） 该区域的圆锥壳是以下完整生成的圆锥：圆锥（X）={kXi=1λixi+lXj=1νjyj:λ，ν≥ 0}.为了用形式（8）表示半空间的交集，我们可以使用Chernikova算法（alsoknown作为双重描述方法）[Che65，LV92]。每个完整生成的圆锥体也可以写成多面体圆锥体，即{x形式∈ Rd:Dx≥ 0}，反之亦然（见[Zie08，第1章]）。Chernikova的算法再次提供了一种具体的方法，可以在这两种不同的表达之间进行转换。虽然这两种表述在数学上是等价的，正如我们将看到的，但它们在算法上是不同的。我们假设投资组合选择问题的约束条件有以下形式：X=十、∈ Rd:Tx=caTix≤ 如果i=1，m、 x≥ 0,（9） 其中1是1的列向量，c>0。这些限制中的第一个具体说明了要投资的资本总额，这些不平等代表了其他限制，如对特定公司或行业的投资额度。在这种情况下，我们可以立即将圆锥壳描述为多面体圆锥体。提案3.7。设X为（9）中定义的集合，letY=（X∈ 注册护士：bic1- 人工智能德克萨斯州≥ 0表示i=1。

，m，x≥ 0）然后是二次曲线（X）=Y。假设X是凸的，为了证明圆锥曲线（X）=Y，必须证明X是凸的∈ Y\\{0}<==>  λ>0使得λx∈ X.我们首先展示了远期含义。假设x∈ Y\\{0}。那么，假设x>0，我们必须有v:=1Tx>0。然后，设置λ=cv，我们有（λx）=vcv=c。因为Y是一个圆锥体，所以我们有λx∈ Y、 因此（bic1- ai）Tcvx≥ 0∴cvaTix≤BiCvTx |{z}=v∴ aTi（cvx）≤ biand soλx∈ 二次曲线（X）。现在我们来证明这个倒转的含义。假设x∈ 圆锥曲线（X）\\{0}。那么就存在λ>0这样的λx∈ 十、 这是λX=caTiλX≤ 因此，aTiλxTλx≤等等bic1- 人工智能德克萨斯州≥ 0.x∈ 根据需要进行检查。X2x1图2：给定x+x=1和x，x的简单配额约束的圆锥壳≥ 0图2显示了在总投资和正性约束条件下，简单约束如何影响可行区域的圆锥壳。3.3.2投影到完全生成的圆锥上首先，假设我们可以表示可行区域X的圆锥壳 Rd是一个具有k个生成器的完全生成的圆锥体，即k={Ay:y≥ 0}其中∈ Rk×d.定义为apoint x的投影∈ 通过求解以下二次规划，可以找到Rd：≥好的-特别是xk（10），如果y*是最优解，那么pK（x）=Ay*. 通过建立该问题的KKT条件[BV04，第5章]，可以看出该问题等价于求解以下线性互补问题（LCP）：求y，z∈ 就这样- 阿泰=-ATxzTy=0y，z>0。如果（y，z）是上述问题的解决方案，那么所需的投影为pK（x）=Ay。LCP可以通过比标准二次规划（如Lemke算法[CPS92]）更专业的算法来解决。现在，假设我们有一个圆锥壳的多面体特征，这是一个圆锥形式：K={x∈ Rd:Bx≥ 0}.

（11） 点x的投影∈ （11）中多面体圆锥体上的Rd是以下二次规划的解：minimizexkx- XK受Bx约束≥ 0.虽然（10）中的前一个问题通常可以使用专门的算法更有效地解决，但在实践中我们将使用这两种方法。对于带有少量极值射线的圆锥壳，例如K=Rd+，我们将使用前一种方法。随着我们对问题增加更多的约束，我们从经验中发现，极端光线的数量可以呈指数增长，这对于前一种方法会导致麻烦的大型LCP问题。在这种情况下，我们将使用多面体表示法进行投影。3.3.3计算问题鉴于测试风险区域的成员资格（对于椭圆分布回报）涉及求解一个小型LCP或二次规划，使用这种方法可能会增加计算成本，尤其是在用于构建高维问题的大型场景集时。然而，这个问题可以通过几种方式缓解。首先，一个点的隶属度测试可以独立于另一个点的隶属度测试进行，这意味着大量点的隶属度测试自然是可并行的。其次，对于案例K Rd+损失函数y 7→ -xTy是单调的。因此，如果我们有一组点y，在风险区域中，我们知道，如果某个点被这些点中的任何一个控制，那么它也在风险区域中。如果y在非风险区域，测试也存在类似的缺点。最后，通过直接测试条件kpK（y）k，成员资格测试也可以变得更有效≤ α，不计算完整投影pK（y）。例如，用于计算投影的二次规划只能精确到足以测试该条件的程度。

这可以通过二次规划求解器中的回调函数轻松实现。4情景生成在本节中，我们将展示如何利用风险区域生成情景。第4.1节我们介绍了两种具体的方法，它们基本上是通过优先考虑风险区域的场景建设来工作的。在第4.2节中，我们在SAAmethod[KSHdM01]的基础上提出了一种新的启发式算法。该启发式算法通过向问题中添加艺术约束，提高了拟议采样算法的性能。4.1聚集采样和还原[FTW17]我们提出了两种利用风险区域的方法。其中第一个允许用户提前指定场景的最终数量。该算法称为聚合采样，采样场景，聚合非风险区域中的所有样本，并将所有样本保留在风险区域中，直到我们获得所需的风险场景数，即风险区域中所需的场景数。算法1对此进行了描述。设q=PY∈ RcY，X是非风险区域的概率，n是所需风险场景的数量。定义N（N）为聚合采样的有效样本量，即算法终止前的绘图数量。数量N（N）是一个随机变量：N（N）~ n+NB（n，q），其中NB（n，q）表示负二项随机变量。回想一下，负二项随机变量NB（n，q）是伯努利试验序列中的失败次数，成功概率q，直到出现n次成功。因此，聚集抽样的预期有效样本量如下：e[N（N）]=N+nq1- q预期有效样本量可被视为基本抽样所需的样本量，以在风险区域产生相同数量的情景。

预期风险情景数量和预期有效样本量之间的差异与比率1成正比-q、 特别是，随着非风险区域的可能性接近1，这种收益趋于一致。与聚合抽样相反的是，对一组给定大小的n进行抽样，然后聚合基础分布的风险区域中的所有场景。我们称之为聚合还原。这可以被视为n个伯努利试验的序列，其中成功和失败的定义方式与简单说明相同，我们计算算法的while循环以nRc=0终止，而以概率qninput:R终止的事件 Rdapproximate risk region，NR所需风险场景的数量输出：{（ys，ps）}NR+1s=1scenario setnRc← 0，nR← 0，yRc=0；而nR<NRdoSample新点y；如果∈ R thennR← nR+1；ynR← Y恩德尔森尔克← nRc+1；yRc←nRc+1（nRcyRc+y）endendforeach i在1，NRdo pi←（nRc+NR）；如果nRc>0，则PNRC+1←nRcnRc+NR；新点y；nRc← 1.yNR+1← YendpNR+1←nRcnRc+NRC算法1：如上所述的聚合采样。缩减样本中的场景数R（n）如下所示：R（n）~ N- B（n，q）+1其中B（n，q）表示二项随机变量。因此，AggregationReduce中场景的预期减少量为nq- 1.聚集采样和聚集减少之所以有效，是因为对于大样本，它们相当于从聚集的随机向量中进行采样。假设Y，Y。是一个独立同分布（i.i.d.）随机向量序列，其分布与Y相同，然后是ψR（Y），ψR（Y）。是一个i.i.d.随机向量序列，其分布与聚合随机向量ψR（Y）相同。用∧ρn，β（x）表示决策x的尾部风险度量值∈ 对于样本ψR（Y）。

，ψR（Yn），并通过^ρn，β表示通过聚集采样构造的情景集的类似函数。根据[FTW17]对投资组合选择问题的修改，以下结果给出了聚集抽样渐近有效的精确条件。定理4.1。假设以下条件成立：（i）对于每个x∈ 十、 fx在F的某个邻域严格递增且连续-1x（β）（ii）E[Y | Y∈ [Rc]∈ int（RcX）（iii）X是紧凑的。然后，概率为1，对于足够大的nρn，β≡ ρN（N），β。有关这些算法一致性的完整证明，请参见[FTW17，第4节]。4.2 Ghost Constraints我们在上文中指出，随着非风险区域概率的增加，我们的方法的性能会提高。特别是，随着非风险区域概率的增加，聚集抽样中的预期有效样本量增加。现在，根据定义（2），非风险区域随着问题变得更加受限而增长。这表明，为我们的问题添加约束可能会有所帮助，因为约束会缩小可行投资组合的集合，但这些投资组合本身并不活跃，从某种意义上说，它们的存在不会影响最优解决方案的集合。我们将把添加到问题中以提高方法性能的约束称为重影约束。寻找非活动约束来添加到我们的问题中是非常重要的，因为它依赖于最优解集的一些知识。此外，对于随机程序，即使验证某个特定约束是否有效，通常也很困难。对于凸且所有约束均为凸（且最优解唯一）的确定性目标函数，约束{x:g（x）≤ 0}是活动的当且仅当它在最优解x处绑定时*, 这就是g（x）*) = 0

对于一个随机规划，我们通常是在解决一个基于情景的近似，因此一个对基于情景的近似没有约束力的约束可能对真实问题有约束力，反之亦然。在上述意义上，对重影约束是否处于活动状态的严格测试超出了本文的范围。我们只是在这里推广这样一种观点，即鬼约束可能是找到更好解决方案的有用方法。我们求助于启发式规则来选择幽灵约束。例如，我们可以将一组可用的投资组合限制在高质量解决方案的某个邻域内。这建议了一个迭代过程，即使用聚合采样对场景集进行采样，解决由此产生的问题，调整问题约束，然后重新采样。在算法2中，我们在[KSHdM01]的样本平均近似（SAA）方法的基础上提出了这样一种启发式程序。我们将此过程称为带重影约束的SAA方法。与原始SAA方法一样，该算法以非常通用的形式呈现，因为更新规则（例如每次迭代中如何调整边界）可以以多种不同的方式实现。在第7节中，我们将在一个现实且困难的问题上测试该算法。初始化li=-∞, 用户界面=∞ 对于每个i=1，DdoAdd约束≤ 十、≤ u.解决问题；为问题构造风险区域R；对于i=1。

，M d使用风险区域R的聚集抽样生成大小为N的样本；用目标值νmn和最优解^xmN求解相应问题；估计解的最优性差和最优性差的方差；增加N的大小；调整l和u的界限；直到最优性差距和方差对于某些m足够小；使用筛选和选择程序，从xmn产生的所有候选溶液中选择最佳溶液^x。算法2：带ghost约束的样本平均近似法5非风险区域的概率聚合采样和减少的好处取决于非风险区域的概率。正如[FTW17]中所观察到的，非风险区域的概率随着问题维度的增加而降低，但随着我们收紧问题约束，以及随着我们增加β，尾部风险度量的水平而增加。在本节中，我们对这种可能性如何随尾部的重量以及分布的相关性而变化进行了一些经验观察。第一个观察结果是，在存在正性约束的情况下，非风险区域的概率随着随机变量之间相关性的增加而增加。这可以在图3中看到，图3将风险区域的概率绘制为一些二维分布的相关函数。对这种行为的一个直观解释是，在正相关的情况下，各个投资组合的风险区域有更多的重叠。在更高的维度中，概率随相关性变化的程度似乎要大得多。1.0.5 0.0 0.5 1.0相关性。820.840.860.880.900.920.940.96非风险区域的概率2。0t3。0t5。图3：相关性与。

一些二维椭圆分布、正约束和β=0.95的非风险区域概率在图4中，我们绘制了正态收益和一系列维度的非风险区域概率图，特定类型的相关矩阵的非风险区域概率为∧（ρ）∈ Rd×dwhere∧（ρ）ij=ρ，i6=j，ρ>0。在ρ=0的情况下，随着维数的增加，概率迅速衰减为零，而当ρ接近1时，所有维数的非风险区域概率都接近β。我们的下一个观察结果是，非风险区域的概率似乎随着分布的尾部变得更重而增加。在图5中，绘制了一些球形分布和一系列维度的风险区域概率。请注意，多变量t分布的尾部比多变量正态分布更重，但随着自由度参数的增加，尾部会变轻。这种现象也可以在图3中观察到。本节中的观察结果表明，当应用于实际股票数据时，我们的方法将特别有效，并且往往是正相关的，并且具有严重的尾部。6数值测试在本节中，我们将测试我们的方法在实际分布中的数值性能。这些测试分为三个部分：一系列分布和约束条件下非风险区域概率的计算、聚合抽样的性能以及聚合减少的性能。为了使我们能够测量所提出的方法产生的解的质量，大多数测试是针对没有整数变量的问题上的椭圆分布进行的。这些问题可以用其他方法精确地解决。

在第6.1节中，我们描述了我们的实验设置，特别是我们证明了为这些实验构建的分布。剩下的三部分详细介绍了各自的实验及其结果。6.1实验设置为了稳健性，我们将对每个分布族和我们正在测试的每个维度使用几个随机构造的分布。我们通过将参数分布拟合到真实数据来构建这些模型。We0。0.2 0.4 0.6 0.8 1.0相关性0。00.20.40.60.81.0非风险区域的概率=0.99Dim=5Dim=10Dim=20Dim=30图4：一系列相关矩阵的非风险区域概率和正态回归的维度使用真实数据，而不是任意生成的问题参数，原因有二。首先，生成与定义良好的分布相对应的参数可能会有问题。例如，对于矩匹配算法，可能不存在具有给定目标矩集的分布（例如参见[KME00]和[JR51]）。其次，正如在第5节中所观察到的，无风险区域的概率可能会有很大差异，因此测试我们的方法对分布的性能是最有意义的，这对于投资组合选择问题来说是现实的。我们根据FTSE 100指数中90家公司2007年1月至2015年2月的月度回报数据构建分布。对于测试中的每一个维度，我们随机抽取了五组这样规模的公司，每一组都符合正态分布、t分布和相关回报数据的倾斜分布。图6显示了两支股票的投资密度函数与历史回报数据的叠加曲线。对于t分布，我们将自由度参数固定为4.0。这样我们就可以更容易地比较较重的尾巴对测试结果的影响。