Can an optimal weighted average ever have negative weights? I've got a few measurements $\vec{x}$ for some real-world value $\hat{x}$. These measurements have some uncertainty, and are correlated. Given these estimates, and their covariances, I want to take some kind of weighted average of the estimates
$$\bar{x} = \sum_i w_i x_i = \vec{w} \cdot \vec{x}$$
Naturally, I want my weights to sum up to 1:
$$\sum_i w_i = 1 = \vec{w} \cdot \vec{1}$$
I want to choose my weights such that my uncertainty around this estimate is as low as possible, so I want to minimize:
$$\mathbb{E} \left[ \left( \bar{x} - \hat{x} \right)^2 \right] = \sum_i \sum_j w_i w_j C_{i,j} = \vec{w}^T C \vec{w}$$
where $C$ is the covariance matrix of the errors of my measurements: $C_{i,j}=\mathbb{E} \left[ x_i - \hat{x}, x_j - \hat{x} \right]$.
Minimizing this under the constraint that the weights sum up to 1 can be done using a Lagrange multiplier, and (assuming I did everything right) results in:
$$ C \cdot \vec{w^*} = \vec{1}$$
$$ \vec{w} = \vec{w^*} / \sum \vec{w^*} $$
Note that the latter step is just rescaling $\vec{w^*}$ to sum up to 1, so I'm mostly interested in the solution of $\vec{w^*}$:
$$ \vec{w^*} = C^{-1} \cdot \vec{1}$$
This procedure results in negative weights. This doesn't make sense for me intuitively. (E.g. if I have just one estimate $x_1$ of 100, then obviously my total estimate $\bar{x}$ will also be 100. How could the introduction of another measurement, of 110, make it so my overall estimate $\bar{x}$ lowers to below 100?) So I suspect that I'm doing something wrong, like using an inconsistent covariance matrix. But is it definite that I am doing something wrong?
Can the above procedure reasonably return negative weights? How would this make sense in terms of the actual implications of what I'm trying to do (take a weighted average of multiple estimates)?
 A: In addition to the other excellent answer.  Yes, it can give negative weights, in some cases, even if that can look counterintuitive. Let us see. First, I will go through solving the minimization problem (and I will simplify your notation, replacing $\vec{w}$ with $w$ and so on).
Introducing the Lagrange multiplier $\lambda$, define
$$ L(w)= w^T C w -2 \lambda (w^T 1-1). $$ Then we find the partial derivatives 
$$ \frac{\partial L}{\partial \lambda}= w^T 1 - 1 \\ \frac{\partial L}{\partial w} = 2 C w - 2 \lambda 1 $$ Setting this equal to zero, and solving assuming $C$ is positive definite (so invertible) we find
$$w = \lambda C^{-1} 1. $$To find $\lambda$ start with $w^T = \lambda 1^T C^{-1}$ and postmultiply with vector $1$ gives $\lambda=\frac1{1^T C^{-1} 1}$ so finally
$$ w = \frac{C^{-1}1}{1^T C^{-1} 1}. $$ If $C$ is only positive-semidefinite (so inverse do not exist) then the variance is minimized (and equal to zero) by any $w$ in the nullspace of $C$. Let us look at this in the case of two measurements of the same real-world quantity $X$. If the covariance matrix (of measurement errors) have nullspace with dimension 1, this means that the two error terms are linearly dependent, a highly impractical case. But then we have the model
$$
  y_1 = X+\epsilon \\ y_2=X+c\epsilon $$ for some error variable $\epsilon$ with expectation zero and variance $\sigma^2$. This means that with probability 1 the error term $\epsilon_1, \epsilon_2$ belongs to the linear subspace $\{ (x_1, x_2)\in \mathbb{R}^2 \colon x_2=c x_1\}$. The orthogonal complement of this space (which is the nullspace of $C$) is $\{(w_1, w_2)\in\mathbb{R}^2 \colon w_2=-w_1/c\}$, and this subspace then contains optimal weights$^\dagger$.  Then we can calculate that 
$$
   (y_1, y_2)^T w = (X+\epsilon) w_1 + (X+c\epsilon)w_2 = X(w_1+w_2)+(\epsilon w_1 + c \epsilon w_2) =X(w_1+w_2)+\epsilon(w_1-c w_1/c) = X$$
