Optimering

Optimering handlar om att hitta de punkter där en funktion får sitt lägsta eller högsta värde. I likhet med optimering i en variabel kan sådana punkter förekomma på tre ställen:

Observera att inte alla funktioner har en definitionsmängd med randpunkter. I synnerhet måste definitionsmängden vara en sluten och begränsad mängd.
Sluten och begränsad mängd:

Inte stängd men begränsad mängd:

I många fall av optimering är dock en funktions fullständiga definitionsmängd inte av intresse eftersom den kan innehålla orealistiska värden på variablerna i praktiken.

Därför har optimeringsproblem ofta begränsade definitionsmängder, där vi kan vara säkra på att hitta sådana extrema genom att komma ihåg de tillräckliga villkoren för deras existens:

Ett optimeringsproblem av den här typen är relativt enkelt, och det finns ett trestegsrecept för att lösa det:

Det andra steget här kanske inte verkar okomplicerat till en början, så låt oss undersöka hur detta görs.

Den bästa metoden är ofta att göra en kurvparametrisering av randen, uttrycka som en funktion av parametrarna och hitta eventuella extrema längs denna kurva.

Här kan kurvan parametriseras bitvis. I ett sådant fall, glöm inte att undersöka slutpunkterna för varje separat del!

Hitta maxvärdet för funktionen på triangeln med hörnen i origo, och .

Låt oss börja med att hitta de kritiska punkterna för funktionen.

Av detta drar vi slutsatsen att det inte finns några kritiska punkter inuti definitionsmängden. Låt oss nu kontrollera randen.

Randen består av tre räta linjer, två av dem är längs - och -axlarna där funktionen är noll.

Låt oss nu titta på längs den tredje raden:

Här,

och så:

vilket betyder att f har ett extremvärde vid .

Eftersom det inte fanns några kritiska punkter inuti triangeln eller någon annanstans på randen måste vi bara kontrollera funktionens värde här och i slutpunkterna för den bitvis definierade rand.

Dessa ligger alla på - eller -axeln, där funktionen är noll, och eftersom vet vi att vårt maximum inträffar vid .

Du är chef för en bilfabrik, och du har själv den här intäktsfunktionen, . Intäkterna beror på mängden tillgängligt stål och graden av vakenhet hos dina anställda - våra och . Låt oss också anta att du kan lite häxhantverk, så att du kan skapa ett oändligt utbud av stål. Du har också förtrollat för att göra dina anställda oändligt fokuserade. Din besvärjelse är mer kraftfull än kaffe!

Detta är ett fall av obegränsad optimering. Du vill maximera din intäktsfunktion och du kan justera och som du vill. Men tänk på att om du gör dina anställda för fokuserade på sitt arbete kan polisen misstänka att du drogar dem eller något. Och om du kastas i fängelse kommer dina intäkter att rasa. Du kanske inte vill öka och till oändlighet. Så du måste vara street smart.

I den här typen av problem är det inte säkert att det finns ett optimum. Du vill omvandla problemet till ett begränsat optimeringsproblem och sedan analysera funktionsbeteendet.

Hitta det högsta och lägsta värdet för funktionen:

Lösning:
Om vi tittar på funktionen är alltid positiv. Tecknet för beror bara på , vilket är

Vi börjar med det "enkla" fallet, för att leta efter ett minimum. Om vi utför förändringen av variabler:

vi kan se att närmar sig som . Således har inget minimivärde.

När det gäller maxvärdet kommer vi att söka efter kritiska punkter inuti cirkeln .

med de två lösningarna:

alltså har ett maximum vid:

En oändlig flod som beskrivs av:

har blivit förorenad. Koncentrationen av föroreningen beskrivs av:

Floden antas vara stilla. Var i floden, är koncentrationen av föroreningarna den högsta?

Lösning:
Först, givet en godtycklig , vill vi hitta vid vilken koncentrationen är högst. Definiera därför funktionen:

Differentiera:

Att ställa derivatan till noll:

Om vi tar en titt på teckentabellen:

vi kan se att har ett maximum för . Det betyder att koncentrationen av föroreningar är högst i mitten av älven.

Nu vill vi ta reda på vid vilken koncentrationen är högst med . Det vill säga vi vill maximera

Differentiera:

Ta en titt på teckentabellen:

vi kan se att koncentrationen är högst när . Koncentrationen av föroreningen är alltså högst i punkten .

Hittills har vi strävat efter att optimera funktioner på någon definitionsmängd utan att några andra förhållanden stör oss i vårt arbete.

Ofta, i verkliga livet, har vi inte den friheten; det brukar vara någon som säger: gör det här så bra som möjligt, men du kan bara gå på kanterna av brickorna för att komma dit , eller så måste du sjunga opera medan du gör det , eller så måste du också göra det så billigt som möjligt .

