Minimizing a function containing an integral - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T14:03:02Z http://mathoverflow.net/feeds/question/15147 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/15147/minimizing-a-function-containing-an-integral Minimizing a function containing an integral Legend 2010-02-12T22:54:20Z 2010-07-23T20:06:18Z <p>I am trying to optimize a function of the following form:</p> <p>$L = \int_{t=0}^{T}(AR-x)dt$, where A is a system parameter</p> <p>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:</p> <p>$\frac{dR}{dt} = axRY - bR$, where a and b are system parameters and $R(0) = R_{0}$</p> <p>$\frac{dY}{dt} = -xRY$</p> <p>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:</p> <p>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.</p> <p>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:</p> <p>---------------------- $L_{00}$<br /> -----------------------/--\---------<br /> ------------------$L_{10}$----$L_{11}$----<br /> -----------------/-----\----/----\-------<br /> -------------$L_{20}$-----$L_{21}$-$L_{22}$-$L_{23}$--</p> <p>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? </p> http://mathoverflow.net/questions/15147/minimizing-a-function-containing-an-integral/15187#15187 Answer by Harald Hanche-Olsen for Minimizing a function containing an integral Harald Hanche-Olsen 2010-02-13T14:39:48Z 2010-02-13T14:39:48Z <p>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 <a href="http://en.wikipedia.org/wiki/Hamilton%E2%80%93Jacobi%E2%80%93Bellman%5Fequation" rel="nofollow">Hamilton–Jacobi–Bellman equation</a>. Your problem here is quite general, namely, a <em>linear</em> and <em>unconstrained</em> 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.</p> <p>(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.)</p> http://mathoverflow.net/questions/15147/minimizing-a-function-containing-an-integral/33134#33134 Answer by Gilead for Minimizing a function containing an integral Gilead 2010-07-23T20:06:18Z 2010-07-23T20:06:18Z <p>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$)</p> <p>$\min_{x(t)} L(T)$</p> <p>s.t. $\frac{dL(t)}{dt} = AR(t)-x(t)$, with $L(0) = 0$</p> <p>$\frac{dR(t)}{dt} = ax(t)R(t)Y(t) - bR(t)$, with $R(0) = R_{0}$</p> <p>$\frac{dY(t)}{dt}=−x(t)R(t)Y(t)$, with $Y(0) = Y_{0}$</p> <p>$x(t) = \delta(t) x_{min} + (1 - \delta(t)) x_{max}$ where $\delta(t) \in {0,1}$</p> <p>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.</p> <p>Bonmin <a href="https://projects.coin-or.org/Bonmin" rel="nofollow">https://projects.coin-or.org/Bonmin</a></p> <p>Couenne <a href="https://projects.coin-or.org/Couenne" rel="nofollow">https://projects.coin-or.org/Couenne</a></p> <p>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.)</p> <p>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.</p> <p>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.</p>