Timeline for Need help to find an efficient algorithm for the following problem!
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 30, 2011 at 15:05 | answer | added | lemire | timeline score: 1 | |
| Nov 29, 2011 at 3:32 | comment | added | Nilima Nigam | @Gilead, thanks - of course, you are correct. The constraint that the solution consist of integers renders it (very) hard. I think Xiao-wen Chang has some papers in this area, including one on box-constrained integer least squares: cs.mcgill.ca/~chang/pub/ChaH08.pdf | |
| Nov 28, 2011 at 18:40 | comment | added | Barry Cipra | @Gilead, if you catch it quickly enough, you can always "edit" a comment by deleting it (after making a copy) and reposting with the changes. | |
| Nov 28, 2011 at 17:03 | comment | added | Gilead | Sorry, the statements that the $x$ are integers and that the objective is quadratic are unrelated. Garrgh... I wish I could edit comments. | |
| Nov 28, 2011 at 16:58 | comment | added | Gilead | @Federico Poloni, this terminology is often associated with estimation problems. I think the OP meant to say that $x$ is a vector of random variables with an associated covariance matrix $A$. Usually $A$ is updated recursively, this in this instance, $A$ would be a constant covariance matrix and is used as a weighting matrix in the estimation problem. @Barry Cipra, you have hit the nail on the head. It is a quadratic integer programming problem. | |
| Nov 28, 2011 at 16:52 | comment | added | Gilead | @Nilima Nigam, I'm not sure that would work. Two considerations: $x$ are restricted to integers with bounds $0$ and $k$, and the objective is quadratic (well, with this form, one may be able to reformulate the bilinears terms into linear constraints by introducing dummy variables). At any rate, this makes an integer programming problem, which is not that trivial to solve. | |
| Nov 28, 2011 at 16:50 | comment | added | Barry Cipra | The question mathoverflow.net/questions/9531/… from a couple of years ago might be of some help here. | |
| Nov 28, 2011 at 12:22 | comment | added | Federico Poloni | What do you mean by "$A$ is the covariance matrix of $x$"? Is $A$ constant, or does it depend on $x$? | |
| Nov 28, 2011 at 5:53 | comment | added | Nilima Nigam | I suggest rephrasing this as locating the minimizer of $x^T A x - bx +c$, and then using the fact that $A$ is symmetric, and positive semi-definite, to use a Krylov method to solve the associate linear problem. | |
| Nov 28, 2011 at 4:29 | history | edited | chepukha | CC BY-SA 3.0 |
Correct some typos mentioned by other readers.
|
| Nov 28, 2011 at 4:25 | comment | added | chepukha | @Gerry: by $X$ I means the vectors $x$. @fedja: Yes, I actually means $1 \leq i,j \leq n, i \neq j$ | |
| Nov 27, 2011 at 14:49 | comment | added | fedja | Also it is not clear to me what the range of indices in the double sum is. I guess what was meant is just $i,j:1\le i,j\le n, i\ne j$ but that's certainly not what is written. | |
| Nov 27, 2011 at 11:20 | comment | added | Gerry Myerson | What is the $X$ that appears only at the end of the second sentence? | |
| Nov 27, 2011 at 5:05 | history | asked | chepukha | CC BY-SA 3.0 |