iEPPA

iEPPA : a MATLAB software for solving a class of structured LPs based on an inexact entropic proximal point algorithm 
Hong T.M. Chu, Ling Liang, Kim-Chuan Toh, and Lei Yang
Corresponding author: Lei Yang (yanglei.math@gmail.com)

This is a software package for solving a class of structured linear programming problems of the form:
\begin{eqnarray*}
\begin{array}{rl}
\mbox{(SLP)} \quad \min & \langle C, X \rangle \\
\mbox{s.t.} & {\cal A}^{(i)}(X) = b^{(i)}, \quad i = 1,\ldots, N \\
& 0 \leq X \leq U, \quad X \in \mathbb{R}^{n_1\times n_2}
\end{array}
\end{eqnarray*}
where \(C,U\in\mathbb{R}^{n_1\times n_2}\), \(b^{(i)} \in \mathbb{R}^{m_i}\) are given data, and for each \(i\), \({\cal A}^{(i)} : \mathbb{R}^{n_1\times n_2} \rightarrow \mathbb{R}^{m_i}\) is a given linear map defined by
$$
{\cal A}^{(i)} (X) = \left[ \begin{array}{c} \langle A^{(i)}_1, X\rangle \\ \vdots \\ \langle A^{(i)}_{m_i}, X\rangle
\end{array} \right]
$$
and the constraint matrices \( \{ A^{(i)}_1, \ldots, A^{(i)}_{m_i} \} \) are binary (\(0\)-\(1\)) matrices  satisfying the property that for all
\(1\leq j < k \leq m_i\), \(A^{(i)}_j \circ A^{(i)}_k = 0 \), i.e., the non-zero patterns of \(A^{(i)}_j\) and \(A^{(i)}_k\) do not overlap.
The above problem includes an optimal transport LP as a special case, which is given by
\begin{eqnarray*}
\min \big\{ \langle C, X \rangle \mid Xe = b^{(1)}, \; X^\top e = b^{(2)}, \; X \geq 0 \big\}.
\end{eqnarray*}
An inexact entropic proximal-point algorithm is developed to solve (SLP); details can be found in the following reference, where higher order tensor variable is also allowed.

  • H.T. Chu, L. Liang, K.C. Toh, and L. Yang, An efficient implementable inexact entropic proximal point algorithm for a class of linear programming problems, Computational Optimization and Applications, in print. arXiv:2011.14312
  • Codes available at here