Revision 1 PDF

Preview

Summary

MATH3404 Revision...

Description

MATH3404 (revision1) Optimization in Rn Problem III. Minimize f (x) in Rn given that x satisfies the equality constraints gj (x) = cj ,

j = 1, ..., m < n,

where c1 , ..., cm are given numbers. Theorem 3.1. Let f (x) and gj (x) be defined and have continuous second derivatives in some open region of Rn . Then necessary condition that a minimize f (x) with the constraints gj (x) = cj ,

j = 1, ..., m < n

is that there exist m-Lagrange multipliers λ1 ,...,λm such that   m ∑  grad f + λj gj  = 0 at a j=1

For g = (g1 , · · · , gm ), we define 

∂g1 ∂x1

B = ∇g =  ·

∂g1 ∂xn

1

··· ··· ···

∂gm ∂x1



· 

∂gm ∂xn

2

Bordered Hessian H=

(

HL BT

B O

)

, at x = a.

is a (m + n) × (m + n)-matrix, where O is a m × m zero matrix. Point a at which grad L = 0 and detH = 0 is called a nondegenerate critical point. Theorem 3.2. : (Nec. & Suff. for a minimum) Let a be a non-degenerate critical point for f , subject to gi = ci , i = 1, ..., m. A necessary and sufficient condition that x = a is a point where f has a local minimum subject to the constraints is that hT HL h ≥ 0 for all tangent vectors h.

∗

Sufficient condition for a local maximum is that hT HL h ≤ 0, for all tangent vectors h. ∗ ∗ Recall vector h is tangent if hT grad gi = 0, for all i.

3

Example. Find the critical points of the following constrained optimization problem f (x1 , x2 , x3 ) = x21 + 2x22 + 2x32 subject to g(x1 , x2 , x3 ) = x1 + x2 + x3 = 4. and check that they are non-degenerate. Determine the local minima and maxima. Solution. Lagrangian is L(x) = f (x) + λg(x) = x12 + 2x22 + 2x32 + λ(x1 + x2 + x3 ). Then

∂L = 2x1 + λ = 0 ∂x1

(2.1)

∂L = 4x2 + λ = 0 ∂x2

(2.2)

∂L = 4x3 + λ = 0 ∂x3

(2.3)

It follows from (2.1)-(2.2) that x1 = 2x2 and from (2.1)(2.2) that x2 = x3 . Substituting these into the constrain g(x) = 4 yields x2 = x3 = 1,

x1 = 2,

λ = −4

4

The Hessian matrix  2 0 HL =  0 4 0 0

of L is    1 0 0  and B = ∇g =  1  1 4

The bordered Hessian at the point (2, 1, 1) is

H=

(

HL BT

2 0 ) B 0 4 = 0 0 0 1 1

0 0 4 1

1 1  1 0

We find that det H = 0 at the point (2, 1, 1).

Moreover, for any tangent vector hT = (h1 , h2 , h3 ) with hT ∇g = 0, hT HL h = 2h12 + 4h22 + 4h32 ≥ 0 Then (2, 1, 1) is a local minimal point. There is no maximal point. 

5

Optimization for functionals Theorem 4.1. In order that x = x∗ (t) should be a min∫ t1 imizing curve, (i.e. Minimize J [x] = f (t, x, x)dt, ˙ t0 2

x(t0 ) = x0 , x(t1 ) = x1 ) in the class of C functions to the fixed endpoint problem it is necessary that ( ) d ∂f ∂f − =0 (4.1) ∂x dt ∂ x˙ at each point of x = x∗ (t). Definition. An extremal of minimizing J [x] with variable endpoint ⇔ transversality + E − L equation. ∫ T Example 1. Find the extremal of x˙ 2 t3 dt, x(1) = 0, 1

T > 1 is finite and x(T ) lies on x = c(t) =

2 t2

− 3.

Solution. Since f (t, x, x) ˙ = t3 x˙ 2 ,

∂f = 0, ∂x

∂f = 2t3 x˙ ∂ x˙

