0

I would like to optimize a function $f(x): \displaystyle\bigcup_{n=1}^\infty \mathbb{R}^n \rightarrow \mathbb{R} $.

It seems that classical optimization routines does not work here since the space does not have a fixed dimension and it is actually badly huge. Do you know any meta-algorithm which could help finding the optimal value?

Ps: This is not important but in case people ask for more details, the function is actually a multiplication of exponentials-like functions (the more dimensions $x$ has the more factors the function $f(x)$ has).

Francisco
  • 415
  • Optimize... with respect to what? What are you minimising / maximising? – 5xum Nov 08 '16 at 12:55
  • What is the objective function that you are minimizing? $f$ is not real-valued so it doesn't make sense to minimize it. – littleO Nov 08 '16 at 12:58
  • @5xum with respect to $x$. I am maximizing but this is not important since I can minimize $-f(x)$ as well. – Francisco Nov 08 '16 at 12:59
  • @littleO yes, that was a typo. I just edited, $f$ goes to $\mathbb{R}$ – Francisco Nov 08 '16 at 13:00
  • @Francisco Oh, I see now you changed the codomain. – 5xum Nov 08 '16 at 13:00
  • I haven't seen methods for minimizing this type of function, so I'm guessing we'd need to see an explicit formula for $f$ to invent an appropriate method. – littleO Nov 08 '16 at 13:35

1 Answers1

1

For an introduction to infinite-dimensional optimisation you have have a look at H.H. Bauschke and P.L. Combettes, Convex analysis and monotone operator theory in Hilbert spaces, Springer, 2011. There are several fixed-point iterations aiming at finding fixed points, $x=T(x)$.

The algorithm you need to choose depends on $T$ and its properties. If $T$ is a contraction, you can apply $T$ iteratively, that is $x_{k+1} = Tx_{k}$ (where $x_k$ is infinite dimensional).

If $T$ is a nonexpansive operator, then you can use the Krasnosel’skii–Mann iteration which reads $$ x_{k+1} = x_{k} + \lambda_k (T(x_k) - x_k), $$ where $\{\lambda_k\}_k\in [0,1]$ and $\sum_k \lambda_k (1-\lambda_k)=+\infty$.

Once you write your optimisation problem in the equivalent form of finding a fixed point for the (infinite-dimensional) gradient of your cost function, then you can use the above algorithm (I assumed that your problem is convex, otherwise you can only obtain a stationary point).

The KM iteration converges weakly to a fixed point, or strongly if additional conditions are satisfied ($T$ to be firmly nonexpansive and $\{\lambda_k\}$ to be chosen slightly differently.

Pantelis Sopasakis
  • 5,155
  • With $T$ you mean $f$ or something else? – Francisco Nov 09 '16 at 11:08
  • @Francisco No, $T$ is the operator whose fixed points you're looking for. It can be $T(x) = x - \nabla f(x)$ if $f$ is differentiable (Then $x^$ is a fixed point of $T$ iff $\nabla f(x^)=0$), or it can be $T(x) = \mathrm{prox}{\gamma f}(x)$, if the proximal operator of $f$ is easy to compute (it often is). Or maybe you can write $f(x) = f_1(x) + f_2(x)$ where $f_1$ is diff/ble and $f_2$ is prox-friendly (they often call it like that) and then you can take $T(x) = x - \mathrm{prox}{\gamma f_2}(x - \gamma \nabla f_1(x))$. – Pantelis Sopasakis Nov 09 '16 at 11:13