Can we obtain an analytical solution for the following optimization problem?
$$\max\limits_{x_i \in [0,1]} \left(\sum\limits_{i = 1}^n a_i x_i \right) - \left( \sum\limits_{i = 1}^n x_i \right)^2$$
Do the KKT conditions imply the following,
For all $j$,
i. $x^*_j \in \lbrace 0,1\rbrace$, or
ii. if $x_j \in (0,1)$, then $\sum\limits_{i = 1}^nx^*_i = \dfrac{v_j}{2}$.
First it is easy to see that if $ a_i \leq0 $ at optimal solution we have $x_i = 0$, and we can omit the variable $x_i$ so let's first assume $a_i$ are distinct hence (WLOG by rearranging x_i) $$ 0 < a_1 < a_2 < a_3 ... < a_n $$
Now let assume at the Unique optimal solution, say $(x^*_1 , x^*_2,..., x^*_n)$, we have $\sum\limits_{i = 1}^nx^*_i = \epsilon,$ obviously based our assumption $ \epsilon > 0. $ So one can rewrite problem equivalently as $$ \begin{array}{ll} \text{maximize} & \sum\limits_{i = 1}^na_ix_i\\ \text{subject to} & \\ & \sum\limits_{i = 1}^nx_i = \epsilon \\ & 0\leq x_1,x_2,...,x_n \leq 1\end{array} $$
This is a linear programing. A simple analysis reveals that the optimal solution is $(0,0,..0, \epsilon -j,1,1,..,1)$. Where numbers of $1$s is $j$ and $ 0 \leq x^*_{n-j} = \epsilon - j < 1.$
Clarification about the index $j:$ depending $\epsilon$ the index $j$ can be any number within the set $\{0,1,2,..,n\}$, for example if $\epsilon < 1$ then optimal solution is $(0,0,..0,\epsilon)$ i.e., $j=0$, or if $\epsilon = \frac{3}{2}$ then the optimal solution is $(0,0,..0,\frac{1}{2},1)$ i.e., $j=1$, or if $\epsilon =n$ then optimal solution is $(1,1,...,1)$ i.e., $j=n$.
Now to finish problem we only need find $\epsilon$ (or $x^*_{n-j}$)! To End this, back to original problem we know at optimal solution we have $$ x_1 = x_2 = x_{n-j-1} = 0, ~ x_{n-j+1} = x_{n-j+2}=...=x_{n} =1 $$
so we only need to maximize $a_{n-j} x_{n-j} - (x_{n-j} + j )^2 $ over the interval constraint $ x_{n-j} \in [0,1]$, Hence, $x^*_{n-j} = \max \{ \frac{a_{n-j}}{2} - j , 0 \}.$
Therefore in general the closed formula is obtained if $a_I$ are distinct.
For the case $a_i$ are not distinct, one can merge all variables with same $a_i$! and consider similar approach to get result.