Scholarlink

<p>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 <i>O</i>(1/<i>n</i>) 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Bregman proximal gradient method for linear optimization under entropic constraints

  • 期刊论文

  • 发表日期：

    2026年5月20日

查看全文
  • Luis M. Briceño-Arias,
  • Maël Le Treust

摘要

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.