PV027 Optimalizace
Radka Svobodová
Co je optimalizace?
Již v minulosti řada matematiků a přírodovědců
dospěla k přesvědčení, že přírodní děje lze
popsat jako optimalizační procesy.
O čem jsou optimalizace?
Euler: „Na světě se nestane nic, v čem by nebylo
vidět smysl nějakého maxima nebo minima“.
Leibnitz: „Náš svět je nejlepší ze všech možných
světů, a proto lze jeho zákony vyjádřit
extremálními principy“.
Definice optimalizace
Optimalizaci lze definovat například
následovně:
Obor zabývající se určením nejlepšího
řešení jistého matematicky
definovaného problému.
Definice optimalizace II
Postup při optimalizaci:
• Nastudování optimalizačních kritérií problému
• Nalezení metody řešení problému
• Matematický popis řešení (pomocí funkce)
• Nalezení minima funkce
Definice optimalizace IV
Předmět PV027 se zabývá matematickou
optimalizací, tedy minimalizací reálných
funkcí, tj. úlohami typu:
kde:
min ( )
x M
f x

f R R
M R
n
n
: →

Definice optimalizace V
Poznámka:
Není nutné zabývat se samostatně také
maximalizací, neboť ji lze převést na
minimalizaci pomocí vztahu:
( )max ( ) min ( )
x M x M
f x f x
 
= − −
Definice optimalizace VI
Speciální oblasti optimalizace:
• Diskrétní optimalizace:
Využívají se v případech, kdy mají význam pouze
celočíselná řešení.
• Speciální úlohy:
Existuje určitý typ úloh, jejichž řešení nemá příliš
smysl popisovat jako .
Příklad: problém obchodního cestujícího
min ( )
x M
f x

Sylabus
• Úvod
– Definice optimalizace
– Informace o předmětu
• Sylabus předmětu
• Vstupní požadavky předmětu
• Požadavky ke zkoušce a k zápočtu
• Materiály ke studiu
– Aplikace optimalizačních metod
– Motivační příklady
– Matematické základy
Sylabus II
• Optimalizace bez omezení (unconstrained)
– Nelder-Meadova metoda
– spádové metody
– metody sdruženého gradientu
– newtonovské metody
– metody s omezeným krokem
– úloha nejmenších čtverců
Sylabus III
• Optimalizace s omezením (constrained)
– Lineární programování:
• grafické řešení úloh
• přímá metoda
• simplexová metoda
– Nelineární programování:
• Obecný přístup
• kvadratické programování
– Celočíselné programování
• metoda větví a mezí
Sylabus IV
• Globální optimalizace:
– simulované žíhání
– genetické algoritmy
– metoda difuzní rovnice
• Praktický projekt
• Aplikace vybrané optimalizační metody pro řešení
konkrétního problému
Vstupní požadavky
• Znalosti z oblastí:
– Lineární algebra
– Matematická analýza
Požadavky ke zkoušce a hodnocení
Požadavky: znalosti v rozsahu přednášek
Hodnocení:
• A: 100 - 90 %
• B: 90 - 80 %
• C: 80 - 70 %
• D: 70 - 60 %
• E: 60 - 50 %
• F: 49 - 0 %
Možnost bonusových procent.
Požadavky k zápočtu
Požadavky:
Vypracovat zápočtový projekt (zadání
projektu získá student po domluvě s učitelem).
Hodnocení:
z projekt splňuje požadavky, domluvené
při zadávání
n jinak
Poznámka:
Předmět PV027 nelze ukončit kolokviem.
Aplikace optimalizačních metod
Optimalizační úlohy se vyskytují všude tam, kde je možné
vybírat si z více možných rozhodnutí a přitom kvalitu
jednotlivých rozhodnutí ohodnotit nějakým reálným
číslem. Konkrétní oblasti využití optimalizace:
Matematika: teorie aproximace, optimalizace
numerických procesů atd.
Geometrie: geodézie, minimální křivky a plochy,
optimální oblasti a tvary, atd.
Ekonomické a politologické teorie: využívání zdrojů a
zásob, optimální skladba výroby, tvorba cen, rozložení
rizika, strategické hry, teorie eskalace konfliktu, atd.
Fyzika: mechanika, geometrická optika, teorie pružnosti,
hydrodynamika, teorie relativity, atd.
Aplikace optimalizačních metod II
Přírodní vědy: modely fyzikálních, chemických a
biologických procesů, atd.
Teorie řízení: optimální řízení, optimální systémy,
hierarchické řízení, koordinační strategie, atd.
Teorie konstruování: optimalizace konstrukcí,
optimalizace tvarů, optimální odhad neznámých
parametrů, optimalizace dynamických vlastností
mechanických systému, optimalizace spolehlivosti a rizika
konstrukcí, atd.
Další aplikace: při správě vodních toků (vypouštění a
napouštění nádrží), v zemědělství (např. optimální krmná
směs pro zvířata), v dopravě a logistice a kdekoliv jinde,
kde se nám podaří zformulovat smysluplnou
optimalizační úlohu
Typy optimalizací
Lokální X globální:
Lokální optimalizace:
• Nalezení jediného minima, nacházejícího se v určitém
intervalu
f(x)
x
Typy optimalizací II
Lokální optimalizace – další možný přístup:
• Nalezení nejbližšího minima do kterého lze sestoupit ze
vstupního bodu
f(x)
x
Typy optimalizací III
Globální optimalizace:
• Hledání nejhlubšího minima v daném intervalu
f(x)
x
Typy optimalizací IV
Bez omezení X s omezeními:
Bez omezení (unconstrained)
Kromě podmínky minimality funkce f(x) neexistuje
žádná jiná podmínka, kterou by měla hledaná
optimální hodnota x splňovat.
S omezeními (constrained)
Vedle podmínky minimality pracujeme ještě s dalšími
podmínkami.
Lineární X nelineární:
Lineární
f(x) je lineární funkcí x
Nelineární
jinak
Motivační příklady
Aproximace dat: nelineární model bez omezení
Najděte nejlepší aproximaci pomocí součtu čtverců
pro funkci:
f(U) = U / R
kde aproximované body (U, f(U)) jsou dány
tabulkou a hledáme hodnotu parametru R.
Motivační příklady
Aproximace dat: nelineární model bez omezení
Najděte nejlepší aproximaci pomocí součtu čtverců
pro funkci:
kde c = 96,05 a aproximované body dány tabulkou
( , )t x
x t
x
x c
= −






