2025/06/12 by Briceño-Arias, Luis M., Treust, Maël Le
#90C25 and 65K05 #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2506.10849
In this paper, we present an efficient algorithm for solving a linear optimization problem with entropic constraints, a class of problems that arises in game theory and information theory. Our analysis distinguishes between the cases of active and inactive constraints, addressing each using a Bregman proximal gradient method with entropic Legendre functions, for which we establish a convergence rate of O(1/n) in objective values. For a specific cost structure, our framework provides a theoretical justification for the well-known Blahut-Arimoto algorithm and the uniqueness of the Lagrange multiplier associated with the entropic constraint. In the active constraint setting, we include a bisection procedure to approximate the strictly positive Lagrange multiplier. The efficiency of the proposed method is illustrated through comparisons with standard optimization solvers on a representative example from game theory, including extensions to higher-dimensional settings.