Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
Sorry... A is another parameter. I will clarify this in the question. And no, I meant (AR-x) inside the integral. –  Legend Feb 12 '10 at 23:07
2  
Maybe I'm misunderstanding your question, but I think you just need to solve the Euler-Lagrange equations ( en.wikipedia.org/wiki/Euler%E2%80%93Lagrange_equation ) for the Lagrangian $\mathcal{L}(t,R,\dot R) = AR -\frac{1}{a}(\frac{\dot R}{R} + b)$. Also see calculus of variations: en.wikipedia.org/wiki/Calculus_of_variations –  Steve Huntsman Feb 12 '10 at 23:28
    
@Steve: Currently looking into it.. Thanks. @Leonid: Yes.. All those are positive. –  Legend Feb 12 '10 at 23:33
    
It doesn't look like the E-L equations have a solution for $A \ne 0$, and they're trivially satisfied if $A = 0$. This motivates the following Conjecture: your problem does not originate from physics. –  Steve Huntsman Feb 12 '10 at 23:39
    
@Steve: Yes... You are right (but I hate to accept this, because pretty much everything boils down ultimately to physics... Pardon me if I've mistaken). It is more from a problem I am seeing inside the domain of social networks, more specifically, the propagation of a message amongst a set of connected nodes. –  Legend Feb 12 '10 at 23:43
show 1 more comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.