Constrained Optimization and Spanning Tree Polytope

[cuent]

Hi, is this the correct place to ask questions?

I am currently working on a concave function $\max_\mu \mathcal{F(\mu)}$, where $\mu\in\mathbb{T}(G)$. Here, $\mathbb{T}(G)$ represents the spanning-tree polytope, and it has the following constraints for the graph $G=(V, E)$:

1. $\sum_{i\in E} \mu_i = n-1 $
2. $\sum_{i\in F\subseteq E} \mu_i <= |E[F]| - 1 $
3. $\mu_i\geq 0$

This problem can be efficiently solved using the Maximum Spanning Tree algorithm, seen as a Linear Program, since $\mathcal{F(\mu)} $ represents the Bethe free energy and its gradient is $\nabla\mathcal{F(\mu)}=\text{Mutual Information}(\mu)$.

I am currently exploring the use of constrained optimization with jaxopt. However, I am facing challenges in setting up the projection, particularly when dealing with expanding subsets $F$ that depend on the complexity of the graph. This approach may not be scalable.

Do you have any suggestions on how I can proceed or if there is a better alternative approach?

[mblondel]

Maybe you could use Frank-Wolfe instead? (not supported in JAXopt)

[mblondel]

For questions not directly related to JAXopt, "Discussions" would be better than "Issues".

[fabianp]

For questions not directly related to JAXopt, "Discussions" would be better than "Issues".

we should probably have a contact section in the doc explaining what is the preferred entry point to report bugs / ask questions / etc.

[cuent]

Moved this to discussions thanks :)