−
1 1
2
1
1
1
Motivační příklady II
Plánování výroby: lineární model s omezeními
Výrobce používá materiál (m) a práci (l) k výrobě nejvýše čtyř
výrobků (a až d). Požadavky na jednotlivé výrobky a zisk z
jejich prodeje jsou dány následovně:
k výrobě 1 kusu výrobku a je třeba 4m + 2l zdrojů a zisk je 50 Kč/kus
k výrobě 1 kusu výrobku b je třeba m + 5l zdrojů a zisk je 80 Kč/kus
k výrobě 1 kusu výrobku c je třeba 2m + l zdrojů a zisk je 30 Kč/kus
k výrobě 1 kusu výrobku d je třeba 2m + 3l zdrojů a zisk je 40 Kč/kus
Během jednoho dne je k dispozici nejvýše 30 jednotek materiálu a
50 jednotek (např. hodin) práce. V jakém počtu mají být
produkovány jednotlivé výrobky tak, aby bylo dosaženo
maximálního zisku?
Motivační příklady III
Konstrukční problém: nelineární model s omezeními
Navrhněte válcovitou plechovku o objemu 1 dm3, na kterou se
spotřebuje co nejméně kovu.
Motivační příklady IV
Aplikace v chemii: nelineární model bez omezení (s více
lokálními minimy)
Je dána molekula, urči konformace této molekuly, které jsou v
definovaném chemickém prostředí nejstabilnější.
Konformace = uspořádání atomů v prostoru.
Strukturní vzorec: Konformace:
Židličková Zkřížená židličková
Vaničková Poloviční židličková
Motivační příklady IV b)
Čím je konformace stabilnější, tím nižší má
potenciální energii.
Potenciální energie = energie daného uspořádání
atomů v prostoru.
Epot = (souřadnic atomů)
kde  je potenciálová funkce
 : R3N → R, kde N je počet atomů v molekule.
Motivační příklady IV c)
Vytvoříme model molekuly:
Nabité koule, spojené pružinami.
Motivační příklady IV d)
Popíšeme vztah mezi souřadnicemi a Epot:
Nevazebné
interakce
Vazebné
interakce
Motivační příklady IV e)
Grafem potenciálové funkce je
potenciálová hyperplocha
(PES):
Motivační příklady IV f)
Hledáme minima potenciálové funkce.
Matematické základy
Vektory:
– budeme pracovat hlavně se sloupcovými vektory
– vektor budeme označovat malými tučnými písmeny
– transpozici vektoru označíme pomocí písmene T v horním
indexu
a = aT = (a1, a2, ..., an)a
a
an
1
2
...












