Optimalisatie, een van de elementaire problemen van de mathematische fysica, economie, techniek en vele andere gebieden van de toegepaste wiskunde, is het probleem van het vinden van de maximale of minimale waarde van een functie, de zogenoemde doelfunctie, alsmede de waarden van de ingangsvariabelen waarbij die optimale waarde optreedt. In elementaire enkel-variabele calculus is dit een zeer eenvoudig probleem dat neerkomt op het vinden van de waarden van x waarvoor df/dx nul is.
Meer-variabele optimalisatieproblemen zijn ingewikkelder omdat we beperkingen kunnen opleggen. We beschouwen beperkingen die kunnen worden uitgedrukt in de vorm g(x,y,z)=c voor een functie g en een constante c. Dit worden gelijkheidsbeperkingen genoemd, en de verzameling van punten die aan deze beperkingen voldoen wordt de haalbare verzameling genoemd, die we aanduiden met S. Als men ons bijvoorbeeld vraagt de maximale waarde van f(x,y) op de eenheidscirkel te vinden, dan is g(x,y)=x²+y² aangezien de eenheidscirkel gedefinieerd is door x²+y²=1.
De standaardtechniek voor het oplossen van dit soort problemen is de methode van Lagrange-vermenigvuldigers. In dit artikel zal ik de methode afleiden en een paar demonstraties geven van het gebruik ervan.
Motivatie en afleiding
Een functie f heeft een lokaal extremum (maximum of minimum) in een punt P als de partiële afgeleide van f nul is voor elk van de onafhankelijke variabelen en als het punt geen zadelpunt is (een situatie waar we hier geen tijd aan hoeven te besteden). We kunnen dit in compacte vorm schrijven als ∇f=0, waarbij ∇ de gradiëntoperator is:
In een beperkte optimalisatie, volgt echter niet uit het feit dat f een lokaal maximum of minimum heeft in een punt van de haalbare verzameling, dat f in dat punt zijn optimale waarde heeft in de haalbare verzameling.
Als voorbeeld nemen we het volgende optimalisatieprobleem:
Door de gradiënt uit te schrijven, kunnen we zien dat f een lokaal minimum heeft als x=0 en y=1:
Daarnaast, f(0,1)=0, maar f(0,-1)=-4 dus hoewel (0,1) een lokaal minimum is van f(x,y), is het niet het minimum van f(x,y) op de eenheidscirkel.
Als ander voorbeeld, laten we f(x,y)=y maximaliseren op de eenheidscirkel. De gradiënt van f(x,y)=y is een constante vector, dus f(x,y) heeft geen lokale maxima of minima, maar op de eenheidscirkel heeft f een maximum waarde van 1, en wel bij (0,1).
De reden voor dit falen is dat de gradiënt de veranderingssnelheid van f(x,y,z) meet ten opzichte van de positie in de driedimensionale ruimte, maar wij willen de veranderingssnelheid van f(x,y,z) meten ten opzichte van de positie in de haalbare verzameling. Voor een driedimensionaal probleem is S ofwel een kromme ofwel een oppervlak, en in het algemeen voor problemen met n variabelen is S een hypersurface van dimensie strikt kleiner dan n.
De meest natuurlijke benadering is om krommen in S te beschouwen. Zij P een punt in S waarvoor f(P) een lokaal optimale waarde in S aanneemt maar ∇f(P) niet noodzakelijk nul is, en zij r(t) de parametrisering van elke kromme in S die door P gaat, dat wil zeggen:
Als S een kromme is, dan is r(t) gewoon een parametrisering van S. Verder, laat r(T)=P, r′(T)≠0, en laat h(t) = f(r(t)) zodat h′(T)=0. Laten we h′(t) uitbreiden met behulp van de kettingregel:
Omdat r(t) altijd in S is, moet de snelheidsvector r′(t) altijd raken aan het oppervlak of de kromme van S, want als r′(t) een component zou hebben die loodrecht op het oppervlak staat, dat wil zeggen van het oppervlak af gericht is, dan zouden er punten zijn waar r(t) S verlaat. Aangezien dit waar is voor elke kromme r(t) die door P gaat, volgt hieruit dat ∇f(P) loodrecht staat op elke raakvector aan het oppervlak in P. Dus als P een punt is waar f een maximum of minimum waarde heeft ten opzichte van de positie in S, dan staat ∇f(P) loodrecht op S.
Het omgekeerde is ook waar: Aangezien r′(T) nooit nul is en altijd evenwijdig met S, dan staat ∇f(P) loodrecht op S, als h′(T)=∇f(P)∙r′(T)=0.
Maar hoe vinden we nu eigenlijk punten waar ∇f loodrecht staat op S? Hier is het antwoord: De verzameling S is de verzameling van alle punten waar g(x,y,z)=c, dat wil zeggen, S is een niveauverzameling van g. Dit betekent dat ∇g loodrecht op S staat voor alle punten in S, dus ∇f en ∇g zijn evenwijdig op punten in S waar f optimale waarden aanneemt. Dit betekent dat f zijn optimale waarden in S aanneemt precies wanneer ∇f=λ∇g voor een constante λ. De constante λ wordt de onbepaalde Lagrange-vermenigvuldigingsfactor genoemd, en hieraan dankt de methode haar naam. Het probleem van de optimalisatie van f kan nu worden opgelost door vier onbekenden x, y, z, en λ te vinden die deze vier vergelijkingen oplossen:
Op een andere manier gezegd, ons doel is nu om de functie f-λg met betrekking tot x, y en z zonder beperkingen te optimaliseren door te zoeken waar ∇(f-λg)=0.
Wat als er meer dan één beperking is? Stel nu dat we f(x,y,x) moeten optimaliseren onder voorwaarde dat g(x,y,z)=c en h(x,y,z)=d. Dit is wat we doen. Om f te optimaliseren met inachtneming van g(x,y,z)=c, optimaliseren we f-λg zonder beperking, dus de eerste beperking wordt opgeheven door f te vervangen door f-λg, en dan blijft over f-λg te optimaliseren met inachtneming van de beperking h(x,y,z)=d. Dit is een probleem met slechts één beperking, dus we voegen gewoon nog een Lagrange-vermenigvuldigingsfactor μ toe, en het probleem is nu om f-λg-μh te optimaliseren zonder beperking.
Laten we nu eens kijken naar enkele voorbeelden.
De maximale oppervlakte van een rechthoek
Voor een gegeven omtrek, wat is de grootst mogelijke oppervlakte van een rechthoek met die omtrek? We kunnen dit formuleren als een Lagrange-multiplicatorprobleem. Als de breedte en hoogte x en y zijn, dan willen we f(x,y)=xy maximaliseren voor g(x,y)=2x+2y=c. Het resulterende stelsel vergelijkingen is:
De eerste twee vergelijkingen vertellen ons meteen dat x=y, dus de maximale oppervlakte ontstaat wanneer de rechthoek een vierkant is. Als we dit in de derde vergelijking invoeren, zien we dat x=y=c/4, dus de maximale oppervlakte van een rechthoek met omtrek c is c²/16.
Een (aangepast) Putnam-probleem
De Putnam-wiskundewedstrijd is een examenwedstrijd die elk jaar in december wordt uitgeschreven voor studenten. Studenten hebben zes uur de tijd om 12 zeer uitdagende problemen op te lossen. Het examen is zo moeilijk dat, op een mogelijke score van 120, de gemiddelde score in de meeste jaren 0 of 1 is. Vandaag bekijken we een aangepaste versie (voor de eenvoud en om copyrightproblemen te vermijden) van probleem A3 uit het examen van 2018:
Er zijn twee problemen. Het eerste is dat de doelfunctie een zeer ongewenste eigenschap heeft: het is een som van cosinussen, en sommen van trigfuncties kunnen lastig zijn om mee om te gaan. Het tweede is dat er geen manier is om de constraint functie netjes en expliciet in de objectieve functie te laten verschijnen, ook al lijkt het op het eerste gezicht dat dit mogelijk zou moeten zijn. Putnam-problemen bevatten vaak “valstrikken” zoals deze, waar je ertoe verleid kan worden tijd te verspillen aan een aanpak die niet tot een oplossing zal leiden als je niet stilstaat bij wat je aan het doen bent. Het is een val die vooral gevaarlijk zou zijn voor een deelnemer met ervaring in wiskundewedstrijden op de middelbare school, waar vaak sterk de nadruk wordt gelegd op trigonimiteiten.
Maar als we een probleem zien met de tekst “maximaliseer f onder g=0”, moeten we onmiddellijk aan Lagrange-multiplicatoren denken. Laten we ons stelsel van vergelijkingen opstellen:
Nu kunnen we onze goniometrische identiteiten gebruiken om de beperking expliciet te maken. Herschrijf het stelsel vergelijkingen met behulp van de dubbele-hoekformule:
Het resultaat is:
Nu annuleer je de sinusfunctie aan elke zijde, en tel de vergelijkingen op:
En dit betekent dat λ=0, dus volgens de Lagrange-multiplicatorvergelijkingen betekent dit dat:
Daarom zijn w, x, y, en z alle gehele vermenigvuldigingen van π/2 zijn. Voor even gehele vermenigvuldigingen van π/2, zeg m=2k voor een geheel getal k:
Maar als m een oneven geheel getal is, dan is cos(mπ/2)=0. Dit betekent dat we drie mogelijkheden hebben om aan de beperkingenvergelijking te voldoen. Ten eerste kunnen we w, x, y, en z allemaal op oneven gehele vermenigvuldigingen van π/2 stellen, bijvoorbeeld k, l, m, en n, dan:
De eerste regel laat zien dat aan de constraint-vergelijking is voldaan, en de tweede regel is het resultaat van het invoeren van deze waarden in de doelfunctie, die ons -4 oplevert.
De tweede optie is dat we twee van de variabelen op oneven gehele veelvouden van π/2 kunnen stellen, bijvoorbeeld k en l, en de andere twee op even gehele getallen, bijvoorbeeld 2m en 2n waarbij m even en n oneven is. Als we dit in de vergelijking van de beperkingen invoeren, krijgen we als resultaat:
Dus aan de constraintvergelijking is voldaan. Hier is het resultaat van het invoegen van deze vergelijking in de doelfunctie:
De laatste optie is dat we alle variabelen kunnen instellen op even gehele vermenigvuldigingen van π/2, bijvoorbeeld 2k, 2l, 2m, en 2n, waarbij k en l even zijn en m en n oneven. Het resultaat van dit in de constraintvergelijking in te vullen is:
Dus aan de beperking is voldaan. Nu stoppen we deze in de doelfunctie om te krijgen:
Dus het antwoord is 4, wat toevallig de globale maximumwaarde van de doelfunctie blijkt te zijn.
Kijk eens naar dit andere artikel dat ik schreef voor een bespreking van een ander Putnam-probleem.
Thomson’s Theorem
Nu gaan we in plaats van een functie te optimaliseren, de methode van Lagrange-vermenigvuldigers gebruiken om een functionaal te optimaliseren: een object dat een functie neemt en een getal teruggeeft. Definitieve integralen zijn een belangrijk voorbeeld. Deze laatste demonstratie zal laten zien hoe de methode van Lagrange vermenigvuldigers kan worden gebruikt om de functie te vinden die de waarde van een bepaalde integraal minimaliseert.
Als demonstratie beschouwen we een fundamenteel feit uit de elektrostatica, de studie van systemen onderworpen aan elektrische krachten in mechanisch evenwicht, zodat geen van de ladingen in beweging is. Wij zullen aantonen dat wanneer een geleider, een lichaam waarin de elektrische lading vrij kan bewegen, in evenwicht is met een systeem van elektrische krachten, er geen elektrisch veld bestaat binnen het lichaam van de geleider. Dit is de stelling van Thomson. Deze stelling wordt meestal gesteld in termen van het fundamentele natuurkundige feit dat de energie van een systeem in stabiel mechanisch evenwicht minimaal is:
Thomson’s Stelling: De elektrostatische energie van een geleidend lichaam met vaste afmetingen en vorm is minimaal wanneer de ladingen zodanig zijn verdeeld dat de potentiaal ϕ constant is in het lichaam zodat E=-∇ϕ=0.
Laat ρ(r) de ladingsdistributiefunctie zijn en ϕₑₓₜ de potentiaal als gevolg van eventuele bronnen buiten het geleidende lichaam. De totale elektrostatische energie kan worden uitgedrukt als een functionele U van ρ(r):
Dit zijn volume-integralen over het lichaam van de geleider. De eerste integraal is een dubbele integraal die eerst over de geprimede coördinaten en dan over de ongeprimede coördinaten wordt uitgevoerd. We willen U minimaliseren als een functie van ρ(r) gegeven dat de totale lading onafhankelijk is van de ladingsverdeling:
Gelukkig maar waar, werkt de methode van Lagrange-vermenigvuldigers voor functionalen met beperkingen. Voer een Lagrange-multiplicator zonder beperkingen in, en voer dan in plaats van een optimalisatie met beperkingen op U, een optimalisatie zonder beperkingen uit op de volgende functie:
Naar analogie van afgeleiden van functies, is het doel hier om de ladingsverdeling ρ zo te vinden dat wanneer ρ wordt gevarieerd met een kleine variatie δρ, de verandering in I, δI, nul is:
Dit is niet helemaal een afgeleide omdat δρ een functie is in plaats van een getal, dus het heeft niet echt zin om van de limiet te spreken als δρ naar nul gaat, maar de basisintuïtie is hetzelfde.
Laten we beginnen met U uit te breiden:
Dit ziet er misschien slecht uit, maar we kunnen dit sterk vereenvoudigen. Ten eerste, omdat δρ zeer klein is, is (δρ)² zo klein dat we het kunnen negeren, dus neem aan dat δρ(r)δρ(r′)=0. Vervolgens zien we door de volgorde van integratie te veranderen dat:
We kunnen ook zien dat U in de expansie voorkomt. Dit geeft ons genoeg om U te vereenvoudigen:
Nu kunnen we δI uitzetten:
Nu kunnen we de integraal over δρ(r) ontbinden:
Om ervoor te zorgen dat dit waar is voor elke keuze van de variatie δρ(r), moet de term tussen haakjes nul zijn, dus:
Maar deze integraal is gewoon de potentiaal op r als gevolg van de ladingen in de geleider, dus de linkerkant van deze vergelijking geeft de totale potentiaal op elk punt r in de geleider, dus ρ(r) is de verdeling die de totale potentiaal binnenin de geleider constant maakt. Hiermee is het bewijs af.
Dit zou ook gelden als de elektrostatische energie van de geleider gemaximaliseerd is, in welk geval de geleider in onstabiel evenwicht is. In de praktijk komt men eigenlijk nooit geleiders in onstabiel evenwicht tegen, omdat de willekeurige thermische beweging van de elektronen in de geleider het systeem snel, in de orde van 10-¹⁴ seconden voor metalen geleiders, uit onstabiel evenwicht en in stabiel evenwicht zal drijven.