How do I solve the following equality-constrained quadratic program?

Question

I am trying to minimize: $$(x_1-k_1)^2 + (x_2-k_2)^2 + (x_3-k_3)^2 +\ldots+ (x_n-k_n)^2$$

subject to following equality: $$B = 1 + x_1 + x_2 + x_3 + x_4+\ldots+x_n.$$

Is there a closed form solution for this? I found the case where $n=2$ using Lagrange multipliers and could do the same for case $n=3$, but does anyone see a simple solution?

Wikipedia gives this solution, but I'm not sure if the matrix has an inverse so I'm weary of going down that route. Also inverting matrix takes some computer time and may not be feasible for solving different instances of the problem thousands of times.

Also, I put $B$ above as a constant, which it is, but I'm interested in the case where $B = (1+k_1)\times(1+k_2)\times\ldots\times(1+k_n)$, but I'm not sure if that makes the problem easier. My intuition is that it does not and just complicates things.

Answer 1

You can rewrite the constraint as:

$$0= 1-B +\sum_{i=1}^nx_i$$

and then turn it into a cost function:

$$\lambda\left\|1-B+\sum_{i=1}^{n}x_i\right\|_2$$

If we want to we can rewrite this with matrices, $\bf 1$ being the column vector full of ones:

$$\min_{\bf x} \left\{ \|{\bf x}-{\bf k}\|_2 + \lambda\|1-B+{\bf 1}^T{\bf x}\|_2\right\}$$

You will probably get better faithfulness to the constraint if you solve a sequence of linear problems using for example iterated reweighting approach replacing the 2-norm with another norm for the constraint term:

$$\min_{\bf x} \left\{ \|{\bf x}-{\bf k}\|_2 + \lambda\|1-B+{\bf 1}^T{\bf x}\|_k\right\}$$

you could aim for different $k$, but I think $k=1$ would be a good choice.

---

EDIT I erroneously claimed that 1-norm term in this case would be the Lasso method, but as pointed out below in comments, in that case the 1-norm is of course applied on the $\bf x$ vector alone. Even as the constraint is in fact a scalar the $k$ norm is still relevant as the deviation for the constraint would be punished differently from the terms in the least-squares term.

Answer 2

We have a quadratic program

$$\begin{array}{ll} \text{minimize} & \|\mathrm{x} - \mathrm{k}\|_2^2\\ \text{subject to} & 1_n^T\mathrm{x} = c\end{array}$$

where $c = -1 + \displaystyle\prod_{i=1}^n (k_i+1)$. Using a Lagrange multiplier,

$$\mathcal{L} (x,\lambda) := \frac{1}{2}\|\mathrm{x} - \mathrm{k}\|_2^2 + \lambda (1_n^T \mathrm{x} - c)$$

Taking the partial derivatives and finding where they vanish,

$$\nabla_x \mathcal{L} = \mathrm{x} - \mathrm{k} + \lambda 1_n = 0_n \qquad \qquad 1_n^T \mathrm{x} = c$$

Hence,

$$1_n^T \mathrm{x} - 1_n^T \mathrm{k} + \lambda 1_n^T 1_n = 0_n$$

and

$$\lambda = \dfrac{1_n^T \mathrm{k} - c}{n}$$

Thus, the minimum is attained at

$$\mathrm{x} = \mathrm{k} + \left(\dfrac{c - 1_n^T \mathrm{k}}{n}\right) 1_n$$

and the minimum is

$$\|\mathrm{x} - \mathrm{k}\|_2^2 = \left\|\left(\frac{c - 1_n^T \mathrm{k}}{n}\right) 1_n \right\|_2^2 = \frac{\left(c - 1_n^T \mathrm{k}\right)^2}{n}$$