CS计算机代考程序代写 Extension:

Extension:
Variable end‐point conditions
Some applications involve the case when one of the end points, or both, are variable (not fixed).
How to solve the problem of Lagrange minJ(x)tb f(x,x,t)dt
t a
when ta , tb , x ta  and x tb  are NOT fixed.
4/20/2020 @2020 New York University Tandon 376 School of Engineering

Classical Example
Context: A boatman wants to find the optimal path leading to the shortest time when crossing a river
from a fixed initial point on one bank to an unspecified terminal point on the other bank.
4/20/2020 @2020 New York University Tandon 377 School of Engineering

4/20/2020
@2020 New York University Tandon School of Engineering
378
Left bank
y

Right bank
0l
x
Water current

4/20/2020
@2020 New York University Tandon 379 School of Engineering
Standing Assumptions
H1: There is no cross current so that the current velocity is everywhere directed downstream along the y-direction.
H2: The downstream current speed w depends only on x :
ww(x), 0xl.
H3: The boat travels at a constant natural speed v0 .


 x   ( t )  v 0 c o s  ( t ) ,
Modeling
If the path of the boat is represented by a curve  :  x    t 
yt for0tT
for suitable functions  t ,  t , then the absolute
velocity of the boat satisfies
  
where (t) is the steering angle of the boat from the x-axis.

 y   ( t )  v 0 s i n  ( t )  w  t
4/20/2020 @2020 New York University Tandon 380 School of Engineering

0 0dx dt Then,
T  T dx
0 v0 cos
Time of Transit
The time of transit T of the boat can be calculated as TTdtT dtdx, notingdx(t).
. note: cos  0
Now, we use x as the parameter(why possible?) for the curve  :
: yY(x), 0xl. Indeed,Y(x)  (x) .
1 
4/20/2020 @2020 New York University Tandon 381 School of Engineering

Note that
Y(x)  dy  (t)  sin  e(x) ,
dx (t) cos where e(x)w(x).
v0 Then,
Ycosesine 1cos2 e(x)Y(x) 1e(x)2 Y(x)2
 cos 1Y(x)2
.
4/20/2020 @2020 New York University Tandon School of Engineering
382

Problem Formulation
Summarizing the above, the minimum transit time problem becomes:
1 l 1Y(x)2 minTT(Y)v0 0 e(x)Y(x) 1e(x)2 Y(x)2 dx
where
Y C1[0,l] the class of continuously differentiable functions
over 0  x  l.
4/20/2020 @2020 New York University Tandon 383 School of Engineering

Comment
Clearly, the above min problem is subject to one constraint at the starting point:
Y(x0)y0, inthepresentcase, x0,y0(0,0)
along with the terminal constraint C:(x,y)0, inthiscase,xl0.
No constraint on y ! Such a modified problem is often called:
James Bernoulli’s Brachistochrone Problem (1697).
4/20/2020 @2020 New York University Tandon 384 School of Engineering

Variable End‐point Conditions
It corresponds to the following situation: for the optimization problem
minJtb fx,x,tdt, t
a
thevaluesofta, tb, xta, xtbarenot
necessarily fixed.
Question: what are the end-point conditions
that the optimal variables must satisfy?
4/20/2020 @2020 New York University Tandon 385 School of Engineering

The Transversality Condition
(Necessary Condition)
4/20/2020
@2020 New York University Tandon 386 School of Engineering
Optimal values of ta , tb , xta , xtb  must satisfy:
t
f xf tb f x(t)b 0.
t  x ta x ta

4/20/2020
@2020 New York University Tandon 387 School of Engineering
Ideas of Proof
For simplicity, assume that one end point, say ta,xtaisfixed.Then,ta 0,xta0.
In this case, the transversality condition reduces to:
  f  x f   t    f  x ( t )   0 .
 x tb x
tb

4/20/2020
@2020 New York University Tandon School of Engineering
388
ta
tb
t
x t   xv (t )
xt
tb tb

t   ta
Ideas of Proof (cont’d)
Consider the increment J :
 J  b  f x   x , x   x , t  f x , x , t  d t
   tbtb fxx,xx,tdt
vv
tb v  v
tbfxfxdtfx,x,t| t taxv xv ttb b
where Taylor’s series expansion was used to ignore H.O.T. Via integration by parts,
tb t tbd
  f x  f x  dt   f x     f  f  x dt
xv xvxvb xdtxv ta ta ta  
4/20/2020 @2020 New York University Tandon School of Engineering
389

Ideas of Proof (cont’d)
tb t tbd
  f x  f x  dt   f x     f  f  x dt
