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)$. While Frank-Wolfe offers an optimal solution, I am unsure of how to seamlessly incorporate it into the implicit theorem as done in Projected Gradient Descent.

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?

[fabianp]

It is the right place to ask questions! Unfortunately I don't have any ideas on how to make your problem more scalable ...

[cuent]

I appreciate your response, Fabian.

I'm not certain if it's possible because of the constraint set containing all subsets of E. Even choosing certain subsets may be too difficult to compute, especially as the graph size increases. 😢