Lineaire Optimalisering WI 2608 De stof voor het tentamen bestaat in grote lijnen uit de Hoofdstukken 1 tot en met 11 uit het boek van Hillier en Lieberman (8e editie) en Hoofdstuk 22 (op de CD-ROM). Een aantal onderwerpen wordt echter niet behandeld en sommige onderwerpen komen wat uitvoeriger aan de orde dan in het boek. Hieronder wordt beschreven wat je moet kennen en kunnen op het tentamen. Daarbij is de nummering uit de achtste editie gebruikt. Voor degenen die dit vak herkansen van een voorafgaand jaar en niet het project hebben gedaan, en voor Tulo studenten waarmee een dergelijke afspraak is gemaakt dat zij naast de beschreven tentamenstof ook hoofdstuk 12 (niet-lineaire programmering) uit het boek moeten kennen en een aangepast tentamen zullen krijgen.
Hoofdstuk 1 Introduction Hoofdstuk 2 Overview Deze hoofdstukken kun je doorlezen als je meer wilt weten over de geschiedenis van Besliskunde (Operations Research, OR) en over het nut en effect van OR in de praktijk. Zeer aan te bevelen voor de algemene ontwikkeling en de karaktervorming. Het vak Operations Research (Operationele Analyse, Besliskunde) vond zijn oorsprong in de Tweede Wereldoorlog, waar de vele militaire logistieke operaties (Operations) vroegen om een gestructureerde, wiskundige behandeling (Research, Analyse). De uitvinding van de computer en de simplexmethode om lineaire optimaliseringsproblemen op te lossen vonden rond deze tijd plaats en maakten dat Lineair Optimaliseren tot op heden tot de meest gebruikte technieken uit de toegepaste wiskunde behoort. Er wordt bijvoorbeeld productie- , voorraad- en routeplanningen mee gedaan, het opstellen van werk-/dienstroosters, industriële mengproblemen mee opgelost en aandelenportefeuilles mee opgesteld.
Hoofdstuk 3 Introduction to Linear Programming 3.1 Prototype Example Beschrijft het standaardvoorbeeld van de Wyndor Glass Co, dat door het boek heen telkens wordt aangehaald. Het is belangrijk dat je weet wat een Lineair Optimaliseringsprobleem (LO of LP probleem) precies is (een lineaire doelfunctie met eindig veel lineaire constraints in eindig veel variabelen). Wat zijn de criteria, wat is een lineaire functie (Zie Lineaire Algebra)? Je moet voor een probleem met twee beslisvariabelen de oplossing grafisch kunnen bepalen. Dit staat uitgelegd in deze paragraaf.
3.2 The Linear Programming Model
Hierin wordt de standaardterminologie voor Lineair Optimaliseren ingevoerd. Je moet het verschil kennen tussen beslisvariabelen (decision variables, de variabelen in het probleem die optimaal gekozen moeten worden) en parameters (constanten in het probleem, die per probleeminstantie anders kunnen worden gekozen), weten wat een doelfunctie (objective function) is, wat begrenzingen (constraints, beperkingen) zijn, wat met een oplossing (solution = een keuze voor de waarden van de beslisvariabelen, hoeft niet optimaal te zijn, zelfs niet toelaatbaar) wordt bedoeld, wat een toelaatbare (feasible) oplossing is (voldoet aan alle beperkingen), een optimale oplossing (geeft een best mogelijke waarde voor de doelfunctie), een corner point feasible (CPF) oplossing (hoekpunt van het toelaatbare gebied), wat het toelaatbare gebied is, wat bedoeld wordt met de standaardvorm van een LP probleem. Verder moet je weten dat een optimale oplossing van een LP probleem niet uniek hoeft te zijn, dat het toelaatbare gebied leeg of onbegrensd kan zijn, en dat het toelaatbare gebied altijd convex is, d.w.z. een oplossing op het lijnstuk tussen twee toelaatbare oplossingen is weer toelaatbaar.
3.3 Assumptions of Linear Programming In deze paragraaf wordt dieper ingegaan op de eisen die aan een Lineair Optimaliseringsprobleem worden gesteld (reële variabelen divisibility+certainty en lineariteit, proportionality+additivity).
3.4 Additional Examples 3.5 Some Case Studies Deze twee paragrafen bevatten meer voorbeelden van lineaire problemen. Je kunt ze eventueel bekijken als je behoefte hebt aan meer voorbeelden. Bekijk bijvoorbeeld: Design of radiation therapy, Regional planning, Personnel scheduling, Distributing goods.
3.6 Formulating and solving linear programming models on a spread sheet 3.7 Formulating very large linear programming models Hier wordt uitgelegd hoe je met de programma’s van de CDROM LP problemen kunt oplossen. Niet belangrijk voor het tentamen.
Hoofdstuk 4 The Simplex Method 4.1 The Essence of the Simplex Method Hier wordt de meetkundige achtergrond van de simplexmethode behandeld aan de hand van het Wyndor voorbeeld. Dit moet je begrijpen en kunnen uitleggen en toepassen. Het nut van de standaardvorm van een LP probleem is dat de oorsprong (alle beslisvariabelen gelijk aan 0) altijd toelaatbaar is, en ook een hoekpunt van het toelaatbare gebied (een CPF oplossing). De simplexmethode kan dus starten in dit hoekpunt en gaat via de ribbe
waarop de doefunctie het sterkst stijgt naar het volgende hoekpunt, totdat langs geen enkele ribbe een verbetering meer mogelijk is. Dan is een optimale oplossing gevonden. Langs ribben waarop de doelfunctie constant blijft kun je eventueel equivalent optimale oplossingen vinden.
4.2 Setting up the Simplex Method In deze paragraaf wordt een LP probleem van de standaardvorm omgeschreven naar een vorm met alleen vergelijkingen. Dit gebeurt om het algebraïsch manipuleren met het probleem te vereenvoudigen, omdat dat met ongelijkheden moeilijker gaat. Dit omschrijven van een LO probleem naar een (augmented) vorm met alleen gelijkheidsconstraints door het invoeren van slack-variabelen moet je kunnen. Verder moet je weten wat de interpretatie van deze slack-variabelen is, wat een basisoplossing is, een toelaatbare basisoplossing (BF, toelaatbaar en n slackvariabelen zijn gelijk aan 0)), wat basis- en niet-basisvariabelen zijn, wanneer twee CPF oplossingen buren zijn en hoe je dat algebraïsch kunt zien (bede hebben n slackvariabelen gelijk aan 0, waarvan er precies één verschillend is).
4.3 The Algebra of the Simplex Method De algebraïsche uitvoering van de simplexmethode wordt hier uitgelegd. Dit moet je kunnen uitvoeren in een voorbeeld, en je moet het verband kennen met de grafische oplossing. Verder moet je weten wat bedoeld wordt met een intredende (entering) en uittredende (leaving) basisvariabele.
4.4 The Simplex Method in Tabular Form De Simplexmethode wordt hier in tableauvorm behandeld. Deze vorm moet je kunnen uitvoeren in een willekeurige situatie en je moet weten waarom het werkt, wat het verband is met de algebraïsche variant, waarom en wat er in de afzonderlijke stappen gebeurt. Wat is een pivotrij of –kolom, wat is de ratiotest, en waarom voer je die uit? Waarom moeten de rechterleden in de ongelijkheden niet-negatief zijn (anders is de startoplossing niet toelaatbaar)?
4.5 Tie breaking in the Simplex Method Hier worden de uitzonderingssituaties behandeld die op kunnen treden tijdens het uitvoeren van de simplexmethode. Dit moet je kennen, want je moet onder alle voorwaarden de simplexmethode correct kunnen uitvoeren. Hoe zie je als er geen optimale oplossing is of juist meerdere, en hoe vind je die, wat doe je bij negatieve getallen in het tableau of bij gelijke waarden, en wat betekenen die? Je moet weten dat de simplexmethode in principe een eindig aantal stappen maat, behalve als er cycling optreedt. Hierbij is de lengte van de stap die wordt gezet in de grootste stijgrichting gelijk aan 0 (ratio test levert dan 0), zodat er geen verbetering van de doelwaarde optreedt. Hierdoor kan het algoritme in een oneindige loop komen zonder dat de optimale doelwaarde wordt bereikt. Dit kan eenvoudig worden opgelost door een richting te kiezen waarin de doelwaarde minder dan optimaal stijgt.
4.6 Adapting to Other Model Forms Hier wordt beschreven wat je moet doen om een LO probleem in de standaardvorm te brengen, als dit nog niet het geval is. Je moet de standaardvorm kennen en elk nietstandaardprobleem in de standaardvorm kunnen omschrijven, eventueel door het invoeren van extra variabelen (surplus, auxilliary en slack) en het aanpassen van de doelfunctie (de “Big M Method”). Je moet de “Big M Method” kunnen uitvoeren. Je moet weten wat het verband is tussen de “Big M” methode en de tweefasenmethode (in fase 1 wordt een toelaatbare oplossing gevonden, in fase 2 wordt binnen het toelaatbare gebied een optimale oplossing gevonden).
4.7 Postoptimal Analysis Het begrip schaduwprijs is hier van belang. Je moet weten dat programma’s die lineaire problemen oplossen vaak meer informatie kunnen geven over het probleem, zonder nieuwe problemen op te lossen. Zo kan er informatie worden gegeven over de cost coefficient ranging: Hoeveel kun je de coëfficiënten in de kostenfunctie veranderen zonder dat de oplossing verandert, of over de right-hand side ranging: Hoeveel kunnen de grenzen in de ongelijkheden veranderd worden, zonder dat er een essentieel andere oplossing komt (een oplossing die door de simplexmethode langs andere ribben wordt gevonden). De schaduwprijzen krijg je door het duale probleem op te lossen. Uit de informatie van het laatste tableau in de simplex methode kunnen ook de schaduwprijzen worden gevonden, dus het duale probleem hoeft niet apart te worden opgelost. De doelwaarden van duaal en primaal probleem zijn gelijk als ze bestaan.
4.8 Computer Implementation Kun je eventueel doorlezen voor het verhogen van het algemene begrip.
4.9 The Interior Point Approach Je moet weten dat inwendige-punt-methoden een recenter alternatief vormen voor de simplexmethode. Een verschil is dat de oplossing niet na een eindig aantal stappen door het lopen langs ribben van het toelaatbare gebied wordt gevonden, zoals bij de simplexmethode, maar dat de oplossing vanuit het inwendige van het toelaatbare gebied steeds beter wordt benaderd. De complexiteit van inwendige-punt-methoden is polynomiaal in de grootte van het probleem, terwijl dat bij de simplexmethode exponentieel kan zijn (veel slechter dus). In de praktijk echter is het moeilijk om slecht werkende voorbeelden voor de simplexmethode te verzinnen en blijkt de performance in het algemeen erg goed te zijn. Voor heel grote problemen doen de inwendigepuntmethoden het vaak beter.
Hoofdstuk 5 The Theory of the Simplex Method
5.1 Foundations of the Simplex Method Hier wordt iets preciezer ingegaan op de achtergronden van de simplexmethode. Je moet de formele definitie van een CPF oplossing kennen (hoekpunt van het toelaatbare gebied, bij n van de constraints wordt gelijkheid aangenomen) en weten hoe je kunt bepalen of twee CPF oplossingen buren zijn (van de n constraints waar gelijkheid wordt aangenomen zijn er n-1 gelijk). Verder moet je weten dat de optimale oplossing (meestal) een CPF oplossing is en waarom, en wat er gebeurt als er meer optimale oplossingen zijn. Je moet een bovenschatting kunnen geven voor het aantal CPF oplossingen. 5.2 en 5.3 zijn niet behandeld
Hoofdstuk 6 Duality theory and Sensitivity Analysis 6.1 The Essence of Duality Theory 6.2 Economic interpretation of duality Om het duale probleem te motiveren bekijken we het volgende voorbeeld. Een fabriek kan van twee verschillende grondstoffen drie soorten producten maken. In de volgende tabel zie je hoeveel (ton) grondstof nodig is voor het maken van één (ton) product, hoeveel van de grondstoffen er beschikbaar is en hoeveel winst er (per ton product) wordt gemaakt. Benodigde grondstof per Beschikbaar product Product Product Product 1 2 3 3 2,5 2 1250 Grondstof 1 4 2 1 1000 Grondstof 2 € 275 € 210 € 175 Verkoopprijs Er zijn drie beslisvariabelen: xj is het aantal ton dat van product j wordt geproduceerd. Dit wordt beschreven in het volgende LO model: Max Z = 275x1 + 210x2 + 175x3 z.d.d. 3x1 + 2,5x2 + 2x3 ≤ 1250 4x1 + 2x2 + x3 ≤ 1000 en x1, x2, x3 ≥ 0 De optimale oplossing van dit probleem is: x1 = 150, x2 = 0, x3 = 400, met Z = 111250. Stel nu dat een opkoper geïnteresseerd is om de voorraden van de fabriek op te kopen. Hij wil daarvoor natuurlijk een zo laag mogelijke prijs bieden, maar voor het bedrijf moet het voordeliger zijn om niet te gaan produceren, anders verkopen ze hun grondstoffen niet. De verkoper wil optimale prijzen yj per ton voor grondstof j (j=1,2) bepalen. Hij wil het totale bedrag dat hij moet betalen: 1250y1 + 1000y2 minimaliseren. De fabriek kan
met 3 ton van grondstof 1 en 4 ton van grondstof 2 één ton product 1 maken, en daar een winst van € 275 mee maken. De handelaar betaalt hiervoor 3y1 + 4y2. Dit bedrag mag niet onder de winst na productie komen te liggen, anders kan er beter geproduceerd worden. Er moet dus gelden: 3y1 + 4y2 ≥ 275. Analoog geldt voor producten 2 en 3 dat 2,5y1 + 2y2 ≥ 210 en 2y1 + y2 ≥ 175. Verder zullen de prijzen natuurlijk niet-negatief zijn. De handelaar moet dus het volgende probleem oplossen: Min Z’ = 1250y1 + 1000y2 z.d.d. 3y1 + 4y2 ≥ 275 2,5y1 + 2y2 ≥ 210 2y1 + y2 ≥ 175 en y1, y2 ≥ 0. Dit probleem wordt wel het duale probleem genoemd, en het originele probleem heet het primale probleem. Het is duidelijk dat de handelaar minstens de winst moet betalen die het bedrijf bij normale productie kan behalen, maar omdat hij zuinig is zal hij ook niet meer bieden dan dat. Het duale probleem heeft dus een optimale doelwaarde die gelijk is aan de optimale waarde van het primale probleem. De optimale oplossing van het duale probleem is in ons geval: y1 = 85, y2 = 5, Z’ = 111250. De waarden y1 en y2 heten wel schaduwprijzen. Deze waarden zijn niet alleen van belang voor de handelaar, maar ook voor het bedrijf. Ze geven namelijk de marginale waarden van de grondstoffen aan, ofwel: welke bijdrage levert een grondstof aan de totale winst? Een schaduwprijs is de prijs die een handelaar per ton voor de grondstof over heeft, maar dat is dus ook de waarde voor het bedrijf, omdat productie dezelfde winst oplevert. In de optimale oplossing van ons primale probleem wordt de eerste constraint aangenomen. Dat betekent dat grondstof 1 een beperking vormt voor verdere winstgroei. De duale waarde y1 geeft aan hoeveel extra winst het bedrijf kan maken met 1 ton extra van grondstof 1. De oplossing van het primale probleem levert x2 = 0. Dit betekent dat het niet gunstig is op product 2 te fabriceren. We kunnen de economische waarde van product 2 uitrekenen: Voor 1 ton product 1 zijn 2,5 ton grondstof 1 en 2 ton grondstof 2 nodig. De economische waarde van product 2 is dus 2,5y1+ 2 y2 = 222,5. De winst is echter € 210 per ton. De winst moet dus minstens met 12,5 euro per ton toenemen wil productie interessant worden. Primaal probleem Max 275x1 + 210x2 + 175x3 z.d.d. 3x1 + 2,5x2 + 2x3 ≤ 1250 4x1 + 2x2 + x3 ≤ 1000 en x1, x2, x3 ≥ 0
Duaal probleem Min 1250y1 + 1000y2 z.d.d. 3y1 + 4y2 ≥ 275 2,5y1 + 2y2 ≥ 210 2y1 + y2 ≥ 175 en y1, y2 ≥ 0.
Je moet bij een (primaal) probleem in de standaardvorm het bijbehorende duale probleem kunnen opschrijven: Als je een lineair optimaliseringsprobleem (het primale probleem) dualiseert krijg je een nieuw optimaliseringsprobleem (het duale probleem): Primaal probleem: Maximaliseer: Z = cTx als functie van x ∈ Rn, zodanig dat: Ax ≤ b en x≥0 Duaal probleem: Minimaliseer: Z’ = bTy als functie van y ∈ Rm, zodanig dat: ATy ≥ c en y≥0 In het duale probleem zitten alle coëfficiënten van het primale probleem weer, maar nu op een andere plek. Als je het duale probleem opnieuw dualiseert krijg je weer het oorspronkelijke probleem. Om dit te laten zien moeten we eerst het duale probleem herschrijven. Dat komt omdat we het duale probleem alleen hebben gedefinieerd voor een primaal probleem in de standaardvorm. Het duale probleem staat niet in die vorm, maar nu wel: Duaal probleem, herschreven: Maximaliseer: Z’’ = (-b)Ty als functie van y ∈ Rm, zodanig dat: (-A)Ty ≤ -c en y≥0 Nu kunnen we het duale probleem opschrijven door de juiste coëfficiënten op de goede plek neer te zetten: Duaal-duale probleem: Minimaliseer: Z’’’ = (-c)Tz als functie van z ∈ Rn, zodanig dat: ((-A)T)Tz ≥-b en z≥0 Omdat ((-A)T)T = -A kunnen we dit weer herschrijven als: Duaal-duale probleem, herschreven:
Maximaliseer: Z’’’’ = cTz als functie van z ∈ Rn, zodanig dat: Az ≤ b en z≥0 Dit is gelijk aan het primale probleem! Verder moet je weten dat de optimale waarde van het duale probleem gelijk is aan de optimale waarde van het primale probleem, en dat een toelaatbare oplossing van het duale probleem een bovengrens geeft voor de optimale waarde in een primaal maximaliseringsprobleem. 6.3 – 6.5 zijn niet behandeld
Hoofdstuk 7 Other Algorithms for Linear Programming Dit hoofdstuk is niet behandeld
Hoofdstuk 8 The Transportation and Assignment Problems 8.1 The Transportation Problem In het boek wordt aan de hand van een voorbeeld gedefinieerd wat een transportprobleem is (Er zijn leveranciers (suppliers), en afnemers. Er wordt precies evenveel geleverd als afgenomen. Voor elke leverancier-afnemer combinatie zijn de transportkosten per eenheid gegeven). Je moet een ingekleed probleem kunnen herkennen en formuleren als een transportprobleem. Een probleem dat niet helemaal voldoet aan de specificaties van een transportprobleem (bijvoorbeeld meer of minder supply dan demand, begrenzingen op supply of demand, of leverancier-afnemercombinaties die niet kunnen voorkomen) moet je door het invoeren van dummyleveranciers of –afnemers en het toepassen van de Big M Method kunnen herformuleren als een correct transportprobleem. Verder moet je weten dat een transportprobleem een geheeltallige oplossing heeft als de geleverde en gevraagd aantallen geheel zijn. Je moet de LO formulering van een transportprobleem kunnen geven en weten dat het handig is als je een algemeen LO probleem eventueel kunt herformuleren als transportprobleem, omdat hiervoor snellere algoritmen zijn, en omdat hiervoor de geheeltallige eigenschap geldt (Als de geleverde en afgenomen hoeveelheden allemaal geheeltallig zijn en het probleem wordt opgelost met de simplexmethode, dat is de gevonden optimale oplossing ook geheeltallig. Dit betekent dat in dit geval een relatief moeilijk discreet probleem opgelost kan worden met een snelle continue methode). 8.2 A Streamlined Simplex Method for the Transportation Problem Niet behandeld.
8.3 The Assignment Problem Een toewijzingsprobleem (assignment problem) is een speciaal geval van een transportprobleem (evenveel afnemers als leveranciers. Elke leverancier levert 1 eenheid, elke afnemer heeft 1 eenheid nodig. Een toewijzing is een koppeling van elke leverancier een precies een afnemer). Zo’n probleem moet je kunnen herkennen en verder moet je er dezelfde dingen mee kunnen als met een transportprobleem. Je moet weten dat een toewijzingsprobleem dat als LO probleem wordt geformuleerd en opgelost met de simplexmethode automatisch een binaire oplossing heeft. 8.4 A special algorithm for the assignment problem Hier wordt de zgn. Hongaarse methode uitgelegd waarmee je een toewijzingsprobleem (assignment problem) kunt oplossen.
Hoofdstuk 9 Network Analysis 9.1 Prototype Example Het Seervada Park probleem wordt hier beschreven en dient als illustratie van de diverse soorten transportproblemen. 9.2 The Terminology of Networks Je moet de standaardterminologie van grafen (netwerken) kennen: knoop (node), zijde of kant of tak (edge, arc, link), gerichte/ongerichte zijde (directed arc/ undirected arc of link), gerichte/ ongerichte graaf, pad, cycle, samenhang (connectedness), boom (tree), binaire boom, opspannende boom (spanning tree), capaciteit van een zijde. Het volgende is achtergrondinformatie, die je voor het tentamen net hoeft te kennen. Wanneer is een graaf te tekenen in het platte vlak, zonder dat de zijden elkaar doorsnijden? Hiervoor is een stelling van Kuratowki, die zegt dat een graaf vlak is, precies dan als deze graaf geen deelgraaf heeft die hetzelfde is als K3,3 of K5. Hierbij is K5 de volledige graaf op vijf punten die je krijgt door tussen vijf punten elke mogelijke verbinding te trekken. K3,3 krijg je door twee verzamelingen van elk drie punten te nemen en elk punt in de ene met elk punt in de andere te verbinden (Dit is het bekende gas-water-licht probleem: Drie huizen moeten elk van gas, water en licht worden voorzien door een directe verbinding met elk van de fabrieken. Dit is alleen mogelijk als leidingen mogen kruisen). Niet elke graaf is “vlak”, d.w.z. te tekenen het vlak zonder doorsnijdingen. Wel kun je elke graaf in een driedimensionale ruimte tekenen , zelfs met rechte lijntjes. Dit is als volgt met wat lineaire algebra te bewijzen: We nummeren de knopen en beelden knoop nummer j af op het punt (j, j2, j3). We hoeven nu alleen maar aan te tonen dat het lijnstukje van knoop j naar knoop k nooit het lijnstukje van knoop l naar knoop m kan snijden, zolang j, k, l en m maar allemaal verschillend zijn. Als de twee lijnstukjes elkaar wel zouden snijden, dan zouden de vier punten (j, j2, j3), (k, k2, k3). (l, l2, l3) en (m, m2, m3) in één vlak moeten liggen. dat zou betekenen dat drie verschilvectoren van deze punten lineair afhankelijk zijn, zodat de volgende determinant nul is:
k− j k 2 − j2 k 3 − j3
l− j l − j2 l3 − j3 2
m− j m2 − j 2 m 3 − j 3 =0.
We kunnen eerst in elke rij een gemeenschappelijke factor buiten haakjes halen en die vervolgens buiten de determinant brengen:
k− j k2 − j2 k 3 − j3
l− j l − j2 l3 − j3
m− j m2 − j 2 m3 − j 3 = (k − j ) (l − j ) (k − j )(k + j ) (l − j )(l + j ) (k − j ) k 2 + kj + j 2 (l − j ) l 2 + lj + j 2 2
(
)
(
1 (k − j )(l − j )(m − j ) k + j k 2 + kj + j 2 =
)
(m − j ) (m − j )(m + j ) (m − j )(m 2 + mj + j 2 )
1 l+ j l 2 + lj + j 2
1 m+ j m 2 + mj + j 2 = 0
Door met de eerste kolom te vegen krijgen we:
1 k+ j
1 l+ j
k 2 + kj + j 2
l 2 + lj + j 2
1 m+ j
m 2 + mj + j 2 = 1 0 0 k+ j l−k m−k l−k 2 2 k + kj + j (l − k )(l + k + j ) (m − k )(m + k + j ) = (l − k )(l + k + j ) 1 1 (l − k )(m − k ) l + k + j m + k + j = (l − k )(m − k )(m − l ) =
m−k (m − k )(m + k + j )
Er geldt dus dat
k− j k 2 − j2 k 3 − j3
l− j l − j2 l3 − j3 2
m− j m2 − j 2 m 3 − j 3 = (l − k )(m − k )(m − l )(k − j )(l − j )(m − j ) =0
We zien dat deze determinant alleen maar gelijk aan nul kan zijn als twee van de indices uit j, k, l, m aan elkaar gelijk zijn. In zo’n geval vallen twee knopen samen, maar dat was niet zo, daar waren we vanuit gegaan. We hebben hiermee bewezen dat twee lijnstukjes tussen vier verschillende knopen elkaar nooit kunnen snijden.
9.3 The Shortest-Path Problem
Het algoritme dat in het boek wordt gebruikt om een kortste pad te bepalen staat bekend als het algoritme van Dijkstra, hoewel het in het boek niet expliciet zo wordt genoemd.
Edsger Dijkstra is een van de grondleggers van de informatica in Nederland en is jarenlang hoogleraar geweest in Eindhoven en in de Verenigde Staten. Het kortste pad algoritme moet je kunnen uitvoeren. 9.4 The Minimum Spanning Tree Problem
Je moet weten wat een minimale opspannende boom is (elke knoop is met elke ander verbonden, de totale kosten van alle zijden is minimaal), en dit eventueel in een probleemstelling kunnen herkennen. Verder moet je het algoritme uit het boek kunnen uitvoeren. Dit is een zogenaamd “greedy” algoritme van Prym. Je bouwt een boom op door bij een willekeurige knoop te beginnen en je voegt telkens de goedkoopste zijde aan de boom toe, die je een nieuwe knoop oplevert. 9.5 The Maximum Flow Problem
Je moet weten wat een Max-Flow probleem is en het algoritme uit het boek om zo’n probleem op te lossen kunnen uitvoeren. Je moet met behulp van een snede een bovengrens voor de flow (stroom) kunnen aangeven en de formulering van de max-flow min-cut stelling kennen (met de kleinste snede correspondeert een oplossing met maximale stroning). Let erop dat je bij het bepalen van de maximale flow door een snede alleen de capaciteiten in de juiste richting meetellen. 9.6 The Minimum Cost Flow Problem
Hier wordt uitgelegd wat een minumum cost flow probleem is en wat de LP formulering hiervan is. Je moet weten wat bron- (supply), vraag- (demand) en doorvoerknopen (transshipment nodes) zijn. Belangrijk is om de integer solutions property te kennen (als alle in- en uitvoerwaarden en alle beperkingen geheel zijn, dan vindt de simplexmethode een gehele optimale oplossing) en te weten dat transportproblemen, toewijzingsproblemen, kortste padproblemen en max-flowproblemen speciale gevallen zijn van minumum cost flow probleem en te weten waarom.
Hoofdstuk 9.8 + 22 (op CD-ROM) Project Management with PERT/CPM Je moet activiteiten met een volgorde in een gerichte graaf kunnen rangschikken (activity on node of activity on arc), het kritieke pad kunnen bepalen, met een forward en backward sweep van elke activiteit de Earliest Start en Latest Finish time kunnen bepalen (10.3), en weten hoe je een project kunt crashen (10.5) met een LP model. Je moet ook weten hoe je met LP een kritiek pad kunt bepalen (sheets).
Hoofdstuk 10 Dynamic Programming Bij dynamisch programmeren moet je je realiseren dat het meer een algemene techniek is dan een oplosmethode speciaal voor lineaire problemen. Het is een techniek die geschikt is voor problemen die van nature een bepaalde gelaagde structuur hebben. Een standaardvoorbeeld is het kortste pad probleem. Daar heb je een natuurlijke opdeling in
fasen die bestaan uit punten die met resp. 1, 2, 3, etc. stappen vanuit het startpunt zijn te bereiken. Verder is de lengte van een kortste pad eenvoudig uit te rekenen uit de kortste verbinding tot een punt uit de vorige fase en de afstand van dit punt naar het punt waar je nu zit – in dit geval omdat het gewoon de som van die twee afstanden is; deze afstand hangt niet op een ingewikkeldere manier af van de precieze vorm van de “beste oplossing tot dusver”. In het algemeen is dat voor lineaire problemen waar, omdat je gewoon de som van twee termen krijgt, maar ook in het geval van een product (zie het voorbeeld met kansen in het boek), een niet-lineair probleem dus, kan het werken. 10.1 A Prototype Example
Het idee van dynamisch programmeren wordt uitgelegd aan de hand van het postkoetsprobleem. Het is belangrijk dat je weet dat dynamisch programmeren handig kan zijn bij problemen waarin je een aantal lagen kunt onderscheiden en waarbij de doelfunctie recursief gedefinieerd is in termen van de lagen. 10.2 Characteristics of Dynamic Programming Problems
Hier wordt uitgelegd welk soort problemen zich lenen voor de dynamische programmeringsaanpak. 10.3 Deterministic Dynamic Programming
Een aantal andere voorbeelden waarin dynamisch programmeren wordt toegepast. Je moet deze techniek kunnen toepassen op een voorbeeld. Voorbeelden 4 en 5 zijn op het college niet behandeld.
Hoofdstuk 11 Integer Programming 11.1 Prototype Example
Een voorbeeld van een BIP probleem wordt hier behandeld. Je moet het verschil weten tussen LP (lineair programmeren, continue variabelen, lineaire doelfunctie en constraints), BIP (Binary Integer Programming, binaire variabelen, lineaire doelfunctie en constraints), IP (Integer Programming, geheeltallige variabelen, lineaire doelfunctie (coëfficiënten hoeven niet geheeltallig te zijn) en constraints), en MIP problemen (Mixed Integer Programming, variabelen mogen zowel reëel, binair als geheeltallig zijn, doelfunctie en constraint zijn lineair) . Je moet afhankelijke beslissingen in een binair probleem met behulp van lineaire ongelijkheden kunnen formuleren. Vb: x1 óf x2 is waar: x1 + x2 = 1. Vb: x1 kan alleen als x2 geldt: x1 ≤ x2. 11.2 Some BIP Applications
Voorbeelden voor het kiezen van beslisvariabelen. Kun je doorlezen.
11.3 Innovative Uses of Binary Variables in Model Formulation
Hier wordt uitgelegd hoe je een aantal vaak voorkomende constructies kunt formuleren met behulp van binaire variabelen. Dit moet je kunnen uitvoeren: k van de n voorwaarden, n mogelijke waarden, vaste kosten, en een integer probleem kunnen omzetten in een binair probleem. 11.4 Some Formulation Examples
Een aantal voorbeelden die aangeven hoe je problemen als BIP, IP en MIP kunt formuleren. In de voorbeelden worden trucs gebruikt die bij het modelleren en in de opgaven van pas komen. Je hoeft ze niet zelf te kunnen verzinnen, maar je moet ze wel kunnen verifiëren. 11.5 Some Perspectives on Solving Integer Programming Problems
Uitleg waarom IP problemen moeilijk kunnen zijn. Uitleg van LP relaxatie. De problemen die op kunnen treden als je de oplossing van het gerelaxeerde probleem afrondt op gehele waarden. Je moet weten dat afronden van gerelaxeerde oplossingen vaak goede resultaten levert (zeker als de variabelen zeer veel verschillende waarden kunnen aannemen, en het probleem daardoor op het continue probleem lijkt), maar dat het soms grandioos mis kan gaan. Bij het afronden moet je erop letten dat afgeronde oplossingen ontoelaatbaar kunnen zijn. 11.6 The Branch-and-Bound Technique and Its Application to Binary Integer Programming
Uitleg van de Branch-and-Bound methode voor een BIP probleem aan de hand van een voorbeeld. Deze methode moet je kunnen uitvoeren. (Het stukje over Lagrangian relaxation Other Options …hoef je niet te kennen). 11.7 A Branch-and-Bound Algorithm for Mixed Integer Programming
Uitleg van de Branch-and-Bound methode voor een MIP probleem aan de hand van een voorbeeld. Dit moet je kunnen uitvoeren. 11.8 Other Developments in Solving BIP Problems
Je moet weten hoe je uit een constraint in een BIP probleem de waarde van een variabele kunt afleiden, als deze door de constraints vastligt (Fixing variables). Er wordt een algoritme uitgelegd waarmee je een constraint in een BIP probleem kunt aanscherpen. Dit algoritme moet je kunnen uitvoeren. Verder wordt uitgelegd hoe je met een minimum cover cutting plane kunt vinden. Dit hoef je niet uit je hoofd te kennen, maar wel kunnen uitvoeren als het gegeven wordt.
Appendix 2: Convexity Je moet weten wat een convexe verzameling is en de convexiteit van eenvoudige verzamelingen kunnen bewijzen, met behulp van de definitie of door stellingen van hieronder te gebruiken.. Definitie: Voor twee vectoren x en y en twee reële getallen λ en μ heet λx + μy een lineaire combinatie van x en y. De lineaire combinaties vormen de lineaire ruimte die wordt opgespannen door deze twee vectoren. Meestal is dat een (tweedimensionaal) vlak, maar als de twee vectoren lineair afhankelijk zijn kan het ook een lijn zijn (ééndimensionaal), of zelfs een punt (nuldimensionaal) als je begint met twee nulvectoren. Als λ en μ voldoen aan λ + μ = 1, dan krijgen we alle punten op de lijn door de eindpunten van x en y, want λx + μy = λx + (1-λ)y = y +λ(x – y) is de vectorvoorstelling van de lijn door y met als richting x – y. Als bovendien geldt dat λ, μ ≥ 0, dan krijgen we het lijnstuk tussen de eindpunten van x en y. Definitie: λx + μy met λ + μ = 1 en λ, μ ≥ 0 heet een convexe combinatie van x en y. Alle convexe combinaties van x en y vormen dus het lijnstukje tussen x en y. Net als een lineaire combinatie kun je ook in het algemeen een convexe combinatie van meer vectoren als n
n
∑λj xj
∑λ
j
=1
λ ≥0
j voor alle j. Voor twee vectoren is het een volgt opschrijven: j =1 met j =1 en lijnsegment, voor drie vectoren is het een driehoekig gebied, voor vier vectoren een piramide, etc. De convexe combinaties van n+1 vectoren die niet toevallig in een n-1 dimensionale deelruimte liggen vormen een simplex.
Definitie: Een verzameling K, deelverzameling van een lineaire ruimte, bijvoorbeeld Rn, heet een convexe verzameling als voor alle x, y ∈ K en alle λ ∈ [0,1] geldt dat λx + (1-λ)y ∈ K. In woorden: K is convex, precies dan als de verbindingslijn tussen twee punten uit K weer helemaal in K zit, of: als elke convexe combinatie van punten uit K weer in K ligt. Een convexe verzameling kan dus niet uit losse stukken bestaan, geen gat hebben (fietsband, donut), niet naar binnen gestulpt zijn (banaan). Triviale voorbeelden van een convexe verzameling zijn: de lege verzameling ∅ (hier valt niets te controleren), de hele ruimte Rn, een singletonverzameling {x}. Minder triviaal zijn: Stelling: Als a ∈ Rn en b ∈ R, dan is de halfruimte Ha,b = {x∈Rn | aTx ≤ b} convex. Bewijs: Kies x, y ∈ Ha,b en λ ∈ R, dan geldt: aTx ≤ b en aTy ≤ b. We moeten aantonen dat (λx + (1-λ)y ∈ Ha,b. De vraag is dus of aT(λx + (1-λ)y) ≤ b. In dat geval ligt namelijk de convexe combinatie van x en y weer in K. Er geldt: aT(λx + (1-λ)y) = aT(λx) + aT( (1-λ)y) = λaTx + (1-λ)aTy ≤ λb + (1-λ)b = b. Deze ongelijkheid geldt omdat zowel λ als 1-λ niet-negatief zijn. Hiermee hebben we het resultaat bewezen. Ha,b is de verzameling van alle punten die aan de lineaire ongelijkheid aTx ≤ b voldoen. Die punten vormen een halfruimte. De vector a staat loodrecht op het scheidingshypervlak aTx = b Stelling: De n-dimensionale bal Br = {x∈Rn | |x| ≤ r} is convex. B
Bewijs: Kies x, y ∈ Br en λ ∈ R, dan geldt: |x| ≤ r en |y| ≤ r. Nu geldt voor de convexe combinatie: |λx+(1λ)y| ≤ |λx|+|(1-λ)y| = λ|x|+(1-λ)|y| ≤ λr + (1-λ)r = r. In de eerste stap is gebruik gemaakt van de B
driehoeksongelijkheid: |a+b| ≤ |a|+|b| (maak een plaatje), de tweede ongelijkheid is waar omdat 0 ≤ r ≤ 1. Hiermee is het bewijs klaar. Verder hebben we nog het volgende handige resultaat: Stelling: Als A en B convex zijn, dan is ook A ∩ B convex. Bewijs: Kies x, y ∈ A ∩ B en λ ∈ R. Er geldt nu voor de convexe combinatie: λx + (1-λ)y ∈ A en λx + (1λ)y ∈ B, want A en B zijn elk convex, dus ook: λx + (1-λ)y ∈ A∩B, dus A∩B is convex. Uit het bovenstaande volgt dat een toelaatpaar gebied in een lineair optimaliseringsprobleem altijd convex is, want het is de doorsnede van een aantal halfruimtes, die elk door een lineaire ongelijkheid worden gedefinieerd. We noemen nog het volgende resultaat dat we niet zullen bewijzen: Stelling: Elke convexe verzameling in Rn is de doorsnede van (mogelijk oneindig veel) halfruimtes. Zo is bijvoorbeeld een bal de doorsnede van alle halfruimtes die de bal bevatten (of die eraan raken). Hiermee kun je een ander bewijs van de convexiteit van de bal leveren. Definitie: Een functie f: Rn → R heet een convexe functie als voor alle x, y ∈ Rn en λ ∈ R geldt: f(λx + (1λ)y) ≤ λf(x) + (1-λ)f(y). In woorden: Het lijnstuk tussen twee punten op de grafiek ligt niet onder de grafiek. Een convexe functie heeft dus een grafiek die “hol naar boven” is. Voorbeelden: Elke lineaire functie is convex, de functie f: R→R: x→x2 is convex, de functie die aan een vector zijn lengte toevoegt (vanwege de driehoeksongelijkheid). Definitie: Laat K ⊆ Rn. Een punt x ∈ K heet een inwendig punt van K als er een ε > 0 is, zodanig dat voor alle y ∈ Rn geldt: |x-y| < ε ⇒ y ∈ K. In woorden: Een punt is een inwendig punt als er een (klein) bolletje om dat punt bestaat dat nog helemaal binnen de verzameling K ligt. Het punt ligt dus niet “op de rand”, want bij zo’n punt steekt elk bolletje een stukje buiten de verzameling. Stelling: Laat x ∈ K ⊆ Rn een inwendig punt van K zijn, f: Rn → Rn een lineaire functie, die niet constant is (niet identiek gelijk aan nul dus), dan geldt: max {f(y) | y ∈ K} ≠ f(x). In woorden: een niet-constante lineaire functie neem zijn maximum nooit in een inwendig punt aan, maar altijd op de rand. Bewijs: Stel dat f maximaal is in het inwendige punt x. f kunnen we schrijven als f(z) = aTz, voor een bepaalde niet-nulvector a ≠ 0 (want f is niet-constant). Omdat x een inwendig punt is, is er een bolletje met straal r dat helemaal in K ligt. Dan ligt ook het punt x + λ a in K (a is de richting waarin f stijgt), waarbij λ=r/(2|a|). In dit punt geldt (f is lineair): f(x + λ a) = f(x) + λ f(a) = f(x) + λ aTa = f(x) + λ |a|2. Deze waarde is groter dan f(x), maar dat kan niet, want f was maximaal in x. Klaar! Stelling (Ongelijkheid van Schwarz): xTy ≤ |x||y|. Bewijs: Voor elke λ ∈ R geldt: 0 ≤ |x+λy|2 = (x+λy)T(x+λy) = xTx +λxTy+ λyTx+λ2yTy = | x|2 + 2λxTy + λ2|y|2. Deze kwadratische functie van λ is alleen dan altijd niet-negatief als de discriminant niet-positief is: 4( xTy)2 – 4 | x|2 |y|2 ≤ 0. hier staat de ongelijkheid van Schwarz. Uit de ongelijkheid van Schwarz volgt de driehoeksongelijkheid:
Gevolg (Driehoeksongelijkheid): |x + y| ≤ | x| + |y|. Bewijs: |x + y|2 = | x|2 + 2xTy + |y|2 ≤ | x|2 + 2| x||y| + |y|2 = (| x| + |y|)2. De driehoeksongelijkheid zegt eigenlijk dat de lengte van de zijde van een driehoek nooit groter kan zijn de lengtes van de andere twee zijden bij elkaar.
Zie verder de informatie in de sheets.
De informatie hieronder is alleen relevant voor herkansers en TULO studenten
Hoofdstuk 12 Nonlinear Programming 12.1 Sample applications 12.2 Graphical Illustration of Nonlinear Programming Problems
Voorbeelden van niet-lineaire optimaliseringsproblemen. Doorlezen. 12.3 Types of Nonlinear Programming Problems
Handig om door te lezen, maar hoef je niet te kennen. 12.4 One-Variable Unconstraint Optimization
Uitleg van een bisectiemethode waarmee je het optimum van een ééndimensionale functie kunt benaderen als je de afgeleide kent. 12.5 Multivariate Unconstraint Optimization
Uitleg van de gradientmethode (steepest descent). 12.6 Karush-Kuhn-Tucker Condition for Constrained Optimization
De KKT voorwaarden zijn noodzakelijke en voldoende voorwaarden voor een optimale oplossing voor een niet-lineair optimaliseringsprobleem met nevenvoorwaarden. Met deze voorwaarden kun je controleren of een oplossing optimaal is, en in principe kun je er zelfs optimale oplossingen mee vinden, hoewel dat in de praktijk er moeilijk kan blijken te zijn. 12.7/ 12.8
Niet behandeld
12.9 Convex Programming
Behandelt het “Sequential Linear Approximation Algorithm” van Frank-Wolfe voor het benaderend oplossen van een niet-lineair probleem met lineaire constraints. De nietlineair functie wordt met een Taylor-ontwikkeling lineair benaderd. Het resulterende LP probleem wordt met de simplex methode opgelost. Tussen de startoplossing en de LP oplossing wordt met een ééndimensionale line search de beste oplossing gevonden en dit punt wordt gebruikt als het startpunt van een nieuwe iteratie. 12.10/12.11
Niet behandeld
Aanvulling niet-lineaire optimalisering Convexe functies op R Een functie f : R → R heet convex, als voor alle x, y ∈ R en elke λ ∈ [0,1] geldt dat f(λx + (1-λ)y) ≤ λf(x) + (1-λ)f(y). Voor een functie op R betekent dit dat als je twee willekeurige punten op de grafiek van de functie met een recht lijnstukje verbindt, de grafiek daartussen nooit boven dit lijnstukje komt. De grafiek van een convexe functie is “hol” naar boven, “bol” naar beneden, bijvoorbeeld f(x) = x2.
Convexiteit kun je ook definiëren voor functies die op een deelverzameling van R bestaan, hoewel het dan handig is als die deelverzameling zelf ook convex is en niet uit losse stukken bestaat.
Een functie f : R → R heet strikt convex, als voor alle x, y ∈ R en elke λ ∈ ]0,1[ geldt dat f(λx + (1-λ)y) < λf(x) + (1-λ)f(y). Een functie f heet (strikt) concaaf als –f (strikt) convex is. De grafiek van een concave functie is “bol” naar boven, “hol” naar beneden. Een lineair functie is bijvoorbeeld zowel convex als concaaf, maar niet strikt convex of strikt concaaf. Voorbeeld: We zullen bewijzen dat de functie f(x) = 1/x convex is als x > 0. Hiervoor moeten we laten zien dat voor iedere x, y > 0 en λ ∈ [0,1] geldt:
1 λ 1 − λ λy + (1 − λ ) x ≤ + = . λx + (1 − λ ) y x y xy Omdat x, y en λx + (1-λ)y allemaal positief zijn kunnen we de ongelijkheid hiermee vermenigvuldigen en is dit equivalent met aantonen dat xy ≤ λ2xy + λ(1-λ)(x2 + y2) + (1-λ)2xy ofwel dat: -λ2(x2 + y2 - 2xy) + λ(x2 + y2 - 2xy) ≥ 0. Maar dit is hetzelfde als
λ(1-λ)(x -y)2 ≥ 0 en dit is duidelijk waar. Als je een net bewijs wilt moet je dit argument achterstevoren opschrijven! De grafiek van een functie is de verzameling {(x,y) ∈ R2 | y = f(x)} De epigrafiek van een functie is de verzameling {(x,y) ∈ R2 | y ≥ f(x)}. Dat zijn alle punten die op of boven de grafiek liggen. Het is eenvoudig in te zien dat een functie convex is precies dan als zijn epigrafiek een convexe verzameling in R2 is. Als f convex is, dan is ook een veelvoud af convex, voor elk getal a ≥ 0 (en af is concaaf voor elk getal a ≥ 0). Als f en g convex zijn, dan ook f + g (maar f – g meestal niet). Een constante functie is convex, dus in het bijzonder blijft een functie convex als je er een constante bij optelt. Als f en h convex zijn en h bovendien monotoon niet-dalend, dan is h o f weer convex. Convexiteit is een behoorlijke beperking voor een functie. Zo kan een convexe functie eigenlijk geen sprongen maken en is zo goed als continu. Alleen op de rand van het domein kunnen er sprongen optreden: Stelling: Als f: C → R convex is, dan is f continu op het inwendige van C.
Bewijs: Kies x in het inwendige van C. Dit betekent dat het interval [x - ε, x + ε] helemaal in C bevat is voor een zekere ε >0. Voor het gemak nemen we nu even aan dat x = 0 en dat f(0) = 0,. Dat is voor het gemak van notatie, maar is geen werkelijke restrictie (dat zie je door wat te schuiven). We bekijken nu de functies f1 (x ) =
f (ε )
ε
x
en
f 2 (x ) =
f (− ε ) x −ε
De functie f ligt tussen deze twee functies en dat zien we als volgt. Als x ∈ [0, ε], dan is f2(x) ≤ f(x) ≤ f1(x).
Dit volgt uit de convexiteitsongelijkheid f(λs + (1-λ)t) ≤ λf(s) + (1-λ)f(t) als je kiest: s = -ε, t = x, λ = x/(x+ε), voor de eerste ongelijkheid en s = 0, t = ε, 1 - λ = x/ε voor de tweede. Op dezelfde manier geldt dat f1(x) ≤ f(x) ≤ f2(x) als x ∈ [-ε,0]. De grafiek van f ligt dus eigenlijk ingeklemd tussen de twee rechte lijnen die de grafieken van de functies f1 en f2 vormen. Omdat f1 en f2 continu zijn met f1(0) = f2(0) = 0 geldt dat f(x) → f1(0) = f2(0) = 0 = f(0) als x → 0, dus f is continu in 0, waarmee we de stelling hebben bewezen.
Merk op dat convexiteit niet de continuïteit van een functie overal impliceert, omdat het op de rand van een gebied mis kan gaan. Zo is de functie f waarvoor geldt f(0) = f(1) = 1 en f(x) = 0 als 0 < x < 1 duidelijk niet continu (in 0 en 1), maar wel convex. De convexiteit van een functie aantonen gaat soms goed met behulp van de definitie, zoals in het bovenstaande voorbeeld. Vaak lukt dit echter niet op een eenvoudige manier. Probeer het maar eens voor f(x) = ex. In zo’n geval kan het handiger zijn om een ander criterium toe te passen. Als een differentieerbare functie convex is dan kan de afgeleide niet dalend zijn. Dat betekent dat de tweede afgeleide nooit negatief is. Soms kun je van een functie eenvoudig laten zien dat de tweede afgeleide positief is. Je hebt dan op een simpele manier de convexiteit van de functie aangetoond. We zullen nu bewijzen dat de convexiteit van een tweemaal differentieerbare functie inderdaad helemaal wordt bepaald door zijn tweede afgeleide.
Stelling: f ∈ C2(R,R) is convex dan en slechts dan als f’’(x) ≥ 0 voor alle x. Bewijs: “⇒” We moeten aantonen dat de tweede afgeleide van een convexe functie overal niet-negatief is. Omdat f convex is, geldt er (kies x = t - h, y = t + h, λ = ½) dat : ½ f(x+h) + ½ f(x-h) ≥ f( ½ (x+h) + ½ (x-h)) = f(x). Voor de tweede afgeleide gebruiken we nu het volgende differentiequotiënt, en zien met de vorige ongelijkheid direct dat de tweede afgeleide niet-negatief is: lim f ( x + h) − 2 f ( x ) + f ( x − h) ≥ 0. h↓0 h2 (dit differentiequotiënt krijg je door f’’ uit te drukken als limiet van een differentiequotiënt in f’, en vervolgens f’ weer als differentiequotiënt in f te schrijven. Een andere manier om het te zien is door van de teller een Taylorreeksontwikkeling rond x te maken) f ' ' ( x) =
“⇐” Nu moeten we laten zien dat een functie waarvan de tweede afgeleide overal niet-negatief is automatisch convex is. Het ligt voor de hand om de tweede afgeleide te integreren. We krijgen dan: y
f ' ( y ) − f ' ( x) = ∫ f ' ' (t )dt. x
Als y ≥ x dan is de integraal niet-negatief omdat de integrand het is, dus f’(y) ≥ f’(x). We hebben hiermee aangetoond dat de afgeleide van f niet-dalend is. We halen nu dezelfde truc uit en integreren f’: y
y
x
x
Als y ≥ x dan is f ( y ) − f ( x ) = ∫ f ' (t )dt ≥ ∫ f ' ( x)dt = f ' ( x)( y − x) . We hebben toegepast dat f’ niet-dalend is, dus dat f’(t) ≥ f’(x) als t ≥ x. y
x
y
x
y
x
Als y ≤ x dan is f ( y ) − f ( x) = ∫ f ' (t )dt = − ∫ f ' (t )dt ≥ ∫ − f ' ( x)dt = f ' ( x)( y − x) . Gevolg is dat f(y) – f(x) ≥ f’(x)(x – y). Dit betekent dat de grafiek van de functie f nooit onder de raaklijn in het punt x ligt. Hiermee gaan we de convexiteit bewijzen. Noem tλ = λx + (1-λ)y, dan volgt uit de bovenstaande ongelijkheid: f(y) – f(tλ) ≥ f’(tλ)(y - tλ), f(x) – f(tλ) ≥ f’(tλ)(x - tλ). We vermenigvuldigen de eerste ongelijkheid met 1 - λ, de tweede met λ en tellen ze op (dat mag omdat deze getallen niet-negatief zijn): λf(x) + (1-λ)f(y) – f(tλ) ≥ f’(tλ)(λx + (1-λ)y - tλ) = 0, want tλ = λx + (1-λ)y. Hier staat nu dat f(λx + (1-λ)y) = f(tλ) ≤ λf(x) + (1-λ)f(y), dus dat f convex is.
Daarmee is het bewijs klaar.
Voorbeelden: Door tweemaal te differentiëren kun je het volgende eenvoudig laten zien: f(x) = ax2 + bx + c is convex als a ≥ 0, f(x) = ex is convex op R, f(x) = -log x is convex als x > 0, f(x) = 1/x is convex als x > 0 (en concaaf als x < 0), f(x) = x log x is convex als x > 0, f(x) = xp is convex als x > 0 en p ≥ 1, of p ≤ 0 (en concaaf als x > 0 en 0 ≤ p ≤ 1). Soms kun je met de tweede afgeleide de convexiteit van een functie bewijzen en vervolgens via de definitie van convexiteit ongelijkheden opschrijven die op een andere manier veel moeilijk of niet te bewijzen zijn. Uit de convexiteit van f(x) = ex volgt bijvoorbeeld dat
2e
x+ y 2
≤ ex + ey
en uit de convexiteit van –log x volgt dat xλy1-λ ≤ λx + (1-λ)y Voor λ = ½ staat hier bijvoorbeeld:
xy ≤
x+ y . 2
De linkerkant heet het meetkundig gemiddelde van x en y, de rechterkant is het gewone (rekenkundige) gemiddelde. Het meetkundig gemiddelde is dus altijd kleiner dan of gelijk aan het rekenkundig gemiddelde. Je kunt ook nog een harmonisch gemiddelde definiëren als
⎡ 1 ⎛ 1 1 ⎞⎤ ⎢ ⎜⎜ + ⎟⎟⎥ ⎣ 2 ⎝ x y ⎠⎦
−1
=
2 xy x+ y
Het is eenvoudig in te zien dat het harmonisch gemiddelde altijd weer kleiner dan of gelijk aan het meetkundig gemiddelde is. Dit volgt grappig genoeg uit omschrijven van de vorige ongelijkheid.
Convexe functies op Rn Tot nu toe hebben we convexe functies op R bekeken. Het is echter eenvoudig dit begrip ook te definiëren voor functies van Rn naar R: Een functie f : Rn → R heet convex, als voor alle x, y ∈ Rn en elke λ ∈ [0,1] geldt dat f(λx + (1-λ)y) ≤ λf(x) + (1-λ)f(y). Hetzelfde geldt als de functie op een convex deel van Rn is gedefinieerd. De uitbreidingen naar strikt convex en concaaf zijn volledig analoog.
Voorbeeld: We zullen bewijzen dat de euclidische normfunctie f(x) = |x| convex is op Rn. Er geldt dat |λx + (1-λ)y|2 = λ2|x|2 + (1-λ)2|y|2 + λ(1-λ)(x,y) ≤ λ2|x|2 + (1-λ)2|y|2 + λ(1-λ)|x| |y| = (λ|x| + (1-λ)|y|)2, want volgens de ongelijkheid van Schwarz is (x,y) ≤ |x| |y|. Hieruit volgt nu dat f(λx + (1-λ)y) = |λx + (1-λ)y| ≤ λ|x| + (1-λ)|y| = λf(x) + (1-λ)f(y), dus f is convex. Als f convex is, dan is ook af weer convex, voor elke scalar a ≥ 0. Als f en g convex zijn, dan ook f + g (maar f – g meestal niet). Een constante functie is convex, dus in het bijzonder blijft een functie convex als je er een constante bij optelt. Als f : Rn → R en h: R → R convex zijn en h bovendien monotoon niet-dalend, dan is h o f weer convex. Er geldt ook weer dat een convexe functie continu is op het inwendige van zijn domein, maar dat er op de rand sprongen kunnen optreden. Voor de convexiteit van een tweemaal differentieerbare functie is er weer een criterium in termen van zijn tweede afgeleide: Stelling: f ∈ C2(Rn,R) is convex dan en slechts dan als ∇2f(x) ≥ 0 voor alle x. Hierbij is ∇2f(x) de tweede afgeleide van f – de Hessematrix – en ∇2f(x) ≥ 0 betekent dat deze matrix overal niet-negatief definiet is. Een matrix A heet niet-negatief definiet als voor elke vector x geldt dat (Ax,x) ≥ 0. Een matrix A heet positief definiet als voor elke vector x ≠ 0 geldt dat (Ax,x) > 0.
Een matrix is positief (niet-negatief) definiet dan en slechts als al zijn eigenwaarden positief (niet-negatief) zijn. Voorbeeld: Bekijk de functie f ( x 1 , x 2 , x 3 ) =
x 12 + x 32 voor x2 > 0. De eerste en tweede x2
afgeleiden zijn: ⎛ x1 ⎞ ⎛ 2 ⎜2 ⎟ ⎜ ⎜ x2 ⎟ ⎜ x2 2 ⎜ x1 ⎟ , ⎜ ∇f ( x1 , x 2 , x3 ) = ⎜ − 2 ⎟ ∇ 2 f (x1 , x 2 , x3 ) = ⎜ − 2 x1 2 x ⎜ 2⎟ ⎜ x2 ⎜ 2 x3 ⎟ 0 ⎜ ⎟ ⎜ ⎜ ⎝ ⎠ ⎝
2 x1 x 22 2 x12 x 23 0
−
⎞ 0⎟ ⎟ ⎟ 0⎟ ⎟ 2⎟ ⎟ ⎠
x12 + x 22 . Deze zijn allemaal niet-negatief, dus de x 23 matrix is niet-negatief definiet en de functie f is convex. Direct met de definitie is dit ook te zien: De eigenwaarden van de Hessematrix zijn 0, 2,
⎛ ⎛ 2 ⎜ ⎜ ⎜ ⎛ y ⎞ ⎜ x2 ⎜ ⎜ 1 ⎟ ⎜ 2 x1 ⎜ ⎜ y2 ⎟, ⎜ − 2 ⎜ ⎜ y ⎟ ⎜ x2 ⎜⎝ 3 ⎠ ⎜ 0 ⎜ ⎜ ⎝ ⎝
2 x1 x22 2 x12 x23 0
−
⎞ ⎞ ⎟ 0⎟ ⎟⎛ y1 ⎞ ⎟ 2 ⎟⎜ ⎟ ⎟ 2 ⎛ x1 y2 ⎞ ⎟⎟ + 2 y32 ≥ 0. 0 ⎟⎜ y2 ⎟ ⎟ = ⎜⎜ y1 − x x 2 2 ⎝ ⎠ ⎟⎜ ⎟ ⎟ 2 ⎟⎝ y3 ⎠ ⎟ ⎟ ⎟ ⎠ ⎠
Orde van convergentie
Om uitspraken te kunnen doen over de convergentiesnelheid van benaderende processen is het handig om onderscheid te kunnen maken tussen verschillende ordes van convergentie. Een belangrijk soort convergentie is lineaire convergentie. Bij een proces dat lineair convergeert zal de fout na elke iteratie ongeveer met een vaste factor kleiner worden. Een rij (αk) convergeert lineair naar een limiet α als α k +1 − α ≈ β α k − α voor een zekere constante β . Het is duidelijk dat deze constante niet groter dan 1 kan zijn, want anders komt α k niet dicht bij de limiet α . We spreken van kwadratische convergentie als
α k +1 − α ≈ β α k − α voor een zekere constante β .
2
We maken dit wat preciezer met de volgende definitie van de orde van convergentie. Een rij (α k ) convergeert met orde p naar een limiet α als
⎧⎪ lim sup α k +1 − α ⎫⎪ p = sup⎨q | . q ⎬ ⎪⎩ k → ∞ α k − α ⎪⎭ De convergentiefactor bij deze orde is
β=
lim sup α k +1 − α k → ∞ αk −α
p
.
Als p = 1 heet de convergentie lineair. Als bovendien β = 0, dan heet de convergentie superlineair (de fout wordt telkens verkleind met een factor die zelf steeds kleiner wordt). Als daarentegen β = 1, dan heet de convergentie sublineair (de fout wordt telkens verkleind met een factor die steeds dichter bij 1 komt, de convergentie gaat dus steeds trager). Voorbeeld: Bekijk de meetkundige rij αk = ak voor een getal a met 0 < a < 1. Deze rij convergeert naar α = 0. Nu geldt:
α k +1 − α αk −α
p
a k +1 = kp = a k (1− p )+1 = a a 1− p a
(
)
k
.
Als p > 1, dan is a1-p > 1, dus de bovenstaande rij is niet begrensd als k → ∞. Als p = 1, dan is a1-p = 1, dus de bovenstaande rij is constant a. Als p < 1, dan is a1-p < 1, dus de bovenstaande rij nadert naar 0. De orde van convergentie is dus p = 1, en de convergentiefactor is β = a, dus we hebben te maken met lineaire convergentie.
Voorbeeld: Bekijk de rij αk = a (2 ) voor een getal a met 0 < a < 1. Deze rij convergeert ook naar α = 0, maar sneller dan de bovenstaande. We laten zien dat deze rij kwadratisch convergeert door p = 2 te nemen: k
α k +1 − α αk −α
2
(a ( ) ) = = (a ( ) ) (a ( ) ) k =1 a (2 )
2K
2k
2
2K
2 2
= 1.
De orde van convergentie is dus p = 2, en de convergentiefactor is β = 1, dus we hebben te maken met (sub)kwadratische convergentie. Voorbeeld: De rij αk = 1/k convergeert naar α = 0. Nu geldt:
α k +1 − α k = . αk −α k +1
De limiet van deze getallen is 1, de orde van convergentie is dus p = 1, en de convergentiefactor is β = 1, dus we hebben te maken met (trage) sublineaire convergentie. Voorbeeld: Bekijk de rij αk = k-k. Nu is:
α k +1 − α αk −α
p
=
k pk
(k + 1)k +1
=
k ( p −1)k
(k + 1)⎛⎜1 + 1 ⎞⎟ ⎝ k⎠
k
=
(k )
k p −1
(k + 1)⎛⎜1 + ⎝
1⎞ ⎟ k⎠
k
.
k
⎛ 1⎞ Er geldt dat ⎜1 + ⎟ → e . ⎝ k⎠ Als p > 1, dan is de bovenstaande rij niet begrensd als k → ∞. Als p = 1, nadert de bovenstaande rij naar 0. Als p < 1, nadert de bovenstaande rij naar 0. De orde van convergentie is dus p = 1, en de convergentiefactor is β = 0, dus we hebben te maken met superlineaire convergentie.
Line search methoden (Eéndimensionaal optimaliseren)
Het minimum van een functie van één variabele kun je soms vinden door de afgeleide nul te stellen. Dat kan alleen als de functie expliciet is gegeven als een differentieerbare functie en als de vergelijking die je krijgt ook op te lossen is. Maar in de praktijk weet je de functie niet altijd expliciet. Het kan zijn dat voor het uitrekenen van één functiewaarde een hele simulatie nodig is. Als je bijvoorbeeld de wrijvingsweerstand van een auto wilt verbeteren door de vorm van de auto te veranderen, dan zal er voor elke vorm van de auto een windtunnelsimulatie moeten worden gedaan om de wrijving te bepalen. We gaan nu kijken naar algoritmes waarmee je een optimum van een ééndimensionale functie kunt benaderen. Je kunt deze algoritmes vergelijken met algoritmes om een nulpunt van een functie te bepalen. Het bisectie-algoritme gaat er bijvoorbeeld vanuit dat je twee punten a < b hebt en dat de waarde van de functie in deze twee punten een verschillend teken heeft. Als je functie continu is, dan weet je dat er tussen a en b een nulpunt moet liggen. Je rekent dan de functiewaarde in het gemiddelde uit. Op één van de twee intervallen [a, (a+b)/2] en [(a+b)/2, b] moet de functie ook een tekenwisseling vertonen. Zo kun je door het uitrekenen van één functiewaarde de lengte van het interval waarin een nulpunt ligt halveren.
Bij het vinden van een minimum ligt het wat ingewikkelder, omdat je aan de hand van twee functiewaarden niet kunt zien of er een maximum aanwezig is. Eén manier van zoeken is uniform zoeken: Verdeel in het interval [a,b] uniform n nieuwe punten:
xk = a + k
b−a , n +1
k = 1,..., n.
Reken de functiewaarde uit in elk punt en zoek de kleinste. Als die wordt aangenomen in xk vervang je het interval [a, b] door [xk-1, xk+1]. Het interval heeft als lengte
2 (b − a ). n +1 Per functie-evaluatie reduceert de lengte dus (worst case) met een factor 1
⎛ 2 ⎞n ⎜ ⎟ . ⎝ n + 1⎠ Het is eenvoudig te zien dat deze factor minimaal is als n = 3. De reductiefactor per evaluatie is dan 2-1/3 = 0.793700… Eigenlijk is de factor kleiner, omdat je de functiewaarde in het middelste punt niet opnieuw hoeft uit te rekenen. Dit levert een factor 2-1/2 = 0.707106… per iteratie. Een efficiëntere methode is de gulden snede zoekmethode (golden section search). Het idee hierbij is dat je in het interval [a,b] nog een punt c hebt waarvan je de functiewaarde kent, en dat de waarde in het inwendige punt kleiner is dan die in de randpunten: f(a) ≥ f(c) ≤ f(b). Vervolgens wordt er een nieuw punt d gekozen. We nemen aan dat dit tussen a en c ligt, maar tussen c en b gaat het analoog. Nu is f(d) minstens f(c), of hoogstens f(c).
als f(d) ≥ f(c), dan is f(d) ≥ f(c) ≤ f(b).
Als f(d) ≤ f(c), dan is f(a) ≥ f(d) ≤ f(c). Dit betekent dat we het interval [a,b] met tussenpunt c kunnen vervangen door [d,b] met tussenpunt c, of door [a,c] met tussenpunt d, terwijl telkens de waarde in het tussenpunt het kleinst is. Het ligt nu voor de hand om de posities van c en d zo te kiezen dat de lengtes van de nieuwe intervallen gelijk zijn, zodat je altijd dezelfde reductie hebt. Kies d op verhouding λ en c op verhouding 1-λ op het interval [a,b], ofwel: d = a + λ(b-a), d = a + (1-λ)(b-a). De slimme truc van de methode bestaat er nu in dat je λ zo kiest dat je na reductie het middelste punt weer kunt gebruiken. Het punt op verhouding λ kan natuurlijk niet weer op verhouding λ liggen, omdat het interval kleiner is geworden, maar het kan wel op verhouding (1-λ) liggen in het nieuwe interval. Omdat het nieuwe interval een factor (1-λ) kleiner is geworden is de nieuwe factor van het tussenpunt nu λ/(1-λ). Als deze verhouding gelijk is aan 1-λ, dan is het punt weer te gebruiken. Dit is het geval als λ2 - λ - 1 = 0, dus als
λ=
3− 5 = 0,381966..., 2
1− λ =
5 −1 = 0,618033... 2
Dit is de gulden snede verhouding. Met één functie-evaluatie wordt het interval dus verkleind met een factor 1-λ = 0,618033, dat is beter dan bij de bovenstaande methode.
Als je ook de afgeleide van de functie kent kun je ook de volgende methode toepassen: Kies c midden tussen a en b en bereken f’(c). Als f’(c) ≤ 0, dan ligt het minimum rechts van c en neem je als nieuw interval [c,b]. Als f’(c) ≥ 0 dan kies je [a,c] als nieuw interval. In beide gevallen heb je met één evaluatie van de afgeleide het interval gehalveerd, dus de reductiefactor is 0,5, nog weer kleiner dan bij de gulden snede methode. Voorbeeld: Benader het minimum van f(x) = x(x-1) op [0,3]. Omdat f’(3/2) = 2 > 0 wordt het nieuwe interval [0,3/2]. f’(3/4) = 0,5 > 0, dus het interval wordt [0,3/4]. f’(3/8) = -0,25 < 0, dus het nieuwe interval is [3/8,3/4]. f’(9/16) = 1/8 > 0, het interval wordt [3/8, 9/16], etc.
Als je ook de beschikking hebt over een tweede afgeleide kun je de methode van Newton toepassen. Het idee is dat je de functie benaderd met een kwadratische functie: f(xk+h) ≈ f(xk) + hf’(xk) + h2f’’(xk)/2. Het minimum als functie van h treedt op als
h=−
f ′( x k ) f ′( x k ) , dus x k +1 = x k − . f ′′( x k ) f ′′( x k )
In het bovenstaande voorbeeld geeft de Newtonmethode bijvoorbeeld met één iteratie het exacte antwoord, omdat de functie al kwadratisch is. In het algemeen convergeert het algoritme kwadratisch, terwijl de voorgaande algoritmes lineair convergeren. Optimaliseren zonder afgeleiden
Gradiëntmethoden
Numerieke algoritmen om met behulp van een daalrichting een locaal minimum te vinden van een differentieerbare functie f die is gedefinieerd op een open convex gebied C zijn vaak van de volgende generieke vorm: Input:
ε > 0, een nauwkeurigheidsparameter. x0 een startpunt in C.
Initialisatie:
x := x0; k := 0.
Stap 1:
Vind een zoekrichting sk zodat δf(xk, sk) < 0 Als er geen locale daalrichting is: Stop, optimum gevonden.
Stap 2 (line search):
Zoek λk = argminλ f(xk + λsk)
Stap 3 (update):
xk+1 := xk + λksk.
Stap 4 (stopcriterium):
Als aan het stopcriterium voldaan is: stop. Anders ga naar stap 1.
In het algoritme wordt op een of andere manier een richting bepaald, waarmee lokaal een verbetering van f kan worden bereikt. In die richting wordt de optimale stapgrootte vastgesteld, en er wordt een stap in die richting gedaan. Welke richting wordt gebruikt, welk line search algoritme, hoe nauwkeurig dit ééndimensionale minimum wordt bepaald en welk stopcriterium wordt gebruikt bepalen de precieze vorm van het algoritme. Als we voor sk de richting nemen waarin de functie het sterkst daalt krijgen we de “Steepest Descent” methode. Om sterkste daalrichting te bepalen kijken we naar de Taylorontwikkeling: f(xk + εh) = f(xk) + ε∇f(xk)Th + O(ε2). De term die in eerste instantie de verandering van f rond het punt xk bepaalt is ∇f(xk)Th = |∇f(xk)T| |h| cosϕ, waarbij ϕ de hoek is tussen ∇f(xk) en h. Hieruit zien we dat de richting waarin f het sterkst stijgt is: ∇f(xk), en de richting waarin f het sterkst daalt is -∇f(xk). Deze richting staat loodrecht op de niveauoppervlakken van f. Voor de steepest descent methode geldt dus dat de zoekrichting sk = -∇f(xk) is. Voorbeeld: Als voorbeeld rekenen we de gradiënt uit van een willekeurige positief definiete kwadratische functie: f(x) = ½ xTQx + qTx +c. Hierin is Q een positief definiete matrix. Dit kan op twee manieren. De eerste manier is door de functie in coördinaten uit te schrijven en daarvan de afgeleiden uit te rekenen. De tweede manier is door de functie uit te rekenen rond x en door vergelijken met de Taylorreeksontwikkeling de afgeleide te bepalen. We zullen dit laatste doen:
f(x+h) = ½ (x+h)TQ(x+h) + qT(x+h) + c = ½ xTQx + ½ xTQh + ½ hTQx + ½ hTQh + qTx + qTh +c = f(x) + ½ (QTx)Th + ½ (Qx)Th + qTh + ½ hTQh. Als we dit vergelijken met de Taylorreeksontwikkeling f(x+h) = f(x) + (∇f(x))Th + O(h2) dan zien we dat moet gelden dat ∇f(x) = ½ (QT + Q)x + q. We zullen nu aantonen dat de steepest descent methode de functiewaarde monotoon laat dalen en dat convergentie optreedt naar een stationair punt (waar de afgeleide nul is). Stelling: Laat f ∈ C2, en {x | f(x) ≤ f(x0)} compact. Dan geldt voor de steepest descent methode met exacte line search dat f(xk+1) < f(xk) en voor elk verdichtingspunt x van de rij (xj) geldt ∇f(x) = 0. Verder staat elke zoekrichting telkens loodrecht op de voorgaande. Bewijs: Het is duidelijk dat f(xk+1) < f(xk), want anders zou het algoritme afbreken. We gaan er even vanuit dat het algoritme niet afbreekt, dus dat er een oneindige rij van iteranden xj is. Deze zitten in de compacte verzameling {x | f(x) ≤ f(x0)}, dus er is een convergente deelrij. Deze deelrij noemen we yj = xk(j) → y. Uit de continuïteit van f volgt dat f(yj) → f(y). Noem de zoekrichtingen sk(j) die bij de yj horen tj = sk(j), dan geldt, omdat de afgeleide van f continu is:
s=
lim k ( j ) lim s = − ∇f x k ( j ) = −∇f ( x ) . j→∞ j→∞
(
)
Nu is f(xk(j+1)) ≤ f(xk(j)+1) ≤ f(xk(j) + λsk(j)) voor een willekeurige λ. Door de limiet j → ∞ te nemen zien we dat f(x) ≤ f(x + λs) voor alle λ. Nu geldt voor de richtingsafgeleide
δf ( x, s ) =
lim f ( x + λs ) − f ( x ) ≥ 0. λ↓0 λ
Aan de andere kant is
δf ( x, s ) = (∇f ( x ))T s = −(∇f (x ))T (∇f ( x )) ≤ 0
Er moet dus gelden dat ∇f ( x ) = 0. De zoekrichtingen van de steepest descent methode staan telkens loodrecht op de vorige. We kunnen dit als volgt zien. In de line search wordt λ zo bepaald dat f(xk + λsk) minimaal is. Dat wil zeggen dat de afgeleide van f(xk + λsk) naar λ gelijk is aan 0: 0 = ∇f(xk + λsk)Tsk = ∇f(xk+1)Tsk = -(sk+1)Tsk = (sk+1, sk). Voor een kwadratische doelfunctie f(x) = ½ xTQx + qTx +c, waarbij Q een symmetrische, positief definiete matrix is, kan het convergentiegedrag van de steepest descent-methode gemakkelijk bepaald worden. Er geldt dan dat
( ) ( ) (λ
f x k +1 − f x * ≈
max
− λ min )
2
(λmax + λmin )
2
( ) ( )
f x k − f x* .
Hierin zijn λmin en λmax de kleinste en grootste eigenwaarde van Q (Q is symmetrisch en positief definiet, dus alle eigenwaarden zijn reëel en positief). Hieruit zien we dat het convergentiegedrag van de steepest descent methode lineair is, en dat de convergentiecoëfficiënt afhankelijk is van het conditiegetal van de matrix κ = λmax/λmin:
( ) ( ) (κ − 1) f (x ) − f (x ) .
f x k +1 − f x * ≈
2
(κ + 1)
k
*
2
Als het conditiegetal klein is (Q lijkt dan erg op de eenheidsmatrix), dan is de convergentiecoëfficiënt klein (Als Q = I is er zelfs maar één iteratie nodig). Als het conditiegetal groot is neigt het convergentiegedrag naar sublineair. Deze analyse is weliswaar slechts waar voor kwadratische functies, maar omdat een willekeurige differentieerbare functie in de buurt van een minimum erg lijkt op een kwadratische functie is het convergentiegedrag van de steepest descent methode in essentie ook lineair.
Newtonmethode
Tot nu toe hebben we informatie van de functie gebruikt en van zijn afgeleide om dichter bij het minimum te komen. Een volgend idee zou zijn om ook de tweede afgeleide te gebruiken. Met behulp van de tweede afgeleide kan de functie namelijk benaderd worden met een kwadratische functie en van een kwadratische functie kun je direct het minimum uitrekenen. De Taylorontwikkeling levert: f(x) = f(xk) + ∇f(xk)T(x – xk) + 1/2 (x – xk)T∇2f(xk)T(x – xk) + O(|x – xk |3). Als we de derde-orde term weglaten en f benaderen met deze functie, dan kunnen we het minimum uitrekenen door de afgeleide naar x 0 te stellen: 0 = ∇f(xk) + ∇2f(xk)(x – xk). Hieruit kunnen we x oplossen, dit wordt de nieuwe benadering: xk+1 = xk – (∇2f(xk))-1∇f(xk). Merk op dat we, in tegenstelling tot de steepest descent methode, geen line search hoeven te doen, maar de nieuwe benadering in één keer vinden. Wel is het uitrekenen van die benadering meer werk. Je moet namelijk de Hessematrix inverteren en toepassen op de gradiënt.
Karush-Kuhn-Tucker voorwaarden (zie boek p. 679)
We hebben eerder al noodzakelijke en voldoende voorwaarden gezien waaraan een optimaal punt moet voldoen. Als de afgeleide bijvoorbeeld gelijk is aan 0 en de tweede afgeleide is positiefdefiniet, dan is het punt lokaal optimaal. Als er beperkingen in het spel zijn worden deze voorwaarden echter een stuk ingewikkelder omdat een optimum nu ook op de rand van gebied kan liggen zonder dat de afgeleide er 0 is. We bekijken nu het volgende nietlineaire optimaliseringsprobleem met niet-lineaire beperkingen: Max z.d.d. en
f(x) gi(x) ≤ bi voor alle i = 1, …, m xi ≥ 0 voor alle i = 1, …, m
Er geldt nu dat een punt x* een locaal optimale oplossing van dit probleem is, precies dan als er getallen u1, …, um zijn zodat aan de volgende zes voorwaarden is voldaan: 1.
( )
m
∇f x * − ∑ u i ∇g i ( x ) ≤ 0 i =1
2. 3. 4. 5. 6.
m ⎛ ∂f * ⎞ ∂g x *j ⎜ x − ∑ u i i ( x )⎟ = 0 voor alle j = 1, …, m ⎜ ∂x ⎟ ∂x j i =1 ⎝ j ⎠
( )
gi(x*) ≤ bi voor alle i = 1, …, m ui(gi(x*)-bi) = 0 voor alle i = 1, ..., m x* ≥ 0. ui ≥ 0.
De getallen ui, die elk bij een constraint horen, heten de Lagrange multiplicatoren. Ze zijn nietnegatief en kunnen alleen positief zijn (vierde eis) als de bijbehorende constraint actief is, d.w.z., als voor x* de gelijkheid gi(x*) = bi geldt, x* ligt op de rand van het gebied dat wordt bepaald door deze constraint. De derde en vijfde eisen zijn gewoon de eisen voor toelaatbaarheid: x* voldoet aan de beperkingen in het optimaliseringsprobleem. De bovenstaande, zogenaamde Karush-Kuhn-Tucker (KKT) voorwaarden karakteriseren de lokaal optimale oplossingen van een optimaliseringsprobleem met randvoorwaarden. Je kunt ze gebruiken om van een punt te controleren (bewijzen) of een punt optimaal is, en in principe zou je zelfs hiermee de optimale oplossingen kunnen bepalen, hoewel het vinden van punten die aan de KKT voorwaarden voldoen vaak erg lastig is. Als voorbeeld bekijken we het volgende probleem: Max z.d.d. en
f(x1, x2) = log(x1+1) + x2 2x1 + x2 ≤ 3 x1, x2 ≥ 0
De KKT voorwaarden zijn nu: 1a 1b
1 ≤ 2u1 x1 + 1 u1 ≥ 1
2a 2b 3 4 5 6
⎞ ⎛ 1 x1 ⎜⎜ − 2u1 ⎟⎟ = 0 ⎠ ⎝ x1 + 1 x2 (1 − u1 ) = 0 2 x1 + x2 ≤ 3 u1 (2 x1 + x 2 − 3) = 0 x1 , x 2 ≥ 0 u1 , u 2 ≥ 0
We gaan nu met behulp van deze voorwaarden de optimale oplossingen zoeken. Dat vergt enige combinatie van deze voorwaarden, in de juiste volgorde: Volgens 1b is u1 ≥ 1 en omdat x1 niet-negatief is (5), is
1 − 2u1 ≤ 1 − 2 < 0 . Uit 2a volgt dus x1 + 1
dat x1 = 0. Uit 4 volgt dan dat x2 = 3 en uit 2b ten slotte dat u1 = 1. Het is nu eenvoudig in te zien dat x1 = 0, x2 = 3, u1 = 1 voldoet aan alle KKT condities, dus (0,3) is de optimale oplossing van het probleem en de doelwaarde is f(0, 3) = 3.
Frank-Wolfe algoritme (zie boek p. 698) Als voorbeeld van een algoritme waarmee een niet-lineair optimaliseringsprobleem met lineaire constraints kan worden opgelost bekijken we het “sequentiele lineaire benaderingsalgoritme, het algoritme van Frank-Wolfe. Dit algoritme is toepasbaar op een optimaliserinsprobleem waarin de doelfunctie welliswaar niet-lineair is, maar de beperkingen wel lineair zijn: Max. z.d.d. en
f(x) Ax ≤ b x≥0
Het idee van het algoritme is om de functie met behulp van een Taylorontwikkeling te benaderen met een lineaire functie:
f ( x) ≈ f (x k ) + ∇f (x k ) (x − x k ) T
In plaats van f wordt nu als doelfunctie genomen cTx, waarbij
ci =
∂f k x ∂xi
( )
Vervolgens wordt het ontstane LP probleem opgelost, en de LP oplossing gebruikt om een betere benadering voor het niet-lineaire probleem te krijgen. Dat wordt gedaan door met een line-search een optimale oplossing te zoeken op de verbindingslijn tussen de oude benadering en de zojuist gevonde LP oplossing. We zullen dit algoritme illustreren met het volgende voorbeeld: Max z.d.d. en
f(x1, x2) = 5x1 – x12 + 8x2 – 2x22 3x1 + 2x2 ≤ 6 x1 , x2 ≥ 0
Als startpunt nemen we x0 = (0, 0), dit is een toegelaten punt, met doelwaarde 0. De gradient van f is:
⎛ 5 − 2 x1 ⎞ ⎟⎟ ∇f ( x1 , x 2 ) = ⎜⎜ ⎝ 8 − 4 x2 ⎠ We zien dat het probleem zonder beperkingen als optimale oplossing zou hebben: (5/2, 2), maar deze oplossing is niet toegelaten. Als lineaire benadering in het startpunt (0, 0) nemen we dus 5x1 + 8x2. Het LP probleem Max z.d.d. en
5x1 + 8x2 3x1 + 2x2 ≤ 6 x1 , x2 ≥ 0
heeft als optimale oplossing x1LP = (0, 3). De eerstvolgende benadering wordt nu gezocht op de verbindingslijn tussen de startoplossing en de LP oplossing: (1-t)(0, 0) + t(0, 3) = (0, 3t). Er geldt nu dat f(0, 3t) = 24t – 18t2 maximaal is als t = 2/3, dus de eerste benadering is x1 = (0, 2) met doelwaarde 8. In dit punt berekenen we weer de gradiënt: (5, 0)T en vinden de volgende lineaire benadering van het probleem: Max z.d.d. en
5x1 3x1 + 2x2 ≤ 6 x1 , x2 ≥ 0
De optimale LP oplossing is x2LP = (2, 0). We zoeken nu een optimale oplossing tussen x2LP en x1: (1-t)(0, 2) + t(2, 0) = (2t, 2-2t). De waarde van de objectfunctie is hier 10t – 6t2, en is maximaal in t = 5/6, dus x1 = (5/6, 7/6) met doelwaarde 10,08333.