xv xvxvb xdtxv ta ta ta  
f x  0, usingELequationwithx t 0. xvtb va
Therefore,

 J   f x  x v  t  f x , x , t | t  t  t b
b fxft fx ,
b
 x  t  t b x t  t b
usingxv tb x xb x xb tb.      
So, J  0  the transversality condition.
4/20/2020 @2020 New York University Tandon 390 School of Engineering

4/20/2020
@2020 New York University Tandon School of Engineering
Special Cases
Case 1: All variations are independent The transversality condition
t
fxftb fx(t)b 0
t  x ta x ta
implies
f xf t f xf t
0,
391
 x  t  t a  x  t  t b fxx(t) fxx(t) 0.
tta ttb

Case 2:
x(ta ), x(tb ), ta fixed; tb variable. The transversality condition
4/20/2020
@2020 New York University Tandon School of Engineering
Special Cases
t
f xf tb f x(t)b 0
t  x ta x ta
implies
f(x,x,t)x(t)f (x,x,t)
0.
392
 x  t  t b

4/20/2020
@2020 New York University Tandon School of Engineering
393
Example: an electric circuit
vi (t) –
C
v0(t)
i(t) +
R

Problem of Optimization
Maximize the average value of the output voltage v0 (t ) : JT v0(t)dt
T KTi2RdtT RC2v2dt
0
subject to the limited energy constraint:
00

0
withfixedv0(ta)0atta 0, andvariablev0(T)V.
4/20/2020 @2020 New York University Tandon 394 School of Engineering

Problem of Optimization
The augmented functional is defined by: J 1Tv hRC2Tv2dt.
a T0 0 1 0
We are interested in finding the optimal value
V* ofVv(T)thatmaximizesJ. 0a
4/20/2020 @2020 New York University Tandon 395 School of Engineering

4/20/2020
@2020 New York University Tandon 396 School of Engineering

v0 
10, v (0)0, v (T)V 00
Outline of Solution
Using the Euler-Lagrange equation, we have
with 1/2hRC2T. 1
It is easy to solve the above linear equation:
v (t)ct2 ct 021
and, in particular,
V  v (T )  c T 2  c T . 021

To determine the values of c and c , let’s invoke 12
the transversality condition to this example:
f  v (T)0  2hRC2v (T)v (T)0
a0 100 v
 0 tT
becauseta 0,tb Tandv0(0)arefixed.
So, it holds:
v (T )  2c T  c  0 (1)
0 2 1
Applying the constraint equation to arrive at
KT 21 
 2ctcdt 4c2T36ccT23c2T (2)
RC2021 32 21 1
4/20/2020 @2020 New York University Tandon 397 School of Engineering

4/20/2020
@2020 New York University Tandon 398 School of Engineering
Outline of Solution
By eqs. (1) and (2), we obtain:
1/2 1/2
c2T 3K  ,c 3K  .
4RC2T3  Therefore, the optimal value of V is:
1 4RC2T3  2 
1/2 V*3KT .
4RC2  

Exercise
What is the shortest path between two points on a sphere?
4/20/2020 @2020 New York University Tandon 399 School of Engineering

Solution (Geodesics on a Sphere) Problem formulation
Introduce “spherical polar coordinates” r, ,  : xrsincos, r x2 y2 z2,
yrsinsin, tan1 y/x, zrcos, cos1 z/r.

4/20/2020 @2020 New York University Tandon 400 School of Engineering

Solution (Geodesics on a Sphere) Then the surface of a sphere S
of radius a centered at 0 is:
 x  a s i n  c o s  ,
 y  a s i n  s i n  ,
 z  a cos  , for 0     , 0    2 .
Let  be a curve on the surface S that connects
two points P , P which is parametrized as: 01
4/20/2020
@2020 New York University Tandon 401 School of Engineering

Solution (Geodesics on a Sphere)  x  a s i n  c o s   ,
  :  y  a s i n  s i n   ,
zacos, for  01

where   is a function relating , on  , and 
 ,  correspond to P ,P, resp., i.e. 01 01
z x2y2z2cos,i0,1 iiiii
i 0, .
4/20/2020 @2020 New York University Tandon 402 School of Engineering

Solution (Geodesics on a Sphere) The length L of  is thus given by:

L 0 dx/d dy/d dz/d d
which implies
 0
1222
12
1 sin2d  
La
 1 f   , d.
0
To sum up, the problem reduces to minimizing L w.r.t.
=  , subject to the terminal constraints: taniyi /xi,i0,1.
4/20/2020 @2020 New York University Tandon 403 School of Engineering

