Shannon-and von neumann-entropy regularizations of linear and semidefinite programs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910905040633856 |
|---|---|
| author | Chhatoi, Saroj Prasad Lasserre, Jean B |
| author_facet | Chhatoi, Saroj Prasad Lasserre, Jean B |
| contents | We consider the LP in standard form min {c T x\,: Ax = b; x $\ge$ 0} and inspired by $ε$-regularization in Optimal Transport, we introduce its $ε$-regularization ''min {c T x + $ε$ f (x)\,: Ax = b; x $\ge$ 0}'' via the (convex) Boltzmann-Shannon entropy f (x)\,:= i x i ln x i . We also provide a similar regularization for the semidefinite program ''min {Tr(C $\bullet$ X)\,: A(X) = b; X 0}'' but with now the so-called Von Neumann entropy, as in Quantum Optimal Transport. Importantly, both are not barriers of the LP and SDP cones respectively. We show that this problem admits an equivalent unconstrained convex problem max $λ$$\in$R m G$ε$($λ$) for an explicit concave differentiable function G$ε$ in dual variables $λ$ $\in$ R m . As $ε$ goes to zero, its optimal value converges to the optimal value of the initial LP. While it resembles the log-barrier formulation of interior point algorithm for the initial LP, it has a distinguishing advantage. Namely for fixed $λ$, G$ε$($λ$) is obtained as a minimization over the whole space x $\in$ R d (and not over x $\ge$ 0) to still obtain a nonnegative solution x($λ$) $\ge$ 0, whence an explicit form of G$ε$ very useful for its unconstrained maximization over R m . |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_23815 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Shannon-and von neumann-entropy regularizations of linear and semidefinite programs Chhatoi, Saroj Prasad Lasserre, Jean B Optimization and Control We consider the LP in standard form min {c T x\,: Ax = b; x $\ge$ 0} and inspired by $ε$-regularization in Optimal Transport, we introduce its $ε$-regularization ''min {c T x + $ε$ f (x)\,: Ax = b; x $\ge$ 0}'' via the (convex) Boltzmann-Shannon entropy f (x)\,:= i x i ln x i . We also provide a similar regularization for the semidefinite program ''min {Tr(C $\bullet$ X)\,: A(X) = b; X 0}'' but with now the so-called Von Neumann entropy, as in Quantum Optimal Transport. Importantly, both are not barriers of the LP and SDP cones respectively. We show that this problem admits an equivalent unconstrained convex problem max $λ$$\in$R m G$ε$($λ$) for an explicit concave differentiable function G$ε$ in dual variables $λ$ $\in$ R m . As $ε$ goes to zero, its optimal value converges to the optimal value of the initial LP. While it resembles the log-barrier formulation of interior point algorithm for the initial LP, it has a distinguishing advantage. Namely for fixed $λ$, G$ε$($λ$) is obtained as a minimization over the whole space x $\in$ R d (and not over x $\ge$ 0) to still obtain a nonnegative solution x($λ$) $\ge$ 0, whence an explicit form of G$ε$ very useful for its unconstrained maximization over R m . |
| title | Shannon-and von neumann-entropy regularizations of linear and semidefinite programs |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2503.23815 |