I'm looking at some optimization problems which involve multiple stages. The motivation is utility maximization from economics. Suppose the target goal is to maximize the terminal wealth $u(W_T)$, where $u$ is a utility function and $W_T$ is denoting the terminal wealth at time $T$. Formally, we want to maximize

$$ \max E[u(W_T)]$$

where the max is taken over the allocation to different assets $x$. The wealth evolves as $W_{t+1}= W_t + \langle x_t, R_t\rangle$ where $x_t$ is the allocation at time $t$ and $R_t$ is the return (random) of the different assets. There might be some linear constraints which are not that important for my question. One approach to solve this problem and find the correct allocation over time is to use dynamic programming. For this problem the Bellman equation turns into $$V_{t}(W_{t}) = \max_{x} E[V_{t+1}(W_{t+1})|W_t]$$ With $V_T = u$. Now, often it is assumed that $u$ is concave. My question is whether all other value function $V_i$ resulting from the optimization are then concave as well. This is important to decide which optimizer to use.

  • $\begingroup$ What is $x$? Is it just a constant? And is $R$ dependent on it? $\endgroup$ – Slug Pue Jun 30 '17 at 12:51
  • $\begingroup$ @SlugPue Yes condition on $x$ you can treat is a constant and $R$ doesn't depend on it. You can think of it as $x = $ "current wealth" and you invest in stock market which returns are $R$ and $w$ are your portfolio weights. So $W$ is your future wealth. $\endgroup$ – math Jun 30 '17 at 12:54
  • $\begingroup$ I believe it holds for concave $u$ but not convex. We have the composition of a partial maximization and an integration (infinite sum). The latter preserves concavity or convexity; the former preserves only concavity. $\endgroup$ – Michael Grant Jun 30 '17 at 13:03

This is a relatively standard exercise in dynamic programming. See e.g. the textbook of Stokey, Lucas and Prescott.

A proof does require constraints on your $x_t$, as without such constraints, the maxima may not even exist, e.g. suppose you could take an arbitrarily large short position in an asset whose return was statewise dominated by another asset.

Additionally, your Bellman equation is incorrect in general, as the expectation should be conditional on all information at $t$, not just the wealth. (Asset returns may be auto-correlated, or have auto-correlated standard deviations.) Your notation is also slightly misleading, as the returns of assets purchased at $t$ are not learnt until $t+1$.

Given all this, let me rewrite your problem as follows:


where $\Gamma_t$ is a concave, compact set for all $t$, and, as before, $V_T=u$.

Furthermore, for simplicity, let us suppose that conditional on information observed up to period $t-1$, $R_t$ takes values from the finite list $[R_{t,1},\dots,R_{t,I_t}]$, with probabilities $p_{t,1},\dots,p_{t,I_t}$. (See Stokey, Lucas and Prescott for the more general case.)

Then, the problem becomes:


We prove that $V_t$ is well defined and concave by induction.

Base case:

$V_T=u$ which is concave by assumption.

Inductive step:

Suppose that $V_{t+1}$ is concave for some $t$. Hence, $V_{t+1}$ is also continuous, since concavity implies continuity. This in turn implies that $V_t$ is well defined, as it is the maximum of a continuous image of a compact set (which is compact, hence closed and bounded by Heine-Borel).

Let $W_0\ne W_1$ and define $W_\theta=\theta W_0 + (1-\theta) W_1$. By the definition of $V_t$, we can find $x_0,x_1$ such that:

$$V_t(W_0)=\sum_{i=1}^{I_t}{p_{t+1,i}V_{t+1}(W_0+x_0'R_{t+1,i})},$$ $$V_t(W_1)=\sum_{i=1}^{I_t}{p_{t+1,i}V_{t+1}(W_1+x_1'R_{t+1,i})}.$$

Then, if we define $x_\theta=\theta x_0 + (1-\theta) x_1$:

$$\begin{align} V_t(W_\theta)&=\max_{x\in\Gamma_t}{\sum_{i=1}^{I_t}{p_{t+1,i}V_{t+1}(W_\theta+x'R_{t+1,i})}} \\ &\ge\sum_{i=1}^{I_t}{p_{t+1,i}V_{t+1}(W_\theta+x_\theta'R_{t+1,i})} \\ &=\sum_{i=1}^{I_t}{p_{t+1,i}V_{t+1}(\theta W_0 + (1-\theta) W_1+(\theta x_0 + (1-\theta) x_1)'R_{t+1,i})} \\ &=\sum_{i=1}^{I_t}{p_{t+1,i}V_{t+1}(\theta (W_0+x_0'R_{t+1,i}) + (1-\theta) (W_1+x_1'R_{t+1,i}))} \\ &\ge\sum_{i=1}^{I_t}{p_{t+1,i}\left[\theta V_{t+1}(W_0+x_0'R_{t+1,i})+(1-\theta)V_{t+1}(W_1+x_1'R_{t+1,i})\right]} \\ &=\theta V_t(W_0) + (1-\theta)V_t(W_1), \end{align}$$

establishing concavity of $V_t$. (The first $\ge$ here follows from the definition of a maximum, the second $\ge$ follows from the definition of concavity.)


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.