Solution (Geodesics on a Sphere)
By EL equation, it holds for any extremum function   : d / d f , f , 0
where the last equality holds because f does NOT depend on . Thus,
f   , C.    
Simple computation gives
A/sin sin2sin2 for some constants A, .
4/20/2020 @2020 New York University Tandon 404 School of Engineering

Solution (Geodesics on a Sphere) Letting tan1/u, itholds:
d/dutan/ 1u2 tan2
that, upon integration on both sides, yields
cos1utan, or,
(*) cos1tan/tan
where the constants ,  can be determined using
the end conditions.
Using the Cartesian coordinates, (*) can be rewritten as: (**) xcos  ysin  ztan, (a plane crossing the center).
So, any geodesic curve indeed is an arc of some circle.
La, with theangle
4/20/2020 @2020 NewYorkUniversityTandon betweenOP andO4P05. School of Engineering 0 1

Outline
Dynamic Programming
A method for Multi-Stage Decision Making
• Basics of dynamic programming • Application examples
4/20/2020
@2020 New York University Tandon School of Engineering
406
Richard Bellman

Bellman’s Principle of Optimality
PO: An optimal policy has the property that whatever the initial state and the initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.
4/20/2020 @2020 New York University Tandon 407 School of Engineering

4/20/2020
@2020 New York University Tandon 408 School of Engineering
Illustrative Figure of PO
Optimal trajectory cost
x(tf )
x(t)
J*(t0,x(t0))
x(t0 )

Illustrative Example of A Routing Network
4/20/2020
School of Engineering
409
d
k h
8 4b26
9 11
3 g 16
9 5 e 10i
a
7c47
l 14f 6
12j 8 @2020 New York University Tandon
m

Illustrative Example of A Routing Network (cont’d)
Problem:
Find the minimum-cost path that starts at node a and ends at any of the nodes k, l, m
4/20/2020 @2020 New York University Tandon 410 School of Engineering

Illustrative Example of A Routing Network (cont’d)
We will find the optimal path by performing a backward pass through the network.
Let J * be the minimum cost from a generic node q
q to any one of three possible final nodes. Then, J* 16, J* 8, J* 7, J* 6.
ghij
The next stage yields
J* min 3J*, 11J* min 19, 19 19.


dgh
4/20/2020 @2020 New York University Tandon 411 School of Engineering

Illustrative Example of A Routing Network (cont’d)
Thus, we have two optimal paths from node d: dgk and dhk. Similarly,
J* min 6J*, 10J* 
min 68, 107 14 
ehi and
J* min 4J*, 12J* 
min 47, 126 11. 
fij
Therefore, the optimal path emanating from node e
is ehk, and the path from node f is fil.
4/20/2020 @2020 New York University Tandon 412 School of Engineering

Illustrative Example of A Routing Network (cont’d)
The next stage yields
J* min 9J*, 2J* 
min 919, 214 16 
bde and
J*  min 5 J*, 14 J* 
 min 514, 1411 19. 
cef
Therefore, the optimal path emanating from node b is behk, and the path from node c is cehk.
4/20/2020 @2020 New York University Tandon 413 School of Engineering

Illustrative Example of A Routing Network (cont’d)
Finally, the initial, and thus final, stage yields
J* min 4J*, 7J* min 416, 719 20.


abc
Hence, the optimal, minimum total cost route from node a to any one of the three nodes k, l, m is abehk, and the total cost of this path is 20.
4/20/2020 @2020 New York University Tandon 414 School of Engineering

Comment:
In a nutshell,
“Dynamic Programming” is a technique for solving a complex problem in such a way that the problem is broken into several simpler steps.
4/20/2020 @2020 New York University Tandon 415 School of Engineering

4/20/2020
4573
@2020 New York University Tandon
416
1
43266 10
2751
413 343
9
4
Exercise
Find the shortest path from node 1 to node 10 in the following network. Also, find the shortest path from node 3 to node 10.
264 3383
School of Engineering

Solution to the “Blood Diamond” Problem
(97, 0, 1, 2, 0) or (97, 0, 1, 0, 2)
Do you know why?
4/20/2020 @2020 New York University Tandon 417 School of Engineering

Detailed Analysis based on PO
• IfNos.1‐3die,itremainsonlyNo.4andNo.5.
Then, No. 5 will vote against whatever No.4 proposes
to earn all diamonds.
So, the only option for No. 4 is to vote for No.3.
• AssoonasNo.3knowsthispoint,hewillpropose (100, 0, 0) to earn all diamonds while No.4 has to vote “yes” in order to survive.
4/20/2020 @2020 New York University Tandon 418 School of Engineering

