1.

FUNDAMENTAL CONCEPTS OF OPTIMIZATION

DYNAMICS

OPTIMIZATION:

Optimization is a predominant topic in economic analysis. For this reason

reason, the classic calculation methods for finding free and bounded extremes and
the latest mathematical programming techniques occupy a
important place in the daily tool kit of economists. Useful
how they are, these tools are only applicable to optimization problems
static. The sought solution in this type of problems generally consists
in a single optimal magnitude for each choice variable, such as the level
optimal production per week and the optimal price to charge for a product.
Does not call for an optimal sequential action calendar.

THE ECONOMIC DYNAMICS:

It allows the study of the facts that precede an economic phenomenon, the
phenomenon itself, the repercussions or consequences of such phenomenon, as well as
its interrelationship.

Economic dynamics allows for the study of facts and phenomena in a way
changing, studying general aspects of them, as well as analyzing
specifically the way in which various economic aspects develop

DYNAMIC OPTIMIZATION

Study the obtaining of the optimal solution of evolving dynamic systems

en el tiempo; a estos sistemas se trata de guiar o controlar de manera óptima a lo
long given a time horizon according to a fixed objective since they are
susceptible to influence through external decisions.
Dynamic optimization, as its name indicates, studies optimization.
dynamic systems dynamics, that is, the optimization of systems that
they evolve over time, it is about guiding or controlling the system in a way
optimal over a given time horizon, according to a certain objective
previously set. Let's look at some examples that can help with a first
compression.
A dynamic optimization problem raises the question of what the magnitude is
optimal choice of a variable at each point in time within the period
of planning (discrete time case) or at each point in time in a
given time interval, let's say [0, 21 (continuous time case). It is even
It is possible to consider an infinite planning horizon, so that the interval
the corresponding time is [0, co) - literally, "from here to eternity." The
solution to a dynamic optimization problem would therefore be to take the
form of an optimal temporal trajectory for each choice variable,
detailing the best value of the current variable, take row, and so on,
until the end of the planning period. Throughout this book, we will use
the asterisk to denote optimality. In particular, the optimal temporal trajectory
of a continuous-time variable and is denoted by Y *(t)

2. HISTORY OF DYNAMIC PROGRAMMING

Dynamic optimization can be considered to have roots in calculus.

variations, classical control theory, and linear and nonlinear programming
(Bryson 1999)
The calculus of variations emerged in the 18th century and received attention in the works of Euler.

(1707-1783) and LaGrange (1736-1813) the form of a mathematical theory

