quasi
Posts:
10,660
Registered:
7/15/05


Re: An optimization problem
Posted:
Sep 8, 2013 3:13 AM


>quasi wrote: >>analyst41 wrote: >> >>consider f(x1,x2,...xn) = {1 + sum(xi)^2)} / {1 +sum{x(i)} >> >>0 <=xi <=1 for all i. >> >>The maximum function value of 1 occurs at either >>all x's = 0 or all x's = 1. >> >>Can an explicit formula be given for the minimum? > >Yes. > >The minimum value is > > ((2n)*((n+1)sqrt(n^2+n)))/sqrt(n^2+n) > >which occurs when all x's are equal to > > (sqrt(n^2+n)  n)/n
As Ray Vickson noted, the values above are wrong.
I was rushing out so had no time to check the values but, while my values were wrong, my strategy was correct.
Here's a corrected version, complete with reasoning ...
Fix a positive integer n.
Let X = {x = (x_1,...,x_n) in R^n  0 <= x_i <= 1 for all i}.
For x in X, let
sum(x_i) = x_1 + ... + x_n
sum((x_i)^2) = (x_1)^2 + ... + (x_n)^2
f(x) = (1 + sum((x_i)^2))/(1 + sum(x_i))
For s in [0,n] let
X_s = {x in X  sum(x_i) = s}
For x in X_s, the CauchySchwarz inequality yields
s^2 <= n*sum((x_i)^2)
with equality iff x_i = s/n for all i.
Thus,
sum((x_i)^2) >= (s^2)/n
=> 1 + sum((x_i)^2) >= 1 + (s^2)/n
=> (1 + sum((x_i)^2))/(1 + s) >= (1 + (s^2)/n)/(1 + s)
=> f(x) >= (1 + (s^2)/n)/(1 + s)
with equality iff x_i = s/n for all i.
Thus, on X_s, f has minimum value (1 + (s^2)/n)/(1 + s) which occurs uniquely at x = (s/n,...,s/n).
Hence, to find the minimum value of f on X, it suffices to find the minimum value of
v(s) = (1 + (s^2)/n)/(1 + s)
for s in [0,n].
At the endpoints, v(0) = v(n) = 1.
For s in (0,n),
s/n < 1
=> (s^2)/n < s
=> 1 + (s^2)/n < 1 + s
=> v(s) < 1
Thus, since v(0) = v(n) = 1, the minimum value of v(s) for s in the closed interval [0,n] occurs at a value of s in the open interval (0,n) such that v'(s) = 0. For s in (0,n), v'(s) = 0 occurs uniquely at
a = 1 + sqrt(n+1)
Thus, the minimum value of v on X is
v(a) = (2*((n+1)sqrt(n+1)))/(n*sqrt(n+1))
which occurs uniquely at the point
x = (x_1, ..., x_n)
where
x_i = a/n = (1 + sqrt(n+1))/n
for all i.
quasi

