3

Let $X$ be some set such as $\{a,b,c\}$ or $\mathbb R^n$. We want to choose a vector $x=(x_0,x_1,...)\in X^\infty$ that maximizes the sum below. Interpret this as a value $x_t$ for each time period $t$. (Assume the sum exists for all $x$).

My question is, under what conditions can we "move the argmax inside the limit operator", as follows?

$$\arg\max_{x\in X^\infty}\lim_{T\to \infty}\sum_{t=0}^T \gamma^tf(x_t)=\lim_{T\to \infty}\arg\max_{x\in X^\infty}\sum_{t=0}^T \gamma^tf(x_t)$$

With $\gamma\in (0,1)$. This is essentially a "limit of a set" equation. I'm not sure where to start to find out an answer to this question.

EDIT: I don't necessarily want to assume that $f:X\to \mathbb R$ is continuous, or even that $X$ is an infinite set.

EDIT: I just realized that I mistyped the equation at first... I was too hasty, and now understand people's comments... I forgot to add the $\gamma$. Sorry for wasting people's time.

user56834
  • 12,925
  • What is exactly $\operatorname{arg max}$? – qualcuno Sep 07 '18 at 03:56
  • @GuidoA. $\operatorname{arg,max}f(x)$ is a point $x_0$ at which $f$ is maximal. Saludos de Alemana a UBA. ;-) – amsmath Sep 07 '18 at 04:09
  • 1
    @amsmath, actually $\arg\max f(x)$ is the set of all such points. – user56834 Sep 07 '18 at 04:19
  • @Programmer2134 That is indeed the most accurate definition. – amsmath Sep 07 '18 at 04:21
  • 1
    @amsmath Grüße :P – qualcuno Sep 07 '18 at 04:27
  • @Programmer2134 you are essentially asking if the operator that takes a function to its maximum value is continuous. Certainly we must ensure first that such a point exists. I remember proving something along this lines in an old exam in the context of metric spaces, but I can't remember the exact constraints. I'll try to find it. In any case, searching this site for the continuity of such function may be of use. – qualcuno Sep 07 '18 at 04:30
  • There's actually a large body of literature surrounding this topic from the 1970s and 1980s, including work by legendary optimizers like Dantzig. This Paper contains many of the relevant results. See Corollary 8.{1,2}, which is close to what you want but supposes the set you are taking the limit under is compact. If you could transform this limit to one over a compact set you could apply the result and be done. – cdipaolo Sep 07 '18 at 05:05
  • You can get results very close to this by variational convergence (or $\Gamma$-convergence). In your case, I find it hard to see any nontrivial results, as the assumption that $\sum_{t=0}^T f(x_t)$ converges is pretty strong. If $f\le 0$ I think one set is finite sequences that only consist of zeroes of $f$, the limit is infinite sequences that only consist of zeroes of $f$. – Kusma Sep 07 '18 at 06:06
  • @Kusma, why would the fact that that assumption is strong mean that there are no non-trivial results? The stronger your assumptions, the stronger your results, generally? – user56834 Sep 07 '18 at 06:55
  • I mean the class of $f$ where the assumptions hold isn't very large, and so you don't get a very broadly applicable result. It might be more interesting to have problems where you sum $f(t,x_t)$ or $f(x_t,x_{t+1}-x_t)$. But I might also be completely wrong -- it probably depends on your application what will be interesting for you. – Kusma Sep 07 '18 at 07:58
  • @cdipaolo, I am not sure I understand this. I am definitely willing to assume that $X$ is compact, but that isn't enough is it? (In fact, I am willing to assume $X$ is finite). What I am less willing to assume is that $f(x)$ is continuous, which wouldn't make any sense anyway if $X$ is finite. – user56834 Sep 07 '18 at 12:00
  • @Programmer2134 the continuity has to be in both $x$ and $T$, and the set of $T$ has to be a compact set. If you transform to include infinity as a number and induce a topology on the natural numbers by the transformation $n\mapsto 1/n$ then I think this would work actually... After this you’d have to show the objective function is jointly continuous in the variable and $T$ under this topology which doesn’t seem too bad. Then again if you can’t assume continuity this approach won’t help. – cdipaolo Sep 07 '18 at 16:19

1 Answers1

0

For finite sums, if $\max_{x\in X^T} \sum_{t=1}^{T-1} \gamma^t f(x_t)$ exists, we must have that $f$ assumes its maximum $M$ in a set $N=\arg\max_{x\in X} f$. The expression $\sum_{t=0}^{T-1} \gamma^t f(x_t)$ is maximal if each of the terms is maximal, so $\arg\max_{x\in X^T}\sum_{t=1}^{T-1} \gamma^t f(x_t)=N^T$ (if any of the entries is not in the argmax, then you can find a way to make the sum larger).

Now we consider the infinite sum. As $f(x)\le M$ on $X$, we have $$\sum_{t=0}^\infty \gamma^t f(x_t) \le M\sum_{t=0}^\infty \gamma^t=\frac{M}{1-\gamma}. $$ If we have a sequence $(x_t)$ such that $f(x_t)=M$ for every $t$, we have equality. If $f(x_t)<M$ for one $t$, then $\sum_{t=0}^\infty \gamma^t f(x_t) < M$. So $$\arg\max_{x\in X^\infty} \sum_{t=0}^\infty \gamma^t f(x_t) = N^\infty. $$ At the same time, as the finite sum only cares about the first terms, $$\arg\max_{x\in X^\infty} \sum_{t=0}^{T-1} \gamma^t f(x_t) = N^{T}\times \prod_{t=T}^\infty X \simeq N^T\times X^\infty. $$ All we need now is a sense of convergence of sets where $N^T\times X^\infty\to N^\infty$ as $T\to\infty$. My set / category theory are rusty, but I think this is an inverse limit that we can write as the intersection $$N^\infty = \bigcap_{T=0}^\infty \{(x_0,\dots, x_T,y_{T+1}, y_{T+2}, \dots) : x_i \in N, y_j\in X\}\subset X^\infty. $$

Kusma
  • 3,979
  • I can't really follow this, but you are assuming that $X=\mathbb R$ it seems to me. But $X$ could really be anything. e.g. it could be ${\text {John Travolta}, \text{Cheese}, 5}$ – user56834 Sep 08 '18 at 05:46
  • No, I am assuming that $X$ is any set and $f:X\to\mathbb{R}$. The supremum I take is over a set of values of $f$, which is a set of real numbers. I show that for both sides of your limit to be defined, $f$ has to be nonpositive with a nonempty zero set, and we can explicitly calculate the argmax in that case. – Kusma Sep 08 '18 at 05:52
  • sorry, I now see that I've made a very clumsy mistake in the question... Very sorry for this. – user56834 Sep 08 '18 at 07:28
  • @Programmer2134 no worries, the answer is almost the same and I think I improved my exposition :) – Kusma Sep 08 '18 at 08:52