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

Consider positive weights $\pi_1, \ldots, \pi_n$ (one can suppose that they add up to $1$) and $n-1$ lengths $d_1, \ldots, d_{n-1}$. Is there an analytical solution to the following problem: find the configuration of $n$ vectors $X_1, \ldots, X_n \in \mathbb{R}^n$ that maximizes the weighted sum $$ V(X_1, \ldots, X_n) = \pi_1 \|X_1\|^2 + \ldots + \pi_n \| X_n\|^2 $$ under the constraints $\|X_{i+1}-X_i\| \leq d_i$ for $i=1, 2, \ldots, n-1$ and $\sum_i \pi(i) X_i = 0$.

Motivation: as described in this article, this is another formulation of the following problem: among all possible reversible Markov chain in continuous time that have $\Pi=(\pi_1, \ldots, \pi_n)$ as invariant distribution on $\{ 1, \ldots, n\}$ and that can only jump on neighbouring sites, find the one that has maximum spectral gap, under a certain (linear) constraint on the jump intensities.

Remarks:

  • one can consider the more general problem where the constraints are $\|X_i-X_j\| \leq d_{i,j}$: one can show that this is equivalent to a semidefinite programming optimization problem. It seems in general hard to solve; see above mentioned article.
  • the case $\pi(1) = \ldots = \pi(n)$ is exactly solvable and an optimal configuration is a set of $n$ collinear vectors $X_i = \alpha_i U$, where the $\alpha_i$'s are easily computable; in this case, the problem is equivalent to maximizing $\sum_{i,j} \|X_i-X_j\|^2$.
share|improve this question
    
Alekk, the article link is broken... –  Joseph O'Rourke Jan 20 '11 at 15:38
    
thanks: should be fixed now. –  Alekk Jan 20 '11 at 16:45
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.