rigorous.
Tras algunos trabajos previos Euler público en 1744 el libro Método de búsqueda
of curved lines with maximum or minimum property, or the resolution of
isoperimetric problem taken in its broadest sense, which is the first book
in the history of the calculus of variations.
In 1755, Lagrange communicated to Euler the general analytical method, created by him, in
the one that introduces the variation of a function and where it extends to the variations
the rules of differential calculus. This idea of variations would give the name to the
new discipline.
Other important contributions to the calculus of variations are due to Legendre.
(1752-1833), Jacobi (1804-1851), Hamilton (1805-1865), Weierstrass (1815-
Bolza (1857-1942) and Bliss (1876-1951).
The calculus of variations was applied, after its discovery, mainly in physics,
especially in mechanics.
The systematic development of control theory began in the United States.
around 1930 in the field of electrical and mechanical engineering. Until
Around 1940, the control systems built were systems of
regulation: the speed of a motor or a hydraulic turbine should be
maintained in an environment of a constant value. The designs aimed to avoid
instability.
During World War II, control systems appeared in which the
transition was more important than stillness: It is the class of servomechanisms,
pursuit systems for example: the control system for a firearm
required to reach a mobile objective, with the help of a radar. It was discovered
that a large part of the necessary theory for the design of such systems was already
has been developed in the field of communication engineering. To appear the
classical control theory call, fundamentally based on the domain
[Link] was found that the differential or difference equations that
describing the dynamics of the system were often intractable, but passing the
frequency domain through the Laplace transform or z-transform is
algebraic results were produced from which one could infer
characteristics of the system; however, this theory presented serious
limitations as it restricted the study to linear systems with a single variable of
input and one output, and time-invariant. On the other hand, it was necessary to
consider other criteria that value the evolution in certain problems
of the system.
The concepts of controllability and observability introduced by Kalman (1960)
as well as the optimization methods of Belma (1957) and Pontryagin (1962),
they were the origin of what is known as modern control theory or theory of
optimal control, based on the description of a system according to the approach of
space of the states. The new advances and their applications not only fell into
the field of engineering, but also in that of economics, biology, medicine,
social sciences. In those years, the most important applications took place.
from optimal control to the American space program.
In economics, some appeared in the 1950s and 1960s of the 20th century.
contributions that utilize control theory, although they are contributions
isolated. In the sixties, control techniques are already used systematically.
optimal in the research of growth theory.
Since 1970, there has been a great interest in control theory in various fields.
the economy, both in theoretical and empirical work, and since then
Works on the subject are proliferating, which has been the basic instrument for
describe the behavior of individuals and companies when the activity
the economy develops over time.
These techniques are used in business economics, with very good results.
results, for the study of problems such as inventory control,
investment selection, maintenance and replacement of machines,
production planning, advertising policy, etc. All of them from the
second half of the sixties.
In macroeconomics, there was great interest in the utilization of the 1970s.
Kendri's control theory 1976 analyzes around ninety applications.
 3. MAIN CHARACTERISTICS OF THE PROBLEMS OF
DYNAMIC OPTIMIZATION

Although dynamic optimization is expressed mainly in terms of a

time sequence, it is also possible to contemplate the planning horizon
as a sequence of stages in an economic process. In that case, the
Dynamic optimization can be seen as a decision-making problem.
of multiple stages. The distinguishing feature, however, remains the
the fact that the optimal solution would involve more than one unique value for the variable

of choice.

MULTI-STAGE DECISION

The character of multiple stages of dynamic optimization can be illustrated with a

simple discrete example. Suppose a company is engaged in
transformation of a certain substance from an initial state A
(raw material state) in a terminal Z state (products state
finishes) through a five-stage production process. At each stage,
the company is facing the problem of choosing between several alternative subprocesses
possible, each one involving a specific cost. The question is: How should
the company to select the sequence of subprocesses through the five
stages in order to minimize the total cost.
In figure 1.1, a problem is presented by outlining the stages.
Horizontally and vertically the states. The initial state A is shown by the
point furthest to the left (at the beginning of stage 1), the status of terminal Z
is shown by the rightmost point (at the end of stage 5). The rest of the
points B, C,..., K show the various intermediate states in which the
substance can transform during the process. These points (A, B,…,Z) are
they are called vertices. To indicate the possibility of transforming from state A to
state B, we draw an arc from point A to point. The other arc AC shows
That the substance can also be transformed into state C instead of state B.
Each arc is assigned a specific value - in the present example, a cost is
shown in a circle in figure 1.1. The decision of the first stage is whether for
transform the raw material into state B (at a cost of $2) or into state C (at a
cost of $ 4), that is, whether to choose arc AB or arc CA. Once the
decision, another problem will arise from the choice in stage 2, and so on,
until the state Z is reached. Our problem is to choose a sequence
connected arcs that go from left to right, starting at A and that
ends in Z, such that the sum of the values of the arcs of
components are minimized. Such a sequence of arches will constitute a
optimal trajectory.
The example in figure 1.1 is simple enough for a solution to
can be found by enumerating all the admissible paths of the
From A to Z and choose the one with the minimum total arc values. For
more complicated problems, however, a systematic method is needed for
attack. We will discuss this later when we introduce programming.
dynamic in Section 1.4. For now, we will only note that the solution
optimal for the present example is the ACEHJZ road, with US $ 14 as the
minimum production cost. This solution serves to indicate a very
important: A myopic one-stage procedure - in -a-time optimization
it will not affect the overall performance of the optimal trajectory. For example, a
myopic decision maker would have chosen arc AB over arc CA in the
first stage, since the first only involves half the cost of this one
last, however, in the span of five stages, the most expensive arc of the
the first stage of CA must be selected in its place. It is precisely for this reason.
reason, of course, that a method that can take into account the entire period of
planning must be developed.

THE CONTINUOUS VARIABLE VERSION

The example in figure 1.1 is characterized by a discrete stage variable, which

take only integer values. In addition, it is assumed that the state variable for
take values that belong to a small finite set, {A, B,..., Z). If these
variables are continuous

We can instead have a situation as shown in figure 1.2,

where, for example, we have only based five possible paths from A to Z.
Every possible path is now seen to travel through an infinite number of
stages in the interval [0, TI. There are also an infinite number of states in each
route, each state being the result of a particular election made in a
specific stage.
To be specific, let's visualize fig. 1.2 as a map of a terrain.
open, with the phase variable representing length, and the state variable
What latitude represents. Our assigned task is to transport a load.
from point A to Z locating a minimum cost when selecting a travel route
apropiado. El coste asociado con cada posible camino depende, en general, no
not only of the distance traveled, but also of the topography along that path. Without
embargo, in the special case where the land is completely homogeneous, of
so that the cost of transportation per mile is a constant, the problem of
lower cost will simply come down to a shortest distance problem. The
the solution in this case is a straight path, well, because this path implies the
lowest total cost (it has the lowest route value). The straight line solution is,
of course, well known, to the point that one generally accepts it
without demanding to see proof of it.
For most of the problems described in what follows, the variable stage
represent the time; then the curves in fig. 1.2 will represent the trajectory in the
time. As a concrete example, let us consider a company with a share capital
initial equal to A at time 0, and a predetermined target stock capital equal to Z
T moment. Many alternative investment plans during the interval of
time [0, They are capable of reaching the capital objective at time T. and
each investment plan entails a specific capital path and involves a
potential specific benefit for the company. In this case, we can
interpret the curves of figure 1.2 as possible paths of capital and their
route values like the corresponding benefits. The company's problem
it is to identify the investment plan, hence the capital path - that produces the
maximum potential benefit. The solution to the problem, of course, will depend
Crucially, how the potential benefit is related to and determined by the
configuration of the capital route.
From the previous discussion, it should be clear that, regardless of whether the
variables are discrete or continuous, a simple type of optimization problem
the dynamics would contain the following basic ingredients:
a. A certain initial point and a determined final point;
b. A series of admissible trajectories from the initial point to the point
terminal;
c. A set of path values that serve as indices of
performance (cost, benefit, etc.) associated with the various paths; and
d. A goal that has been specified to maximize or minimize the value of the
route or the performance index by choosing the optimal route.

4. ALTERNATIVE APPROACHES TO OPTIMIZATION

DYNAMIC

To address the previously mentioned problem of dynamic optimization, there is

three main approaches. We have previously mentioned the calculation of
variations and dynamic programming. The remaining part, the modern generalization of
The calculation of variation goes under the name of optimal control theory. We are going to give

a brief review of each one.

CALCULATION OF VARIATIONS

The calculus of variations dates back to the 17th century, the calculus of variations is
the classical approach to the problem. One of the first problems that arises is
the determination of the shape of a surface of revolution that finds the
less resistance when moving through some resistant medium (a
surface of revolution with the minimum area). Isaac Newton solved this problem
and declared his results in his Principia, published in 1887. Others them
mathematicians of the time (for example, Juan and Jacobo Bernoulli) also
they studied problems of a similar nature.
These problems can be represented by the following general formulation:

Maximize or minimize

Subject to:

Y y (0)=A (given) y (T)=Z (T, Z given)

Such a problem, with an integral functional in a single state variable, with points
completely specified initial and terminal, and without limitations, is known as
the fundamental problem (or simplest problem) of the calculus of variations. With
the purpose of doing this type of meaningful problems, which, it is necessary that the
integrable functional (that is, the integral must be convergent). We will assume that
this condition is met when we write an integral in the general form.
In addition, we will assume that all the functions appearing in the problem are
continuous and continuously differentiable. This hypothesis is needed because the
the basic methodology underlying that of the variations is very similar to the
of classical differential calculus. The main difference is that, instead of dealing with
the differential dx that changes the value of y = f(x), now we are going to face the '
variation of an entire curve and (t) that affects the value of the functional V [y].
The basic problem of calculating control of variations is presented with the
deduction of the necessary and sufficient conditions of optimality. The result
fundamental is Euler's equation.
In any problem of calculus of variations, each admissible function is assigned
assign a real number, which is established from a functional.
A functional is an application, whose domain is a set of functions, and whose
Range is a subset of R.
 a. Previous Concepts of Problem Formulation in Calculation of
Variations:
In the case at hand, we consider functions J whose domain is the
set Ω

Let's look at some simple examples of functionals:

1) We correspond each function.

How, x is a continuous function, so it is integrable, and therefore, is

a real number. It is therefore a functional.
For sea .In this case, it is not a functional one because the
The derivative of a differentiable function is generally another function, and not a number.

real.
For sea

( )

In this case, it is a functional since, being derivable, the derivative of at the point
the mean of the interval in which it is defined, exists and is a real number.

b. Formulation of the Variational Calculus Problem:

A continuación, se define el problema de cálculo de variaciones para el caso

scaling, with fixed endpoints.
Let the function F be a function of three variables, of class C (meaning it has ...
all the first and second partial derivatives, and they are continuous.
The following functional is considered:
 ∫ ̇ [ ]

Where is the derivative function of regarding It is about finding

that function with first and second continuous derivatives , [ ]
checking that being data, for which the
functional reach the maximum value (or the minimum value).
The problem, therefore, in the case of maximization is

∫ ̇ [ ]

Where we remember that

{ [ ]} ] [

Therefore, for this problem, the feasible set (called the set of functions
admissible) is
{ }

As is common in optimization, considering only the maximum (or the minimum) of the
objective function, in this case of the objective functional, does not imply any loss
de generalidad, ya que

[ ]

Y, furthermore, the element that minimizes it's the same that maximizes . [ ]

c. Necessary first-order condition. Euler's equation:

The condition that we will obtain, called Euler's condition or equation, is
most important of the calculus of variations. Its deduction is very simple and
easily understandable, as it is based on mathematical programming of
differential functions.
Yes it is a local maximum, then in the following condition is verified:
[ ̇ ] ̇ ̇
[ ] [ ]

What is Euler's equation, where it is the partial derivative of regarding

your first variable y it is thė partial derivative of regarding your second
variable .̇

EXERCISE:

Obtain the functions that verify the necessary conditions for local maximum
from the following problem:

∫ ̇ [ ]

In this case, ̇ [ ̇]
Let's calculate their derivatives with respect to and to :̇

̇ ̇
Where from: ̇

As the Euler equation is ̇

En este caso queda así: ̈ , that is to say ̈

Integrating both sides of the equation, we obtain:

̈

What is the only extremal.

By imposing the initial and final conditions now, it is obtained.

So the maximum can only be reached in the function

 OPTIMAL CONTROL THEORY

The continued study of variation problems has led to the development of the
most modern method of optimal control theory. In optimal control theory,
the dynamic optimization problem is seen as consisting of three (instead of
of two types of variables. Apart from the time variable t and the state variable y
In (t), a control variable u(t) is taken into account. In fact, it is the last type of
variable. Which gives the optimal control theory its name and occupies the central place
in this new approach to dynamic optimization. To focus attention on the
control variable implies that the state variable is relegated to a position
secondary. This would only be acceptable if the decision on a control route u (t),
once an initial condition of y is given, determine unambiguously a
path and state variable (t) as a byproduct. For this reason, a
The optimal control problem must contain an equation that relates Y to U:

Such equation, called the equation of motion (or the transition equation or
state equation), shows how, at any moment in time, given the
value of the state variable, the choice of the scheduler that will drive the
state variable and in time. Once we have found the path of
optimal control variables u * (t), the movement equation would make it possible to
construction of the related to the optimal state variable route 30 (t).
The optimal control problem related to the calculus of variations problem
(1.8) is the following: maximize or minimize
Please note that, in (1.9), not only the functional objective contains as a
argument, but it has also changed from V [and] to V [u). This reflects the
made that it is now the fundamental optimization tool. However,
this control problem is closely related to the calculation of the
variations - problem (1.8). In fact, by substituting y(t) with u(t), and
the adoption of the differential equation y(t) U(t) as the equation of motion,
is obtained immediately (1.9). The most significant advance in the theory of
optimal control is known as the maximum principle. This principle is associated
commonly with the Russian mathematician LS Pontryagin, although a mathematician

American, Magnus R. Tlestenes, produced independently a

comparable work in a report by the Rand Corporation in 1949.2 The
the omnipotence of this principle lies in its ability to deal directly
with certain restrictions on the control variable. Specifically, it allows the study
of the problems in which the permissible values of the control variable are
they are confined to other closed, bounded convex ones to fix well. For example, the
the set of t can be the closed interval (0, 13, 0 requiring its (t) 5 1 during
the entire planning period. If the marginal propensity to save is the variable

of control, for example, below, with a restriction can

very well suitable. In summary, the problem addressed by control theory
optimal is (in its simple form) the same as in (1.9), except that a restriction
Additionally, u (t) is in U. It can be added to it. In this sense, the
control problem (1.9) constitutes a special case (without restrictions) when the
U control game is the entire real line.

a. Basic Knowledge:
Optimal control is defined as an admissible control that maximizes the functional.
objective.
The theory of optimal control constitutes a generalization of calculus
variations. This method was developed by the Russian mathematician L.S. Pontryagin,
in the late 1950s. This mathematician developed the condition of
first order to the optimal control problem, which is called the principle
maximum. Difference from the calculus of variations, in the optimal control problem it
It incorporates both the control variable (u) and the state variable (y). Furthermore, the
two variables are related by the equation of motion g (.).El
The objective of optimal control is to determine the trajectories of the control variables and
states that optimize an objective functional:

Maximize: [( ] ∫)

Subject to: ́( )

This problem is very similar to that of the calculus of variations. Optimal control has been
has been applied in the formulation of economic problems since mid
the sixties. The pioneering works were those of Koopmans and Cass, in the
how the optimal growth of an economy is modeled over time.
The approach of this macroeconomic model is simple. On one hand, the
The objective function is the sum of the future profits of the company:

On the other hand, in each period, the economy is subject to a restriction: the
production must be allocated for consumption or for gross capital investment. From this

way
́

Where the production function ́

depends on the capital (k) represents the
variation of capital stock with respect to time or net investment in capital,
the depreciation rate and the depreciation of capital. This constitutes the
equation of motion, and relates consumption (control variable) to capital
existing in the economy (state variable).
In this type of dynamic optimization problem, it is assumed that there exists a
"benevolent dictator" (referred to as social planner), who is interested in
maximize the well-being of society and decide the allocations of consumption and
capital in the economy.

In this way, the problem that the social planner faces is the following:

Maximize:

subject to: ́

Given)

From problem (22) the optimal path of three variables is obtained: the
consumption, CAPITAL (K) and aggregate production .
A detailed review of optimal control theory can be found in Chapter III.
In the development of the theory and applications, the case of a
control variable (u) and state (y).

[Link] of the optimal control theme:

The theory of optimal control, through which problems can be developed
more complex intertemporal optimization. The basic optimization problem
more complex intertemporal. The basic problem of optimal control to be solved is
the following:

Maximize: ∫
Subject to: ́
( Die
( Free
 ] [

As mentioned in the first chapter, in the optimal control problem

basically three types of variables intervene: time (t), the state variable
(y) and the control variable (u). Some economic examples of variables of
control and status could be money issuance and inflation, or spending on
advertising and the sales of a company. In these cases, the first variable, that of
control is subject to the decision of the agent facing the problem of
intertemporal optimization, while the second variable, the state variable, reflects
the result of the decisions made regarding the control variable.

The trajectory of the state variable is determined through the

motion equation or state equation, in which the variation is related
of the state variable with respect to time ( ́ with the variables "t", "y" and "u" to
through the function g (.).
Once the optimal value of the control variable has been selected at a given moment of
time, the function g (.determine the direction of growth of the variable of
state and, in this way, its trajectory over time. Thus, when the
the optimizing agent selects the optimal path of the control variable, affects
both directly through the objective function using the variable 'u', and from
indirect way through the variable 'y', which is defined by the
equation of motion.

On the other hand, in problem (1) a free value of y (T) is considered.

This characteristic is due to the derivation of the first-order condition of the
problema de control optimo, se hace referencia a sendas de control factibles,
similar to those used in the demonstration of Euler's equation. Through
the equation of motion, each feasible control path has a
corresponding feasible trajectory of the state variable. In this sense, if the
the problem would have a terminal value given, the feasible control paths
they would not be arbitrary, but rather predetermined to satisfy the
terminal value of the state variable. In this way, a free terminal value
allows deriving the first-order condition of the optimal control problem.

Regarding the control variable, it is restricted to the set Ω.

which is generally a compact and convex set. This restriction opens the
possibility of corner solutions existing in the optimization problem,
unlike the problems of variational calculus, in which only one
interior solutions are allowed. In some problems, they are not established.
restrictions on the control path (Ω=] ), so the condition u is omitted
(t) .

One of the advantages of the optimal control technique is that it does not require
necessarily the continuity and differentiability of the paths of the variables
of control and state over the entire time horizon (0, T). For the case of the
optimal control path, it is sufficient for it to be continuous by segments or
piecewise continuous. This requirement implies that the trajectory of the variable of
control can present a certain number of points with discontinuities,
as long as at those points it does not take an infinite value.

[Link] ORDER CONDITION: maximum principle:

Just as the calculus of variations bears similarity to optimization.

unconstrained static, optimal control would be equivalent to a
static optimization problem subject to constraints. In this case, the
the problem can be solved using the method of multipliers
Lagrange. From the objective function, the constraint, and an auxiliary variable λ,
known as the Lagrange multiplier, a new function is formed,
called Lagrangian. The values that solve the problem a new
function, called Lagrangian. The values that solve the problem are
determine from the optimization of this function.

Similarly, in optimal control from the intermediate function f (t, y, u), the
equation of motion ́ and an auxiliary variable λ(t), named
co-state variable, the Hamiltonian function is determined as follows:

To determine the path of the control and state variables that solve the
problem, starting from the Hamiltonian function a first condition is employed
order, called the principle of maximum. Next, the following will be derived.
conditions of the maximum principle and some applications will be developed.

[Link] of maximum:

The paths u (t) and (t) and they solve the problem (1) if they satisfy the
conditions of the maximum principle established for the function
Hamiltonian (2)

a)

b) ́

c) ́

d)

The first condition states that the Hamiltonian must be maximized with
regarding the control variable, subject to the constraint given by the set Ω. The
maximization of the Hamiltonian can basically provide two types of
solutions: a solution inside the set Ω or a solution on the boundary.
Assuming that the control set is equal to Ω= ( ) y H is a function
that depends non-linearly on 'u', then we would find ourselves in a
situation as presented. In this case, to maximize H, at point A
it must comply that the first derivative with respect to the control variable is
equal to zero and that the Hamiltonian is concave with respect to 'u'

<0.

On the other hand, with the same set Ω, if H would depend linearly on
the control variable, the first derivative would never be equal to zero.

The second condition constitutes the equation of motion of the variable of

state. The third condition represents the equation of motion of the variable
side by side. These two equations, simultaneously, are called a system of
canonical or Hamiltonian system. Finally, the fourth condition consists of the
transversality condition for the optimal control problem, when the value
the state variable terminal is free.
Example:

To illustrate the principle of maximum, let us first consider an example outside of the
economy: that of finding the shortest path from a given point A to
a given straight line. In the figure, we have plotted point A on the vertical axis.
in the planoty, and we have drawn the straight line as a vertical for t=T.
they show three admissible trajectories (out of the infinite number of them), each with
a different length. The length of any trajectory is the aggregate of
small segments of trajectory, each of which can be considered
like the hypotenuse (which is not drawn) of a triangle formed by small ones
movementsdtydy. If we denote the hypotenuse as dh, by the theorem of
We have Pythagoras:

The division of both sides by and the extraction of the square root yields

[ ()] [ ] …….. (a)

The total length of the trajectory can then be found by integration of

(a) from t=0 to t=T. if we make y=u the control variable, (a) can
to express oneself like

………………… (b)

The minimization of the integral of (b) is equivalent to maximizing the negative of (b).
just as the shortest path problem is:
Maximize ∫
Subject to

The Hamiltonian for the problem is:

DYNAMIC PROGRAMMING

For the first time by the American mathematician Richard Bellman,

dynamic programming presents another approach to the control problem indicated in
The most important distinguishing characteristics of this approach are two: In
first, it incorporates the control problem given in a family of problems
of control, with the consequence that in the resolution of the given problem, in
In reality, we are solving the entire family of problems. Secondly, for
each member of this family of problems, the main focus is on the
optimal value of the functional, V *, instead of on the properties of the optimal YS
access path state (t) (as in the calculation of variations) or the control path
optimal u * (t) (as in optimal control theory). In fact, an optimal value
function - the assignment of an optimal value for each member of this family of
problems - it is used as a characterization of the solution. All of this
Explain better with a specific discrete example. Referring to the figure.
1.6 (adapted from Fig. 1.1), let us first see how the 'embedding' of a
problem that arises. Given the original problem of finding the shortest path
cost from point A to point Z, we consider that the biggest problem
great to find the lowest cost route from each point in the set (A, B, C)
..., Z) for the terminal point of Z. There is then a family of problems.
of components, each of which is associated with a starting point
different. This is, however, not to be confused with the problem of the
variable at the starting point where our task consists of selecting the best
starting point. Here, we will consider all possible points as point
initial legitimate by right of its own. That is to say, apart from the genuine starting point A,

we have adopted many pseudo-initial points (B, C, etc.) The problem

related to the initial pseudo Z point is obviously trivial, since it does not
allows no real choice or control, but is being included in the
general problem in pursuit of exhaustiveness and symmetry. But the component

Problems at the other pseudo-initial points are not trivial. Our problem
original has been thus 'embedded' in a family of significant problems. Given
that all component problems have a unique optimal path value, it is
possible to write an optimal function value
V * = V * (i) (i = A, B,..., Z) which says that we can determine an optimal path value
for each possible starting point. From this, we can also build a function.
optimal policy. Which will tell us the best way to proceed from any point
specific initial i, in order to reach V * (i) through proper selection
of a sequence of arcs that goes from point i to point Z, terminal of
The purpose of the optimal value function and the optimal policy function is easy
to understand, but one can still wonder why we have to go to the
dificultad de encajar el problema, multiplicando así la tarea de solución. La
the answer is that the onboarding process is what leads to development of
a systematic iterative procedure for solving the original problem.
Returning to figure 1.6, let's imagine that our immediate problem is no longer
that of determining the optimal values for stage 5, associated with the three
initial points I, J, and K. The answer is easily seen that V*(I)=3
V*(J)=1 V*(K)=2
After confirming the optimal values of I, J, and K, the task of finding the
minimum cost values V * (G) and V * (H) become easier. Returning to stage 4
and the use of optimal information - value obtained previously in (1.10),
we can determine V * (G), as well as the optimal GZ path (from G to Z) as
continue. If we take the GIZ route, the resulting route value will be the value of GI
arch more V * (I). Likewise, if we take the GJZ route, the route value
the result will be the value of arc GJ plus V *(J). Thus, the minimum cost of letter G
to indicate Z is:
(1.11) * V (G) = min (GI arc value + V * (I), GJ arc value + V * (J))
= min (2 + 3,8 + 1) = 5 [The optimal trajectory. GZ is GIZ]

To indicate that the optimal path from G to Z must pass through I, we have drawn
an arrow pointing towards the I of G, the number 5 on the arrow shows the value of
the optimal route V (G). In the same way, we encounter
(1.12) * V (H) = min ( value of arc HJ + V * (J), value of arc HK + V * }
=min (4 + 1, 6 + 2) = 5 [The optimal path Hz is HJZ.]
Note again the arrow pointing towards the J of H and the number on it. The set
of all those arrows constitutes the function of optimal policy, and the set of
all the numbers in the arrows constitute the optimal value function. With the
knowledge of V * ( G) and V * ( H), then we can go back one more stage
to calculate V * (D), V * (e), and V * (F) and the optimal routes DZ, EZ, and FZ- of
a similar way. And, with two more of these steps, we will be back to the
stage 1, in which we can determine V * (A) and the optimal path AZ, that is,
solve the original problem given.
The essence of the iterative solution procedure is captured in the principle of
Bellman's optimality, which states, more or less, that if cutting the first
arc of an optimal sequence of arcs, the remaining abbreviated sequence still
it must be optimal in its own right - like an optimal route from its starting point
to the endpoint. If EHJZ is the optimal path from E to Z, for example,
then HJZ must be the optimal route from H to Z. On the contrary, if HJZ is already
known for being the optimal path from H to Z, then a longer path than
Optimal step to H must use the sequence HJZ at the end of the queue. This
reasoning is behind the calculations in (1.11) and (1.12). But keep in mind
that in order to apply the principle of optimality and the iterative procedure
To outline the optimal path from A to 2, we need to find the value
optimal associated with all possible points in figure 1.6. This explains by
what we have to integrate the original problem. Although the essence of the
dynamic programming is sufficiently clarified by the discrete example in the
Figure 1.6, the complete version of dynamic programming includes the case of
continuous time. Unfortunately, the solution to continuous time problems
dynamic programming involves the most advanced mathematical topic of the
partial differential equations. Additionally, partial differential equations
they usually don't provide analytical solutions.

5. EXAMPLES OF DYNAMIC OPTIMIZATION

in Continuous Time
To solve problems of the type we will see in class, we will apply a
result known as the Maximum Principle. In general, this theorem is
describe de la siguiente forma. Supongamos que tenemos el problema de
maximize
These last conditions are called transversality conditions and
to the co-state functions. Conditions (5) to (8) are sufficient (in addition
necessary) for a solution to the problem if the functions f and g are concave
in (x, u).
If the time horizon were finite, that is, if the problem were to maximize
with respect to x(t) and y(t) the function
 b. Discrete Time
To understand the maximum theorem, let's think about the problem but in
discrete time and finite horizon. We want to choose x(t+1) = [x1(t+ 1),... ,xn(t+
1)] y u(t)=[u1(t),... ,um(t)] to maximize