A Two-Step Pre-Processing for Semidefinite Programming

Understand

In semidefinite programming (SDP), a number of pre-processing techniques have been developed including chordal-completion procedures, which reduce the dimension of individual constraints by exploiting sparsity therein, and facial reduction, which reduces the dimension of the problem by removing redundant rows and columns.

• This paper suggest that these work in a complementary manner and that facial reduction should be used after chordal-completion procedures.
• In computational experiments on SDP instances from the SDPLib, a benchmark, and structured instances from polynomial and binary quadratic optimisation, we show that such two-step pre-processing with a standard interior-point method outperforms the interior point method, with or without the traditional pre-processing.