Using the E-L equation, extremals have the form x=

k + l. t2

x(1) = 0 ⇒ l = −k ⇒ x =

k − k. t2

6

Use the transversality condition to find the 2 unknowns k, 2 T . Now x˙ = − 2k − 3 when t = T, so t3 and x(t) = c(t) = t2 c(t) ˙ = − t43 . Transversality Condition

∂f (t1 ) = 0 ∂ x˙ replace t1 by T :

f (t1 ) + [c(t ˙ 1 ) − x˙ ∗ (t1 )] f (t) = x˙ 2 t3 ,

x(T ˙ )2 T 3 + 2x(T ˙ )T 3 [−4/T 3 + 2k/T 3 ] = 0 −

2k 3 T + 2T 3 [−4/T 3 + 2k/T 3 ] = 0 3 T 2k − 8 = 0 , k = 4.

Still have to determine T : x(T ) lies on x = c(t) =

2 −3 t2

4 x(T ) = 2/T 2 − 3 = 2 − 4 T √ √ 2 =1 T = 2 (T > 1, so not − 2). T2 √ ∗ Consequently x (t) meets target curve at T = 2, when x(T ) = −2.

7

Example 2. Find the extremal of J=

∫

T

(x2 + x˙ 2 )dt

0

when x(0) = 1,

T = 2;

Solution. Since f does not involve t explicitly, we could use the other form, but this is easy with the E-L eqn ( ) d ∂f ∂f − =0 ∂x dt ∂ x˙ d ˙ = 0 , x¨ − x = 0. 2x − (2x) dt λ2 − 1 = 0, λ = −1, +1 , e−t , et x = Aet + Be−t

(1) x(0) = 1 ⇒ A + B = 1. Transv. condn. is ∂f (T ) = 0 ⇒ 2x(T ˙ ) = 0 i.e. x(2) ˙ =0 ∂ x˙ Ae2 − Be−2 = 0 ⇒ B = Ae4 The extremal is x =

cosh(t−2) cosh 2 ,

x(2) = 1/ cosh 2.

8

Isoperimetric Problems Find a minimizing curve for J [x], while x = x(t) gives another functional I[x] a prescribed value. ∫ t1 Problem: Minimize J [x] = t0 f (t, x, x)dt, ˙ x(t0 ) = x0 , x(t1 ) = x1 , subject to the constraint I=

∫

t1

g(t, x, x)dt ˙ = c. t0

The problem is symbolically the same as Lagrange multiplier problems. What is surprising is that the solution is formally the same. Theorem. For x = x∗ (t) to be a solution of the constrained problem, it is necessary that it should be an extremal of J [x] + λI[x] ∫ t1 {f (t, x, x) ˙ + λg(t, x, x)} ˙ dt = t0

for some cosntant λ.

9

Example 1. Minimize ∫ 1 x˙ 2 dt, J=

x(0) = 2,

x(1) = 4,

0

subject to

∫1 0

x dt = 1.

Solution. Lagrangian J + λI is just

∫

1

(x˙ 2 + λx)dt. Con0

sider the extremals of this functional. Euler-Lagrange eqn. is d ˙ =0 λ − (2x) dt i.e. x¨ = λ/2, or x = λt2 /4 + kt + l. From the endpoint conditions: 2 = l;

4 = λ/4 + k + 2 ,

k = 2 − λ/4.

That is, x = λt2 /4 + (2 − λ/4)t + 2. Remember to use the ∫ 1 x dt = 1 constraint 0

λ/12 + (1 − λ/8) + 2 = 1 2 = λ/24 ,

λ = 48.

x = 12t2 − 10t + 2. • E–L eqn. on Lagrangian give DE & unknown constants k, l, λ. • Endpoints gave 2 conditions. • Constraint gives extra condition.

10

Question. (assignment 2) Let x = x(t) : [t0 , t1 ] → R be a curve in C 2 with boundary conditions x(t0 ) = x0 and x(t1 ) = x1 . Consider a functional

J [x] =

∫

t1

