Hilfe bei einer Abschätzung

19/02/2010 - 19:24 von Stephan Berger | Report spam
Hallo,

ich bin in dem Buch "Iterative Methods for Optimization" (C.T.
Kelley), http://www.siam.org/books/kelley/fr18/index.php in einem
Beweis (S. 53, Beweis zu Theorem 3.3.1) auf eine Abschàtzung gestoßen,
die ich nicht ganz nachvollziehen.
Ich schicke voraus, dass ich Informatiker bin und nicht zwingend von
mir erwartet wird, diese Beweise zu 100% nachvollziehen zu können;
oder gar duchzuführen.
Dennoch, àhnliche Abschàtzungen tauchen in dem Buch mehrmals auf und
ich würde mich gerne nicht jedesmal àrgern wenn ich drüber lese.
Vielleicht kann mir ja jemand helfen!

Es geht um einen Beweis zur Konvergenz eines Trust Region Algrithmus.

Sei

ared_t := f(x_k) - f(x_t)
pred_t := m_k(x_k) - m_c(x_t)
(die tatsàchliche Reduktion des Funktionswertes von x_c nach x_t und
die durch das quadratische Model geschàtzte)

Dabei ist
m_k(x) = f(x_k) + grad(f)(x_k)^T * (x - x_k) + 1/2 * (x - x_k)^T *
H_k * (x - x_k)
Es wird davon ausgegangen, dass die model Hessian H_k spd ist und
|| H_k || <= M

s_t := x_t - x_k
also der "Schritt" von x_k nach x_t

Ausserdem wird angenommen das grad(f) Lipschitz-Stetig mit Lipschitz-
Konstante L ist
||grad(f)(x) - grad(f)(y)|| <= L * ||x-y||

und

||s_t|| < ||grad(f)(x_k)||


Hier nun die Abschàtzung

ared_t = -grad(f)(x_k)^T * s_t - \int_0^1{ [grad(f)(x_k - t*s_t) - grad(f)
(x_k)]^T * s_t }dt
(dieser Schritt ist klar, es wird der HS der Diffenerential und
Integralrechnung verwendet und das übliche
abziehen und wieder draufaddieren spiel betrieben)

= pred_t + s_t^T * H_k * s_t - \int_0^1{ [grad(f)(x_k - t*s_t) -
grad(f)(x_k)]^T * s_t }dt >
(ist auch klar, es wird einfach die Def. von pred_t und m_c verwendet)


= pred_t - 1/2 * (M+L) * ||s_t||^2



nochmal zur Erinnerung: ||H_k|| < M, L Lipschitz-Konstante für grad(f)

Ich krieg die Abschàtzung einfach nicht hin. Wenn mir jemand einen
Hinweis geben könnte oder die paar Zwischenschritte die hier fehlen
aufzeigen könnte wàre ich sehr dankbar!

Grüße
Stephan
 

Lesen sie die antworten

#1 Rainer Urian
20/02/2010 - 12:41 | Warnen spam
Hi,
ich habe den Originaltext kurz überflogen und dabei folgende Fehler bei
deinem Posting bemerkt
1. die Hessian wird als NON-SPD angenommen. (3.3 1. Abschnitt)
2. du hast den Faktor 1/2 bei s_t^T * H_k * s_t vergessen.


Jetzt zur Abschàtzung:

1/2* s_t^T * H_k * s_t >= -1/2*M*||s_t||^2


\int_0^1{ [grad(f)(x_k - t*s_t) - grad(f)(x_k)]^T * s_t }dt
<= \int_0^1{ ||grad(f)(x_k - t*s_t) - grad(f)(x_k)|| * ||s_t|| }dt
<= \int_0^1{ L||t*s_t|| * ||s_t|| }dt
= L*||s_t||^2*\int_0^1{ t}dt
= L*||s_t||^2*1/2

nach Multiplikation mit -1 dreht sich die Ungleichung um, also
-\int_0^1{ [grad(f)(x_k - t*s_t) - grad(f)(x_k)]^T * s_t }dt >= -
L*||s_t||^2*1/2


Rainer


"Stephan Berger" schrieb im Newsbeitrag
news:
Hallo,

ich bin in dem Buch "Iterative Methods for Optimization" (C.T.
Kelley), http://www.siam.org/books/kelley/fr18/index.php in einem
Beweis (S. 53, Beweis zu Theorem 3.3.1) auf eine Abschàtzung gestoßen,
die ich nicht ganz nachvollziehen.
Ich schicke voraus, dass ich Informatiker bin und nicht zwingend von
mir erwartet wird, diese Beweise zu 100% nachvollziehen zu können;
oder gar duchzuführen.
Dennoch, àhnliche Abschàtzungen tauchen in dem Buch mehrmals auf und
ich würde mich gerne nicht jedesmal àrgern wenn ich drüber lese.
Vielleicht kann mir ja jemand helfen!

Es geht um einen Beweis zur Konvergenz eines Trust Region Algrithmus.

Sei

ared_t := f(x_k) - f(x_t)
pred_t := m_k(x_k) - m_c(x_t)
(die tatsàchliche Reduktion des Funktionswertes von x_c nach x_t und
die durch das quadratische Model geschàtzte)

Dabei ist
m_k(x) = f(x_k) + grad(f)(x_k)^T * (x - x_k) + 1/2 * (x - x_k)^T *
H_k * (x - x_k)
Es wird davon ausgegangen, dass die model Hessian H_k spd ist und
|| H_k || <= M

s_t := x_t - x_k
also der "Schritt" von x_k nach x_t

Ausserdem wird angenommen das grad(f) Lipschitz-Stetig mit Lipschitz-
Konstante L ist
||grad(f)(x) - grad(f)(y)|| <= L * ||x-y||

und

||s_t|| < ||grad(f)(x_k)||


Hier nun die Abschàtzung

ared_t = -grad(f)(x_k)^T * s_t - \int_0^1{ [grad(f)(x_k - t*s_t) - grad(f)
(x_k)]^T * s_t }dt
(dieser Schritt ist klar, es wird der HS der Diffenerential und
Integralrechnung verwendet und das übliche
abziehen und wieder draufaddieren spiel betrieben)

= pred_t + s_t^T * H_k * s_t - \int_0^1{ [grad(f)(x_k - t*s_t) -
grad(f)(x_k)]^T * s_t }dt >
(ist auch klar, es wird einfach die Def. von pred_t und m_c verwendet)

= pred_t - 1/2 * (M+L) * ||s_t||^2



nochmal zur Erinnerung: ||H_k|| < M, L Lipschitz-Konstante für grad(f)

Ich krieg die Abschàtzung einfach nicht hin. Wenn mir jemand einen
Hinweis geben könnte oder die paar Zwischenschritte die hier fehlen
aufzeigen könnte wàre ich sehr dankbar!

Grüße
Stephan

Ähnliche fragen