4
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ If the function is convex, can't you restrict trivially to spectral radius=1? $\endgroup$
    – Federico Poloni
    Commented Sep 16, 2010 at 19:21
  • $\begingroup$ Well, I want <1, but restricting to, say, 1/2 would be useful, how would I do that? $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 16, 2010 at 20:45
  • $\begingroup$ By convexity, $f(\frac{a+b}2) \leq \frac{f(a)+f(b)}2$, therefore one among $f(a)$ and $f(b)$ is larger (or equal) than $f(\frac{a+b}2)$. So the supremum cannot occur on an inner point (i.e., one that you can write as the midpoint of two other points in the set). So you are can restrict wlog to the boundary of your (convex) set. $\endgroup$
    – Federico Poloni
    Commented Sep 17, 2010 at 2:04

2 Answers 2

Reset to default
5
$\begingroup$

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 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Good observation, I re-examined the underlying problem, and looks like it comes down to minimizing a convex objective (or maximizing concave negation, as it's more frequently presented) $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 17, 2010 at 18:03
  • $\begingroup$ Thanks, that formula seems pretty useful. But I still don't know how to turn it into Semidefinite Programming since my objective is not linear...do you have a good reference for some examples of how that's done? $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 21, 2010 at 20:59
  • $\begingroup$ Ben-Tan and Nemirovski is the bible for semidefinite modelling, so you should start looking there. $\endgroup$
    – F_G
    Commented Sep 22, 2010 at 10:03
5
$\begingroup$

This started as a comment, but it's too long.

Is the objective function invariant under conjugation?

Spectral radius is far from a convex function of matrices. If you take two non-negative matrices with 1's on the diagonal, one zero below the diagonal and positive above, the other vice versa, any convex combination has spectral radius bigger than 1. It's easy to make the spectral radius as large as you like.

The set of characteristic polynomials for matrices of spectral radius 1 isn't convex either. For example, the average of $(x - .99)^2$ and $(x - .99i)^2$ has roots outside the unit circle.

However, every conjugacy class in $GL(n,\mathbb C)$ has a representative that is upper triangular, and the upper triangular matrices of spectral radius 1 form a convex set. This may make it easier to find the optimum (depending what it is, which you didn't say). There are convex sets containing just conjugacy classes of spectral radius < 1 for various other kinds of matrices.

Even if the function is not invariant under conjugation, it may help to break it up by conjugacy class: for each conjugacy class, find the optimum, then find the optimum among all conjugacy classes.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Does invariance under conjugation matter if my objective and constraints only involve real numbers? Also, I added the complete problem description $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 17, 2010 at 4:42
  • $\begingroup$ No, with the added information, you're using $A$ as a quadratic form, and as FG noted, spectral radius is a convex function among those, and the potential function is not invariant by a significant group. But: as you've phrased it, $\hat(X)$ might contain exponentially many $d$-tuples, so to evaluate the function just once already could take exponential time. Are you asking about probabilistic algorithms? $\endgroup$
    – Bill Thurston
    Commented Sep 17, 2010 at 5:23
  • $\begingroup$ Actually $O(|\hat{X}|)$ time is acceptable because $\hat{X}$ represents the input to the optimizer which is small compared to $2^d$. A typical value would be $|\hat{X}|<10,000$, $d<1000$ $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 17, 2010 at 8:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .