Static and Dynamic Optimization

Static and Dynamic Optimization

Course Introduction

Niels Kjølstad Poulsen

Build. 303b, room 016 Section for Dynamical Systems

Dept. of Applied Mathematics and Computer Science The Technical University of Denmark

Email: nkpo@dtu.dk phone: +45 4525 3356 mobile: +45 2890 3797

www2.imm.dtu.dk/courses/42111

L1

Dynamic Optimization

What is Dynamic Optimization?

Dynamic Optimization has 3 ingredients:

A performanceindex(cost function, objective function) depending on the states and decisions.

In our case it is a summation (or integral) of contribution over a period of time of fixed or free length (might be a part of the optimization).

Eventually someconstraints on the decisions or on the states.

Somedynamics.

Here (in this course) described by a state space model.

Lets have a look at some examples:

Ex1: Optimal Pricing (simplified)

We are producing a product (brand A) and have to determine its price in order to maximize our income.

There is a competitor product B and a problem.

If we are to modest we might have almost all the costumers but we will not earn that much.

If we are to greedy then the bulk majority of the costumers will bye the other brand B.

Optimal Pricing - the performance index

We have to decide the price of the productui∼u (ubeing the production cost) in each interval.

0 1 2 N

LetMbe the size of the marked and letxi(0≤xi≤1) be the (A) share of the marked in the i’th interval.

Objective: to make some money - i.e. to maximize

M ax J where J=

N−1

X

i=0

M¯xi ui−u

¯ xi= 1

2(xi+xi+1)

More precisely,xiis the marked share at the beginning of intervaliandx¯iis the average share of the marked in intervali.

Optimal Pricing - the dynamics

x

1−x

p A q

B

Transition probability A−>B

A −> B

price

p 1

0

Escape prob. Attraction prob.

B −> A

price Transition probability B−>A q

0 1

Dynamics: A→A B→A

xi+1= 1−p[ui]

xi+q[ui] 1−xi

x0=x₀

Recap Optimal Pricing

Dynamics:

xi+1= 1−p(ui)

xi+q(ui) 1−xi

x0=x₀ Objective:

M ax J where J=

N−1

X

i=0

Mx¯i ui−u

Notice: This is a discrete time model. No constraints. The length of the period (the horizon,N) is fixed.

Ifui=u+ 5(u= 6,N= 10) we getJ= 8(rounded to integer).

0 1 2 3 4 5 6 7 8 9

0 0.05 0.1 0.15 0.2 0.25

x

0 1 2 3 4 5 6 7 8 9

0 2 4 6 8 10 12

u

Optimal pricing (given correct model):J= 27(rounded to integer).

0 1 2 3 4 5 6 7 8 9

0 0.2 0.4 0.6 0.8 1

x

0 1 2 3 4 5 6 7 8 9

0 2 4 6 8 10 12

u

Notice different axis for x.

Free Dynamic Optimization

Dynamics (described by a state space model):

xi+1=fi(xi, ui) x0=x₀

Objective (to optimize the index):

J=φN(xN) +

N−1

X

i=0

Li(xi, ui)

HereNandx₀are fixed (given),J,φandLare scalars.xiandfiaren-dimensional vector and vector function anduiis a vector of decisions.

Notice: no constraints (except given by the dynamics).

Ex2: Inventory control - A classical OR problem

Stock Dynamics:

xi+1=xi+ui−si x0=x₀ Stock : x_i 0≤x_i≤x¯ Production: ui 0≤ui≤u¯

Sale: si 0≤si≤min(xi, wi)

Order: wi

Notice: constraints on decisions and states. Stochastics involved.

Goals:

to earn some money

to avoid situation with no stock to reduce stock charge to obtain an even production.

Objective (index to be maximized):

J=

N−1

X

i=0

p si−c ui−k xi−h M ax wi−si,0

wherep,c,kandhare constants (prices).

Constrained Dynamic Optimization

Dynamics (described by a state space model):

xi+1=fi(xi, ui) x0=x₀

Objective (to optimize the index):

J=φN(xN) +

N−1

X

i=0

Li(xi, ui)

Constraints:

g(xi, ui)≤Ci

Variations of the problem

Dynamic optimization with:

Terminal constraints (take the system from one place to another).

Constraints (onuiandxiwithin the horizon).

Continuous time problems

Open final time (Minimum time problems).

Stochastic elements (orders in the inventory problem).

2 examples.

Minimum drag nose shape (Newton 1686)

Find the shape i.e.r(x)of a axial symmetric nose, such that the drag is minimized.

θ

a

l

x y

V Flow

The decisionu(x)is the slope of the profile:

∂r

∂x=−u=−tan(θ) r(0) =a

Minimum drag nose shape (Newton)

Find the shape i.e.r(x)of a axial symmetric nose, such that the drag is minimized.

D=q Z a

0

Cp(θ)2πrdr

q=1

2ρV² (Dynamic pressure) Cp(θ) = 2sin(θ)² for θ≥0

θ

a

l

x y

V Flow

Minimum drag nose shape (Newton)

θ

a

l

x y

V Flow

Dynamic:

∂r

∂x=−u r0=a tan(θ) =u Cost function (drag coefficient, including a blunt nose):

Cd= D

qπa² = 2r²_l + 4 Zl

0

ru³

1 +u²dx ≤1

Minimum drag nose shape (Newton)

0 0.5 1 1.5 2 2.5 3 3.5 4

-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

r//a

x/a

Cd = .098

.750 .321 .165

Free Dynamic Optimization (C)

Find a functionutt∈[0; T]which takes the system system

˙

x=ft(xt, ut)

from its initial statex₀along trajectories such that the performance index J=φT[xT] +

Z T 0

Lt(xt, ut)dt is minimized.

Min. Time Orbit Transfer

Thrust direction program for minimum time transfer from Earth orbit to Jupiter orbit.

-6 -5 -4 -3 -2 -1 0 1

-1.5 -1 -0.5 0 0.5 1 1.5 2

x/ro

y/ro

EARTH ORBIT JUPITER ORBIT

SUN

˙

r=u u˙=v² r − 1

r² +asin(θ) v˙=−uv

r +acos(θ)

Min. Time Orbit Transfer

-6 -5 -4 -3 -2 -1 0 1

-1.5 -1 -0.5 0 0.5 1 1.5 2

x/ro

y/ro

EARTH ORBIT JUPITER ORBIT

SUN

d dt



 r u v



=











u v²

r − 1

r²+asin(θ)

−uv

r +acos(θ)





















Initial conditions Terminal conditions

J=T











Web page

Concluding remarks

have 42111 and your study nomber in the subject field when emailing us Matlab available on Gbar download site