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

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

Optimeringslära