PDF
研究文章|开放获取
安娜·维甘特、凯特琳·图希尔、沙菲乌·吉布林， ＂求二阶锥内可行点的约束一致性方法",应用数学学报， 卷。2010， 物品ID307209， 19 页面， 2010． https://doi.org/10.1155/2010/307209
求二阶锥内可行点的约束一致性方法
摘要
内点法可以有效地求解二阶锥约束的优化问题。为了使这些方法更快地开始或收敛，有一个初始可行点或接近可行点是很重要的。本文研究并应用了Chinneck软件起初的约束一致性方法及其应用DBmax用约束一致法求解soc系统的近可行点。在这些方法上，我们还开发并实现了一种新的类似回溯的线搜索技术，试图在每次迭代时增加共识向量的长度，以寻找内部可行点为目标。数值结果表明，该方法是求解soc内部可行点的有效方法。
1.介绍
我们考虑一个二阶锥不等式系统如下: 哪里 是一个矩阵是一个向量，是一个向量,是一个标量。范数是标准的欧几里德范数。我们假设可行域的内部非空的。
二阶锥的研究非常重要，因为在许多优化问题中，约束条件都可以写成这种形式。例如，soc可以用来很容易地表示处理规范、双曲约束和鲁棒线性规划的问题。在天线阵重量设计、抓取力优化和组合优化等领域也有大量的实际应用(参见[1]有关这些应用程序和其他应用程序的更多信息）。此外，存在有效的内点方法来解决具有SOC约束的优化问题，例如原始-对偶内点方法。由于这些应用以及内点方法在应用于SOCs时的成功，因此需要能够有效地找到SOC的近似可行点或可行点SOCs系统[1- - - - - -4］.一种可行性的方法载于[5］.
在本文中，我们将描述两种Chinneck约束共识算法，并将其应用于soc中寻找近可行点。这些都是起初的约束一致性方法及其应用DBmax约束共识方法。当然可以在这些方法的最终共识向量上加一个小值，使其进入可行域的内部[6]。但是，如果最终共识向量远离边界，这将不起作用。我们提出了一种不同的方法，使用回溯技术在每次迭代中增加一致性向量的步长。目标是找到内部可行点，减少迭代次数和时间。该技术的工作原理是将一致性向量扩展一个给定的值，然后回溯，直到在满足的约束数量不减少的点处尽可能接近可行区域。最后，我们研究了修改后的算法在实际应用中的有效性起初的和DBmax方法对随机生成的问题进行测试，结果表明回溯技术在寻找内部可行点方面是有效的，并且大大减少了方法所需的迭代次数和时间。
我们还研究了如何将我们的工作应用于凸二次约束的特殊情况。更多关于cqc在优化领域的重要性的信息可以在[7，8].我们对CQC的结果表明，回溯还显著减少了必要的迭代次数和测试时间起初的方法。它还能够在许多测试问题上找到内部可行点。然而，回溯法不能很好地用于测试DBmax方法在cqc的情况下。我们注意到，在这两种约束类型(soc或cqc)中，DBmax方法的性能优于起初的方法,如预期。
2.应用于二阶锥的约束一致性方法
在本节中，我们研究和应用Chinneck的起初的约束共识,DBmax约束一致性方法用于SOCs，以找到系统的近似可行点(1．1).
第一种约束一致方法，在此称为起初的由Chinneck于年开发[3.)(见算法1).该方法从不可行点开始. 该方法关联每个约束用一个可行性向量 ．以我们的soc为例，．可行性向量定义为哪里是约束违反在和为梯度在某一点上.我们假设的存在。注意,如果是线性的,从到它在约束上的正交投影．可行性向量的长度被称为可行性距离．我们定义是可行的附近关于如果哪里是预先指定的可行性公差。我们说是可行的关于如果和是一个室内可行点如果．
|
||||||||||||||||||||||||||||||||||||||||||
然后将可行性向量组合成单个向量一致向量它反映了所有可行性向量所建议的运动。的一致向量，，通过求可行性向量的非零分量的平均值来创建。每个组件的是由平均数违例可行性向量的分量)是在点处违反的每个约束的可行性向量的组件,是在点上被违反(不接近可行)的约束的数量．然后将共识向量添加到来获得一个新的迭代，并重复该算法，直到当前迭代的违反约束数(NINF)为零为止。如果一致向量变得太短，并且没有足够快地向可行区域进展，如果运动公差，算法也将停止循环到达。
Ibrahim等人给出了几个修改起初的方法[9］.而起初的方法对所有符合条件的可行性向量一视同仁，其发展的变异侧重于对一致性向量有较强影响的可行性向量。它们产生了两种不同类型的改进约束共识算法。他们通常会找到一种基于方向的算法，叫做DBmax，是所有变体中最成功的，请参见算法2．
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
DBmax看看组成每个有效的可行性向量，并取投票最多的符号的最大值，然后成为共识向量的入口。如果正数和负数相等组件，成为最正和最负的平均值有效可行性向量的分量是最积极的价值可行性向量的组成部分，成为最负价值的人可行性向量的组成部分，是投票赞成变量正向移动的违反约束数,为为变量投反对票的违反约束的数量．
对于一个更具体的例子，我们考虑了一个3个SoC的系统。，如图所示1．在整个论文中演示概念时，我们将参考这个系统。
例2.1。制度二级锥(soc)与变量:
(1)，
(2) ，
(3) ，
哪里
我们定义函数
注意给出了圆锥的边界，锥可行域内为非负，锥外为负。如图所示2，这是一个为圆锥(1)的例子2．1．
(一)
（b）
下面的定理是众所周知的。可以用如图所示的三角形不等式给出一个初等证明。它将用于讨论方程的收敛性起初的和DBmax方法。
定理2.2。 是凹的吗．
证明。为了方便起见，我们将考虑两个独立的功能，和．两个凹函数的和也是凹的，证明了这一点和都是凹的。是线性的，所以它是凹的。为了显示凹进，足以证明对于和．
通过三角不等式，我们得到了
这意味着,所以是凹的。两个凹函数的和也是凹的，所以是凹的，所以也是凹。
投影算法，如起初的和DBmax证明了约束一致方法在函数收敛时的收敛性凹面[3.，10，11］.所以,定理2．2保证了soc的收敛性。定理2．2证明了可行域(1．1)是凸的。
使一致性方法适应SOCs的主要任务是计算梯度的。由
在计算梯度时，存在两个潜在的问题。首先，有时梯度可能不存在。当梯度是未定义的。例如，在我们的第一个圆锥体中是．如图所示3.，这个点恰好在圆锥的可行区域内。这并不总是这样，但选择一个解决方案的概率在我们的算法中是非常小的。另一个潜在的问题是，当梯度为零时，可行性向量将是未定义的。如果或者在迭代时未定义，算法失败了，我们应该选择一个不同的起点。对于圆锥(1)，我们的例子中不存在梯度为零的点，如下所示 这个系统唯一可能的解决方案是和，这是梯度未定义的地方。这意味着没有解决方案对于这个特殊的例子。
我们从定理中知道2．2那是凹的。一个很好的结果是是严格凹的，那么梯度为零的唯一可能位置出现在可行区域内，如定理2．3．
定理2.3。认为是严格凹的。如果然后在可行域内吗．
证明。如果梯度是零，一定是在临界点。自是严格凹的，唯一的潜在临界点将是．自在可行区域之外，以及在可行域内，可以得出也必须是非负的。因此，梯度只能在可行区域内为零。
因此，对于严格凹约束，可行域内的梯度仅为零，因此在我们算法的所有迭代中都存在可行向量。
让哪里可行性向量在吗. 图形4是一个例子．的图像是图形的一部分这是从定理出发的2．2那凹进结束．
下面的结果表明，在算法的每一次迭代中，我们都向可行区域的边界移动。
定理2.4。假设这条线相交于…的边界在．然后不减损结束了吗．
证明。 是负的了在点处为零．自是凹的吗然后越来越多的．
为凹时，可行性向量的近似最常达不到的边界．因此，一致向量也将达不到边界。它可能是可取的，以增加一致向量的长度尽可能地接近边界。从图5，我们可以看到，对于锥可行区域之外的所有点，梯度点的方向就是边界的方向。然而，并非所有soc都是如此。如图所示6，有些迭代可能没有直接指向可行域的梯度。因此，一般来说，增加共识向量的长度是有限制的。这一点在我们稍后讨论回溯技术时要注意到。
3.凸二次约束的情形
在本节中，我们将研究上一节的讨论如何应用于凸二次约束的特殊情况。本研究将仅限于与cqc相关的不同结果。
我们考虑CQCs的一个系统： 哪里，是一个矩阵是一个向量，是一个向量,是一个标量。
为了便于表示，考虑单个CQC 值得注意的是，CQC也是SOC 哪里 为简单起见，又不失泛化，我们假设是正定的。所以,存在且可逆。然后，CQC (3.2)相当于 这相当于SOC 上述结果表明，我们关于soc上的凹性和收敛性的所有结果也推广到CQC系统(3.1).计算梯度就足够了和黑森的．它们是由 当梯度为零时，可行性向量不存在。注意梯度是由线性方程组的解给出的吗 作为例证，请考虑下面的例子。
例3.1。带的凸二次约束(CQC)变量。
哪里
例如3.1线性系统(3.8)是
解决方案和，它在可行域内。参见图7．
自从黑森，是严格凸的，如果是正定的。和定理类似2．3,如果是正定的，那么梯度只能在可行域内的一点为零。这意味着，在这种情况下，可行性向量存在于共识算法的所有迭代中。
4.约束一致性方法的新变化
在本节中，我们提出对起初的和DBmax约束共识方法。该方法在每次迭代时都扩展了一致性向量的长度，目标是在可行域内找到一个点(1．1).
的回溯线搜索技术(算法3.)是约束一致性方法（算法）中的一个步骤1和2)，试图扩展共识向量的长度更接近可行点。它会到达一个点，即满足约束的数量不会减少。回溯技术通过低成本的测试来寻求快速收敛，看看我们是否可以增加共识向量的大小。首先以通常的方式计算共识向量(使用起初的方法或DBmax)，测试是否能成功地增加共识向量的大小，希望在更少的迭代和时间内更接近可行区域。这项技术还有一个额外的好处，那就是最终的点有可能实际上是在内部，而不是一个接近可行的点。
回溯线搜索技术使用了一个概念二进制字．
定义4.1。定义为约束集的二进制词(1．1)或(3.1),由
如果然后是可行的。我们可以很容易地检验……的可行性通过对二进制数的分量求和。当和为0时，我们知道是可行的，我们可以允许算法退出哪里有关如果二进制单词是同一个二进制单词．等价类形成的一个分区．
我们从计算共识向量开始. 然后，我们通过初始标量因子对一致性向量进行缩放。我们将这个共识向量添加到．使用这个新点，我们计算二进制单词违反约束的数量。我们认为新的共识向量是成功的，如果结果点违反相同的数量或更少的约束比前一个点。如果不是这样，算法回溯并尝试在共识向量中增加一个较小的增量。如果回溯三次后，该点仍然没有发现满足约束的数量有所改善，则返回到初始一致向量。在我们的测试中，我们将共识向量缩放2、1.5、1.25，如果没有一个满意的，那么我们将返回到1的步长。算法3.根据约束或问题的类型，可以很容易地改变以使用其他步长。
在图中8，我们可以看到一个比较起初的方法与起初的回溯法在实例中的应用2．1．设(- 8,6)的出发点相同起初的回溯法以较少的迭代次数和较少的时间达到了可行性，并且利用回溯法得到了最终点起初的回溯法实际上对所有三个约束都是可行的，而不是近似可行的。得到的最后一点起初的方法仅对第2个约束条件可行，其余2个约束条件的距离公差均在0.01以内。
(一)
（b）
5.数值实验
在本节中，我们使用数值实验来测试起初的方法与DBmax随机测试问题的回溯寻线方法。
对于每个SOC测试问题，我们首先生成整数值,,在间隔中均匀地，,,分别。然后，随机选择一个点，每个条目的值都是均匀的.在这之后，SOC是使用和，其中的每一项，，,在区间内是一致的吗．我们检查以确保所有的在随机点满足SOC。表1列出SOC测试问题。CQC测试问题就像SOC测试问题一样产生。然而,生成cqc是为了使每个cqc在原点和条目处都得到满足是统一的.表中给出了CQC测试问题1．
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
对于每个测试问题和方法，我们选择一个随机的不可行点作为我们的起点，以进入统一的．我们设定了我们的可行性距离公差为以及我们的运动耐力．我们选择了最大的迭代次数.所有代码都是用MATLAB编写的©7.9.0并在Dell OptiPlex GX280上运行。
5.1.二阶锥
表3.和4给出SOC测试问题的结果。如果迭代次数（Iter）为500，则表示该方法未收敛。最后一列显示该方法是否收敛到内部可行点。表2给出了在所有25个问题中找到一个内部可行点的成功率和每个问题(收敛处)的平均时间。这两个起初的方法与DBmax方法在第6题和第13题中失败。
|
|||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
正如所料，平均而言DBmax方法迭代次数少，耗时短起初的方法。另外，请注意DBmax在问题24中找到了一个内部可行点。有趣的是，回溯技术表明，在所有测试问题上，在迭代和处理时间方面都有普遍的改进，其中存在收敛性。
平均的起初的方法与回溯法相比，用了更少的时间起初的方法。类似地,DBmax方法与回溯法相比，用了更少的时间DBmax方法起初的回溯法具有严格的可行性，成功率为64%，而DBmax回溯的成功率为84%。
5.2. 凸二次约束
表6和7给出CQC测试问题的结果。桌子5给出了在所有25个问题中找到一个内部可行点的成功率和每个问题(收敛处)的平均时间。和预期的一样，平均而言DBmax方法迭代次数少，耗时短起初的方法。
|
|||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
从表中可以看出，将回溯技术应用到起初的方法大大减少了迭代次数和时间起初的回溯法具有严格的可行性，成功率为44%DBmax在美国，回溯技术并没有很好地工作。在实现可行性的迭代和时间上都有显著的增加，25个问题中有11个出现了分歧。这很可能是由于共识向量DBmax已经很长。这意味着共识向量的扩展可能会使它移动得太远，使它正好超过可行域。我们怀疑这是由于CQC约束的性质，它倾向于形成有界可行区域。
6.结论
我们研究了下巴脖子的肌肉起初的约束共识,DBmax在二阶锥(soc)和凸二次约束(cqc)的特殊情况下求近可行点。我们还提出了一种新的回溯线搜索技术，以寻找内部可行点为目标，增加一致性向量的大小。
给定一组soc，我们调整起初的和DBmax约束一致性方法，用于寻找近似可行点。仅这些方法很少能找到SOCs的内部可行点。我们发展了一种回溯线搜索技术来寻找内部可行点。我们在各种测试问题上测试使用回溯技术和不使用回溯技术的方法，并将它们与收敛所需的时间和迭代次数进行比较。
在应用回溯之前，已知的方法以最少的时间和最少的迭代次数达到可行性是一致的DBmax．的起初的用回溯法仍然不如DBmax．然而,起初的回溯达到可行性的迭代次数少于DBmax并且能够在大多数测试问题中找到内部可行点起初的带回溯的方法在SOC和CQC中运行良好DBmax回溯方法在SOC中效果很好，但在CQC中效果不好。这可能是因为在CQC中，回溯步骤中的一致性向量增加得太多。
综合考虑soc和cqc，我们发现回溯线搜索最成功地减少了时间和迭代所需的可行区域，当应用于起初的共识的方法。如前所述,DBmax使用回溯方法在CQC中不成功。在未来，尝试回溯线搜索技术的更多变体将是有趣的。我们可以比较回溯技术中不同初始步长和缩减的有效性，特别是在DBmax适用于cqc时。研究回溯技术对其他变体的影响也会很好起初的中给出的方法[9］.
承认
A. Weigandt和K. Tuthill的工作得到了北亚利桑那大学数学和统计系在2010年夏天国家科学基金会REU项目下的支持。
参考文献
- M. S. Lobo, L. Vandenberghe, S. Boyd，和H. Lebret，“二阶锥规划的应用”，线性代数及其应用，第284卷，第1-3期，第193-228页，1998年。视图:出版商的网站|谷歌学者
- F. Alizadeh和D. Goldfarb，《二阶锥规划》，数学规划第95卷第1期1, 2003年。视图:出版商的网站|谷歌学者
- J. W. Chinneck，“在非线性规划中寻找近似可行点的约束一致方法”，为《计算机杂志》提供信息，第16卷，第3期，第255-265页，2004年。视图:谷歌学者
- Y. Nesterov和A. Nemirovsky，“凸规划中的内点多项式方法”，载应用数学研究，第13卷，暹罗，费城，宾夕法尼亚州，美国，1994年。视图:谷歌学者
- R. J. Caron, T. Traynor，和S. Jibrin，“线性矩阵不等式集的可行性和约束分析”，为《计算机杂志》提供信息，第22卷，第1期，第144-153页，2010年。视图:谷歌学者
- J. W. Chinneck，私人通讯与S. Jibrin, 2010。
- d .窝Hertog线性、二次和凸规划的内点方法，第277卷，共页数学及其应用， Kluwer学术出版社，Dordrecht，荷兰，1994。
- r . j . Vanderbei线性规划：基础和扩展， Kluwer学术出版社，波士顿，马萨诸塞州，美国，第二版，2001。
- W. Ibrahim和J. W. Chinneck，“改进求解器在达到非线性约束集的可行性方面的成功”，计算机与运筹学，第35卷，第5期，第1394-14112008页。视图:出版商的网站|谷歌学者
- Y. A. Censor和S. A. Zenios，并行优化：理论、算法和应用《数值数学与科学计算》，牛津大学出版社，美国纽约，1997。
- D. butnabariu, Y. Censor和S. Reich，内在并行算法的可行性和优化及其应用，第8卷计算数学研究，北荷兰出版社，荷兰阿姆斯特丹，2001。
版权
版权所有©2010 Anna Weigandt等人。这是一篇发布在知识共享署名许可协议，允许在任何媒介上不受限制地使用、传播和复制，但必须正确引用原作。
