Efficient way to solve "easy" quadratic optimization problem

Question

The linear program \begin{align} \min &\sum_{i=1}^nc_{i}x_{i}\\\ \mbox{s.t.:}&\sum_{i=1}^nx_{i}=1,\\\ &x_{i}\geq 0,&&\forall i=1,\dots,n \end{align} has a trivial optimal solution which is to simply: find an $i^*\in\arg\min_{i=1,...,n}\{c_{i}\}$ and then set $x_{i^*}=1$ - the rest of the $x$'s should be zero. However, the quadratic program \begin{align} \min &\sum_{i=1}^nc_{i}x_{i} + \sum_{i=1}^n \beta_{i}x_{i}^2\\\ \mbox{s.t.:}&\sum_{i=1}^nx_{i}=1,\\\ &x_{i}\geq 0,&&\forall i=1,\dots,n, \end{align} doesn't exhibit this nice "single assignment" property. Albeit, the structure is rather simple, and one could expect that there is a simple way to solve the program anyway. So the questions are

1. Does the quadratic program have a closed form solution, that I just haven't thought of?
2. If the answer to 1. is "No", what would be your approach to solving (to optimality) this problem fast, given the simple structure?

For my purpose, we can assume that both $c_{i}$ and $\beta_{i}$ are non-negative.

Answer 1

Fast resolution

Let's start with speeding up the solution process. For the optimal solutions, all variables will be either inactive ($x_i = 0$) or, due to $\sum x_i = 1$, contribute equally to the gradient. So, for some $\gamma$, either:

• $x_i = 0$ and $c_i \geq \gamma$
• or $c_i + 2\beta_i x_i = \gamma$

In particular, the active variables will be the ones with smallest $c_i$.

To solve the problem, we sort the variables by $c_i$, and solve the unconstrained problem with $1 \leq k \leq n$ active variables. The solution that satisfies the above equations and the non-negativity constraints is the optimal solution.

Closed form solution

Thankfully, there is a closed form solution for this problem.

Since $x_i = \frac{\gamma - c_i}{2\beta_i}$, $\sum \frac{\gamma - c_i}{2\beta_i} = 1$, you get $\gamma \sum_i \frac{1}{\beta_i} - \sum_i \frac{c_i}{\beta_i} = 2$.

And finally $\gamma = \frac{2 + \sum_i \frac{c_i}{\beta_i}}{\sum_i \frac{1}{\beta_i}}$.

Algorithm

So, now our algorithm is to sort the variables by $c_i$, then compute $\gamma$ for $k$ first variables active, $1 \leq k \leq n$.

Then we find $k$ for which, with some tolerance:

• the inactive variables satisfy $c_i \geq \gamma$
• the active variables satisfy $\frac{\gamma - c_i}{2\beta_i} \geq 0$ i.e. $c_i \leq \gamma$

Please check my calculations before using ;)