We introduce a first order method for solving very large convex cone
programs. The method uses an operator splitting method, the alternating
directions method of multipliers, to solve the homogeneous self-dual embedding,
an equivalent feasibility problem involving finding a nonzero point in the
intersection of a subspace and a cone. This approach has several favorable
properties. Compared to interior-point methods, first-order methods scale to
very large problems, at the cost of requiring more time to reach very high
accuracy. Compared to other first-order methods for cone programs, our approach
finds both primal and dual solutions when available or a certificate of
infeasibility or unboundedness otherwise, is parameter-free, and the
per-iteration cost of the method is the same as applying a splitting method to
the primal or dual alone. We discuss efficient implementation of the method in
detail, including direct and indirect methods for computing projection onto the
subspace, scaling the original problem data, and stopping criteria. We describe
an open-source implementation, which handles the usual (symmetric)
non-negative, second-order, and semidefinite cones as well as the
(non-self-dual) exponential and power cones and their duals. We report
numerical results that show speedups over interior-point cone solvers for large
problems, and scaling to very large general cone programs.

该研究提出了一种用于解决大规模凸锥问题的一阶方法，该方法使用交替方向乘子法来解决自对偶嵌入问题，该方法不需要参数，可以找到原始解和对偶解，并且在大规模优化问题上表现出色。

通过算子分裂和齐次自对偶嵌入实现锥优化

Conic Optimization via Operator Splitting and Homogeneous Self-Dual  Embedding

When binary linear error-correcting codes are used over symmetric channels, a
relaxed version of the maximum likelihood decoding problem can be stated as a
linear program (LP). This LP decoder can be used to decode error-correcting
codes at bit-error-rates comparable to state-of-the-art belief propagation (BP)
decoders, but with significantly stronger theoretical guarantees. However, LP
decoding when implemented with standard LP solvers does not easily scale to the
block lengths of modern error correcting codes. In this paper we draw on
decomposition methods from optimization theory, specifically the Alternating
Directions Method of Multipliers (ADMM), to develop efficient distributed
algorithms for LP decoding.
The key enabling technical result is a "two-slice" characterization of the
geometry of the parity polytope, which is the convex hull of all codewords of a
single parity check code. This new characterization simplifies the
representation of points in the polytope. Using this simplification, we develop
an efficient algorithm for Euclidean norm projection onto the parity polytope.
This projection is required by ADMM and allows us to use LP decoding, with all
its theoretical guarantees, to decode large-scale error correcting codes
efficiently.
We present numerical results for LDPC codes of lengths more than 1000. The
waterfall region of LP decoding is seen to initiate at a slightly higher
signal-to-noise ratio than for sum-product BP, however an error floor is not
observed for LP decoding, which is not the case for BP. Our implementation of
LP decoding using ADMM executes as fast as our baseline sum-product BP decoder,
is fully parallelizable, and can be seen to implement a type of message-passing
with a particularly simple schedule.

研究使用线性节目（LP）编码进行错误纠正，使用优化论的分解方法，开发了一种有效的分布式算法，它具有比置信传递解码器更强的理论保证，并可以用于高效地译码大规模错误纠正码，同时避免了误差底座问题。