A light solution of a quadratic programming problem

Question

I have a simple and light quadratic programming problem that I need to solve, as following: \begin{align} & \underset{x}{\arg\min} & & \dfrac{1}{2}x^T x-z^T x\\ & \text{subject to} & & \sum_{i=1}^n x_i=1,\\ & & & x_i\geq 0\;\forall i\in\{1,\ldots,n\},\\ & & & x=\left[x_1,\ldots,x_n\right]^T, z=\left[z_1,\ldots,z_n\right]^T. \end{align}

where $z$ is a constant vector.
I know there are methods like barrier method or interior-point method that can be used to solve such a problem, but I feel like this problem probably does not require a complicated method like those?

Is there any light solution that I could use to solve such a problem?

Thanks.

Answer 1

We have the following property: $$ \frac{1}{2} x^T x - z^T x = \frac{1}{2}(x^T x - 2 z^T x) = \frac{1}{2}||x - z||_2^2 - \frac{1}{2}z^T z = \frac{1}{2}||x - z||_2^2 + CONST $$ Hence, your problem is equivalent to: $$ \begin{aligned} \operatorname*{argmin}_x &\quad \frac{1}{2} ||x - z||^2 \\ \text{subject to} &\quad \sum_{i=1}^n x_i = 1 \\ &\quad x \geq 0 \end{aligned} $$

This the well known problem of projecting $z$ onto the unit simplex, and can be solved in $O(n \log n)$ time. You can google it, or look here.