An efficient implementable inexact entropic proximal point algorithm for a class of linear programming problems

Hong T. M. Chu, Ling Liang, Kim-Chuan Toh, Lei Yang

TL;DR

This paper introduces a new algorithm, iEPPA, for a specific type of large-scale linear programming (LP) problem that arises in areas like optimal transport and discrete tomography. The algorithm is designed to be efficient and numerically stable, overcoming limitations of existing methods, and is demonstrated to perform well on synthetic data for these applications.

What Problem Does This Paper Address?

Many real-world problems, such as optimal transport (moving goods from supply to demand points at minimum cost) and discrete tomography (reconstructing an image from its projections), can be formulated as linear programming (LP) problems. The authors focus on a particular class of LP problems with a special structure that makes them challenging to solve, especially when they become very large. Existing methods for these problems, particularly those using entropic regularization, can suffer from numerical instability and slow convergence, especially when high accuracy is required. This paper aims to develop a more efficient, implementable, and robust algorithm for this class of LPs.

Methods

The core of the paper is the development of an implementable inexact entropic proximal point algorithm (iEPPA). This algorithm tackles the LP problem by iteratively solving a sequence of subproblems. The key innovations are:

  • Inexact Stopping Condition: The iEPPA uses a novel, practically verifiable stopping condition for solving these subproblems. This is crucial for making the algorithm implementable and ensuring convergence without requiring extremely precise solutions at each step.
  • Dual Block Coordinate Descent (BCD): To efficiently solve the subproblems, the authors employ a dual BCD method. This method leverages the special structure of the problem's constraints to derive a more tractable dual problem, which is then solved iteratively by updating blocks of variables.
  • Leveraging Problem Structure: The algorithm heavily relies on a specific structural property of the constraints (Assumption 1), which states that the non-zero patterns of certain constraint matrices do not overlap. This property is key to deriving closed-form solutions for the BCD subproblems, making the overall algorithm efficient.

Datasets

The paper evaluates the proposed iEPPA algorithm on:

  • Synthetic data for 2-marginal and 3-marginal Capacity Constrained Multi-Marginal Optimal Transport (CMOT) problems: These are generated datasets designed to mimic real-world scenarios.
  • Discrete tomography problems: The authors use five ground-truth images of size 256x256 and generate tomographic projections to create test cases.

No new datasets were introduced; existing problem formulations were used for evaluation.

Key Insights and Ideas

  • The power of a "practically checkable" stopping condition: The authors highlight that existing inexact conditions for proximal point algorithms are often hard to implement. Their new condition makes the algorithm truly practical without sacrificing convergence guarantees.
  • Dual BCD as an efficient subsolver: By reformulating the subproblem into its dual form and applying BCD, the authors achieve significant computational advantages, especially due to the specific structure of the problem.
  • Bypassing numerical instability: The iEPPA's design, particularly its ability to not require very small proximal parameters, helps it avoid the numerical issues that plague other entropic regularization methods.
  • Modeling flexibility: The proposed LP formulation (1.1) is shown to be more flexible than previous approaches for problems like discrete tomography, avoiding the need for high-order tensors.

Key Results

  • Efficiency: The iEPPA algorithm consistently outperforms the DyKL algorithm (a state-of-the-art method for similar problems) in terms of both computational time and accuracy for 2-marginal CMOT problems. It also shows comparable or better accuracy than Gurobi (a commercial solver) with significantly less CPU time and memory usage for large-scale problems.
  • Scalability: The iEPPA demonstrates good scalability, with computational time growing almost linearly with problem size, making it suitable for large-scale CMOT problems.
  • Accuracy: The iEPPA achieves normalized objective function values at the level of $10^{-5}$, while DyKL often settles for $10^{-4}$.
  • Discrete Tomography: Preliminary experiments show that the proposed LP model can faithfully recover ground-truth images, with reconstruction quality improving as more projections are used.

Limitations and Future Work

  • Assumption 1: The efficiency of the dual BCD subsolver relies heavily on Assumption 1, which requires specific non-overlapping patterns in the constraint matrices. While the authors note this structure appears in applications, its general applicability might be a limitation.
  • Discrete Tomography Investigation: The authors state that their experiments on discrete tomography are preliminary and a thorough numerical investigation is left for future work.
  • Extension to Other Problems: The authors suggest that their iEPPA+BCD framework could potentially be extended to solve other classes of LP problems, such as two-stage and multi-stage stochastic network problems, which they leave as a future research topic.

Summary updated

Abstract

We introduce a class of specially structured linear programming (LP) problems, which has favorable modeling capability for important application problems in different areas such as optimal transport, discrete tomography, and economics. To solve these generally large-scale LP problems efficiently, we design an implementable inexact entropic proximal point algorithm (iEPPA) combined with an easy-to-implement dual block coordinate descent method as a subsolver. Unlike existing entropy-type proximal point algorithms, our iEPPA employs a more practically checkable stopping condition for solving the associated subproblems while achieving provable convergence. Moreover, when solving the capacity constrained multi-marginal optimal transport (CMOT) problem (a special case of our LP problem), our iEPPA is able to bypass the underlying numerical instability issues that often appear in the popular entropic regularization approach, since our algorithm does not require the proximal parameter to be very small in order to obtain an accurate approximate solution. Numerous numerical experiments show that our iEPPA is efficient and robust for solving some large-scale CMOT problems on synthetic data. The preliminary experiments on the discrete tomography problem also highlight the potential modeling capability of our model.
BibTeX
@article{chu2023efficient,
  author = {Hong T. M. Chu and Ling Liang and Kim-Chuan Toh and Lei Yang},
  title = {{An efficient implementable inexact entropic proximal point algorithm for a class of linear programming problems}},
  journal = {Comput. Optim. Appl.},
  year = {2023},
  doi = {10.1007/s10589-023-00459-2},
}

Loading related content...

Figure