-1

While trying to solve a problem in graph theory I need to find the maximum value of $x_1^2+x_2^2+\dots +x_k^2$ subject to a condition that $x_1+x_2+\dots + x_k=n$.

Could someone guide me how to do this?

Thanks in advance.

lisyarus
  • 15,517
manifold
  • 1,485

2 Answers2

4

There is no maximum. Consider for example the points $$(r,n-r,0,\ldots,0)$$ for $r\to\infty$.

However, there is a minimum, as pointed out in another answer.

Daniel Robert-Nicoud
  • 29,795
  • You are right… but I guess the OP is dealing with non-negative $x_k$. Then the question reduces to "Find max of $\parallel x \parallel_2^2$ if $\parallel x \parallel_1 = n$. But let's see if you are right and I'm wrong :-) – Gono Nov 03 '17 at 11:28
  • 1
    @Gono Might be, but I'm answering the question that was asked, not the question that the OP might have been thinking about ;) – Daniel Robert-Nicoud Nov 03 '17 at 13:06
  • @Gono Also, the maximal value in that case is quite obviously $n^2$. – Daniel Robert-Nicoud Nov 03 '17 at 13:07
1

The constraint describes a hyperplane perpendicular to the vector $(1,1,\cdots1)$. The isosurfaces of the objective function are hyperspheres centered at the origin.

Hence the solution

$$\frac nk(1,1,\cdots1).$$

  • 1
    That point isn't on the plane required. I think you meant $\frac{n}{k}(1, 1, \dots 1)$ – Daniel Martin Nov 03 '17 at 11:20
  • @DanielMartin And even this point is the minimum, not the maximum. – lisyarus Nov 03 '17 at 11:22
  • Though also, this is the point with minimum value, and the question asked for maximum value, which seems odd. – Daniel Martin Nov 03 '17 at 11:22
  • 2
    @lisyarus Indeed.

    If the $x_k$ are subject to the additional constraint $x_k \geq 0$, then the maximum value happens at $(n, 0, \dots 0)$ (and the other $k-1$ points of all $n$ and $0$). If they can be arbitrary real values, there is no maximum.

     – Daniel Martin Nov 03 '17 at 11:24
  • @DanielMartin: yep, my bad. Fixing. –  Nov 03 '17 at 14:04
  • 1
    @lisyarus: right; but the unbounded problem seemed so unlikely that I didn't consider it ;-) –  Nov 03 '17 at 14:05