[a(t)x˙ 2 + x2 ] dt, t0

where a(t) is a C 2 -function and a(t) ≥ 1 for all t ∈ [t0 , t1 ].

Assume that x∗ = x∗ (t) be an extremal for J [x] and x∗ also satisfies the boundary conditions x∗ (t0 ) = x0 and x∗ (t1 ) = x1 . Prove that x∗ = x∗ (t) must be a minimizer of J [x] for all C 2 -curve x(t0 ) = x0 and x(t1 ) = x1 . Solution. Let f (t, x, x) ˙ = a(t)x˙ 2 + x2 . Then the EularLagrangian equation is d ∂f − ∂x dt

(

∂f ∂ x˙

)

= 0.

i.e. Since x∗ is a solution to 2x −

0.

d (2a(t)x) ˙ = 0. dt

Let y = x∗ + η for any η ∈ C 2 [t0 , t1 ] with η(t0 ) = η(t1 ) =

11

∗

∆J = J [y] − J [x ] = =

∫

=

∫

∫

t1 2

2

[a(t)y˙ + y ] dt −

t0

t1 t0 t1

[a(t)(x˙ ∗ + η) ˙ 2 + (x∗ + η)2 ] dt −

∫

∫

t1 t0 t1

2

2 [a(t)x˙∗ + x∗ ] dt 2

2 [a(t)x˙∗ + x∗ ] dt

t0

[a(t)η˙ 2 + 2a(t)x˙ ∗ η˙ + 2x∗ η + η 2 ] dt. t0

Since x∗ is an extremal, i.e. Lagrange equation x∗ −

it satisfies the Euler-

d (a(t)x˙ ∗ ) = 0. dt

Using integration by parts and noting that η(t0 ) = η(t1 ) = 0, we have ∫ t1 [2a(t)x˙ ∗ η˙ + 2x∗ η] dt t0

=

∫

t1

[− t0

d (2a(t)x˙ ∗ ) + 2x∗ ]η dt = 0 dt

Therefore, we have ∗

∆J = J [y] − J [x ] = This proves the claim.



∫

t1 t0

[a(t)η˙ 2 + η 2 ] dt ≥ 0.

12

A local minimizers Let E(t, x, x, ˙ p) = f (t, x, x) ˙ − f (t, x, p) − (x˙ − p)

∂f (t, x, p) ∂p

denote the integrand in the integral defining △J.

(Weierstrass Excess Function)

Theorem A (Weierstrass Conditions) In order that the extremal C ∗ : x = x∗ (t) give a strong local minimum to J [x] it is sufficient that # C ∗ is a member of a field of extremals; # E(t, x, x, ˙ p) ≥ 0 ∀(t, x) close to C ∗ and arbitrary values of x. ˙ Question 3. Find a suitable field of extremals for the following problem: ∫

1 0

1· · · ( x2 + x x + x + x) dt, x(0) = 0, x(2) = 2. 2

(2)

Show that the extremal is a strong (local) minimizing curve (by the Weierstrass’s sufficient Theorem). Solution. The extremal is x = x∗ (t) =

t2 2.

13

is

Then the field of extremal is {xl =

t2 2

+ l}l∈R , so the slop

p = p(t, x) = x˙ l (t) = t. Let f (t, x, x) ˙ =

1·2 · · x + xx+ x+ x, 2

f (t, x, p) =

1 2 p + xp + x+ p. 2

Then E(t, x, x, ˙ p) = f (t, x, x) ˙ − f (t, x, p) − (x˙ − p)

∂f (t, x, p) ∂p

1· 1 · · = x2 + xx + x + x − p2 2 2 − xp − x − p − (x˙ − p)(p + x + 1) 1 1 1 = x˙ 2 + p2 − xp ˙ = (x˙ − p)2 ≥ 0. 2 2 2 2

for all (t, x). This implies that x = x∗ (t) = t2 is a strong local minimizing curve. Actually, since the field of extremals t2 t2 ∗ + l cover the whole space. This implies that x (t) = 2 2 is a (global) minimizing curve. ...