第九章锥优化

第九章锥优化基础知识姓名：毕军龙学号：213010279.1锥一个集合称为一个锥，如果它在正标量乘法下封闭。即，一个集合C是一个锥若它满足：如果xC，则xC对所有的0都成立。若一个锥不含有任何线，则称它是一个点锥。9.2介绍本章和下一章中，我们针对锥优化问题及其在金融中的应用。锥优化指的是可行域由一组线性等式和锥成员确定的集合的最小化或最大化的问题。锥的定义和知识在附录B中。虽然锥不如线性优化和二次优化一样为我们熟知，但由于它们的广泛的实用性和适用性，锥优化问题变得越来越重要。回忆第一章中锥优化问题的标准形式的定义minTxcxAxbxC(9.1)这里C表示有限维向量空间X中的一个闭凸锥。若nXIR并且nCIR，这个问题是线性优化问题的标准形式。因此，锥优化是线性优化的推广。事实上，它比线性规划更具一般性，因为在这些问题的表示中可以用非多面体锥从而变成目标函数和约束条件都是非线性凸函数的特殊的优化类型。特别地，对线性优化问题（LP），二阶锥优化（SOCP）,和半定优化(SDP)来说，锥优化提供了一个强大的统一的框架。我们将在下面的内容中更加详细地描述这两种新的重要的锥优化类型：1.二阶锥优化：当C是一个二阶锥（也被称为二次锥，洛伦兹锥，和冰淇淋锥）时1212:{(,,...,):||(,...,)||}nqnnCxxxxIRxxx(9.2)2.半定优化：当C是一个固定维数的半正定矩阵锥时（不妨记为n）1111:::nnnnsnnnxxCXIRXxx是对称半正定矩阵(9.3)9.3二阶锥优化SCOPs指的是含有二阶锥的锥优化。二阶锥是具有这样性质的锥：锥中的每个成员的第一个元素大于等于剩余元素的欧几里得范数。如公式（9.2）中的定义。如图9.1中是一个三维二阶锥的1[0,1]x的一部分。从图可以看出，三维二阶锥是一个延展到无穷远处的冰淇淋锥。观察到“切割”二阶锥，例如，在不同的角度用一个超平面和它相交可以得到圆集和椭圆集。任何凸二次约束条件可以被表示一个二阶锥（或它的旋转锥）和一个或多个超平面的组合。图9.1：二阶锥9.3.1线性约束的椭球不确定性考虑下面的单约束线性规划：min..0TTcxstaxb讨论目标函数确定但约束条件系数不确定的情况。假设约束条件系数[;]ab属于一个椭圆不确定集：001[;][;][;],1kjjjjababab我们的目标是在可行解中找到一个对所有[;]ab来说使目标函数最小的解。换句话说就是解min..0,[;]TTcxstaxbab固定x，满足约束条件的鲁棒形式当且仅当[;]:10minmin+TTabaxb(9.4)其中，00=Tab及1,,k且Tjjjaxb（9.4）中第二个最小化问题很简单。由于是常数，因此只需在约束:1下求T的最小值即可。矢量和之间的角满足下面的三角函数变换：cosT或者cosT。因为是常数，这个表达式是最小的当1并且cos1。这意味着在的反向，及-的方向上。正规化满足边界限制得到*，见图9.2。代入有200[;]1min=kTTTjjabjaxbaxbaxb(9.5)从而得到不等式0Taxb的鲁棒形式是20010kTTjjjaxbaxb(9.6)易知（9.6）可以用二阶锥等价地表示：01,0,,,TjjjkqzaxbjkzzzC上面介绍的这种方法可以推广到多个约束条件的情况，只要不同约束条件的参数的不确定集是不相关的。因此，约束条件是椭圆不确定的鲁棒优化模型可以化为SOCPs。图9.2：圆上线性函数的最小化9.3.2二次约束化为二阶锥优化二阶锥约束01,,,qkxxxC可以等价地写为一个线性约束和一个二次约束的组合：2220010,0kxxxx反过来，一个优化问题的任何凸二次约束都可以用一个二阶锥优化表示。如果我们有方法得到二阶锥优化的可行解，那么将凸二次优化转化为二阶锥优化是必要的。幸运的是，有个简单的方法使这个转化可行。考虑下面二次约束：20TTxQxpx(9.7)左边的函数是凸的当且仅当Q是一个半正定矩阵，此时它是一个凸约束。假设Q是半正定的。此时，存在一个可逆矩阵，记为R，满足TQRR。例如，Q的Cholesky因子满足这条性质。故，（9.7）可以化为20TTTTRxRxpx(9.8)定义101,,,TTkyyyyRxRp。则有，12TTTTTTyyRxRxpxpQ这样，（9.8）等价为11..,TTTystyRxRpyypQp从这个等价关系中，满足约束（9.7）只有当10TpQp时，这恰好是假设的情形。现在，可以很直接地观察到（9.7）等价于有一个二阶锥约束的线性方程的集合：110011,,,,,.TTkqyRxRpykypQpyyyC9.4半定规划在半定规划中，变量集可以用属于半正定矩阵锥并且满足一个线性方程的对称矩阵表示。如果对所有的ny，0TyMy都成立，就称矩阵M是半正定的。如果M是对称的，则M的所有特征值都是非负的。更强的条件是M是正定的。如果对所有的ny且0y，0TyMy都成立，就称矩阵M是正定的。M是对称矩阵时，M正定等价于M的特征值都是正数。由于半正定矩阵和一个正数做乘法保持半正定性，因此半正定矩阵的集合是一个锥。事实上，这是一个凸锥。固定维（记为n）半正定矩阵锥定义如下：1111:::0nnnnsnnnxxCXIRXxx(9.9)上式中，0X表示X是一个对称半正定矩阵。图9.3中是2维半正定矩阵锥的图像描述。横轴表示的是对角元素，是二维对称矩阵11X和22X；纵轴表示的是非对角元素1221XX。元素在阴影部分的2维对称矩阵是半正定矩阵。和非负随机变量和二阶锥一样，半正定矩阵锥在某处是一个点或者角。还可以看到这个锥的凸性和边界是非线性的。图9.3：半正定矩阵锥半定规划起源于学科的多样性。Todd在文献[72]中对解法和很多应用进行了一个极好的介绍。半定约束的产生被普遍认为来自所谓的S-过程，它是文献[58]中提出的熟知的S-引理的推广：引理9.1令()2,0,1,,TTiiiiFxxAxbxcip是nx的二次函数。则有，0()0,0,1,,()0iFxipFx如果存在0i使得001000piiiTTiiiAbAbbcbc。如果1p，只要01..()0xstFx则反之也成立。S-过程提供了一个二次不等式是其他二次不等式的暗含的充分条件。并且，在特殊情况下，它也是一个必要条件。下面我们介绍的二次约束的鲁棒模型中用到这个等价条件。9.4.1二次约束的椭球不确定性这次我们考虑目标函数是确定的但是约束条件的系数是不确定的一个凸二次约束问题：min..20,;;TTTTcxstxAAxbxAbu其中mnAIR，nbIR及是一个标量。再次考虑不确定集是椭球形的：0001;;;;;;,1kjjjjjAbAbuAbuu利用S-过程来得到这个问题的鲁棒形式的表达式。凸二次不等式的鲁棒形式可以写为：;;20TTTAbxAAxbxu(9.10)这等价于下面的表达式：00001111120TkkkkTjjjjjjjjjjjjuxAAuAAuxbbuxu(9.11)定义():nmkAxIRIR为12()|||,kAxAxAxAx():nkbxIRIR为121201()()2TTTTTkkTbxxbxbxbAxAx以及0002()TTTxbxxAxAx并且将1u转化为10TuIu，从而（9.11）可以化简为：1020TTTTuIuuAxAxubxux(9.12)此时，令1111,,0,1pAIbc以及000()(),,TAAxAxbbxcx，运用引理9.1，这样，鲁棒约束（9.12）可以化为0..0.()()TTxbxstbxAxAxI(9.13)9.5算法和软件