when we in the last step has used that $w_1+w_2=1$. So the negative weights in this case makes it possible to filter the error term completely, to leave an estimate without error!
But negative weight do not occur only in this unnatural case. By a continuity argument, if the correlation is sufficiently close to 1, we could expect something similar to occur even if $C$ has complete range, so is positive definite. Continuing the above case with $n=2$, write $C$ in general form as 
$$
  C=\begin{pmatrix} \sigma_1^2 & \rho \sigma_1 \sigma_2 \\ \rho\sigma_1\sigma_2 & \sigma_2^2\end{pmatrix}
$$ 
Then we can find the inverse as 
$$
 C^{-1}=\frac1{(1-\rho^2)\sigma_1\sigma_2}\begin{pmatrix} \frac{\sigma_2}{\sigma_1} & -\rho \\ -\rho & \frac{\sigma_1}{\sigma_2}\end{pmatrix}
$$
and then we can find the weights are proportional to 
$$
(w_1,w_2) \propto \frac1{(1-\rho^2) \sigma_1 \sigma_2} \left(\frac{\sigma_2}{\sigma_1}-\rho, -\rho+\frac{\sigma_1}{\sigma_2}\right)
$$
Now, if $\sigma_1=\sigma_2$, the weights are equal and positive, but when these are different, for some correlations sufficiently close to 1, one of the weights is negative. For instance, if $\sigma_1 < \sigma_2$, then we get $w_2<0$. So the weight of the least precise measurement is negative.  The intuitive explanation is that for correlation $\rho$ sufficiently close to 1, both error terms will with high probability have the same sign, so it makes sense that one of the weights should be negative.
$^\dagger$ Note that in this argument we have really assumed that $c>0$ (and if $c=1$ the argument will need modification). If $c<0$ much the same will be true, but we must replace "correlation close to 1" with "correlation close to $-1$".
A: In abstract theory, yes, because of the correlation structure.
If you had uncorrelated measurements (with positive variance), then the weights could only be positive.
Example:
Let $\mu$ denote the true value. Let noisy measurement $X_1 \sim \mathcal{N}(\mu, 1)$. Let $X_2 = 2X_1 - \mu$, hence $\operatorname{E}[X_2] = \mu$ but $X_2$ is perfectly correlated with $X_1$. The covariance matrix is $ C = \begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix} $.
The solution is $\mathbf{w} = \begin{bmatrix} 2 \\ -1 \end{bmatrix} $. Observe $2X_1 - X_2 = \mu$ and that linear combination has no variance (because $\mathbf{w}$ lies in the null space of $C$).
(As @kjetil b halvorsen points out and explores more deeply in his answer, negative weights aren't limited to degenerate cases like this.)
An equivalent finance problem:
An almost equivalent problem is solving for the minimum variance portfolio in finance. 
Let $R$ denote a vector of $n$ returns. Let $C = \operatorname{Cov}(R)$ denote the covariance matrix of $R$. Let $\mathbf{w}$ denote a vector of portfolio weights.
The minimum variance portfolio is found by solving:
\begin{equation}
 \begin{array}{*2{>{\displaystyle}r}}
 \mbox{minimize (over $w_i$)} & \mathbf{w}'\Sigma \mathbf{w} \\
 \mbox{subject to} & \mathbf{w}'\mathbf{1} = 1
 \end{array}
\end{equation}
This is exactly the same problem and it has exactly the same solution. For invertible $C$:
$$ \mathbf{w}_{mvp} = \frac{C^{-1} \mathbf{1}}{\mathbf{1}'C^{-1}\mathbf{1}}$$
Perhaps in the portfolio context, it's more intuitive that the minimum variance portfolio may involve both going long and short assets? (Note: before you run off and try to start an investment fund realize that estimating $C$ has big time problems.)
Some linear algebra interpretation
Let $U'\Lambda U = C$ be the eigenvalue decomposition of $C$. (This is basically PCA). Then $Y = R U$ is a random vector of uncorrelated random variables whose variance is given by the diagonal matrix of eigenvalues $\Lambda$. The minimum variance portfolio will give you positive weights on these random variables $Y_1, \ldots, Y_n$ but since these components are themselves linear combinations of security returns, you may get positive and negative weights in security weight space.
