Optimization problem with recursive functions

Question

I could image that the following is a standard optimization problem but nevertheless I have no clue how to specifically solve it: by which specific approach, algorithm, and which computing powers I would need?

Please let me state the problem, then every hint how to approach it is welcome!

Given a recursive formula, that gives the value of a function $f$ at time $t+1$ as a function $F$ of its values at all previous times $t, t-1,\dots,0$ and of a big number $n$ (say $n =50$) of parameters $a_i \in [0,1]$, which may vary over time:

$$f(0) = f_0$$ $$f(t+1) = F\big(f(t-1), f(t-1),\dots, f(0); a_1(t),a_2(t),\dots,a_n(t)\big)$$

Given also a cumulative cost function $c$ with

$$c(0) = 0$$

$$c(t+1) = c(t) + C\big(a_1(t),a_2(t),\dots,a_n(t)\big)$$

Finally an explicit threshold function $\vartheta(t)$.

The problem is (for a given time $T$):

For which choice of parameters $a_1(t),a_2(t),\dots,a_n(t)$, $t < T$ does hold

• $f(t) \leq \vartheta(t)$ for all $t \leq T$

• $c(T)$ is minimal with value $c_{\text{min}}$

I.e. for any other choice of parameters, either $f(t) > \vartheta(t)$ for some $t \leq T$ or $c(T) > c_{\text{min}}$.

I would be more than happy not only with really optimal solutions, but also with almost optimal ones (given high probability, that they are nearly optimal).

---

Maybe the problem becomes significantly easier to solve, when we don't try to minimize $c(T)$ but fix the minimal costs $c_{\text{min}}$ and look for solutions (= choices of parameters) with

• $f(t) \leq \vartheta(t)$ for all $t \leq T$

• $c(T) \leq c_{\text{min}}$

---

Edit: Maybe the problem becomes easier when taking into account, that $F$ in fact only depends on $f(t)$ and $f(t-1)$ and $\sum_{\tau = 0}^t f(\tau)$.

Answer 1

Let $A$ be the $n\times T$ matrix containing $a_i(t)$ $\forall \ i\in [n],t\in[0,T-1]$ and $\mathbf{a}_t=[a_1(t) \ \cdots \ a_n(t)]$. You can simplify your objective value as $c(T)=\sum_{t=0}^{T-1}C(\mathbf{a}_t)$. The resulting optimization problem is then

$\min_{A\in [0,1]^{n\times T}} c(T):=\sum_{t=0}^{T-1}C(\mathbf{a}_t)$ subject to $f(t)\leq \theta(t)\ \forall t\leq T$.

If both $C$ and $F$ are linear functions (you can express objective and $f(t)\leq \theta(t)$ constraints with a matrix product), this yields a Linear Program and you can use e.g. the Simplex or Ellipsoid methods.

If this is not the case, you can apply a primal-dual method such as Augmented Lagrangian. See this for some examples. Note that the gradient of $c$ is trivial to compute given the simplified expression, and you can differentiate $f$ using the same methods as in backpropagation through time.