Alfonso: Matlab Package for Nonsymmetric Conic Optimization
Alfonso: Matlab Package for Nonsymmetric Conic Optimization
复制标题
DOI：
10.1287/ijoc.2021.1058
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
D. Papp;Sercan Yildiz
中科院分区：
文献类型：
--
作者：
D. Papp;Sercan Yildiz
我们提出了 alfonso，一个开源 Matlab 软件包，用于解决非对称凸锥上的圆锥优化问题。该实现基于作者对 Skajaa 和 Ye 的方法的修正分析。只要对数均匀自和谐势垒可用于锥体或其对偶，它就可以对任何凸锥体进行优化。这包括许多非对称锥体，例如双曲锥体及其对偶（例如平方和锥体）、半定锥和二阶锥体可表示锥体、幂锥体和指数锥体。除了能够解决无法转化为对称圆锥上的优化问题的问题之外，非对称圆锥优化算法还为对称圆锥编程表示需要大量辅助变量或具有可在障碍计算中利用的特殊结构的问题提供性能优势。阿方索最坏情况的迭代复杂度是最著名的非对称锥优化： [公式：参见文本] 迭代以达到 ε 最优解，其中 ν 是优化中使用的障碍函数的障碍参数。 Alfonso 可以与 Matlab 函数（由用户提供）连接，计算锥体势垒函数的 Hessian 矩阵。还可以使用简化的界面来优化锥体的直接乘积，软件中已经内置了屏障函数。该接口可以轻松扩展以包含新的锥体。两个接口均通过求解线性规划来说明。 Oracle 接口和阿方索的效率也通过实验问题的优化设计得到了证明，其中与使用最先进的现成圆锥优化软件相比，定制的障碍计算大大缩短了求解时间。贡献总结：本文描述了一个用于非对称锥体优化的开源 Matlab 包。该软件的一个特别重要的功能是，与其他圆锥优化软件不同，只要圆锥或其对偶有合适的障碍函数，它就可以对任何凸圆锥进行优化，而不是将用户限制为少量的特定圆锥。此类势垒已知的非对称锥体包括例如双曲锥体及其对偶锥体（例如平方和锥体）、半定锥体和二阶锥体可表示锥体、幂锥体和指数锥体。因此，该软件的范围远远大于当前大多数圆锥曲线优化软件。这并不以效率为代价，因为我们算法的最坏情况迭代复杂度与对称锥体最成功的内点方法的迭代复杂度相匹配。除了能够解决无法转化为对称锥优化问题的问题外，我们的软件还可以为对称锥编程表示需要大量辅助变量或具有可在障碍计算中利用的特殊结构的问题提供性能优势。本文还通过一个示例证明了这一点，其中我们的代码显着优于 Mosek 9 和 SCS 2。
We present alfonso, an open-source Matlab package for solving conic optimization problems over nonsymmetric convex cones. The implementation is based on the authors’ corrected analysis of a method of Skajaa and Ye. It enables optimization over any convex cone as long as a logarithmically homogeneous self-concordant barrier is available for the cone or its dual. This includes many nonsymmetric cones, for example, hyperbolicity cones and their duals (such as sum-of-squares cones), semidefinite and second-order cone representable cones, power cones, and the exponential cone. Besides enabling the solution of problems that cannot be cast as optimization problems over a symmetric cone, algorithms for nonsymmetric conic optimization also offer performance advantages for problems whose symmetric cone programming representation requires a large number of auxiliary variables or has a special structure that can be exploited in the barrier computation. The worst-case iteration complexity of alfonso is the best known for nonsymmetric cone optimization: [Formula: see text] iterations to reach an ε-optimal solution, where ν is the barrier parameter of the barrier function used in the optimization. Alfonso can be interfaced with a Matlab function (supplied by the user) that computes the Hessian of a barrier function for the cone. A simplified interface is also available to optimize over the direct product of cones for which a barrier function has already been built into the software. This interface can be easily extended to include new cones. Both interfaces are illustrated by solving linear programs. The oracle interface and the efficiency of alfonso are also demonstrated using an optimal design of experiments problem in which the tailored barrier computation greatly decreases the solution time compared with using state-of-the-art, off-the-shelf conic optimization software. Summary of Contribution: The paper describes an open-source Matlab package for optimization over nonsymmetric cones. A particularly important feature of this software is that, unlike other conic optimization software, it enables optimization over any convex cone as long as a suitable barrier function is available for the cone or its dual, not limiting the user to a small number of specific cones. Nonsymmetric cones for which such barriers are already known include, for example, hyperbolicity cones and their duals (such as sum-of-squares cones), semidefinite and second-order cone representable cones, power cones, and the exponential cone. Thus, the scope of this software is far larger than most current conic optimization software. This does not come at the price of efficiency, as the worst-case iteration complexity of our algorithm matches the iteration complexity of the most successful interior-point methods for symmetric cones. Besides enabling the solution of problems that cannot be cast as optimization problems over a symmetric cone, our software can also offer performance advantages for problems whose symmetric cone programming representation requires a large number of auxiliary variables or has a special structure that can be exploited in the barrier computation. This is also demonstrated in this paper via an example in which our code significantly outperforms Mosek 9 and SCS 2.