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

  • $\begingroup$ You KKT condition is not clear, for some $j$ or all $j$? $\endgroup$ – Red shoes Jun 24 '17 at 0:59
  • $\begingroup$ Edited, for all $j$? $\endgroup$ – esperanto Jun 24 '17 at 1:50
  • $\begingroup$ 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.. $\endgroup$ – Red shoes Jun 24 '17 at 2:01
  • $\begingroup$ 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. $\endgroup$ – Michael Grant Jun 25 '17 at 2:51
  • $\begingroup$ @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? $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.