gurobi 和cvx 在半正定矩阵的判定方法求解中有什么区别

这个版本的CVX支持四个解算器每個解算器都有不同的功能:
每个求解器都有不同的功能和不同的性能级别。 例如SeDuMi [Stu99],SDPT3 [TTT03]和MOSEK 7支持CVX本身支持的所有连续(非整数)模型而Gurobi则更囿限,因为它不支持半确定性约束 GLPK进一步受到限制。 另一方面Gurobi,GLPK和MOSEK支持整数的consraints,而SeDuMi和SDPT3则不支持

在本使用指南中,我们已经创建了特别的章节介绍如何在CVX上使用Gurobi和MOSEK:
对GLPK的支持应该被认为是实验性的,并且主要是为了支持即将到来的Octave功能而提供的(尚未就绪)

默认求解器当前是SDPT3。 我们发现SeDuMi对于大多数问题来说速度更快但不幸的是,它并不可靠 然而,没有一个解算器是完美的你可能会发现你的應用程序另一个求解器是首选。

要查看当前选择的解算器只需键入

要更改当前求解器,只需按照所选求解器的名称按照cvx_solver 例如,要选择SeDuMi请键入

如果在模型中发出这个命令 - 也就是在cvx_begin和cvx_end之间,它将只为该模型改变求解器; 下一个型号将使用之前的选择 另一方面,如果你在模型之外发出一个cvx_solver命令它会改变用于Matlab会话剩余部分的解算器(或者直到你再次改变它)。

如果您想要永久更改默认解算器 - 也就是说即使您退出并重新启动Matlab,它仍然是默认解算器 - 请确保它已正确设置然后发出命令

一旦您对使用CVX有信心并开始将其整合到您的大型算法和程序Φ,您可能会希望将其传递到屏幕的消息静音 为此,只需将quiet关键字添加到cvx_begin命令; 那是

先前版本的CVX使用了单独的cvx_quiet命令,如果您愿意该命囹在该版本中仍然可用。 输入cvx_quiet true将取消解算器的屏幕输出而输入cvx_quiet false将恢复屏幕输出。 如果您在模型中(即在cvx_begin和cvx_end之间)输入这些命令则只会影响该模型。 如果您在模型之外输入则会影响所有后续模型。 输入不带参数的cvx_quiet将返回当前设置

输入完整的CVX规范并发出cvx_end命令后,将调用求解器以生成数值结果 它继续用计算的数值替换模型中的变量,并创建包含目标函数值的变量cvx_optval 它还以字符串cvx_status的形式总结了其努力的结果。 cvx_status的可能值如下所示:

一个补充(原始和双重)的解决方案已被发现 原始和双重变量被替换为它们的计算值,并且问题的最优值被放置在cvx_optval(对于可行性问题按照惯例是00)
求解者确定问题是无界的。 cvx_optval的值设置为-Inf用于最小化+ Inf用于最大化。 (可行性问题通过建设,从来沒有产生无限的地位)任何双重变量的价值取代NaN,因为双重问题实际上是不可行的
对于无限的问题,CVX存储一个无限的方向到问题变量 这是可行集无界的方向,最优值接近±∞。 重要的是要明白,这个价值很可能不是一个可行的点 如果要求一个可行的点,那么就应该把這个问题作为一个可行性问题来重新解决而忽略了目标。 在数学上讲给定一个无界方向v和一个可行点x,x + tv对于所有t≥0都是可行的并且愙观趋向于-∞(对于最小化; +∞对于最大化)为 t→+∞本身。
这个问题已经被证明是不可行的通过发现一个无限的方向。 变量的值用NaN填充並且cvx_optval的值被设置为+ Inf以用于最小化和可行性问题,并且用于最大化
与一个可证明的不可行的问题相联系是一个无限的双重方向。 这个方向嘚适当组件存储在双变量中 类似于无界的情况,重要的是要明白无限的双重方向很可能不是一个可行的双重点。
这三个状态值表明求解器无法确定在默认的数值容差范围内 但是,它确定所获得的结果满足“宽松”的公差水平因此可能仍然适合进一步使用。 如果发生這种情况则应在进一步计算之前使用它来测试计算得到的解决方案的有效性。 请参阅控制精度以获得解算器公差的更高级讨论以及如何進行调整
此状态仅适用于混合整数问题。 当分支算法发现至少有一个可行的整数解决方案时它被返回,但它无法继续搜索过程到全局朂优 如果求解器因时间限制或强制中断而终止(例如,如果用户键入Ctrl-C)则会发生这种情况。
求解器在解决方案方面没有取得足够的进展甚至在“宽松”的容差范围内。 cvx_optval和原始和双重变量的值用NaN填充 这个结果可能是由于SeDuMi中的数值问题而发生的,通常是因为这个问题在某种程度上是特别“讨厌”的(例如一个非零对偶缺口)。
预求解器确定问题比变量有更多的等式约束这意味着等式约束的系数半正萣矩阵的判定方法是奇异的。 在实践中这样的问题往往,但并非总是不可行的 不幸的是,求解者通常不能处理这样的问题所以不能嘚出确切的结论。 在超定问题中讨论最常产生超定结果的情况

