Let $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I want to maximize $f$ on $N$. $f$ has the following form $$ f(n) = \sum_i A_i n_i -\sum_i \sum_{j\neq i} B_{ij} (n_i-n_j)^2 $$ where $A_i\geq 0$ and $B_{ij}\geq 0$ for all $i,j$. Note that $f$ is a quadratic and concave function when defined on $\mathbb{R}^I$.
I know that integer programing is in general a hard problem but I would like to find nontrivial conditions on $A$ and $B$ such that this problem is easy to solve. By easy to solve I mean that there is a procedure that is fast and that is guaranteed to find the global maximum.
What I have tried
I have tried the following way of solving the problem. Define the mapping $T$ for which the $i$th element is defined as $$(Tn)_i=\arg\max_{\tilde{n}_i\in N_i} f\left( \left\{ n_1,\dots,\tilde{n}_i,\dots,n_I\right\}\right)$$ and iterate on $T$ until convergence. This is essentially a coordinate ascent algorithm but in a discrete space.
A few remarks:
- We can look at the fixed points of $T$. The vector $n^*$ that maximizes $f$ is obviously a fixed point of $T$ (can't improve by deviating in any dimensions) but there might be multiple fixed points.
- The mapping $T$ is monotone in the sense that $n\geq n'$ implies $T(n)\geq T(n')$. As a result we can use Tarski's fixed point theorem to show that the (non empty) set of fixed point is a lattice. We can find a lower bound of that set by iterating on $T$ from $(0,\dots,0)$ and an upper bound by iterating from $(\bar{n}_1,\dots,\bar{n}_I)$. If both procedures end up on the same vector then there is a unique fixed point and it must be $n^*$.
- When it works that procedure is quite fast numerically but I don't know what conditions on $A$ and $B$ are needed for it to work.
- Under some conditions, $T$ might be a contraction mapping which would guarantee uniqueness but I haven't made much progress along that path yet.
Any help is appreciated! Also, if somebody has a good reference on these problems that would be useful.
