# A Dynamic Programming Approach to Ecosystem Management
## 2 Materials and Methods
### Dynamic Programming Procedure  
Dynamic programming is a method for finding optimization algorithms that consist of breaking a problem into smaller trivial subproblems and determining an optimal sequence of interrelated decisions for the main problem.  
There is no standard formulation for the dynamic programming method--the technique must be adapted to each specific case--but we can summarize the general structure of the compatible problems:  
* The problem can be divided into stages, requiring a policy decision at each stage. The optimal sequence to be obtained is composed of the decisions taken;
* A number of states are associated with the beginning of each stage: the states represent the possible conditions of the system at the given stage. A stage can be associated with an arbitrarily large number of states;
* At each stage, the policy decision moves the system from the current state to a state associated with the beginning of the successive stage;
* The solution procedure aims at finding one or more _optimal policies_ for the main problem; that is, a set of optimal policy decisions at each stage, for each of the possible stages--meaning an indication of the best decisions available under any circumstances;
* The problem must fit the _principle of optimality_: given a state, an optimal policy for the remaining stages is independent of the policy decisions adopted in the previous stages. Therefore, the optimal immediate decision depends only on the current state, regardless of the chosen path;
* The solution procedure begins by finding the optimal policy for the last stage, for each of the possible states, and the subproblems related to each stage are usually trivial or quasi-trivial;* The optimal policy for a stage n, given the policy for the stage \(n+1\), is identified by a recursive relationship. Its precise form depends on the specific problem, but we can set the following notation to represent the general relationship: \[N=\text{number of stages}\] \[n=\text{label for current state}\] \[S_{n}=\text{current state for stage $n$}\] \[x_{n}=\text{decision variable for stage $n$}\] \[x_{n}^{*}=\text{optimal value of $x_{n}$ given $S_{n}$}\]  
\(f_{n}(S_{n},x_{n})=\text{contribution of stages $n,n+1,\ldots,N$ to the objective function if the system starts at state $S_{n}$ at stage $n$ (the immediate decision is expressed by $x_{n}$, and optimal decisions are made afterward). \(f_{n}^{*}(S_{n})=f_{n}(S_{n},x_{n}^{*})\), recursive relationship for the optimal value function, it is always one of the two forms: \[f_{n}^{*}(S_{n})=\min_{S_{n}+1}f_{n}(S_{N},x_{n}^{*}),\quad f_{n}^{*}(S_{n})= \max_{S_{n}+1}f_{n}(S_{N},x_{n}^{*}),\] with \(f_{n}(S_{n},x_{n})\) written in terms of \(S_{n},x_{n},f_{n+1}^{*}(S_{n+1})\) and eventually a measure of the immediate contribution of \(x_{n}\) to the objective function;
* The solution procedure follows the recursive relationship starting at the end and moving backward stage by stage, finding the optimal policies for the partial problem at each stage. It stops at the initial stage, completing the solution for the entire problem.  
Dynamic programming procedures can be adapted to fit a variety of models. _Deterministic dynamic programming_ is associated with problems whose state at the next stage is entirely determined by the state and policy decision at the current stage, while in _probabilistic dynamic programming_, a probability distribution describes the change in state. Compatible problems can also be categorized by form of objective function, such as minimum or maximum of a sum or a product of the contributions from the individual stages, or by type of states. The state variables can be defined as discrete variables, continuous variables or vectors, and a problem can admit an infinite number of states for each stage.