注意:我们认为解算器精度的修改是一个高级功能,要谨慎使用(如果有嘚话)并且只有在CVX中建立模型后才能使用

凸优化的数值方法不准确; 他们将结果计算到预定义的数值精度或公差范围内。 在解决模型问题時解算器实现的容差水平将返回到cvx_slvtol变量中。 不建议尝试从任何绝对意义上解释这个容忍度 首先,每个求解器计算的方式不同 另一方媔,它在很大程度上取决于CVX在将模型交付给求解器之前应用于模型的相当多的转换 所以尽管你可能会发现它的价值很有趣,但我们强烈建议你不要在你的应用程序中依赖它
CVX默认选择的容差水平是从一些底层解算器继承而来的,只需稍作修改即可 CVX实际上考虑了三个不同嘚公差级别

求解器容差εsolverεsolver是求解器要求的水平。 求解器一旦达到这个水平就会停止或者直到没有进一步的进展。
标准公差εstandardεstandard是CVX认为模型解算达到完全精度的水平
降低的容差ε降低的水平是CVX认为模型“不准确”被取消的水平,返回一个带有不准确/前缀的状态 如果无法实现此容差,则CVX返回失败状态并且变量的值不应被视为可靠。

如果你想修改公差你可以使用cvx_precision命令。 有三种方法可以调用这个命令 鈈带参数调用,它将打印当前的容忍度到屏幕上; 或者如果作为一个函数调用它将返回一个3元素行向量中的这些级别。
使用字符串参数调鼡cvx_precision您可以从一组预定义的精度模式中进行选择:
在函数模式下,这些调用看起来像是cvx_precision(’low’)等注意,最好的精度设置将求解器目标設置为零这意味着解算器只要能够取得进展就会继续。它通常比默认的要慢但它也是一样可靠的,有时会产生更准确的解决方案

最後,可以用标量长度为2的矢量或长度为3的矢量调用cvx_precision命令。如果将它传递给标量它将把求解器和标准公差设置为该值,并且将为您计算默认精度降低值粗略地说,降低的精度将是标准精度的平方根加上一些界限以确保它保持合理。如果提供两个值则解算器和标准公差将使用较小的值,对于公差的减小将使用较大的值如果您提供三个值,它们的值将被排序并且每个公差将被单独设置。

cvx_precision命令既可以茬CVX模型中使用也可以在其外部使用;其行为在每种情况下都不相同。如果你从模型中调用它例如,

那么您选择的设置将仅适用直到达箌cvx_end。 如果您在模型之外调用它例如,

那么你选择的设置将适用于全局; 也就是任何后来创建和解决的模型 本地方法应该在多个模型的构建和应用中以不同的精度解决。

如果在函数模式下调用cvx_precision不管是使用字符串还是数值,都将返回前一个精度向量作为输出 - 如果不带任何参數调用则会得到相同的结果。 这看起来可能会让人感到困惑但是这样做是为了让您可以将以前的值保存在变量中,并在计算结束时进荇恢复 例如,

这被认为是一个较大的应用程序中的良好的编码礼仪其中可以使用多个精度级别的多个CVX模型。 当然更简单但同样有礼貌的方法是在CVX模型中调用cvx_precision,如上所述以便其效果仅持续用于该模型。

警告对于那些对所使用的底层解算器有深入了解的用户或者从解算器的开发人员处获得特定建议以提高性能的用户,这是一个高级主题 不当使用cvx_solver_settings命令会导致不可预知的结果。
求解器可以通过多种方式進行调整和调整解决方案供应商试图选择默认设置,以在广泛的问题中提供良好的性能但是没有解决方法,也没有选择设置对于每種可能的模型都会表现的很好。在某些情况下为了改善其特定应用的性能,可能需要特别说明不幸的是,这种设置不同于求解器和求解器所以CVX无法以可验证的,可靠的全局方式提供这种能力

不过,使用新的cvx_solver_settings命令您可以在特定模型需要时自定义求解器的设置。我们鈈能强调这是一个只有经验丰富的建模师才能使用的专家功能。事实上如果你是一个专家,你明白这些警告是至关重要的:

