Optimal rounding a sequence of reals to integers I'm given positive real numbers $c_1,\dots,c_m \in \mathbb{R}$ and an integer $d \in \mathbb{N}$.  My goal is to find non-negative integers $x_1,\dots,x_m \in \mathbb{N}$ that minimize $\sum_i (x_i - c_i)^2$, subject to the requirement $\sum_i x_i = d$.
I'm inclined to suspect that there exists $t \in \mathbb{R}$ such that the optimal solution is $x_i = \lfloor t c_i \rceil$ for all $i$ (i.e., take $x_i$ to be $tc_i$ rounded to the nearest integer).  Is this the case?
My first instinct was to apply Lagrange multipliers, but I guess that doesn't work given the requirement that $x_1,\dots,x_m$ be integers.

Motivation: I'm trying to help with someone's quantization problem, but the problem seems fun in its own right.
 A: This is an MIQP (Mixed Integer Quadratic Programming) problem. This version is the easy one: convex. That means there are quite a few good solvers available to handle this. Still, finding proven global optimal solutions is often difficult. On the other hand, solvers find typically good solutions very quickly. For $n=1000$ a good solver should take no more than a few seconds to find a global optimal solution. 
A: Given $\mathrm c > 0_n$ and $d \in \mathbb N$,
$$\begin{array}{ll} \text{minimize} & \| \mathrm x - \mathrm c \|_2\\ \text{subject to} & 1_n^{\top} \mathrm x = d\\ & \mathrm x \in \mathbb N^n\end{array} \tag{OP1}$$
Dropping the nonnegativity constraints,
$$\begin{array}{ll} \text{minimize} & \| \mathrm x - \mathrm c \|_2\\ \text{subject to} & 1_n^{\top} \mathrm x = d\\ & \mathrm x \in \mathbb Z^n\end{array} \tag{OP2}$$
From the equality constraint $1_n^{\top} \mathrm x = d$, we obtain the parametrization
$$\mathrm x = \underbrace{\begin{bmatrix} -1_{n-1}^{\top}\\ \mathrm I_{n-1}\end{bmatrix}}_{=: \mathrm A} \, \mathrm z + d \, \mathrm e_1 = \mathrm A \mathrm z + d \, \mathrm e_1$$
where $\mathrm z \in \mathbb Z^{n-1}$ and $\mathrm e_1 := (1,0,\dots,0)$. Thus, the objective function is
$$\| \mathrm x - \mathrm c \|_2 = \| \mathrm A \mathrm z - \underbrace{(\mathrm c - d \, \mathrm e_1)}_{=: \mathrm b} \|_2 = \| \mathrm A \mathrm z - \mathrm b \|_2$$
and we have the integer least-squares (ILS) problem
$$\underset{\mathrm z \in \mathbb Z^{n-1}}{\text{minimize}} \quad \| \mathrm A \mathrm z - \mathrm b \|_2 \tag{ILS}$$
This problem is also known as the closest vector problem (CVP), as we would like to find the point in the $(n-1)$-dimensional integer lattice $\{ \mathrm A \mathrm z \mid \mathrm z \in \mathbb Z^{n-1} \} \subset \mathbb Z^n$ that is closest to a given vector $\mathrm b \in \mathbb R^n$. Suppose that we find $\hat{\mathrm z}$, the solution of the ILS. Hence,
$$\hat{\mathrm x} := \mathrm A \hat{\mathrm z} + d \, \mathrm e_1$$
is the solution of OP2. If $\hat{\mathrm x} \geq 0_n$, then $\hat{\mathrm x}$ is also the solution of OP1. If it is not the case that $\hat{\mathrm x} \geq 0_n$, then $\hat{\mathrm x}$ is somewhat useless and we have wasted our time.
To find an approximate solution to the CVP, we could use function NearVector of the LLL module of Victor Shoup's NTL C++ library.



*

*Babak Hassibi and Haris Vikalo, Maximum-likelihood decoding and integer least-squares: the expected complexity, in Multiantenna Channels: Capacity, Coding and Signal Processing, J. Foschini and S. Verdu, Eds., American Mathematical Society, 2003.

*Babak Hassibi and Haris Vikalo, On the expected complexity of integer least-squares problems, Proceedings of the 2002 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 1497-500.

*Arash Hassibi, Stephen Boyd, Integer parameter estimation in linear models with applications to GPS, IEEE Transactions on Signal Processing, Vol. 46, No. 11, November 1998.

*Chris Peikert, Lattices in Cryptography, Fall 2013.

*Oded Regev, Lattices in Computer Science, Fall 2009.
A: Omitting the constraint, $x_i = \lfloor c_i \rceil$ is clearly optimal. Now if you perform scaling like you propose to satisfy the constraint, you move "large numbers" further away from $c_i$ than necessary. For example, with $c_1=10$, $c_2=20$, $d=10$, your solution approach results in $x=(3,7)$, while $x=(0,10)$ is a better solution (objective value $\sqrt{218}$ vs $\sqrt{200}$).
Intuitively, all numbers in the final solution should be equally close to $c_i$, since deviations are penalized quadratically. So, the first thing you do is set $x_i = \lfloor c_i \rceil$ and compute $t = \sum_i x_i$. If $t=d$, you are done. Otherwise, you have to adjust. Let me assume $t > d$ (the case for $t < d$ is similar). Then you need to subtract a total $d-t$ from the $x_i$. The best numbers to take this from are the ones you rounded up, so round them down instead, the ones with largest $x_i-c_i$ first. Then subtract $1$ from each $x_i$ in the order of $c_i-x_i$ (smallest first) until $\sum_i x_i = d$. If at the start, $d-t$ is large, you can start by subtracting $\lfloor (d-t)/n \rfloor$ from each number.
A: LinAlg's greedy algorithm is correct.  I will sketch a proof of correctness here.
The greedy algorithm. As a refresher, the algorithm is as follows:


