Minimizing a function containing an integral

Question

I am trying to optimize a function of the following form:

$L = \int_{t=0}^{T}(AR-x)dt$, where A is a system parameter

i.e. I am trying to find the optimum x(t) that minimizes L over all admissible x(t)s. R is related to x using a relation:

$\frac{dR}{dt} = axRY - bR$, where a and b are system parameters and $R(0) = R_{0}$

$\frac{dY}{dt} = -xRY$

I was looking at this problem from mainly a simulation perspective. There is a whole amount of work that went into showing that x can take only two specific values that minimize the function over any given interval. Now, what I was thinking was to convert the integral into its discrete formulation and do the following:

For $t=1$, Let $x = x_{min}$ and calculate $L_{10}$ Let $x = x_{max}$ and calculate $L_{11}$ Finally, choose the one that has the min L.

And then continue with t=2 and so on, in the same way. If I visualize this problem, it is nothing but finding a minimum cost path in a binary tree i.e. something of the following form:

---------------------- $L_{00}$
-----------------------/--\---------
------------------$L_{10}$----$L_{11}$----
-----------------/-----\----/----\-------
-------------$L_{20}$-----$L_{21}$-$L_{22}$-$L_{23}$--

and so on until the last T. I am not sure if my thought process of simulating this is in the right direction. Can someone give me some suggestions?

Answer 1

I don't think the problem as posed has an optimal solution. This is a problem in optimal control, typically dealt with by solving the Hamilton–Jacobi–Bellman equation. Your problem here is quite general, namely, a linear and unconstrained control. Thus the minimum with respect to the control variable ($x$ in your notation, $u$ in the notation of the referenced Wikipedia page) in the HJB equation does not exist, unless the value function $V$ does not depend on the control variable. In other words, an optimum exists only in the trivial case where the control variable does not actually influence the cost function.

(A small caveat: Though I have sat through a number of lectures on optimal control theory, that is the extent of my expertise, so take this with a grain of salt.)

Answer 2

It looks like a mixed-integer dynamic optimization problem. Your problem can be rewritten as follows: (notice the transformation of the integral into a differential equation? It's a standard trick. Also, note that you need an initial condition for $Y$)

$\min_{x(t)} L(T)$

s.t. $ \frac{dL(t)}{dt} = AR(t)-x(t)$, with $L(0) = 0$

$ \frac{dR(t)}{dt} = ax(t)R(t)Y(t) - bR(t)$, with $R(0) = R_{0}$

$\frac{dY(t)}{dt}=−x(t)R(t)Y(t)$, with $Y(0) = Y_{0}$

$x(t) = \delta(t) x_{min} + (1 - \delta(t)) x_{max}$ where $\delta(t) \in \{0,1\}$

To solve this problem numerically, simply discretize the differential equations using backward Euler (easy), or implicit Runge Kutta (harder, but more accurate). Pose this as a Mixed Integer Nonlinear Program (MINLP) and use one of these solvers to find the solution.

Bonmin https://projects.coin-or.org/Bonmin

Couenne https://projects.coin-or.org/Couenne

These solvers will traverse the branch-and-bound tree more intelligently and efficiently than your method of enumerating every single case, which will grow with the no. of discretization grid points you have. (e.g. let's say you discretize over 20 points; the no. of cases you have to search is $2^{20} = 1048576$. Not nice.)

With a branch-and-bound|cut|reduce MINLP solver (and a bit of luck), on average you are unlikely to hit the worst case scenario where every single case is enumerated.

There are other ways of solving this problem -- multiple-shooting, sequential dynamic optimization, etc. In my opinion, optimal control methods (Pontryagin's maximum principle) are typically intractable on problems like this.