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

Consider $J = \sum_{i=0}^{N}y_{i-1}x_{i}y_{i+1}$ where $+$ and $-$ in the indices are mod $N+1$. Let $x_{i} = 1 - y_{i} \in \{0,1\}$. What are some of the tools useful and relaxation techniques available to maximize $J$ or any other symmetric multivariate polynomial?

share|improve this question
1  
Optimizing the given $J$ should not be thought of as a polynomial optimization problem, but rather a very simple combinatorial problem. As such it is not really appropriate for this site. The question of arbitrary $J$ is probably too general to get a good answer, especially since the given $J$ is poor motivation for it. If you're having trouble maximizing the given $J$, feel free to ask on math.stackexchange.com. –  Noah Stein Dec 20 '11 at 14:01
1  
@Noah: this sort of comment can be summarized as: "I am smarter than you, nyah, nyah". If you want to give the OP a hint, by all means, but otherwise this is not appropriate. –  Igor Rivin Dec 20 '11 at 14:35
1  
I intended no offense and so I apologize if any was taken. –  Noah Stein Dec 21 '11 at 1:55
    
@Noah, this is for unknown to comment on, but it is all in the spin :) Anyway, no harm done, I am sure. –  Igor Rivin Dec 21 '11 at 11:22
1  
This seems more suitable for artofproblemsolving, but anyway: Since the polynomial is linear in each variable $y_i$ separately (once $N>2$), we may assume each $y_i \in \lbrace 0, 1 \rbrace$ (even if the intention was to just limit to the hypercube $0 \leq y_i \leq 1$. So we're just asking for the maximal number of 010 patterns in a cycle of $N+1$ zeros and ones. Since no two consecutive triples can be 010, the count is at most $\lfloor (N+1)/2 \rfloor$, and this is easily attained, and only by 010101... and its cyclic shifts (a total of $2$ if $N$ is even and $N+1$ if $N$ is odd). –  Noam D. Elkies May 17 '13 at 17:11

2 Answers 2

For the particular polynomial, you don't need any fancy techniques, as opaquely pointed out by @Noah Stein: you write $J=-\sum_{i=0}^n y_{i-1}y_i y_{i+1} + \sum_{i=0}^n y_{i-1}y_{i+1}.$ Both the first and the second sums depend fairly simply on the pattern of runs of $1$s and $0$s in your sequence $y_0, \dotsc, y_n$ -- I leave it to you to work out the details, which are not too hard.

In general, you are trying to maximize a sum of boolean monomials, and that is both a hard and and often-arising problem. One relaxation is to replace your variables $y_i$ by $z_i^\alpha,$ where $z_i$ are continuous in [0, 1], and $\alpha$ is a positive real number. As $\alpha$ goes to infinity, the problem becomes discrete, and one can try simulated annealing to deal with the continuous problem -- there are no general techniques, since the function is generally not convex, so you have to slaughter many goats and hope for the best (nonetheless, I am ashamed to admit that many centuries ago I was one of the inventors on a patent based on the above idea for the purpose of VLSI testing).

share|improve this answer
    
Hi Igor: Could you please let me know of the patent idea? Also this is a naturally occuring problem in graph theory. the polynomial I have portrayed is the basic step. There are some tensor formulations. There is one more thing: I have managed to get $J$ or any such $J$ as a trace of some matrix power. Would this matrix help in anyway(like looking at the eigenvalues since Trace of matrix power is sum of powers of eigen values)?? –  Turbo Dec 20 '11 at 23:19
    
Igor, you wrote the subtraction backwards in your expression for $J$ -- it's $x_i=1-y_i$, not $y_i-1$. (This dawned on me after staring at your expression and thinking that, in trying to maximize it, you can't get a 1 in the triple product sum without subtracting a corresponding 1 in the double product sum, so you might as well not even try. But of course that's the opposite of what the OP wants.) I'd make the edit myself if I had the clout. –  Barry Cipra Dec 21 '11 at 1:33
    
@Barry, yes, it occurred to me immediately after I did it, but I was in bed then :) Will fix. –  Igor Rivin Dec 21 '11 at 11:01
    
@unknown: there is a paper called "discrete test generation by continuous methods", and a patent called "testing VLSI circuits for defects". I am at home so cannot download the paper right now (that's the thing to look at, though google patent search will tell you all about the patent). I would certainly be interested to know where the problem comes from.. Looking at the eigenvalues is a very reasonable idea (for something related see "counting cycles and finite dimensional $L^p$ norms, by yours truly [there is an arxiv preprint and a paper). –  Igor Rivin Dec 21 '11 at 11:26
    
Sorry, both the paper and the patent are joint with S. Chakradhar. –  Igor Rivin Dec 21 '11 at 12:44

The optimization is a summation of triples over a cycle. You can enumerate the value of a few binary variables to break the cycle down to a (second-order) Markov chain. Then dynamic programming can be used to solve this problem efficiently.

To elaborate, consider enumerating $x_0$ and $x_N$, which are both binary variables. Then the cycle becomes a chain in which the first term contains only $x_1$ (since $x_0$ and $x_N$ are known), the second term contains only $x_1$ and $x_2$ ($x_0$ is known), and similarly for the last two terms. The rest terms still contain three x's.

Then if we consider state $s_i = [x_i, x_{i+1}]$ (which has four possible choices), then the term $x_{i-1}y_ix_{i+1}$ can be written in $\phi_i(s_{i-1}, s_i)$ and the entire summation can be written as

$J = \sum_{i=2}^{N-2} \phi_i(s_{i-1}, s_{i})$

which can be solved efficiently by dynamic programming.

share|improve this answer
    
could you elaborate? –  Turbo May 17 '13 at 13:54
    
I have edited my answer. –  Yuandong May 17 '13 at 16:14
    
I like your approach. Let me think about it. –  Turbo May 18 '13 at 10:22

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.