11 Základy nelineárního programování, gradientové metody

kdy se používá nelineární programování?

když je účelová funkce nebo podmínka vyjádřena křivkou místo příjimkou (není lineární)

jaké jsou důvody nelinearity?

neproporcionální vztahy (pří zvýšení ceny může klesnou poptávka), závislé činnosti (zákon klesajích výnosů), neplatnost součtových pravidel (mísení látek, dopravní trasy)

rozdíl optima oproti LP

optimum může ležet kdekoliv

jaké vlastnosti funkce rozhodují o tom zda je nalezeno lokální nebo globální minimum?

konvexní a konkávní

co znamená že je funkce konkávní a jaký udává vztah k optimálnímu řešení?

spojnice dvou různých bodů vždy leží uvnitř množiny a lokální minimum je i zároveň optimálním řešením

jaké je nebezpečí pro gradientovou metodu?

může uvíznout v lokální extrému

co je gradient?

nástroj, který hledá směr, kterým se vydat k optimu

co je gradient funkce?

sloupcový vektor prvních parciálních derivací proměnných

co ukazuje vektor gradientu?

směr největšího růstu v daném bodě

co je antigradient a co ukazuje?

vektor opačný ke gradientu ukazující největší pokles

co je stacionární bod?

gradient se zde rovná 0, může být max, min, sedlový bod

pomocí čeho zjistím zda je stacionární bod max, min nebo sedlový bod?

2. derivace

jak získám vektor gradientu?

do derivací dosadím souřadnice bodu

pomocí jaké metody se řeší NLP a jak fungují?

iterační (krokové metody), postupné přibližování se k optimu

jaký je obecný postup iterační metody?

zvolím výchozí bod, určím směr posunu pomocí gradientu, určím délku kroku, posunu se do nového bodu, opakuji až do pravidla pro ukončení

jaké jsou druhy gradientových metod?

s konstantním krokem a největšího spádu

jaká je charakteristika gradientové metody s konstantním krokem?

délka kroku je fixní, hrozí zde přeskočení optima nebo dlouhý výpočet

jaká je charakteristika gradientové metody největšího spádu?

délka kroku se po každém kroku vypočítá znovu, dosahujeme tak v každém směru extrému funkce

jaká jsou kritéria pro ukončení výpočtu?

proběhl předem stanovená počet kroků, rozdíl hodnotami dvou funkcí je zanedbatelný, délka kroku je minimální, gradient se blíží nule

z jakého důvodu nelze jednoduše použít gradient pokud má NLP omezující podmínky?

mohli bychom opustit MŘP

jak převedu úlohu s omezením na úlohu bez omezení?

pomocí pokutové funkce

jak určím výši pokutové funkce pokud převádím na úlohu bez omezení?

pokud bod leží v MŘP je pokuta 0, pokud ne je obrovská a algoritmus je zpět tlačen do přípustné oblasti

jaké metody se používají pokud jen jednu proměnnou?

zlatého řezu a půlení intervalů

jak funguje metoda projekce?

pokud bod vyjde mimo oblast, vrátím ho zpět na nejbližší přípustný bod

jak funguje metoda pokutových funkcí?

při porušení podmínek přičteme vysokou pokutu