Funkcja samozgodna

W optymalizacji funkcja samozgodna jest funkcją dla której ${\ Displaystyle f: \ mathbb {R} \ rightarrow \ mathbb {R}}$

${\ Displaystyle | f ''' (x) | \ równoważnik 2f'' (x) ^ {3/2}}$

$wszędzie$${\ Displaystyle f'' (x)>$ , funkcja , która tam, gdzie , satisfies

${\ Displaystyle \ lewo | {\ Frac {d} {dx}} {\ Frac {1} {\ sqrt {f '' (x)}}} \ prawo | \ równoważnik 1}$

i który spełnia gdzie indziej ${\ Displaystyle f ''' (x) = 0}$ .

Bardziej ogólnie, funkcja wielowymiarowa jest samozgodna, jeśli ${\ Displaystyle f (x): \ mathbb {R} ^ {n} \ rightarrow \ mathbb {R}}$

${\ Displaystyle \ lewo. {\ Frac {d} {d \ alfa}} \ nabla ^ {2} f (x + \ alfa y) \right|_{\alpha =0}\preceq 2{\sqrt {y^{T}\nabla ^{2}f(x)\,y}}\,\nabla ^{2}f(x)}$

lub, równoważnie, jeśli jego ograniczenie do dowolnej dowolnej linii jest samozgodne.

Historia

