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?
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ 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. $\endgroup$– Noah SteinCommented Dec 20, 2011 at 14:01
-
1$\begingroup$ @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. $\endgroup$– Igor RivinCommented Dec 20, 2011 at 14:35
-
1$\begingroup$ I intended no offense and so I apologize if any was taken. $\endgroup$– Noah SteinCommented Dec 21, 2011 at 1:55
-
$\begingroup$ @Noah, this is for unknown to comment on, but it is all in the spin :) Anyway, no harm done, I am sure. $\endgroup$– Igor RivinCommented Dec 21, 2011 at 11:22
-
1$\begingroup$ 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). $\endgroup$– Noam D. ElkiesCommented May 17, 2013 at 17:11
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
6
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).
answered Dec 20, 2011 at 22:50
-
$\begingroup$ 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)?? $\endgroup$– TurboCommented Dec 20, 2011 at 23:19
-
$\begingroup$ 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. $\endgroup$ Commented Dec 21, 2011 at 1:33
-
$\begingroup$ @Barry, yes, it occurred to me immediately after I did it, but I was in bed then :) Will fix. $\endgroup$ Commented Dec 21, 2011 at 11:01
-
$\begingroup$ @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). $\endgroup$ Commented Dec 21, 2011 at 11:26
-
$\begingroup$ Sorry, both the paper and the patent are joint with S. Chakradhar. $\endgroup$ Commented Dec 21, 2011 at 12:44
$\begingroup$
$\endgroup$
3
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.
-
-
-
$\begingroup$ I like your approach. Let me think about it. $\endgroup$– TurboCommented May 18, 2013 at 10:22