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}$.

• You KKT condition is not clear, for some $j$ or all $j$? – Red shoes Jun 24 '17 at 0:59
• Edited, for all $j$? – esperanto Jun 24 '17 at 1:50
• Couldn't have for some $j$; $x_j \in \{0,1\}$ and for some others $x_j \in (0,1)$ in optimal solution ! I think you cant write $KKT$ in that way.. – Red shoes Jun 24 '17 at 2:01
• Deleted my answer; I misread your problem. But note that the KKT implications you've offered are self referential, so they're really not all that useful. – Michael Grant Jun 25 '17 at 2:51
• @MichaelGrant I didn't get your comment (Sorry bcuz English is not my first language)! But I believe a smart way of solving KKT conditions , can give us the close formula of solution . However OP didn't set up KKT condition correctly , am I right? – Red shoes Jun 25 '17 at 9:45

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.

• Your LP formulation is correct, but I do not think the corner points are as you have written. – esperanto Jun 27 '17 at 3:12
• . I corrected it. @esperanto – Red shoes Jun 27 '17 at 9:31