Image0007 (3)

X

J.Stadnicki Optymalizacja- wykład dla Mechaniki, część4: PROGRAMOWANIE NIELINIOWE - metody numeryczne 13

K    K

<e

x —X

2    1

Np. dla 6 = 0,1, mamy K> 5

ALGORYTM INTERPOLACJI KWADRATOWEJ POWELLA

Bezgradientowe algorytmy podziału i redukcji wymagały znajomości początkowego przedziału nieokreśloności, w którym funkcja Q{x) posiadała minimum.

Rozpatrzymy wypukłą funkcję Q\x), którą będziemy przybliżać odcinkami parabolą F {x) = a-\-bx+cx² przechodzącą przez trzy punkty ^xv^xv^xr Prawdziwy jest układ równań:

a+bx_]    +cx'i=Q(x^

■ a+bx₂+exl =^(x₂)    =>a,b,c    (4.11)

a+bx_{ + cx², =Q(x._t)

J.Stadnicki Optymalizacja- wykład dla Mechaniki, część4: PROGRAMOWANIE NIELINIOWE - metody numeryczne

Jeżeli punkty x_{,x₂,x._i rozmieścimy tak, aby: a; =0, ^x2⁼t? x^=2t,X.o

a = Q_A

⁴ Q_b~³Qa-Qc

14

b=

21

. gdzie Q(x^=Q_a,Q[x.₁) = Q_b,Q(x.^)=Q_c

(4.12)

Q_c+Q_a Wb

2?

Parabola F{t)

F'(t)=0

ma minimum w punkcie t , w którym:

^b _t ^

2 c

=>    t =—-t => t=—^-~^A

4Q_B-2Q_C-2Q_A

Warunek (4.13) jest warunkiem koniecznym. Na to aby w punkcie t funkcja F miała nimum musi dodatkowo zachodzić:

(4.13)

mi-

(4.14)

F"{t')> 0    =>    _c=^±.^-^_>0    =* !lńŻ—~<Ł>Q

2 t²2 ⁰ Warunek (4.14) oznacza, że punkt B musi leżeć poniżej prostej łączącej punkty A i C. Jest

spełniony zawsze dla wypukłej funkcji Q (x).