Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
If the function is convex, can't you restrict trivially to spectral radius=1? –  Federico Poloni Sep 16 '10 at 19:21
    
Well, I want <1, but restricting to, say, 1/2 would be useful, how would I do that? –  Yaroslav Bulatov Sep 16 '10 at 20:45
    
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. –  Federico Poloni Sep 17 '10 at 2:04
add comment

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
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) –  Yaroslav Bulatov Sep 17 '10 at 18:03
    
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? –  Yaroslav Bulatov Sep 21 '10 at 20:59
    
Ben-Tan and Nemirovski is the bible for semidefinite modelling, so you should start looking there. –  F_G Sep 22 '10 at 10:03
add comment

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.

share|improve this answer
    
Does invariance under conjugation matter if my objective and constraints only involve real numbers? Also, I added the complete problem description –  Yaroslav Bulatov Sep 17 '10 at 4:42
    
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? –  Bill Thurston Sep 17 '10 at 5:23
    
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$ –  Yaroslav Bulatov Sep 17 '10 at 8:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.