Raising the bar

Cauchy-Schwarz inequality and optimization 2

Here we consider a problem from mt3042 Optimization Guide by M. Baltovic:

Example 8.1. Given the initial state $latex s_{1}=W$ for some $latex W>0$ and a discount factor $latex \delta\in(0,1),$ we need to maximize the discounted stream of future rewards

(1) $latex \sum_{i=1}^{\infty }\delta^t\sqrt{a_t}.$

The maximization is over actions $latex (a_1,a_2,...)$ (you can think of them as consumptions). The initial state $latex s_1=W$ is the initial wealth; at each step, the consumption is chosen between zero and the wealth left from the previous period, $latex 0\leq a_t\leq s_t.$ This reduces the amount available for consumption in the next period:

(2) $latex s_{t+1}=s_t-a_t,$ $latex t\geq 1.$

Step 1. Here we reformulate the problem to remove the states from the constraints. From (2) we have $latex a_t=s_t-s_{t+1}.$ Fixing an integer $latex T>0$ then we obtain

(3) $latex a_1+a_2+...+a_{T-1}+a_T=s_1-s_2+s_2-s_3+...+s_{T-1}-s_T+s_T-s_{T+1}=s_1-s_{T+1}.$

Since in each state $latex s_t$ consumption $latex a_t$ is nonnegative, the states can only decrease over time. On the other hand, they cannot be negative. Hence, the sequence $latex \{s_T\}$ is nonincreasing and bounded from below by zero. Therefore the limit $latex S=\lim_{T\rightarrow\infty}s_T$ exists and is nonnegative. Letting $latex T\rightarrow\infty$ in (3) we get $latex \sum_{t=1}^{\infty}a_t=W-S\leq W.$

The problem becomes: maximize (1) subject to

(4) $latex \sum_{t=1}^{\infty}a_t\leq W.$

Step 2. Getting rid of square roots. Denoting $latex x_t=\sqrt{a_t},$ we have to maximize $latex \sum_{i=1}^{\infty }\delta^tx_t$ subject to $latex \sum_{t=1}^{\infty }x_t^2\leq W.$

Step 3. Applying the result on the Cauchy-Schwarz inequality. The result from the previous post does not depend on the number of variables. For our present needs it is formulated as follows: Let $latex a_1,a_2,... \ge 0$ be fixed numbers and let $latex x_1,x_2,... \ge 0$ be variables satisfying the restriction $latex x_1^2+x_2^2+... \le W.$ Then the infinite weighted sum $latex a_1x_1+a_2x_2+...$ is maximized at the point

$latex (x_1,x_2,...)=\frac{W^{1/2}}{\left( a_1^2+a_2^2+... \right)^{1/2}}(a_1,a_2,...)$

and the maximized value is $latex a_1x_1+a_2x_2+...=W^{1/2} \left(a_1^2+a_2^2+... \right)^{1/2}.$

Letting $latex a_{t}=\delta^t$ we get $latex a_1^2+a_2^2+...=1/(1-\delta^2)$ and

$latex (x_1,x_2,...)=[(1-\delta^2)W]^{1/2}(1,\delta,\delta^2,...)$ with the maximized value $latex \sqrt{W/(1-\delta^2)}.$

And no clumsy terminology and notation from the Infinite Horizon Dynamic Programming method!