Matematické základy II
Matice:
– budou se označovat velkými tučnými písmeny
– transpozici matice označíme pomocí písmene T v horním
indexu
B = BT =B B B
B B B
B B B
n
n
m m mn
11 12 1
21 22 2
1 2
...
...
...
   












B B B
B B B
B B B
m
m
n n mn
11 21 1
12 22 2
1 2
...
...
...
   












Matematické základy III
a zi i
i

Matematické základy IV
Posloupnost bodů z Rn:
– jednotlivé body v posloupnosti budeme rozlišovat horním
indexem v závorce. Budeme je tedy psát například jako x(1),
x(2) ... nebo x(k).
– speciální význam bude mít hvězdička (například v x*).
Budeme tak označovat bod, který je řešením vyšetřovaného
problému.
Příklad: (2,2), (1.9, 1.5), (1.7, 1.2), …, (0,0)
Matematické základy V
Přímka v Rn:
– je definována jako množina bodů:
x = f(a) = x´ + a.s
pro všechna a  R, kde x´ je jistý bod, ležící na přímce a
s  Rn je směr přímky.
– kvůli jednoznačnosti je někdy vhodné směr normalizovat,
takže například při euklidovské normě platí:
sTs = = 1si
i
2

Matematické základy VI
Funkce, kterými se budeme zabývat, budou
mít spojité derivace až do druhého řádu.
Gradient:
– Vektor prvních parciálních derivací funkce f v bodě
x = (x1, x2, …, xn)
– Označujeme ho f(x):












=
nx
f
x
f
x
f
xf ,...,,)(
21
Matematické základy VII
Hessova matice (hessián):
– Matice druhých parciálních derivací funkce f v bodě x =
(x1, x2, …, xn)
– Označujeme ho 2f(x)
– Je zřejmé, že Hessova matice je symetrická
( )
( )
( ) 





































=
2
2
2
2
1
2
2
2
2
2
2
12
2
1
2
21
2
2
1
2
2
...
...
...
)(
nnn
n
n
x
f
xx
f
xx
f
xx
f
x
f
xx
f
xx
f
xx
f
x
f
xf

Matematické základy VIII
Gradient a hessián jako zobrazení:
– Operátor  je zobrazením, které každé
diferencovatlené funkci f přiřazuje jinou funkci
f.
– Tedy výrazy f(x) a 2f(x) lze psát také jako
(f)(x) a (2f)(x)
Matematické základy IX
Matematické základy IX
Matematické základy IX
Matematické základy X
Gradient a hessián Rosenbrockovy funkce:
– Rosenbrockova funkce:
f(x) = 100(x2 – x1
2)2 + (1 – x1)2
– Graf má tvar banánovitého údolí se
strmými srázy v jednom směru
a s plochým dnem ve druhém
směru.
Matematické základy XI
Poznámka:
Globálním minimem Rosenbrockovy funkce je bod (1, 1) a leží na dlouhé pomalu
se svažující oblasti, obklopené prudkými srázy.
Je velmi obtížné ji
optimalizovat => používá
se k testování
optimalizačních metod.
Matematické základy X
Vypočítejte gradient a hessián Rosenbrockovy funkce:
– Rosenbrockova funkce:
f(x) = 100(x2 – x1
2)2 + (1 – x1)2
Matematické základy XII
Gradient a hessián Rosenbrockovy funkce:
Gradient:
Hessián:
 =
− − + −
−





2 1
2
2 1
1
1200 400 2 400
400 200
f x
x x x
x
( )
( ) = − − − − −f x x x x x x x
T
( ) ( ) ( ), ( )400 2 1 2001 2 1
2
1 2 1
2
Typy extrémů
Lokální minimum a lokální maximum (často se
označuje pouze minimum a maximum):
Minimum:
$W "xW(x*): f(x)  f(x*)
Maximum:
$W "xW(x*): f(x)  f(x*)
Kde W(x*) je (vícerozměrné) okolí bodu x*.
Typy extrémů III
Globální minimum:
Pokud f(x)  f(x*) pro všechna x z definičního oboru
funkce f, pak je x* globálním minimem funkce f.
Obdobně je definováno globální maximum funkce f.
Typy extrémů IV
Při práci s minimy a maximy, definovanými na předchozích
slidech se může stát, že pro některé funkce dostaneme
„paradoxní“ výsledky.
Např. x = 0 je lokálním minimem funkce:
f(x) = min(1 + x, 0, 1 - x)
a zároveň je také globálním maximem dané funkce.
-3
-2.5
-2
-1.5
-1
-0.5
0
0.5
-3 -2 -1 0 1 2 3
f(x)
Axis Title