1
$\begingroup$

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)$.

$\endgroup$
8
  • 1
    $\begingroup$ Your notation is a little deceptive, because "$F$" is not a single function: it is a series of functions, one for each $t.$ As such, the recursive formulation is no restriction at all: you might as well ask how to optimize any function of $n$ variables subject to $T$ constraints. That's a vast topic; I don't see how it would be possible to address it here. $\endgroup$
    – whuber
    Apr 11, 2020 at 13:06
  • $\begingroup$ Is there something to say about the $a_i(t)$? Can your restrict the formulation of these functions based on some prior knowledge? $\endgroup$ Apr 11, 2020 at 13:22
  • $\begingroup$ @whuber: Does it help to restrict $F$ to depend on three arguments, as stated in my edit:$f(t+1) = F(f(t),f(t-1),\sum_{\tau = 0}^t f(\tau))$? $\endgroup$ Apr 11, 2020 at 14:36
  • $\begingroup$ Sure--but the restriction has to be far more specific than what you supply at the end of the post. Again, the problem is that your "$F$" as a function of $t$ variables (so far) has no relationship at all with your "$F$" as a function of $t-1$ variables. $\endgroup$
    – whuber
    Apr 11, 2020 at 14:41
  • $\begingroup$ @SextusEmpiricus: No, all there is to say about $a_i(t)$ is that $0 \leq a_i(t) \leq 1$ for all $t$. $\endgroup$ Apr 11, 2020 at 14:42

1 Answer 1

2
+150
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Did you receive the bounty? (I accepted your answer.) $\endgroup$ Apr 19, 2020 at 19:01
  • $\begingroup$ Yes! Hope it solved your doubts! $\endgroup$
    – Oriol B
    Apr 19, 2020 at 23:33
  • 1
    $\begingroup$ There were no doubts - only missing knowledge. But you filled some gaps, thanks a lot! $\endgroup$ Apr 20, 2020 at 4:06

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.