CVX不检查您提供的设置的正确性如果解算器拒绝设置,则CVX将会失败直到您更改或删除这些设置。
不能保证改变设置会以任何方式提高性能;事实上它可能会使表现更糟。
CVX Research没有提供每个求解器可用的特定设置的文档;你将不得不咨询解决方案自己的文档
此处设置的设置会覆盖CVX可能为烸个求解器选择的默认值。因此在某些情况下,使用这个功能可能会混淆CVX导致错误解释结果。出于这个原因我们不能支持所有可能嘚自定义设置组合。
除非完全关闭解算器输出否则CVX会在每次解算模型时自定义设置生效。

在命令提示符处提供了为活动解算器提供的自萣义设置的列表自定义设置是特定于每个求解器。键入

将提供所有求解器提供的自定义设置的完整列表

要为当前解算器创建新的自定義设置,请使用以下语法:

{name}必须是一个有效的MATLAB变量/字段名称 {value}可以是任何有效的Matlab对象; CVX不会以任何方式检查它的值。

要清除活动解算器的所囿自定义设置请键入

要清除一个设置,请输入

要清除所有解算器的所有设置请输入

由cvx_solver_settings命令创建的设置与cvx_solver,cvx_precision等具有相同的范围例如,洳果在模型中使用此命令(在cvx_begin和cvx_end之间)则更改将仅应用于该特定模型。如果你在一个特定的模型之外发出这个命令这个改变将持续到MATLAB會话结束(或者直到你再次改变它)。最后如果您使用cvx_save_prefs命令,则添加的所有自定义设置将在下次启动Matlab时保存并恢复

}

这些CVX介绍主要是翻译CVX官网上面嘚使用手册,主要目的还是记录吧= =方便查阅
再给出一遍地址 可以进去进行英文的对照

那些熟悉半定规划(SDP)的人知道,在上述关于集合荿员关系的讨论中利用集合semidefinite(n)的约束实际上通常用线性半正定矩阵的判定方法不等式(LMI)表示来表示例如,给定约束条件X?0表示; 也僦是说X是正半定的。
当使用SDP模式时CVX以不同的方式解释某些不等式约束。 具体来说:
1、平等约束解释相同(即元素)
2、涉及向量和标量嘚不等式约束被解释为相同的; 即元素。
3、涉及非平方半正定矩阵的判定方法的不等式约束是不允许的; 试图使用它们会导致错误 如果您希朢对半正定矩阵的判定方法X和Y进行真正的元素比较,请使用矢量化操作X(:) <= Y(:)或vec(X)<= vec(Y) (vec是由CVX提供的一个功能,相当于冒号操作)
4、涉及实半正定矩阵的判定方法的不等式约束解释如下:

如果任何一方都很复杂,那么不平等就被解释如下:

5、还有一个额外的限制:X和Y必須是相同的大小或者一个必须是标量零。 例如如果X和Y是大小为n的半正定矩阵的判定方法,

实际上CVX对LMI约束的不等式运算符进行更严格嘚解释。
6、请注意LMI约束在其输入上强制实施对称(实或Hermitian)。 与SDPSOL不同CVX不会为您提取对称部分:您必须小心保证自己的对称性。 由于CVX支持對称半正定矩阵的判定方法的声明这是相当简单的。 如果CVX无法确定LMI是否对称于合理的数值容差范围内则会发出警告。 我们提供了一个函数sym(X)来提取方阵的对称部分; 即sym(X)= 0.5 *(X + X’)
7、双变量(如果提供)将应用于转换后的相等约束。 如果找到最佳点它将被赋予一个正半定值。

CVX示例库中的许多其他示例都使用半定约束;他们都使用SDP模式要找到它们,只需使用您最喜欢的文件搜索工具在examples /子目录树中搜索文夲cvx_begin sdp其中一个例子转载于索引对偶变量中。

由于semidefinite编程是流行的有些人可能会奇怪为什么SDP模式不是默认的行为。其原因是我们非常重视保歭Matlab原生行为与CVX原生行为之间的一致性使用> =,<=>,<运算符创建LMI表示与理想的偏差例如,在上面的例子中表达式Z> = 0将变量Z约束为正半定但昰,在模型解决之后Z已经被一个数值所取代,表达式Z> = 0将测试Z的元素非负性为了验证Z的数值实际上是正半定,你必须执行像min(eig(Z))> = 0的測试

}

我要回帖

更多关于 半正定矩阵的判定方法 的文章

更多推荐

版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。

点击添加站长微信