*

*Set $v_i := \lceil c_i \rfloor$ for each $i=1,2,\dots,n$.  Set $t := v_1 + \dots + v_n$.

*While $t < d$:


*

*Let $i^* = \arg\min_i v_i - c_i$.  Then, increment $v_{i^*}$, and set $t := v_1 + \dots + v_n$.


*While $t > d$:


*

*Let $i^* = \arg\max_i \{v_i-c_i : v_i > 0\}$.  Then, decrement $v_{i^*}$, and set $t := v_1 + \dots + v_n$.



Note that only one of the two while-loops will execute, and when this terminates, we'll have a feasible solution.
Intuition.  The idea is that, at each iteration, the algorithm makes the locally optimal choice of which element to increment/decrement, in a way that increases the objective function as little as possible (or decreases it as much as possible).  Define the residuals as $r_i = x_i - c_i$ and the objective function $\Phi = \sum_i r_i^2$.  Then incrementing $x_i$ increases the objective function by $1+2r_i$, so the best choice to increment is the element with the smallest residual.
Of course, this only proves that the algorithm makes locally-optimal choices at each step; it does not prove that it terminates with a globally-optimal solution to the original problem.  For that, we need a proof of correctness, sketched next.
Proof of correctness.  We can show that this finds the optimal solution by induction on the number of iterations of the while loop.  Without loss of generality, let's assume only the while loop in line 2 executes, not the while loop in line 3; similar arguments will apply in the other case.  The inductive predicate is:

At the beginning of each iteration of the while loop, $v_1,\dots,v_n$ is the optimal solution to the problem of minimizing $\sum_i (x_i-c_i)^2$ subject to the requirement $\sum_i x_i = t$.

Notice that we've replaced $d$ with $t$, so at each iteration, $v_1,\dots,v_n$ is a solution to a variant of the original problem where we've tweaked the requirement on what the values must sum to.
To prove the base case, we show that after line 1, the inductive predicate holds.  We'll use an exchange argument.  Let $v_1,\dots,v_n$ be the actual values selected in line 1, and suppose they're not the optimal solution (given the constraint that they must sum to $t$).  Let $v'_1,\dots,v'_n$ be an optimal solution.  Since both solutions sum to $t$ but they aren't the same, there must be an index $j$ where $v'_j > v_j$ and an index $k$ where $v'_k < v_k$.  Now define $v''_1,\dots,v''_n$ by $v''_j=v'_j-1$, $v''_k=v'_k$, and $v''_i=v'_i$ for all other positions.  I claim that $v''_1,\dots,v''_n$ is an even better solution to the original problem.
Why?  Well, since $v_j$ was constructed by rounding $c_j$ to the nearest integer, we know $v_j -c_j > -0.5$.  Since $v'_j \ge v_j+1$, we know $v'_j-c_j > 0.5$.  Therefore
$$(v''_j-c_j)^2 - (v'_j-c_j)^2 = (v'_j-1-c_j)^2 - (v'_j-c_j)^2
 = 1 - 2(v'_j-c_j) < 0.$$
In other words, changing $v'_j$ to $v''_j$ has strictly decreased the objective function.  A similar argument shows that changing $v'_k$ to $v''_k$ cannot increase the objective function.  Therefore, the net effect of moving from $v'$ to $v''$ is to strictly decrease the objective function, i.e., $v''$ is a better solution than $v'$.  This contradicts the assumed optimality of $v'$, so the only conclusion is that our starting supposition (that $v_1,\dots,v_n$ isn't optimal) must have been wrong.
This proves the base case.  Phew, that was tedious, but it could be worse.
Next, we need to prove the inductive step.  In other words, if $v_1,\dots,v_n,t$ are the values at the beginning of one iteration, and the in the previous iteration we values $u_1,\dots,u_n,t-1$, which by assumption satisfy the inductive property (that $u_1,\dots,u_n$ is an optimal solution subject to the constraint that they sum to $t-1$), then we need to prove that $v_1,\dots,v_n,t$ also satisfy the inductive property (that $v_1,\dots,v_n$ is an optimal solution subject to the constraint that they sum to $t$).  Then if $v$ isn't optimal, we show that we can transform an optimal solution $v'$ (summing to $t$) to an optimal solution $u'$ (summing to $t-1$); if $v\ne v'$, then $u \ne u'$.  The argument is tedious and goes similarly to the base case above.
Perhaps someone can find a cleaner, simpler proof?
Efficiency. There are ways to speed up the above algorithm if it is going to do many iterations (if $|d-t|$ is large initially).  We can get the running time down to something like $O(n \log n)$ arithmetic operations.  Sort the residuals $r_1,\dots,r_n$ to put them in increasing order $r_{i_1},\dots,r_{i_n}$.  Then if $r_{i_2}-r_{i_1}>1$, we can predict that index $i_1$ will be chosen for the next $\lfloor r_{i_2}-r_{i_1} \rfloor$ iterations, and we can simulate all of those iterations in a single step.  If $r_{i_2}-r_{i_1}<1$ but $r_{i_3}-r_{i_1}>1$, we can predict that the next iterations will alternate between $i_1$ and $i_2$, and we can simulate the effect of all of the iterations until we reach a point where $r_{i_3}-r_{i_1}<1$.  And so on.