Jak wspomniano w „Komentarzach bibliograficznych” ich książki z 1994 r., funkcje samozgodne zostały wprowadzone w 1988 r. przez Jurija Niestierowa i dalej rozwijane wraz z Arkadim Niemirowskim . Jak $, metoda Newtona jest niezmienna afinicznie w$ sensie, że jeśli dla funkcji mamy kroki ${\ Displaystyle x_ {k + 1} = x_ {k} - [f '' (x_ {k})] ^ {- 1} f' (x_ {k})} wtedy$ dla funkcja $\ phi (y) = f (Ay)}$$gdzie$ jest niezdegenerowaną transformacją liniową, zaczynając od ${ \displaystyle y_{0}=A^{-1}x_{0}}$ mamy kroki Newtona ${\ Displaystyle y_ {k} = A ^ {- 1} x_ {k}},$ które można pokazać rekurencyjnie

${\ Displaystyle y_ {k + 1} = y_ {k} - [\ fi ''(y_{k})]^{-1}\phi '(y_{k})=y_{k}-[A^{T}f''(Ay_{k})A]^{-1 }A^{T}f'(Ay_{k})=A^{-1}x_{k}-A^{-1}[f''(x_{k})]^{-1}f' (x_{k})=A^{-1}x_{k+1}}$ .

Jednak standardowa analiza metody Newtona zakłada, że ​​Hesjan $ciągłym$ Lipschitzem , to jest ${\ displaystyle \ | f''(x) -f''(y) \|\ równoważnik M \|xy \|}$ dla pewnej stałej ${\ displaystyle M}$ . Jeśli założymy, że ${\ displaystyle f}$ jest 3 razy różniczkowalna w sposób ciągły, to jest równoważne

$_$ _ wszystko ${\ Displaystyle u, v \ w \ mathbb {R} ^ {n}}$

gdzie ${\ Displaystyle f''' (x) [u] = \ lim _ { \alpha \to 0}\alpha ^{-1}[f''(x+\alpha u)-f''(x)]}$ . Wtedy lewa strona powyższej nierówności jest niezmienna w ramach transformacji afinicznej ${\ Displaystyle f (x) \ do \ phi (y) = f (Ay), u \ do ZA ^{-1}u,v\to A^{-1}v}$ , jednak prawa strona nie.

Autorzy zauważają, że prawa strona może być również niezmienna, jeśli zastąpimy metrykę euklidesową iloczynem skalarnym zdefiniowanym przez Hessian $of$ jako ${\ Displaystyle \ | w \ | _ {f '' (x)} = \ langle f '' (x) w, w \ rangle ^ {1/2}}$ dla ${\ Displaystyle w \ w \ mathbb {R} ^ {n}}$ . Następnie dochodzą do definicji funkcji samozgodnej jako

${\ Displaystyle | \ langle f ''' (x) [u] u, u \ rangle | \ równoważnik M \ langle f '' (x) u, u\rangle ^{3/2}}$ .

Nieruchomości

Kombinacja liniowa

fa ${\ Displaystyle f_ {1}}$ i $f_ {2}}$${\ Displaystyle M_ {1}}$ są zgodne ze stałymi i i ${\ Displaystyle M_ {2}$ } $> 0}$$beta$ wtedy ze ${\ Displaystyle \ max (\ alfa ^ {- 1/2} M_ {1}, \ beta ^ {- 1/2$ .

Transformacja afiniczna

Jeśli jest samozgodny ze stałą $Displaystyle$$.$ transformacją afiniczną $}$$mathbb {R$$^ {n}$ , wtedy jest również samozgodny z parametrem ${\ Displaystyle \ phi (x) = f (Ax + b$$}$ .

Koniugat wypukły

Jeśli jest $samozgodny$ , to jego wypukły koniugat jest również samozgodny. $^ {*}}$

Heski w liczbie pojedynczej

Jeśli $,$$samozgodny$ a dziedzina nie zawiera linii prostej (nieskończonej w obu kierunkach), $nie$ .

I odwrotnie, jeśli dla niektórych $neq$ domenie $i$${\ Displaystyle u \ in \ mathbb {R} ^ {n}, u \$ and we have $\langle f''(x)u,u\rangle =0$, then $u, u \ rangle = 0}$$x + \ alfa u}$ dla wszystkich , dla których jest $Displaystyle$ w domenie jest liniowy i nie może mieć maksimum, więc wszystkie z $x$$}$${\ Displaystyle x + \ alpha u, \ alpha \ in \ mathbb {R}}$ jest w domenie ${\ displaystyle f}$ . Zauważamy również, że $nie$ mieć minimum w swojej domenie.

Aplikacje

Między innymi funkcje samozgodne są przydatne w analizie metody Newtona . Samozgodne funkcje barierowe są wykorzystywane do opracowywania funkcji barierowych stosowanych w metodach punktów wewnętrznych do optymalizacji wypukłej i nieliniowej. Zwykła analiza metody Newtona nie zadziałałaby dla funkcji barierowych, ponieważ ich druga pochodna nie może być ciągła Lipschitza, w przeciwnym razie byłyby ograniczone na dowolnym zwartym podzbiorze ${\ displaystyle \ mathbb {R} ^ {n}}$ .

Samozgodne funkcje barierowe

• to klasa funkcji, które mogą być używane jako bariery w metodach optymalizacji z ograniczeniami
• można zminimalizować za pomocą algorytmu Newtona z możliwymi do udowodnienia właściwościami zbieżności analogicznymi do zwykłego przypadku (ale wyniki te są nieco trudniejsze do uzyskania)
• aby mieć oba powyższe, zwykła stała granica trzeciej pochodnej funkcji (wymagana do uzyskania zwykłych wyników zbieżności dla metody Newtona) jest zastępowana przez granicę względem hessowskiego

Minimalizowanie funkcji samozgodnej

Funkcję samozgodną można zminimalizować za pomocą zmodyfikowanej metody Newtona, w której mamy ograniczenie liczby kroków wymaganych do zbieżności. Przypuszczamy tutaj, że $.$ funkcją $samozgodną$ ​​to znaczy jest samozgodna parametrem

Definiujemy dekrement Newtona w punkcie λ $}$$f } ($$)$ jako wielkość kroku Newtona ${\ Displaystyle [f'' (x)] ^ {- 1} f' (x)}$ w lokalnej normie określonej przez Hessian of ${\ Displaystyle f}$ w ${\ styl wyświetlania x}$

${\ Displaystyle \ lambda _ {f} (x) = \ langle f'' (x) [f'' (x)] ^ {- 1}f'(x),[f''(x)]^{-1}f'(x)\rangle ^{1/2}=\langle [f''(x)]^{-1} f'(x),f'(x)\zakres ^{1/2}}$

Wtedy dla $,$ domenie jeśli można udowodnić , że $1$${\ Displaystyle \ lambda _ {f} (x) <$ Iteracja Newtona

${\ Displaystyle x_ {+} = x - [f '' (x)] ^ {- 1} f' (x)}$

będzie również w domenie ${\ displaystyle f}$ . Dzieje $się$ tak, ponieważ na podstawie samozgodności możliwe jest podanie pewnych skończonych granic wartości ${\ displaystyle f (x_ {+})$ . Mamy dalej

${\ Displaystyle \ lambda _ {f} (x_ {+}) \ równoważnik {\ Bigg (} {\ Frac {\ lambda _{f}(x)}{1-\lambda _{f}(x)}}{\Bigg )}^{2}}$

Wtedy, jeśli mamy

${\ Displaystyle \ lambda _ {f} (x) <{\ bar {\ lambda}} = {\ Frac {3- {\ sqrt {5}}}} 2}}}$

wtedy jest również zagwarantowane, że ${\ Displaystyle \ lambda _ {f} (x_ {+}) <\ lambda _ {f} (x)}$ , abyśmy mogli kontynuować stosować metodę Newtona aż do zbieżności. Zauważ, że dla pewnego ${\ Displaystyle \ lambda _ {f} (x_ {+}) <\ beta$${\ Displaystyle \ beta \ in (0, {\ bar {\ lambda}})}$ mamy kwadratową zbieżność ${\ Displaystyle \ lambda _ {f}}$ do 0 jako ${\ Displaystyle \ lambda _ {f} (x_ {+}) \ równoważnik (1- \ beta) ^ {- 2} \ lambda _ {f} (x) ^ {2 }}$ . To daje kwadratową zbieżność ${\ Displaystyle f (x_ {k})}$ do ${\ Displaystyle f (x ^ {*})}$ i ${\ Displaystyle x}$ do ${\ Displaystyle x ^ {*}}$ , gdzie ${\ Displaystyle x ^ {*} = \ arg \ min f (x)}$ przez następujące twierdzenie. ${\ Displaystyle \ lambda _ {f} (x) <1$ } to

${\ Displaystyle \ omega (\ lambda _ {f} (x)) \ równoważnik f (x )-f(x^{*})\leq \omega _{*}(\lambda _{f}(x))}$

${\ Displaystyle \ omega '(\ lambda _ {f} (x)} \ równoważnik \| xx ^ {*} \|_ {x} \ równoważnik \ omega _ { *}'(\lambda _{f}(x))}$

z następującymi definicjami

${\ Displaystyle \ omega (t) = t- \ log (1 + t)}$

${ \ Displaystyle \ omega _ {*} (t) = - t - \ log (1-t)}$

${\ Displaystyle \ | u \ | _ {x} = \ langle f '' (x) u, u \ rangle ^ {1/2}}$

Jeśli zaczniemy metodę Newtona od pewnego λ $}}$$lambda$$\ Displaystyle \ lambda _ {f} (x_ {0}) \ geq {\ bar {\$ musimy zacząć od metody Newtona z tłumieniem zdefiniowanej przez

${\ Displaystyle x_ {k + 1} = x_ {k} - {\ frac {1}{1+\lambda _{f}(x_{k})}}[f''(x_{k})]^{-1}f'(x_{k})}$

W tym celu można wykazać, że ${\ Displaystyle f (x_ {k + 1}) \ równoważnik f (x_ {k} ) - \ omega (\ lambda _ {f} (x_ {k}))}$ z ${\ Displaystyle \ omega}$ , jak zdefiniowano wcześniej. Zauważ $,$ funkcją ${\ Displaystyle t> 0}$ tak, że ${\ Displaystyle \ omega (t) \ geq \ omega ({\ bar {\ lambda}})}$ dla dowolnego ${\ displaystyle t \ geq {\ bar {\ lambda}}}$ , więc wartość gwarantuje spadek o określoną wartość w każdej iteracji, co również dowodzi, że $x$$displaystyle x_ {k +1}}$ należy do dziedziny ${\ displaystyle f}$ .

Przykłady

Funkcje samozgodne

• Liniowe i wypukłe funkcje kwadratowe są zgodne same z sobą, $.$ trzecia pochodna wynosi zero
• Dowolna funkcja ${\ Displaystyle f (x) = - \ log (- g (x)) - \ log x}$ gdzie ${ \displaystyle g(x)}$ jest zdefiniowany i wypukły dla wszystkich $x>0$ i weryfikuje ${\ Displaystyle | g''' (x) | \ równoważnik 3g'' (x) / x}$ , jest samozgodny w swojej dziedzinie, która jest ${\ Displaystyle \ {x \ mid x> 0, g (x) <0 \}}$ . Niektóre przykłady są
  • ${\ Displaystyle g (x) = - x ^ {p}}$ dla ${\ Displaystyle 0 <p \ równoważnik 1}$
  • ${\ Displaystyle g (x) = - \ log x}$
  • ${\ Displaystyle g (x) = x ^ {p}}$ dla ${\ Displaystyle -1 \ równoważnik p \ równoważnik 0}$
  • ${\ Displaystyle g (x) = (ax + b) ^ {2} / x}$
  • dla dowolnej funkcji $spełniającej$ warunki funkcja $\ Displaystyle g (x) + ax ^ {2} + bx + c}$ z ${ \displaystyle a\geq 0}$ również spełnia warunki

Funkcje, które nie są samozgodne

• ${\ Displaystyle f (x) = e ^ {x}}$
• ${\ Displaystyle f (x) = {\ Frac {1} {x ^ {p}}}, x> 0, p> 0}$
• $= | x ^ {p} |, p> 2}$

Bariery samozgodne

• dodatnia półprosta ${\ Displaystyle \ mathbb {R} _ {+}}$ : ${\ Displaystyle f (x) = - \ log x}$ z domeną ${\ Displaystyle x > 0}$ jest samozgodną barierą z ${\ displaystyle M = 1}$ .
• ${\ Displaystyle \ mathbb {R} _ {+} ^ {n}}$ : $\ suma _ {i = 1} ^ {n} \ log x_ {i}}$ - z ${\ Displaystyle M = n}$
• bariera logarytmiczna ${\ Displaystyle f (x) = - \ log \ phi (x)}$ dla obszaru kwadratowego określonego przez ${\ Displaystyle \ phi (x) )>0}$ gdzie ${\ Displaystyle \ phi (x) = \ alfa + \ langle a, x \ rangle - {\ Frac {1} {2}} \ langle Ax, x \ rangle} gdzie ZA = ZA T$ ≥ $A ^ {T} \ geq 0}$ jest dodatnią półokreśloną symetryczną macierzą samozgodną dla ${\ Displaystyle M = 2}$
• stożek drugiego rzędu ${\ Displaystyle \ {(x, y) \ in \ mathbb {R} ^ {n-1} \ razy \ mathbb {R} \ mid \|x \|\ równoważnik y \}}$ : ${\ Displaystyle f (x, y) = - \ log (y ^{2}-x^{T}x)}$
• półokreślony stożek ${\ Displaystyle A = A ^ {T} \ geq 0}$ : ${\ Displaystyle f (A) = - \ log \ det A}$
• stożek wykładniczy ${\ Displaystyle \ {(x, y, z) \ in \ mathbb {R} ^ {3} \ mid ye^{x/y}\leq z,y>0\}}$ : ${\ Displaystyle f (x, y, z) = - \ log (y \ log (z / y) -x) - \ log z- \ log y}$
• stożek mocy ${\ Displaystyle \ {(x_ {1}, x_ {2}, y) \ w \ mathbb {R} _ {+} ^ {2} \ razy \ mathbb {R} \mid |y|\leq x_{1}^{\alpha }x_{2}^{1-\alpha }\}}$ : ${\ Displaystyle f (x_ {1}, x_ {2}, y) = - \log(x_{1}^{2\alpha}x_{2}^{2(1-\alpha)}-y^{2})-\log x_{1}-\log x_{2}}$