Detailed Analysis based on PO
• As soon as No.2 knows this point, he will propose (98, 0, 1, 1) to win the support from No.4 and No.5, while giving up on No.3
• When No. 1 is aware of the optimal strategy of No.2, he will give up on No.2 and then propose (97, 0, 1, 2, 0) or (97, 0, 1, 0, 2) to win 3 votes including his own vote, the majority votes!!
4/20/2020 @2020 New York University Tandon 419 School of Engineering

Application to a Control Problem
Find a sequence of control actions {u(k)} to minimize the performance index
N  1 kk0
J (N,x(N))
x(k1) f(k,x(k),u(k)), x(k0)x0.
F(k,x(k),u(k))
where x(k) is the solution of the discrete-time system:
4/20/2020 @2020 New York University Tandon 420 School of Engineering

4/20/2020
@2020 New York University Tandon 421 School of Engineering
A Control Problem (cont’d)
Let J * be the minimum cost of transferring the system from k
x(k)totheterminalstatex(N).Clearly,J* (N,x(N)). N
Using the PO, we obtain J* (x(N 1))
N1

min F(N1,x(N1),u(N1))J*(x(N))
N
 minF(N1,x(N1),u(N1))(N,x(N))
u(N1) u(N1)
 min{F(N1,x(N1),u(N1)) u(N1)
  ( N , f ( N  1, x ( N  1) , u ( N  1) ) ) } .

A Control Problem (cont’d)
A recursive expression of this backward pass is (k0  k  N ): J*(x(k)) min F(k,x(k),u(k))J* (x(k1))
 k u(k) k1
 k1
min F(k,x(k),u(k))J* (f(k,x(k),u(k)) .
u(k)
The backward pass is completed when k  k0 .
Sincex0 xk0isknown,wefinduu(k0)intermsofx0. Then, proceed with the forward pass:
x(k), u(k)  x(k 1), u(k 1)
4/20/2020 @2020 New York University Tandon 422 School of Engineering

Consider a scalar discrete-time system x(k1)2x(k)3u(k), x(0)4,
and the performance index 211
An Exercise
J  x(2)10  x2(k)u2(k) .    
2 k0
Goal: findtheoptimalu*=(u(0), u(1))thatminimizesJ.
4/20/2020 @2020 New York University Tandon 423 School of Engineering

Solution
u(0) = 2.0153, u(1) = ‐1.9237.
4/20/2020 @2020 New York University Tandon 424 School of Engineering

Allocation Problem: the scalar case
4/20/2020
@2020 New York University Tandon 425 School of Engineering
We want to maximize a noninteracting performance index
subject to
K
g (x )  b, g (x )  0, x  . iiiii
K
P   f (x )
ii i1
i1

Solution based on PO
Foreaseofnotation,introducetheresourcevariableK : K
g(x) b
iiK i1
and define
F ( ) max f (x ) f(x).
KK KK
x ,,x 1K
K1 
ii
 i1 
Also, define the policy variable x ( ) which maximizes ˆK K
theaboveF ( )foragiven .Particularly,x (b)x* . KK K ˆKK
4/20/2020 @2020 New York University Tandon 426 School of Engineering

Solution based on PO (cont’d)
F ( )f (x ( )) max
K1 
KK KˆKK K1
x ,,x
1 K1
f(x) ii
ˆ subjectto g(x) g x ( ).
i1 Therefore,

K1 F()f(x())F {g x()}
 K K K ˆK K K1 K K ˆK K
or, equivalently,
F ( )max f (x )F  g (x )
  
K K xK K K K1 K K K subjectto gK(xK)K.
4/20/2020 @2020 New York University Tandon 427 School of Engineering
i1 
iiKKKK
F   K1 K1

Solution based on PO (cont’d)
In brief, the K -stage problem reduces to a simpler (K 1)-stage problem:
K  1 F()max f(x)
K1 K1
ii 1 K1
subjectto
g(x) g (x ) . i i K K K K1
4/20/2020
@2020 New York University Tandon 428 School of Engineering
i1
x ,,x
i1 K  1

Solution based on PO (cont’d)
In general, the following recurrence relation holds:
F()maxf(x)F g(x)
  
k k xk k k k1 k k k subject to
g ( x )   ,  k  1, 2 ,  , K , F (  )  0 . kkk 00
So, the original K-stage problem is replaced by K (easier) one-stage decision problems.
4/20/2020 @2020 New York University Tandon 429 School of Engineering