Icke-linjär optimering
Icke-linjär optimering är, inom matematik, optimering av en målfunktion under förutsättning att vissa bivillkor gäller, och där minst ett av bivillkoren eller målfunktionen är icke-linjär. Detta kan jämföras med linjärprogrammering där alla bivillkor, samt målfunktionen är linjär.
Det generella problemet kan skrivas som:
- , till exempel att man vill minimera en kostnad genom att välja x ur på rätt sätt
där
Ofta kan mängden med tillåtna punkter beskrivas med ett antal bivillkor
Lösningsmetoder
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/79/Gradient_descent.png/250px-Gradient_descent.png)
Det finns flera olika lösningsmetoder som beroende på problemets form lämpar sig olika väl. För att ta reda på problemets karaktär är det viktigt att kunna bestämma om problemet är konvext. För detta gäller att målfunktionen ska vara konvex på den tillåtna mängden som också måste vara konvexa.
Om problemet inte är konvext så är det vanligt att någon typ av relaxation görs för att få ett konvext problem, för vilka bra lösningsmetoder finns. Det är även vanligt att man relaxerar genom att häva ett av villkoren och istället bildar en straffunktion med det hävda villkoret.
Allmän iterativ sökning av lokalt minimum
Praktiskt använder man en iterativ sökmetod för att hitta ett lokalt optimum (i detta fall minimum)
- välj startpunkt
- välj sökriktning
- bestäm steglängd genom att lösa det endimensionella problemet
- ny iterationspunkt
- sätt och upprepa tills avbrottskriterium uppfylls
Val av sökriktning
Om problemet är att minimera f, så väljs riktningen så att f minskar i denna riktning, kallas då avtaganderiktning eller descentriktning. Detta villkor på kan skrivas:
- ty då är vinkeln mellan f:s gradient och riktningen större än 90 grader.
Om väljs parallell med den negativa gradienten till f så erhålls brantaste lutningmetoden (BL), eftersom gradienten pekar i den riktning var i funktionen ökar snabbat. Denna metod kan dock ge väldigt många iterationer med korta steg för att sedan börja ta längre steg igen, typiskt sker detta nere i ett "dike" eller uppe på en "ås". En annan metod som är bättre men kräver mer beräkning (dyrare) än BL, är Newtons metod där riktningen väljs som
Den riktning kan fås med följande beräkning
- approximera f i iterationspunkten med en andra ordningens Taylorutveckling:
- sök stationärpunkt, , till
- , som är riktningen från till
Val av steglängd
Generellt kan det vara nästan omöjligt att finna ett globalt optimalt steg (globalt minimum till ) och därför nöjer man sig ofta med att hitta ett lokalt optimalt steg. Ett lokalt optimalt steg kan resultera i en punkt som är sämre än den nuvarande punkten.
Vid begränsat problem
Då man har ett problem som är begränsat så är det inte säkert att alla avtagande riktningar är tillåtna, de kan peka ut i det otillåtna området så att man skulle kunna hamna utanför om man tar ett (för långt) steg i den riktningen. Om det finns ett tillräckligt litet steg sådant att man fortfarande befinner i sig i den tillåtna mängden så är riktningen en tillåten riktning från .
Om det inte finns någon tillåten avtaganderiktning från den punkt där man står, så befinner man sig redan i ett lokalt minimum. Annars skulle man kunna ta ett steg i den tillåtna avtaganderiktningen och erhålla ett lägre bättre värde på funktionen f.
Källor
- Jan Lundgren, Mikael Rönnqvist och Peter Värbrand (2003). Optimeringslära. Studentlitteratur