#### 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)

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