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?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
1
1
|
||||||||||||||||||||||||
|
|
1
|
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). |
|||||||||||||||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
1
|
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. |
|||||||||
|
