Suppose $F(x)$ is a convex objective function on $n\times n$ matrices, and I need to numerically optimize $F$ with the condition that $x$ has spectral radius less than $1$. This might be too hard, so an approximation would be needed. Has this problem been studied before?


Motivation: Boltzmann machines are hard to evaluate when spectral radius of the weight matrix is large, especially if it's above $1$ so best fit to data subject to this constraint would give a useful model.


Example: Let $X=\{1,-1\}^d$ and $\hat{X}$ some list of $\{1,-1\}$ $d$-tuples. Find $$\max\_A \sum\_{x\in \hat{X}} \mathbf{x}'A\mathbf{x} - |\hat{X}|\log \sum\_{x\in X} \exp(\mathbf{x}'A\mathbf{x})$$
Where $A$ is symmetric real-valued $d\times d$ matrix with spectral radius < 1. This needs to be done in time polynomial in $d$ and linear in $|\hat{X}|$. When spectral radius is <1, belief propagation gives a reasonably accurate way to approximate gradient of this objective in $O(|\hat{X}|d^2)$ time



Optimizing over matrices with spectral radius <1?
If your matrices are symmetric, the set of matrices with spectral radius $\le 1$ is convex, and can be modelled using a linear matrix inequality (LMI), see e.g. [page 147 in Lectures on Modern Convex Optimization](http://books.google.com/books?id=M3MqpEJ3jzQC&lpg=PR1&ots=O2nXBEkTUU&dq=modern%2520convex%2520optimization&pg=PA147#v=onepage) by Ben-Tal and Nemirovski. If you wanted to *minimize* a convex objective that is also semidefinite-representable, you could in principle formulate and solve your problem as a semidefinite programming problem. However, *maximizing* a convex objective over a convex set is a much more difficult problem.