Det är vad vi kallar begränsad optimering , och problem av den här typen finns på både begränsade och obegränsade definitionsmängder.

Detta är den allmänna formen av ett begränsat optimeringsproblem:
hitta max/minimum av , så att .

Antag att är differentierbar och att max/min inte ligger på randen för definitionsmängden för . Sedan visar det sig att lösningen på detta problem ligger där gradientarna för och är parallella.

Hur är och ens relaterade, kan du fråga dig själv. Tja, villkoret är faktiskt en begränsning av definitionsmängden . På bilden nedan är de enda värdena från definitionsmängden som vi får använda när vi söker efter max/min, de på linjen som dras av kurvan i definitionsmängden.

Vi har redan stött på begränsad optimering, i själva verket: när vi försökte hitta max- och minpunkter längs randen för en funktion på ett begränsat område.

Således har vi redan sett några metoder som kan användas för att lösa sådana problem. Det enklaste sättet är att uttrycka kurvan på parameterform, och därefter lösa problemet som ett enda variabelproblem.

Men ofta är det omöjligt att isolera en variabel från de andra. Sedan måste vi ta fram vårt hemliga vapen, Langrange-multiplikatorn.

Vi stannar i två variabler och med ett villkor för tillfället. Metoden sträcker sig till högre dimensioner. Vi kommer också att anta för resten av denna notering att funktionen är differentierbar.

Lagrange-multiplikatorn ser inte ut som mycket för världen: den betecknas med den lilla grekiska bokstaven och vi bryr oss sällan om dess värde. Dessutom försöker vi ofta eliminera det så snabbt som möjligt från ekvationerna där det förekommer.

Men denna lilla kille som vi behandlar så otacksamt är nyckeln till hela metoden för optimering med begränsningar.

När vi skär till punkten nu kommer vi att visa att där max eller min för är, under villkoret , är gradientarna för och parallella. Med andra ord, vid max/min-punkterna har vi:

Här är ett tal, och ekvationen är det matematiska sättet att säga att gradientarna är parallella.

För att motivera påståendet ovan, låt oss titta på ett berg. Med solen som skiner mer på den ena sidan än den andra, har glaciären på toppen smält mer på den sidan. Kanten på glaciären bildar en ellips.

Vi tar en teoretisk promenad runt berget, efter kanten av glaciären. Vi skulle vilja ta reda på vad som är den högsta punkten vi kommer att nå.

Detta motsvarar att maximera , bara utan att lämna kurvan .

Antag att den högsta punkten på banan är en punkt , och att .

Sedan är det möjligt att hitta en parametrisering av en del av nivåkurvan nära . Du kommer att få en bättre förståelse för varför vi behöver det villkoret på gradienten när vi studerar implicita funktioner inom kort. För nu kan du bara acceptera detta som ett faktum.

Funktionen för en variabel har ett lokalt extremum för -värdet för vilket ; vi har precis bytt namn på saker här! Mer specifikt, vid . Att differentiera med hjälp av kedjeregeln på ger:

Men detta måste betyda att vektorn är vinkelrät mot tangenten till kurvan vid . Eftersom gradienten för också är vinkelrät mot tangenten, kan vi dra slutsatsen att gradientarna för och är parallella vid .

Låt oss omsätta detta i handling och hitta den högsta punkten vi kan nå på berget när vi går på stigen.

I exemplet beskriver en cirkel:

Denna cirkel är den elliptiska kurvan som projiceras på -planet i definitionsmängden och en nivåkurva till .

Berget är modellerat som en paraboloid med ekvationen:

Vi sa att gradientarna för och är parallella, vid max- och minpunkterna för på . När vi beräknar och får vi:

Detta ger upphov till ett ekvationssystem:

Eftersom båda ekvationerna är lika med , ta vänster sida och likställ dem. Sedan försvinner och vi får .

Punkterna där på kurvan är och . Den första är den högsta, och den andra den minsta, av på kurvan!

Ett annat exempel följer nedan.

För att belysa processen med att använda Lagrange-multiplikatorn, ta en titt på följande begränsade optimeringsproblem

är vår . Kom sedan ihåg att vi vill leta efter punkter där gradientarna för och är parallella, det vill säga vi vill lösa ekvationen

När vi beräknar gradientarna får vi

Ovanstående vektorekvation består av två skalära ekvationer

När vi löser problem med Lagrange multiplikatorer vill vi eliminera lambda så snart som möjligt.

Här kan detta göras genom att sätta de två skalära ekvationerna lika med varandra:

kan inte vara ett optimum för vårt problem eftersom denna punkt inte uppfyller begränsningen.

Dessutom kan varken eller vara optima eftersom dessa punkter ger och det är tydligt att om . Således kan vi dividera med och för att få

Använd nu detta tillsammans med begränsningarna för att lösa de optimala punkterna

Löser vi för och , vi får det

är de optimala punkterna.