VŠB – Technická univerzita Ostrava Fakulta elektrotechniky a informatiky Katedra aplikované matematiky
Minimalizace nehladké funkce Minimization of nonsmooth function
2009
Martin Hasal
Místopřísežné prohlášení „Prohlašuji, že jsem tuto bakalářskou práci vypracoval samostatně. Uvedl jsem všechny literární prameny a publikace, ze kterých jsem čerpal.“ V Ostravě dne 5. května 2009
Martin Hasal ………………
Poděkování Děkuji Ing. Petru Beremlijskému Ph.D za vedení při vypracování diplomové práce a za cenné připomínky a rady, které zvýšily úroveň celé práce.
Abstrakt Úloha minimalizace nespojitě diferencovatelné (nehladké) funkce se objevuje při řešení některých úloh z mechaniky, např. kontaktní úlohy se třením, či úloh tvarové optimalizace. Tato práce je úvodem do problematiky minimalizace nespojitě diferencovatelných funkcí. Práce bude mít tyto části: 1. Nespojitě diferencovatelný kalkul. 2. Algoritmy pro minimalizaci nespojitě diferencovatelných funkcí - nepřímá a subgradientní metoda. 3. Programová realizace v Matlabu. 4. Testování algoritmů na vhodných úlohách. Klíčová slova: Newtonova metoda, gradient, subgradient, subgradientní metody.
Abstract This Bachelor thesis introduces reader with problem of minimization of nondifferentiable (nonsmooth) function. This kind of problem appears when we are solving some problems in mechanics, e.g. contact problems with friction or shape optimization problems. This work is introduction to the area of nonsmooth optimization. The thesis has these sections: 1. Nonsmooth calculus. 2. Algorithms for nonsmooth minimization – indirect approach and subgradient method. 3. Implementation of mentioned methods. 4. Numerical examples. Keywords: Newton method, Gradient, Subgradient, Subgradient methods.
Seznam použitých zkratek a symbolů: ℕ - množina všech přirozených čísel
ℝ - množina všech reálných čísel
ℝ - n-rozměrný Euklidovský prostor
f (x; d) – jednostranná směrová derivace
f (x; h) - zobecněná směrová derivace
conv(K) – konvexní obal množiny K
∇f(x) - gradient reálné funkce f v bodě x
∂f(x) – zobecněný gradient reálné funkce f v bodě x
x – vektor (x , x , … , x )
F(x) – vektorová funkce (F , F , … , F )
F´(x) - Jacobiho matice reálné vektorové fukce F v bodě x
F´´(x) – Hessova matice reálné vektorové fukce F v bodě x
A – transponovaná matice A
A
– inverzní matice k A
I – jednotková matice
‖∙‖ - euklidovská norma
(∙,∙) - skalární součin
uzel – bod, ve kterém není funkce spojitě diferencovatelná
Obsah 1
ÚVOD ............................................................................................................................. 5
2
ZÁKLADNÍ DEFINICE ................................................................................................ 6
2.1
Konvexní množiny ...............................................................................................................................6
2.2
Konvexní funkce ..................................................................................................................................6
2.3
Lokálně Lipschitzovsky spojité funkce ................................................................................................7
2.4
Regulární funkce ..................................................................................................................................8
2.5
Podmínky minima ................................................................................................................................8
3 3.1
KLASICKÉ METODY................................................................................................ 10 Spádová metoda ................................................................................................................................. 10
3.2 Newtonova metoda ............................................................................................................................. 11 3.2.1 Geometrická ukázka Newtonovy metody.......................................................................................... 11 3.3
Newtonova metoda pro soustavy ....................................................................................................... 12
3.4
Minimalizace funkce pomocí Newtonovy metody ............................................................................. 14
4
SELHÁNÍ KLASICKÝCH METOD .......................................................................... 15
5
NEPŘÍMÁ METODA.................................................................................................. 17
5.1
Poruchová technika............................................................................................................................ 17
5.2
Transformace na problém s omezením.............................................................................................. 18
6
SUBGRADIENTNÍ METODY ................................................................................... 19
6.1
Předpoklady ....................................................................................................................................... 19
6.2
Metoda spádového typu s délkou kroku vybranou a-priori .............................................................. 24
6.3
Metoda spádového typu s monotonním klesáním.............................................................................. 26
6.4
Subgradietní metoda Newtonova typu .............................................................................................. 27
-1-
7
SROVNÁNÍ POUŽITÝCH METOD NA PŘÍKLADECH ........................................ 29
7.1
Funkce č. 1 – nehladká, konvexní ...................................................................................................... 29
7.2
Funkce č. 2 - Rosenbrockova funkce – hladká, konvexní .................................................................. 30
7.3
Funkce č. 3 – nehladká, konvexní ...................................................................................................... 31
7.4
Funkce č. 4 – nehladká, regulární...................................................................................................... 33
7.5 Tabulka srovnání jednotlivých metod na příkladech........................................................................ 34 7.5.1 Srovnání nehladkých metod ............................................................................................................. 35 7.5.2
Srovnání hladké Newtonovy metody pro minimalizaci funkce .......................................................... 35
8
ZÁVĚR ......................................................................................................................... 37
9
LITERATURA ............................................................................................................. 38
PŘÍLOHY ........................................................................................................................... 39 A Zdrojový Kód .............................................................................................................................................. 39
-2-
Seznam tabulek: TABULKA 1: UKÁZKA ,,OSCILACE’’ SUBGRADIENTNÍ METODY S PEVNOU DÉLKOU KROKU ......................... 26 TABULKA 2: POČTY ITERACÍ SUBGRADIENTNICH METOD - STARTOVACÍ BOD 10/[10,10], PŘESNOST 1E-2 .. 35 TABULKA 3: POČTY ITERACÍ SUBGRADIENTNICH METOD - STARTOVACÍ BOD 10/[10,10], PŘESNOST 1E-4 .. 35 TABULKA 4: POČTY ITERACÍ SUBGRADIENTNICH METOD - STARTOVACÍ BOD 10/[10,10], PŘESNOST 1E-6 .. 35 TABULKA 5: POČTY ITERACÍ HLADKÝCH METOD - STARTOVACÍ BOD 10/[10,10], PŘESNOST 1E-2 ................. 36 TABULKA 6: POČTY ITERACÍ HLADKÝCH METOD - STARTOVACÍ BOD 10/[10,10], PŘESNOST 1E-4 ................. 36 TABULKA 7: POČTY ITERACÍ HLADKÝCH METOD - STARTOVACÍ BOD 10/[10,10], PŘESNOST 1E-6 ................. 36
-3-
Seznam obrázků: OBRÁZEK 1: GEOMETRICKÁ UKÁZKA NEWTONOVY METODY .......................................................... 12 OBRÁZEK 2: UKÁZKA SELHÁNÍ KLASICKÉ METODY............................................................................ 16 OBRÁZEK 3: ( ) = | |
OBRÁZEK 4: FUNKCE ( ) = | | PO APROXIMACI ..................... 17
OBRÁZEK 5: SUBGRADIENT FUNKCE ( ) = | |
OBRÁZEK 6: FUNKCE ( ) = | | ............ 20
OBRÁZEK 7: GEOMETRICKÁ INTERPRETACE (6.5) ................................................................................. 23 OBRÁZEK 8: VYKRESLENÍ HLEDÁNÍ MINIMA FUNKCE S DÉLKOU KROKU VYBRANOU A-PRIORI
................................................................................................................................................................ 25 OBRÁZEK 9: GRAF FUNKCE Č.1 ................................................................................................................. 29 OBRÁZEK 10: GRAF ZOBECNĚNÉHO GRADIENTU FUNKCE Č. 1 .......................................................... 30 OBRÁZEK 11: GRAF ROSENBROCKOVY FUNKCE ................................................................................... 31 OBRÁZEK 12: GRAF FUNKCE Č. 3 .............................................................................................................. 32 OBRÁZEK 13: ROZDĚLENÍ FUNKCE Č. 3 NA MNOŽINY .......................................................................... 33 OBRÁZEK 14: GRAF FUNKCE Č. 4 .............................................................................................................. 34
-4-
1 Úvod Úloha minimalizace nespojitě diferencovatelné (nehladké) funkce se týká úloh, které obsahují nespojité parciální derivace prvního řádu. Toto způsobuje, že klasické metody, využívající parciálních derivací prvního řádu, selhávají, proto nehladké úlohy vyžadují nestandardní metody přístupu. Takzvané subgradientní metody, u kterých se předpokládá, že funkce jsou lokálně Lipschitzovsky spojité a, že můžeme určit u každé z funkcí subgradient v každém bodě. Funkce nemusí být diferencovatelné ani konvexní. Historie subgradientních metod začíná na počátku šedesátých let dvacátého století, kdy se začala aplikovat myšlenka nahradit gradient (u hladkých úloh) subgradientem. Tento krok sebou ale přinesl dvě zásadní otázky: ,,Jak vybrat délku kroku? Existuje nějaká zastavovací podmínka?“. Mnoho různých odpovědí bylo vyřčeno pro předchozí otázky, ale navzdory všem odpovědím nedostatek zastavovacích podmínek je jedním z nedostatků subgradientních metod. Vše se opírá o bádání sovětských matematiků, hlavně N.Z. Shora[1]. Obsah této bakalářské práce je následující: po krátkém úvodu si připomeneme v kapitole 2 základní definice týkající se této práce a konvexní analýzy. V kapitole 3 si ukážeme dvě časté metody pro minimalizaci funkce, které využíváme při minimalizaci hladkých funkci. A to metodu spádovou a Newtonovou. Následující kapitola nám popisuje podmínky, při nichž výše zmíněné metody selhávají. V kapitole 5 ukazujeme, jak převést nehladký problém na hladký. Kapitola 5 se zabývá subgradientními metodami. Postupně ukážeme základní předpoklady těchto metod. Seznámíme se dvěma metodami spádového typu a jednou Newtonova typu, u nichž si ukážeme jejich přednosti a nedostatky. V kapitole 7 ukážeme na čtyřech funkcích rychlost konvergence jednotlivých metod. Předposlední kapitola (závěr), zde shrneme veškeré poznatky, na které jsme přišli během této práce.
-5-
2 Základní definice V bakalářské práci se zabýváme minimalizací reálné funkce v n-rozměrném euklidovském prostoru min ( ), v ℝ
(2.1)
Neuvažujeme žádné omezení v (2.1), ani nevyžadujeme hladkou funkci. Spokojíme se jen se znalostí subgradientu. V daném bodě x, kde gradient funkce není definován, stačí nám znát jednostrannou směrovou derivaci ( ; ) = lim →
1
[ ( +
(2.2)
) − ( )],
která existuje v každém směru d. Než si zobecníme pojem gradientu pro nehladké funkce, zavedeme si následující definice. Dále si zavedeme některé pojmy z konvexní analýzy, jejichž znalost je nezbytná pro následující výklad. Obsáhlý přehled konvexní analýzy lze nalézt například v [2].
2.1 Konvexní množiny Definice: Nechť
( ) označuje konvexní obal množiny K (tj. množinu všech
⊂ ℝ . Potom
konvexních kombinací bodů z množiny K)
( )=
∈ ℕ, ∈ ℝ ,
,…,
∈ ,
≥0∀ ,
=1 .
2.2 Konvexní funkce Definice: Funkce f(x) je konvexní, právě když platí: (
+ (1 − ) ) ≤
Věta: (o vlastnostech konvexní funkce)
·
f je konvexní
( ) + (1 − ) ( ) ∀ ,
f je spojitá
-6-
∈ ℝ, ∀ ∈ 〈0,1〉
2.3 Lokálně Lipschitzovsky spojité funkce Definice: Funkce ( ): ℝ → ℝ se nazývá lokálně Lipschitzovsky spojitou, jestliže pro každé
ℝ , K je kompaktní množina, existuje konstanta L =L(K)>0 taková, že platí: | ( ) − ( )| ≤ | − | ∀ ,
Věta: Funkce f(x) je konvexní
∈
.
funkce f(x) je lokálně Lipschitzovsky spojitá.
Uvažujme funkci f z (2.1), která se skládá z
částí, i.e. graf f je hladký, až na jeden uzel kde gradient
∇ ( ) se mění skokem. Uvažujme například funkci jedné dimenze ℎ( ) =
⊂
− , ,
≤0 > 0.
(2.3)
V (2.3) je ∇ℎ( ) = −1 pro záporné x a ∇ℎ ( ) = 2 pro kladné x. V bodě x = 0 není zatím gradient
funkce definován, ale je zřejmé, že limity lim
→
∇ℎ( ) = −1 a lim
→
∇ℎ( ) = 0 charakterizují
dohromady chování funkce h v blízkosti uzlu x = 0. Toto nás vede k následujícímu nahrazení gradientu.
Definice:Nechť funkce f je lokálně Lipschitzovsky spojitá, pak zobecněný gradient funkce f v bodě x (conv označuje konvexní obal) definujeme jako: ( )= Elementy
∈ℝ
∇ ( )
=
∇ ( ), → ,∇ ( )
.
(2.4)
( ) se nazývají subgradienty.
V případě, že funkce f je konvexní, bývá zobecněný gradient často označován jako subdiferenciál. Pro funkci h dostáváme: ℎ(0) = { ∈ ℝ |−1 ≤
≤ 0}.
(2.5)
Směrová derivace (2.2) je další nástroj k charakterizování chování funkce v blízkosti uzlu. Snadným výpočtem dostáváme:
-7-
ℎ (0; ) =
− 0
≤0 ≥ 0.
(2.6)
Můžeme si všimnout těsného vztahu mezi subdiferenciálem a směrovou derivací. Základní teorém konvexní analýzy říká, že směrová derivace ′( ;∙) je support funkce ( ; ) = max
( )
∈
.
( ):
(2.7)
Je snadné ověřit, že (2.7) společně s (2.5) dává zase zpět (2.6). Věta: (vlastnosti směrové derivace a zobecněného gradientu). Nechť funkce ( ): ℝ → ℝ je lokálně
Lipschitzovsky spojitá a nechť , ·
·
f je diferencovatelná v x ⇒
∈ ℝ , potom:
( )
( ; )=∇
zobecněný gradient je neprázdná konvexní kompaktní množina
Důsledek: v případě, že funkce f je diferencovatelná v bodě x, pak zobecněný gradient se rovná gradientu v bodě x.
2.4 Regulární funkce Definice: Nechť funkce f je v bodě x lokálně Lipschitzovsky spojitá. Zobecněnou směrovou derivací funkce f v bodě x ve směru h definujeme jako číslo: ( ; ℎ ) = max ∈
Definice: Řekneme, že funkce
derivavace ´( ; ℎ ) ∀ℎ ∈ ℝ a platí
( )
.
( ): ℝ → ℝ je regulární v bodě ( ; ℎ ) = ´( ; ℎ ) ∀ℎ ∈ ℝ .
∈ ℝ , existuje-li směrová
Věta: Funkce spojitě diferencovatelné v okolí bodu x nebo funkce konvexní v okolí bodu x jsou regulární v bodě x. Dále jsou v bodě x regulární (a) nezáporné lineární kombinace regulárních funkcí a (b) bodová maxima regulárních funkcí. Důkaz najdeme v [3].
2.5 Podmínky minima Věta: Funkce f je lokálně Lipschitzovsky spojitá, pak nutná podmínka minima: 0∈
( ∗ ) ⇐ ( ∗ ) ≤ ( ), ∀ . -8-
(2.8)
Toto vede k jiné ekvivalentní definici subdiferenciálu funkce pro konvexní funkci: ( )={ ∈ℝ |
( − ) ≤ ( ) − ( ) ∀ ∈ ℝ }.
(2.9)
(2.9) nám dává nutnou postačující podmínku minima pro konvexní problém (2.1): ∗
je minimum pro (2.1) ⟺0∈ ( . . ( ∗) ≤ ( ) ∀ )
(2.10a)
( ∗ ).
V případě nekonvexní funkce jde pouze o nutnou podmínku: ∗
Množina
∗
je minimum pro (2.1) ⟹0∈ ( . . ( ∗) ≤ ( ) ∀ )
(2.10b)
( ∗ ).
definuje jako body minima pro (2.1). V případě konvexní funkce dostáváme: ∗
={
Budeme předpokládat, že
∗
∈ ℝ |0 ∈
∗
( ∗ )}.
(2.11)
je neprázdná a omezená.
Předpokládejme, že známe zobecněný gradient funkce f na celém jejím definičním oboru, pak můžeme vypočítat alespoň jeden subgradient v každém bodě, ve kterém není diferencovatelná, dle definice (2.4). Následkem je základní předpoklad: ž é
ě ,
é
á
( ),
á
-9-
∈
( ).
(2.12)
3 Klasické metody Kapitola 3 popisuje základní metody hladké optimalizace. Nejprve si představíme spádovou metodu, která využívá pouze gradientní informace. Dále se zaměříme na odvození Newtonovy metody pro řešení rovnic a soustav rovnic. Na základě řešení soustavy rovnic pomocí Newtonovy metody si odvodíme Newtonovu metodu pro minimalizaci funkcí. Tato metoda už využívá i informace druhého řádu.
3.1 Spádová metoda Často používaná derivační metoda. Protože kroky řešení se provádějí na základě vypočteného gradientu – tj. ve směru největších změn účelové funkce, je tato metoda výhodná zejména při řešení úloh dále od minima funkce. V okolí minima, které není-li příliš ostré, dojde v důsledku zmenšených kroků k jejímu zpomalení. Podmínkou použití je existence alespoň numerických derivací. : ℝ → ℝ, f( ) = ½ (
Například mějme kvadratickou funkci
, ) – ( , ). Řekneme, že matice A
je pozitivně definitní, jestliže je symetrická a pro každý nenulový vektor x platí (Ax, x) > 0. Úloha najít =
řešení rovnice
(∇ ( ) =
−
, pokud x je minimum funkce f, pak ∇ ( ) =
−
= 0)
je ekvivalentní úloze najít (jediné) minimum funkce f. Důkaz tohoto tvrzení je následující. Nechť nejprve vektor 0 ≤
( (
=
je minimem funkce f, potom pro libovolný vektor y a libovolné reálné číslo a platí
( +
)– ( ) = ½( ( +
, )– (
), +
)– ( , +
) − ½(
– , )). Aby byl poslední výraz nezáporný pro všechna a a y, musí nutně platit
. Nechť nyní
=
, potom stejnou úpravou jako v předchozí části dojdeme k závěru, že
funkce f má v bodě x minimum.
Algoritmus Spádove metody: 1. Zvolme malé e, k=1, xk=x0 = −∇ ( )
2. Vypočtěte
3. Pokud ‖∇ ( )‖ ≤ ε, pak konec výpočtu
4. Vypočtěte tk tak, aby (
5. 6.
=
=
+1
, ) + ( , ) =
+
+
) = min
7. jděte na (1.) - 10 -
(
+
)
3.2 Newtonova metoda = 〈 , 〉 leží jediný
Formulace: Jedná se o modifikaci metody prostých iterací. Nechť v intervalu jednoduchý kořen
rovnice ( ) = 0. Jelikož hovoříme o zpřesňující verzi metody prosté iterace,
předpokládáme, že máme zadanou nultou iteraci
∈ , která se nachází poblíž hledanému nulovému
řešení. Vyjádříme si Taylorův rozvoj funkce f v bodě x0. A předpokládáme ( ) = ( ) + ´( )( −
)+
1 ´´( )( − 2
Rovnici ( ) = 0 nahradíme lineární rovnicí: Kořen:
0 = ( ) + ´( )( −
=
−
Dostáváme iterační formuli: = 3.2.1 Křivku
−
( )
´( ) (
´(
∈
:
) .
).
.
)
. )
Geometrická ukázka Newtonovy metody = ( ) nahradíme tečnou ke grafu funkce v bodě xk a hodnotu xk+1 získáme jako průsečík
tečny s osou x, odtud plyne jiný název pro Newtonovu metodu, a to metoda tečen.
- 11 -
Obrázek 1: Geometrická ukázka Newtonovy metody
Jako zastavovací podmínku volíme |
−
| < , ε – přesnost řešení.
Rychlost konvergence Newtonovy metody je 2. řádu.
3.3 Newtonova metoda pro soustavy Jsou dány funkce Označme = 〈
,
: ℝ → ℝ, = 1, … , de inované na . 〉×〈
,
〉×…×〈
,
〉.
- 12 -
Hledáme
=( ,
,…,
) ∈ tak, aby:
( ,
,…,
( ,
Vektorově zapišme ( ) = 0,
kde
=( ,
,…,
) = 0,
,…,
) = 0.
⋮
( ,
) .
,…,
Vyjádříme si Taylorův rozvoj funkce F v bodě xk. ( )=
) = 0,
+
−
+ ´
1 ´´( ) 2
∈C : −
.
Soustavu rovnic ( ) = 0 nahradíme soustavou lineárních rovnic: Její řešení xk+1
Označme:
−
Dostáváme soustavu:
Jejíž řešeni je tvaru:
´
=−
.
−
+ ´
0=
.
−
+ ´
0=
= =−
´
. .
. - 13 -
Novou iteraci xk+1 získáváme ze vztahu: =
+
Jacobiho matice funkce ( ) v bodě
.
je ´
, která musí být regulární.
Z praktických zkušeností vyplývá, že pro ukončení Newtonovy metody dobře funguje testování funkční hodnoty. Více informací o metodě najdeme v [8].
3.4 Minimalizace funkce pomocí Newtonovy metody ´´( ) je Hessova matice (matice druhých parciálních derivací účelové funkce podle proměnných)
v bodě , ze které se zde vypočítává směr největšího spádu.
Věta: Nutná a postačující podmínka o existenci minima v bodě x pro konvexní funkci F: + ´´( )
´( ) = 0 nebo ´
= 0.
−
Za předpokladu existence inverzní matice k ´´( ) dostaneme: =
−
´´
´
,
což je rekurentní forma pro výpočet zpřesňovaného řešení.
- 14 -
4 Selhání klasických metod V klasických metodách aplikovaných na hladké funkce nahrazujeme f v bodě x lineárním nebo kvadratickým modelem (f(x)´ a f(x)´´):
´( ) +
´( ) [≈ ( +
) − ( )],
1 ´´( )( , )[≈ ( + 2
(4.1)
) − ( )]
(4.2)
a následně je minimalizujeme. Minimalizace modelu (4.1) vede k metodám spádového typu a minimalizace (4.2) vede k metodám newtonového typu. Všimneme si, že oba modely nejsou definovány v uzlech a bodech poblíž uzlů. Zde nám ani jeden druh metody nevrací efektivní aproximaci funkce. Jestliže minimum pro body x v blízkosti
∗
∗
je uzlem (poměrně častá záležitost u nehladkých funkcí), pak
je hledání směru poklesu pomocí minimalizačních metod (4.1) a (4.2) zcela
zbytečné. Toto tvrzení bylo dokázáno numerickými experimenty. Vše se muže stát ještě horším v případě nevhodného hladkého modelu (4.1) nebo (4.2), kdy se za řešení můžeme dostat bod, který minimem není. Ukážeme si na příkladu. Mějme funkci:
( ,
5(9 + 16 ) ) = 9 + 16| | 0< 9 + 16| | −
≥| | <| | ≤ 0.
(4.3)
Vrstevnice funkce f jsou vykresleny na následujícím obrázku. Snadným výpočtem si ověříme, že ∗
= (−1,0) je globální minimum funkce f a že funkce f není diferencovatelná pouze na množině
≤ 0,
= 0. Dále platí, že funkce je konvexní. Nyní si vybereme jakýkoliv startovní bod splňující
> | | > (9/16) | |. A na obrázku č. 3 můžeme vidět selhání metody spádového typu s line
search. Mnohoúhlá cesta se správně skládá s pravoúhlých segmentů, jenže konverguje k počátku ̅ = (0,0) , jež zcela jistě není minimem funkce. Správné řešení příkladu si uvedeme později.
- 15 -
zyd
Obrázek 2: Ukázka selhání klasické metody
Pokud se nám podaří překonat nástrahu z předchozího příkladu, stále nám ještě zbývá kritická nevýhoda hladkých metod v nehladkém kontextu. Tato nevýhoda je nedostatek implementovatelných zastavovacích podmínek. Pro C1-funkce musí být norma gradientu menší než máme zadánu přesnost řešení ‖∇ (
)‖ ≤
když se přiblížíme minimu
∗
(malé
> 0),
(4.4)
, tato podmínka nám automaticky zastaví iteraci. Ale pro nehladké
funkce kritérium (4.4) nemá význam i kdyby gradient existoval ve všech bodech iterace, např. pro funkci ( ) = | | dostáváme |∇ (
)| = 1 v každém xk≠0, xk může být libovolně blízko minimu
v uzlu x*= 0. Jak jistě vidíme, zastavovací podmínka je konstantní, ale námi hledaná hodnota ε je blízká nule, k minimu se sice přiblížíme nebo ho dosáhneme, ale díky selhání zastavovací podmínky nikdy nezastavíme.
- 16 -
5 Nepřímá metoda V této kapitole si představíme některé postupy, jak převést nehladký problém na hladký a ten pak můžeme řešit klasickou metodou.
5.1
Poruchová technika
Uvažujme nehladký problém:
∈
Funkce
(5.1)
| ( )|.
min
je hladká a pokud k ní přidáme nějaké malé > 0 ke každé funkci , dostáváme problém: min ∈
( ( ) + ) .
Tento problém je již zřejmě hladký a můžeme jej řešit ,,klasickými“ optimalizačními metodami. Při bližším zkoumání vidíme nedostatek této nepřímé aproximace. Jestliže se
( ) +
blíží k nule,
pak musíme počítat 2. odmocninu z téměř nulové hodnoty. Tento problém je způsoben špatnou podmíněností úlohy a tím, že
je vybráno a priori. Jestliže je jedno
vybráno korektně pro jednu
funkci, může být zničující pro jinou. Pro představu si zvolme z příkladu (5.1) m=1 a
( ) = | |.
Na následujících obrázcích je zobrazena nehladká funkce a ta samá funkce po použití poruchové metody (za ε jsme zvolili hodnotu 0.05). Je zřejmé, že funkce po použití metody je hladká.
Obrázek 3: ( ) = | |
Obrázek 4: Funkce ( ) = | | po aproximaci
- 17 -
Čím menší ε volíme, tím přesnější aproximaci dostáváme.
5.2 Transformace na problém s omezením Nechť existuje množina hladkých funkcí ( ): min max ∈
( ).
(5.2)
Přetransformováním (5.1) a (5.2) na omezený problém přidáním reálné proměnné α (respektive ,…,
):
∈
min ,
, kde −
∈ ∈
min
, ∈
≤ ( )≤
, (1 ≤ ≤
, kde ( ) ≤ , (1 ≤ ≤
),
).
(5.1)‘
(5.2)‘
Shoda (5.1)‘ a (5.2)‘ s (5.1) a (5.2) je snadno ověřitelná. V předchozích problémech se již objevuje nespojitá diferencovatelnost, tudíž jde o nehladký problém. Nepříjemné je, že musíme řešit úlohu s omezením na nerovnost. Tyto úlohy se pak často převádí na úlohu bez omezení pomocí penalt nebo s využitím duality. Další nepříjemností je pro nás zvolit vhodné α (respektive
- 18 -
,…,
).
6
Subgradientní metody
V této části si postupně ukážeme metody, které jsou vhodné pro minimalizaci nespojitě diferencovatelné (nehladké) funkce. Z metod, jež jsou vhodné pro minimalizaci nehladké funkce, se zaměříme na subgradientní metody.
6.1 Předpoklady Předpokládejme na chvíli, že funkce f je hladká,
∈
∨
, a xk je aktuální bod iteračního procesu.
V iteračních metodách se zpravidla volí krok metody jako násobek kladného čísla a −∇ (
(délka kroku)
):
metoda spádového typu: =
Směr −∇ ( (
)≤ (
−
> 0(
∇ (
),
ℎ).
(6.1)
) je směrem klesání. Line search je rutina, která vybere takové
≥ 0, pro které platí
). Pro zvýšení rychlosti konvergence metody potom přidáme další řídící informaci
a přenásobíme ∇ (
) maticí Hk, která v určitém smyslu je blízká inverzi matice Hessianu z funkce
v bodě xk. Matici Hk+1, kterou potřebujeme v dalším kroku, získáváme z matice Hk jednoduchou úpravou(tzv. update formula): metoda Newtonova typu: =
=⋯
> 0(
−
…(
H ∇ (
ℎ),
),
(6.2) ).
Pro nehladkou funkci f (která je lokálně Lipschitzovsky spojitá a regulární) gradient v bodě xk nemusí existovat, ale je zřejmé co musíme udělat. Za předpokladu (2.12), že známe alespoň jeden subgradient v bodě xk, tak jím nahradíme gradient v (6.1 a 6.2). Tento subgradient zapíšeme jako gk. Normalizováním hledaného směru (‖. ‖ značení euklidovské normy) dostáváme zobecnění z (6.1):
- 19 -
=
−
‖
‖
∈
(
),
> 0 ( volíme vhodné).
(6.3)
Odpovídající rozšířením (6.2) se budeme zabývat v sekci 6.3. Z předchozího textu nám vyplývají dvě zásadní otázky okolo subgradietnich metod, které si ilustrujeme na příkladech: 1. Jak lze vybrat tk v (6.3) pomocí line search? 2. Existuje nějaká zastavovací podmínka pro (6.3)? Nejdříve si zodpovíme druhou otázku. V případě hladké funkce je norma gradientu tím menší, čím více se blížíme k hledanému řešení. Tímto máme zaručenu vhodnou zastavovací podmínku. Bohužel, tato gradientní podmínka neplatí pro nehladké funkce. Předpokládejme ještě jednou funkci:
( ) = | |(=
{+ , − }).
Obrázek 5: subgradient funkce ( ) = | |
Obrázek 6: funkce ( ) = | |
Potom máme subgradient +1 nebo -1 v bodě xk ≠ 0, ale to nám nedává žádnou informaci, pokud jsme blízko minima, či nejsme. Předpokládejme teoreticky, že xk je minimum, i.e. xk = 0 a z
(
(
)=
{−1, +1}. Díky našemu základnímu tvrzení (2.12) známe jen jeden element
), například gradient jedné z funkcí + nebo −
S těmito omezenými znalostmi v bodě
(obě jsou aktivní v 0) je +1 nebo -1.
nedokážeme rozpoznat, že jsme se již dostali do minima
funkce, místo toho se budeme vzdalovat používáním
- 20 -
= +1 nebo -1 v (6.3).
To nám ilustruje, že znalost subgradientu nám nestačí k rozpoznání minima. A vskutku chybějící implementovatelná zastavovací podmínka je jedna z hlavních nevýhod subgradientních metod. Nyní se pokusíme vyřešit první otázku a uvažujeme funkci (4.3) v nediferencovatelném bodě, = (0,0) . Podle definice (2.4) vektor
řekněme
= (9,16) je subgradientem
Prozkoumáním vrstevnic v obrázku č. 1 zjistíme, že tento speciální − > 0 splňující (
Nejsme schopni najít délka kroku
)< (
) s tímto
v bodě
.
není směrem klesání.
v (6.2). Rozdíl oproti (6.1) je, že
nemůže být určena prostřednictvím line search.
Dva předchozí příklady nám ilustrují, že je nutné vybrat
a-priori,
je zvoleno bez znalosti
funkce. Následující jednoduché, avšak základní Lemma, nám určuje účelnou cestu, v jejím důsledku získáme korektní iteraci (6.3). Lemma 6.1: Předpokládejme, že
není dosud minimum a
> 0, pro iteraci (6.3), takové že: ‖
∗‖
−
<‖
−
∗‖
∈ (0,
pro všechna
∗
).
je minimum. Pak musí existovat
(6.4)
Důkaz: Podle definice euklidovské normy máme pro libovolné kladné součin): ∗
‖
= ( =‖
∗
∗
−
−
)+
‖
‖ +2
‖ ‖
∗
−
‖
−
,(
‖
‖
, ‖ ‖
‖
Protože:
Dostáváme:
∗
‖ =
−
‖ =‖
∗
−
− ∗
−
,
∗
‖
‖
)+ −
‖
‖
+
‖
= 1.
‖ +2
+ - 21 -
, ‖ ‖
‖
((·,·) značí skalární
s Protože
=
‖
‖
,
je subgradientem v bodě
Tedy diskusí 2
(2
+
+
∗
−
(6.5)
.
,funkce f je regulární a protože
není minimum
< 0.
(6.6)
) < 0 dostaneme:
<0
0<
<
= −2
.
(6.7)
To společně s (6.5) dokazuje tvrzení. Pro konvexní funkce platí: ≤
( ∗) − ( ‖ ‖ < −2
)
⇒
< −2
a pro konkávní:
< −2
a
∗
≤
2
(
≥
2
(
(6.8a)
) − ( ∗) ‖ ‖
) − ( ∗) . ‖ ‖
(6.8b)
Výše uvedené Lemma má krásnou geometrickou interpretaci. (6.6) ukazuje, že úhel | | mezi − −
je menší než π/2 i.e. body polopřímky
poloprostoru, který je určen bodem
−
/‖
‖, ≥ 0,body leží v otevřeném
a normálovým vektorem
uspokojující (6.4), je zřejmá.
- 22 -
∗
−
. Existence
> 0,
α ∗
−
/‖
‖, ≥ 0
Obrázek 7: Geometrická interpretace (6.5)
Nejsme však schopni určit hodnotu
v (6.5) a tudíž ani určit
v (6.7). Víme pouze, že délku kroku
v (6.3) by měla být menší k zachování nerovnosti (6.4). Toto nás vede
k myšlence vybrat
jako člen posloupnosti mající za limitu 0. Toto je jedno z kritérií, které musí být uvažováno pro výběr . Zvolme indexem k platí: ‖
−
za počáteční bod iterace (6.3) a položíme Λ ≔ ∑
‖≤‖
=
−
+
‖+‖
−
+⋯+
‖ +⋯+‖ ≤ Λ.
−
. Poté pro každou iteraci s
‖
Jinými slovy: zůstáváme po celou dobu trvání metody v okolí počátečního bodu
(6.9) s poloměrem Λ.
Protože počáteční bod může být libovolně vzdálen od minima, snažíme se zvolit posloupnost aby suma
tak,
šla do +∞. To nás vede k poněkud více detailně zvolené variantě (6.3): =
−
‖
takové, že lim →
‖
kde
=0
∈
(
),
= ∞. - 23 -
(6.10)
6.2 Metoda spádového typu s délkou kroku vybranou a-priori Teorém 6.2: Předpokládejme, že množina všech řešení minimalizace úlohy a omezená. Pak libovolný počáteční bod k určitému
∗
∈
∗
:
→
tzn.
∗
a vybraná podposloupnost
→ ∞.
∗
∗
, splňující (6.10), konverguje
= inf ( ) a
splňovalo podmínku (6.10). Pro každé ∈ ℕ musí existovat takové =
je neprázdná
(6.11)
Důkaz teorému 6.2 je spíše technického rázu. Zavedeme si
, odtud lim
∗
, které vybereme, aby
, které splňuje
.
≤
∗
+
Iterace (6.10) je jedna z nejjednodušších metod hledání minima funkce. Ve specifických příkladech nepotřebuje rutinu line search. Ale naproti tomu předem určené konvergence. Tedy, pokud nemáme pro určení o minimu funkce f a iteračních bodech
způsobuje velmi malou rychlost
vhodný postup, vycházející z dalších informací
.Nyní si ukážeme, že rychlost konvergence subgradientní
metody je menší než geometrická. Předpokládejme na chvíli, že by konvergovalo k
∗
geometricky (také můžeme říci R-lineární rychlostí konvergence), i.e.
Musí existovat ‖
−
určené pomocí (6.10),
>0
Pak pro všechna k platí:
∗‖
=‖
≤
0<
< 1 takové, pro které
(6.12)
pro všechna .
−
‖≤‖
−
Vysčítáním přes všechna k zjistíme, že:
≤
∗‖
( + 1)
Z předchozí formule obdržíme spor, protože
+‖
∗
=
−
‖≤
( + 1)
.
( + 1) . (1 − )
na levé straně diverguje k +∞, zatímco pravá strana je
konečná. Následkem předchozího jsme dokázali, že řád konvergence (6.11) je menší než geometrický.
- 24 -
Následující obrázek a tabulka ukazuje vybereme hodnotu 0
∑
.
= ∞, pro
,
, které získáváme z funkce (4.3), když si za délku kroku
= 0,1, …, a startovní bod stejný jako v obrázku 8. Podmínky lim
jsou splněny. Podle Teorému 6.2 bod
musí konvergovat k jedinému minimu
∗
bodu
=
(nebo vhodná vybraná posloupnost)
= (−1,0) . Ačkoliv na první pohled se jeví rychlost
konvergence jako dobrá, už po dvou krocích se dostáváme poblíž optimálního bodu ∗
→
∗
, ale pak v okolí
rychlost konvergence začíná oscilovat. Toto je typické chování subgradientních metod, které
je zapříčiněno jejich ,,slepotou“, která je způsobena výběrem
a priori, nezávisle na konkrétní situaci.
Obrázek 8: Vykreslení hledání minima funkce s délkou kroku vybranou a priori
- 25 -
k 0 1 2 3 4 5 6 7 8 9 10
‖
− ∗‖ 0.927048 0.568845 0.472272 0.178671 0.285007 0.013402 0.228266 0.010766 0.186961 0.005711 0.161596
( ) − ( ∗) 26.027756 13.244662 13.036122 5.119481 7.224832 0.834885 4.569998 0.214412 3.652254 0.172254 2.991382
k 20 21 50 51 140 141 180 181 215 216 217
‖
− ∗‖ 0.102132 0.003269 0.053003 0.001218 0.021742 0.000008 0.015000 0.000102 0.000000 0.010023 0.000046
(
) − ( ∗) 0.010745 1.381255 0.000620 0.569872 0.248519 0.000052 0.000023 0.192242 0.161111 0.000000 0.160369
Tabulka 1: Ukázka ,,oscilace’’ subgradientní metody s pevnou délkou kroku
Předchozí tabulka nám ukazuje, jak rychle se blíží
k
∗
. Pří výběru takového
, aby splňovalo
(6.11). V další části se budeme zabývat speciálním případem, kdy Lemmu 6.1 vyjádříme precizněji a v důsledku toho získáme více kvalitativní výběrové pravidlo pro klesání ‖
−
. Toto nám zaručí monotonii
∗‖
, jež nebylo v předchozím případě.
6.3 Metoda spádového typu s monotonním klesáním Předpokládejme na chvíli, že známe ( ∗ ) pro minimum
Pak můžeme vypočítat 2( (
) − ( ∗ ))/‖
ještě minimum) rovnající se nebo menší než
=
(
) − ( ∗) s0< ‖ ‖
∗
.
‖. Získáme nezáporné číslo (v případě, že
není dosud
v (6.7). Proto nerovnost platí pro speciální: (6.13)
< 2.
(6.13) plyne v případě konvexní funkce z (6.8a) a v případě konkávní funkce z (6.8b). Vypočitatelná délka kroku (6.13) včleňuje znalosti, které máme o ‖
−
∗‖
,
a
∗
. To nám zaručí monotonii klesání
pro všechna k. Předchozí výsledek byl ověřen Poljakem [4]
- 26 -
pro speciální případ.
Teorém 6.3: Předpokládejme, že funkce f má jediné minimum ( ∗ ) a nějaké malé ℓ > 0:
( ) − ( ∗ ) ≥ ℓ| −
Pak pro každý startovní bod konvergenci k
∗
∗|
∗
, známe hodnotu minima funkce
pro ∀x.
iterace (6.3) s pravidlem pro délku kroku (6.13) nám zajistí
s geometrickou rychlostí. Matematický důkaz ukázal Goffin [5].
Zajímavým výběrem kroku
, který nepotřebuje a-priorní znalosti funkce
( ∗ ), při zajištění
geometrické konvergence (ačkoliv ne nutně do bodu minima), navrhnul Shor [1] a detailně prostudován Gofiinem[5]. Vezměme si předpis (6.3), pak: s
=
>0a0<
(6.14)
< 1.
6.4 Subgradietní metoda Newtonova typu V případě, že neznáme hodnotu minima funkce ( ∗ ), a také nechceme riskovat konvergenci k bodu,
jež nemusí být minimem, pak nám zůstává jediná cesta k urychlení konvergence sugradientních iterací: nemůžeme použít iterace (6.3), ale můžeme přidat informaci, která je obsažena v předchozím kroce. Shor navrhnul tuto modifikaci v [1]. Základní myšlenka: předpokládejme, že startujeme z bodu musíme najít bod
pohybem určeným
a musíme vybrat
Ve vlastním zájmu se snažíme zkrátit část s rozšíření znamená násobení
s matici
, pak
jako nový subgradient pro
, která je kolineární s již použitým směrem
.
. Toto
. Když toto opakujeme pro každý krok a zapisujeme tuto
zhuštěnou formu (zásluhou Shokova[30]), pak dostáváme následující iterační předpis, ve kterém rozšiřující matice
jsou vypočteny následujícím způsobem: =
− =
Zde
vyjadřuje
/
s
(
∈
− ;
), (6.15a)
. ,
a délka kroku
matice je kladný násobek jednotkové matice,
= - 27 -
. Pro
jsou nezáporné parametry a startovací = 1,
=1 a
= 0 dostáváme zpět
(5.3). Jeden parametr se ukazuje být pro nás zvláště zajímavý. Tímto parametrem je pro nás dimenze prostoru ( > 1). Díky tomu vybíráme pro
= 0,1,2, …
,
a
v (6.15a) jako konstanty: (6.15b)
= /( − 1) = 2/( + 1) = 1/( + 1).
Následující výklad konvergence najdeme zpracovaný v Shor a více detailně v Goffin. Teorém 6.4: Mějme startovací bod minimum
∗
. Pak existuje min
> 0a
=
a startovací matici
−
∗‖
≤ , pro
< 1 takové pro které sekvence generovaná (6.15a,b) splňuje:
− ( ∗) ≤
(6.16)
pro ∀ .
(6.16) garantuje, že vybraná posloupnost funkčních hodnot (
rychlostí. Bližší analýzou se ukáže, že 1 − 1/2
splňující ‖
=[
/(
− 1)]
/
) konverguje k ( ∗ ) geometrickou
[1 − 2/( + 1)]
/
, které je přibližně
. Odtud zjistíme, že q je blízko 1 pro velké n. Podrobnější informace najdeme v [6].
- 28 -
7 Srovnání použitých metod na příkladech V této kapitole si zavedeme 4 funkce, na kterých si ukážeme rychlost konvergence jednotlivých metod s proměnnou přesností. U všech těchto funkcí ( ): ℝ → ℝ, si zavedeme subgradient
7.1 Funkce č. 1 – nehladká, konvexní Předpis:
( ) = | − 1| + | − 2| + | − 3| + | − 4| + | − 5| = Funkce č. 1 pro přehlednost definovaná pomocí intervalů: −5 + 15, ≤ 1 ⎧ −3 + 13, ∈ 〈1,2〉 ⎪ ⎪ − + 9, ∈ 〈2,3〉 ( )= + 3, ∈ 〈3,4〉 ⎨ ⎪ ⎪ 3 − 5, ∈ 〈4,5〉 ⎩5 − 15, ∈ 〈5, ∞〉.
Obrázek 9: Graf funkce č. 1
- 29 -
| − |.
∈
( ).
Obrázek 10: Graf zobecněného gradientu funkce č. 1
7.2 Funkce č. 2 - Rosenbrockova funkce – hladká, konvexní Předpis:
Gradient
Hessova matice
( ) = 100( = [−400(
=
− 1200
)
−
) + (1 −
− 2(1 −
− 400 −400
- 30 -
) .
); 200(
+ 2 −400 −400
−
.
)].
Obrázek 11: Graf Rosenbrockovy funkce
7.3 Funkce č. 3 – nehladká, konvexní Předpis: ( )=−
+ 2(
+
− 1) + 1.75
- 31 -
+
−1 .
Obrázek 12: Graf funkce č. 3
Absolutní hodnota rozděluje funkci na 3 množiny: pro pro pro
+
+
+
− 1 < 0 dostáváme
− 1 = 0 dostáváme
− 1 > 0 dostáváme
= [0.5
= [7.5
= [7.5
1
1
1
− 1; 0.5 2 ],
− 1; 7.5 2 ],
− 1; 7.5 2 ].
Tuto funkci řešíme ještě řešit pomocí poruchové techniky: min| ( )| ≈ min ∈ℝ
(7.1)
( ) + .
Subgradient a Hessián je uveden v příloze užitých m-filů.
- 32 -
Obrázek 13: Rozdělení Funkce č. 3 na množiny
7.4 Funkce č. 4 – nehladká, regulární Předpis: ( ) = max{
+(
− 1) +
− 1, −
- 33 -
−(
− 1) +
+ 1}.
Obrázek 14: Graf funkce č. 4 Maximum rozděluje funkci na 3 množiny: pro pro pro
+(
+(
+(
− 1) − 1 < 0 dostáváme
− 1) − 1 = 0 dostáváme
− 1) − 1 > 0 dostáváme
= [−2 ; −2
= [−2 ; −2
= [2 ; 2
+ 3],
+ 3],
− 1].
7.5 Tabulka srovnání jednotlivých metod na příkladech V této podkapitole ukazujeme závislost počtu iterací na dané přesnosti jednotlivých nehladkých subgradientních metod a hladkých Newtonových metod. Jako zastavovací podmínku jsme si určili ‖
−
‖ < zadaná přesnost. Poznámka: MN – metoda nedokonvergovala k minimu. Funkce 3*
je aproximace funkce 3 podle (7.1).
- 34 -
7.5.1
Srovnání nehladkých metod
Funkce
Spádová metoda s délkou kroku vybranou a priori
Spádová metoda s monotonním klesáním
Metoda Newtonového typu
4 1 141 16 MN 2 609 38 3 MN 44 65 4 MN 24 65 Tabulka 2: Počty iterací subgradientnich metod - startovací bod 10/[10,10], přesnost 1e-2
Funkce
Spádová metoda s délkou kroku vybranou a priori
Spádová metoda s monotonním klesáním
Metoda Newtonového typu
4 1 14142 28 MN 2 905 73 3 MN 72 70 4 MN 46 72 Tabulka 3: Počty iterací subgradientnich metod - startovací bod 10/[10,10], přesnost 1e-4
Funkce
Spádová metoda s délkou kroku vybranou a priori
Spádová metoda s monotonním klesáním
Metoda Newtonového typu
4 1 1414213 39 MN 2 1303 73 3 MN 72 70 4 MN 68 72 Tabulka 4: Počty iterací subgradientnich metod - startovací bod 10/[10,10], přesnost 1e-6
7.5.2
Srovnání hladké Newtonovy metody pro minimalizaci funkce
V této podkapitole si ukážeme konvergenci Newtonovy metody. Funkci č. 3 jsme aproximovali pomocí poruchové techniky pro různá epsilon.
- 35 -
Příklad
Newtonova metoda pro hladké funkce ( = 1 − 4)
Newtonova metoda pro hladké funkce ( = 0.05)
Newtonova metoda pro hladké funkce 1e-4
Newtonova metoda pro hladké funkce epsilon = 0.05
MN 1 3 2 31558 1578 3* MN 4 Tabulka 5: Počty iterací hladkých metod - startovací bod 10/[10,10], přesnost 1e-2
Příklad
MN 1 4 2 63143 1580 3* MN 4 Tabulka 6: Počty iterací hladkých metod - startovací bod 10/[10,10], přesnost 1e-4
Příklad
Newtonova metoda pro hladké funkce 1e-4
Newtonova metoda pro hladké funkce epsilon = 0.05
MN 1 4 2 63144 1580 3* MN 4 Tabulka 7: Počty iterací hladkých metod - startovací bod 10/[10,10], přesnost 1e-6
- 36 -
8 Závěr Cílem bakalářské práce bylo seznámit čtenáře s úvodem do problematiky minimalizace nespojitě diferencovatelných funkcí. K tomuto úkolu jsme si představili základní pojmy z nehladkého kalkulu. Poté jsme si na konkrétním příkladě ukázali selhání klasických hladkých metod pro minimalizaci nehladké funkce. Dále jsme si v kapitole 5 ukázali, jak převést speciální nehladkou funkci na hladkou. A poté, přes klasické metody, kdy jsme brali v potaz pouze hladké funkce, jsme se propracovali až ke kýženým subgradientním metodám, které jsme následně použili pro řešení některých úloh.
Přínos této práce spočívá: 1. Numerická realizace uvedených metod viz příloha. 2. Porovnání efektivity jednotlivých metod pro minimalizaci jednotlivých funkci. Došli jsme k závěru, že pro minimalizaci hladké funkce je výrazně rychlejší Newtonova metoda v porovnání se subgradientními metodami. Také se ukázalo, že možné převedení nehladké funkce na hladkou s použitím Newtonovy metody konverguje k minimu velmi pomalu. S rostoucí přesností aproximace minimalizované nehladké funkce (řízená volbou ) klesá rychlost konvergence Newtonovy metody a naopak. Při použití subgradientních metod na nehladké funkce se ukazuje, že když je funkce po částech lineární je mnohem rychlejší spádová metoda s monotoním klesánim díky tomu, že tato metoda aproximuje funkci po částech lineárním modelem. Naproti tomu, jestliže je funkce po částech kvadratická, pak má větší rychlost konvergence metoda Newtonového typu, která vytváří kvadratický model funkce. Ve všech případech jde vidět, že spádová metoda s délkou kroku vybranou a-priori je pomalejší než ostatní subgradientní metody, to je způsobeno tím, že tato metoda využívá pouze subgradientní informaci, zatímco zbylé metody používají dalších informací o minimalizovaných funkcích. 3. Oproti předpokladům z literatury, z níž jsme čerpali, jsme ukázali, že subgradientní metody jdou použít i na větší škálu funkcí než jen konvexní V literatuře, která se zabývá subgradientními metodami, bývá požadavek na konvexitu minimalizované funkce. Ukázali jsme, že tyto metody jdou použít i na větší šíři funkcí tzv. regulární funkce.
Požadavek regularity, který je slabší než konvexnost, jsme využili v Lemmě 6.1. A požadavek jsme si ověřili u funkce č. 4, která není konvexní, ale pouze regulární. - 37 -
9 Literatura [1] Shor,N. Z. Application of the Gradient Method for the Solution of Network Transportation Problems, Scientific Seminar on Theory and Application of Cybernetics and Operations Research, Academy of Sciences, Kiev, 1962 [2] Hirriart-Urruty, Lemarechal, C. Convex Analysis and Minimization Algorithms I, II, Springer, 1993 [3] Lukšan, Ladislav. Numerické optimalizační metody. Praha: Institute of Computer Science, Academy of Sciences of the Czech Republic, Prosinec 2005. 254 s. [4] Poljak, B. T. Minimization of unsmooth functionals, USSR Computational Mathematics and Mathematical Physics 9, 1969. 14 - 29 s. [5] Goffin, J.L. Nondifferentiable optimization and the relaxation method. Oddíl Nonsmooth Optimization. New York: Pergamon Press, 1981. [6] Zowe, J. Nondifferentiable Optimization , Computational Mathematical Programming, edited by K. Schittkowski, Springer - Verlag, Berlin - Heidelberg, 1985 [7] Shokov, V. A. Note on minimization methods using space dilation, Cybernetics 10, 689-692 s. [8] Daněk,
Josef.
Numerické
metody
[online].
2009
[cit.
03.03.2009].
z WWW:
- 38 -
Dostupný
Přílohy A Zdrojový Kód Metody pro minimalizaci: 1. newtonMinimum.m function [x,it] = newtonMinimum(gradient,hessian,x0,e) % % % % % % % % % %
funkce nalezne minimum rovnice Newtonovou metodou x ... koren it ... pocet iteraci gradient ... subgradient zadane funkce hessian ... Hessova matice zadane funkce x0 ... pocatecni aproximace e ... pozadovana absolutni presnost
it = 0; x=x0; % hodnotu epsilon vyuzivame jen u funkce aproximovane neprimou metodou epsilon = 0.05; % G = feval(gradient,x,epsilon); % H = feval(hessian,x,epsilon); G = feval(gradient,x); H = feval(hessian,x); % iteracni predpis pro hledani minima pomoci newtonovy metody x1 = x - G'*inv(H); %ukoncovaci podminka while norm(x1-x) >= e it = it + 1; x = x1 ; % G = feval(gradient,x,epsilon); % H = feval(hessian,x,epsilon); G = feval(gradient,x); H = feval(hessian,x); x1 = x - G'*inv(H);
end x = x1;
- 39 -
2. subgradientP.m function [x,it] = subgradientP(subG,x0,e) % Spadová metoda s delkou kroku vybranou a-priori % % x ... koren % it ... pocet iteraci % % subG ... subgradient zadane funkce % x0 ... pocatecni aproximace % e ... pozadovana absolutni presnost it = 1; x=x0; % delka kroku splnujici (6.10) tk = 1/(1+it); % vypocet subgradientu z externi funkce subGr = feval(subG,x); %iteracni predpis x1 = x - tk*(subGr/norm(subGr)); %ukoncovaci podminka while norm(x1-x) >= e it = it + 1; x = x1 ; tk = 1/(1+it); subGr = feval(subG,x); x1 = x - tk*(subGr/norm(subGr)); end x = x1;
3. subgradientPosloupnost.m function [x,it] = subgradientPosloupnost(funkce,subG,funMin,x0,e) % Spadová metoda s monotonim klesanim % % x ... koren % it ... pocet iteraci % % funkce ... funkce % subG ... subgradient zadane funkce % funMin ... funkci hodnota minima funkce % x0 ... pocatecni aproximace % e ... pozadovana absolutni presnost it = 1; x=x0; % vypocet subgradientu z externi funkce subGr = feval(subG,x); % delka kroku splnujici (6.13), lambda = 1 tk = 1*(feval(funkce,x)- funMin)/norm(subGr);
- 40 -
%iteracni predpis x1 = x - tk*(subGr/norm(subGr)); %ukoncovaci podminka while norm(x1-x) >= e it = it + 1; x = x1 ; subGr = feval(subG,x); tk = 1*(feval(funkce,x)- funMin)/norm(subGr); x1 = x - tk*(subGr/norm(subGr)); end x = x1;
4. subgradientPosloupnostH.m function [x,it] = subgradientPosloupnostH(subG,x0,e) %Metoda Newtonového typu % % x ... koren % it ... pocet iteraci % % subG ... subgradient zadane funkce % x0 ... pocatecni aproximace % e ... pozadovana absolutni presnost % mala hodna s niz porovnavame odmocninu z Hk, aby nedoslo % k pocitani odmocniny z cisla blizkeho nule epsilon = 1e-12; % dimenze prostoru n = length(x0); it = 1; x=x0; subGr = feval(subG,x); % nastaveni pro pripad kdy se dimenze = 1, % cili osetreni, aby se nedelilo 0 if(n==1) n =2; % konstatny vychazejici z dimenze alfa = n^2/(n^2-1); beta = 2 / (n+1); tk= 1/(n+1); n=1; else alfa = n^2/(n^2-1); beta = 2 / (n+1); tk= 1/(n+1); end % pocatecni matice Ho h0=alfa*eye(n)*100; % vypocet odmocniny
- 41 -
odmocnina = sqrt((subGr')*h0*subGr); % osetreni pripadu kdy je odmocnina blizka 0, cili mozne deleni 0 if(odmocnina < epsilon) x1 = x - (tk*h0*subGr)*epsilon; dk = (h0*subGr)*epsilon; else x1 = x - (tk*h0*subGr)/odmocnina; dk = (h0*subGr)/odmocnina; end % vypocet Hk hk = alfa*(h0-beta*dk*dk'); %ukoncovaci podminka while norm(x1-x) >= e it = it + 1; x = x1 ; subGr = feval(subG,x); % osetreni pripadu kdy je odmocnina blizka 0, cili mozne deleni 0 odmocnina = sqrt((subGr')*hk*subGr); if(odmocnina < epsilon) x1 = x - (tk*hk*subGr)*epsilon; dk = (hk*subGr)*epsilon; else x1 = x - (tk*hk*subGr)/odmocnina; dk = (hk*subGr)/odmocnina; end hk = alfa*(hk-beta*dk*dk'); end x = x1;
Funkce a jejich subgradienty: 1. funkce1.m a subG1.m function out = funkce1(x) % funkce c. 1 out=abs(x-1)+abs(x-2)+abs(x-3)+abs(x-4)+abs(x-5); function out = subG(x) % Subgradient funkce c. 1 if(x<=1) out = -5; elseif(x<=2) out = -3; elseif(x<=3) out = -1; elseif(x<=4) out = 1;
- 42 -
elseif(x<=5) out = 3; else out = 5; end
2. funkce2.m a subG2.m function out = funkce2(x) % funkce c. 2 - Rosenbrockova funkce out=100*(x(2)-x(1)^2)^2+(1-x(1))^2;
function out = subG2(x) % Subgradient funkce c. 2 out = [-400*x(2)*x(1)+400*(x(1))^3+2*x(1)-2; 200*x(2)-200*x(1)^2];
3. funkce3.m a subG3.m function out = funkce3(x) % funkce c. 3 out=-x(1)+2*(x(1)^2+x(2)^2-1)+1.75*abs(x(1)^2+x(2)^2-1);
function out = subG3(x) % Subgradient funkce c. 3 if(x(1)^2+x(2)^2<1) out=[0.5*x(1)-1;0.5*x(2)]; elseif(x(1)^2+x(2)^2>1) out = [7.5*x(1)-1;7.5*x(2)]; else out = [7.5*x(1)-1;7.5*x(2)]; end
4. funkce3Aprox .m a subG3Aprox.m a Hes4Aprox.m function out = funkce3Aprox(x,epsilon) % funkce c. 3 - aproximovana neprimou metodou out=-x(1)+2*(x(1)^2+x(2)^2-1)+1.75*sqrt(((x(1)^2+x(2)^2-1))^2+epsilon); function out = subG3Aprox(x,epsilon) % Subgradient funkce c. 3 - aproximovane neprimou metodou out = [ -1+4*x(1)+1.75*((x(1)^2+x(2)^2-1)^2+epsilon)^(-0.5)*... (x(1)^2+x(2)^2-1)*2*x(1); 4*x(2)+1.75*((x(1)^2+x(2)^2-1)^2+epsilon)^(-0.5)*... (x(1)^2+x(2)^2-1)*2*x(2)];
- 43 -
function out = Hes4Aprox(x,epsilon) % Hessian funkce c. 3 - aproximovane neprimou metodou out = [ 4+1.75*((-1)*((x(1)^2+x(2)^2-1)^2+epsilon)^(-1.5)*(x(1)^2+x(2)^21)^2*4*x(1)^2+((x(1)^2+x(2)^2-1)^2+epsilon)^(-0.5)*4*x(1)^2+((x(1)^2+x(2)^21)^2+epsilon)^(-0.5)*(x(1)^2+x(2)^2-1)*2),... 1.75*4*x(1)*x(2)*(-0.5*((x(1)^2+x(2)^2-1)^2+epsilon)^(-3/2)*(x(1)^2+x(2)^21)^2+((x(1)^2+x(2)^2-1)^2+epsilon)^(-0.5)); 1.75*4*x(1)*x(2)*(-0.5*((x(1)^2+x(2)^2-1)^2+epsilon)^(-3/2)*(x(1)^2+x(2)^21)^2+((x(1)^2+x(2)^2-1)^2+epsilon)^(-0.5)),... 4+1.75*((-1)*((x(1)^2+x(2)^2-1)^2+epsilon)^(-1.5)*(x(1)^2+x(2)^21)^2*4*x(2)^2+((x(1)^2+x(2)^2-1)^2+epsilon)^(-0.5)*4*x(2)^2+((x(1)^2+x(2)^21)^2+epsilon)^(-0.5)*(x(1)^2+x(2)^2-1)*2) ];
5. funkce4.m a subG4.m function out = funkce4(x) % funkce c. 4 f1 = x(1)^2+(x(2)-1)^2+x(2)-1; f2 = -x(1)^2-(x(2)-1)^2+x(2)+1; % vyber funkcniho maxima out = max([f1;f2]); function out = subG4(x) % Subgradient funkce c. 4 if(x(1)^2+(x(2)-1)^2>1) out=[2*x(1);2*x(2)-1]; elseif(x(1)^2+(x(2)-1)^2<1) out = [-2*x(1);-2*(x(2)-1)+1]; else out = [-2*x(1);-2*(x(2)-1)+1]; end
- 44 -
