论文标题
操作员分裂以均匀嵌入线性互补问题
Operator splitting for a homogeneous embedding of the linear complementarity problem
论文作者
论文摘要
线性互补问题（LCP）是一个一般集合成员资格问题，其中包括二次锥编程作为特殊情况。在这项工作中，我们考虑了LCP的均匀嵌入，该嵌入既编码原始LCP的最佳条件又编码Inferesibles证书。由此产生的问题可以表示为单调包含问题，涉及两个最大单调算子的总和，我们将其应用道格拉斯·拉赫福德分裂。所得算法几乎具有将分裂直接施加到LCP上的相同的触电成本。具体而言，每次迭代都需要求解线性系统并投影到凸锥上。 所得算法没有明确的超参数，并且能够返回原始偶型解决方案，或者如果存在一种或不可行证书。如果解决了一系列相关问题，则很容易被温暖启动，并利用线性系统的分解缓存。我们在一系列公共和合成数据集上证明，对于可行的问题，我们的方法往往比将操作员直接拆分到LCP的速度要快一些，并且在不可行的情况下，我们的方法可以比基于迭代迭代的替代方法要快得多。我们描述的算法已在C中实现，可作为SCS-3.0开源。
The linear complementarity problem (LCP) is a general set membership problem that includes quadratic cone programming as a special case. In this work we consider a homogeneous embedding of the LCP, which encodes both the optimality conditions of the original LCP as well as certificates of infeasibility. The resulting problem can be expressed as a monotone inclusion problem involving the sum of two maximal monotone operators, to which we apply Douglas-Rachford splitting. The resulting algorithm has almost identical per-iteration cost as applying the splitting to the LCP directly. Specifically, each iteration requires solving a linear system and projecting onto a convex cone. The resulting algorithm has no explicit hyper-parameters and is able to return a primal-dual solution should one exist or a certificate of infeasibility otherwise. If a sequence of related problems are solved it can easily be warm-started and make use of factorization caching of the linear system. We demonstrate on a range of public and synthetic datasets that for feasible problems our approach tends to be somewhat faster than applying operator splitting directly to the LCP, and in cases of infeasibility our approach can be significantly faster than alternative approaches based on diverging iterates. The algorithm we describe has been implemented in C and is available open-source as SCS-3.0.
