Solve the following constrained maximization problem

Question

Question: let $T\geq$ 1 be some finite integer, solve the following maximization problem.

Maximize $\sum_{t=1}^T$($\frac{1}{2}$)$^t$$\sqrt{x_t}$ subject to $\sum_{t=1}^{T}$$x_t\leq1$, $x_t\geq0$, t=1,...,T

I have never had to maximize summations before and I do not know how to do so. Can someone show me a step by step break down of the solution?

Answer 1

Use the method of Lagrange Multipliers.

Denote your objective function by $f(x) = \sum_{t=1}^T(\frac{1}{2})^t\sqrt{x_t}$.

Since your constraint is on the sum of the x variables, an optimal solution $x^*$ will have a gradient which is parallel to the vector $(1,1,\ldots,1)$, i.e. We seek a point where $\nabla f(x^*) = \lambda (1,1,\ldots,1)$.

Computing the gradient of $f$, we get $(\frac{1}{4\sqrt{x_1}}, \frac{1}{8\sqrt{x_2}}, \ldots,\frac{1}{2^{T+1}\sqrt{x_T}}).$

Solve for which $x^*$ causes the gradient to have all its coordinates equal. In other words, find values for $x_1,x_2, \ldots, x_T$ so that $$\frac{1}{4\sqrt{x_1}} = \frac{1}{8\sqrt{x_2}} = \ldots = \frac{1}{2^{T+1}\sqrt{x_T}}$$ Then you will have your optimal solution.

Answer 2

By Cauchy-Bunyakovsky-Schwarz inequality, we have \begin{align} \sum_{t=1}^T 2^{-t}\sqrt{x_t} &\le \sqrt{\left(\sum_{t=1}^T 2^{-2t}\right)\left(\sum_{t=1}^T x_t\right)}\\ &\le \sqrt{\sum_{t=1}^T 2^{-2t}}\\ &= \sqrt{\frac{1-4^{-n}}{3}} \end{align} with equality if $\sum_{t=1}^T x_t = 1$ and $\frac{\sqrt{x_1}}{2^{-1}} = \frac{\sqrt{x_2}}{2^{-2}} = \cdots = \frac{\sqrt{x_n}}{2^{-n}}$.

Thus, the maximum of $\sum_{t=1}^T 2^{-t}\sqrt{x_t}$ is $\sqrt{\frac{1-4^{-n}}{3}}$ achieved at $x_i = \frac{3}{1-4^{-n}}\cdot 2^{-2i}, \ i=1, 2, \cdots, n$.