Nichtlineaire programmering

Niet-lineaire programmering (NLP) — is een deelgebied van wiskundige programmering en operations research, dat zich bezighoudt met optimalisatieproblemen waarbij de doelfunctie en/of ten minste één van de beperkingen niet-lineaire functies zijn van de beslissingsvariabelen.

NLP is een veralgemening van lineaire programmering en maakt het mogelijk een bredere klasse van reële systemen en processen te modelleren, waarbij de relaties tussen variabelen niet strikt proportioneel zijn (d.w.z. beschreven worden door krommen in plaats van rechte lijnen).

Onderwerp en doel

Niet-lineaire programmering wordt gebruikt om optimale oplossingen te vinden in situaties waarbij:

• De afhankelijkheid van de doelstelling (winst, kosten, efficiëntie, enz.) van de beheersbare parameters niet-lineair is (bijvoorbeeld afnemende schaalopbrengsten, kwadratische kosten).
• Beperkingen op middelen of technologische processen worden beschreven door niet-lineaire relaties (bijvoorbeeld chemische reacties, fysieke wetten, economische verbanden).

NLP-problemen komen voor in vele gebieden:

• Technisch ontwerp (optimalisatie van constructies en processen).
• Economie en financiën (portfoliooptimalisatie met risicoafweging, marktmodellering).
• Chemische technologie (optimalisatie van reactoromstandigheden).
• Machine Learning (training van neurale netwerken, support vector methode).
• Beheer van productieprocessen. Logistiek (rekening houdend met niet-lineaire kosten).

Wiskundige formulering van het NLP-probleem

Het algemene niet-lineaire programmeringsprobleem wordt als volgt geformuleerd:

Gevraagd wordt een set waarden van beslissingsvariabelen te vinden die een niet-lineaire doelfunctie maximaliseert of minimaliseert. Daarbij moeten de waarden van de variabelen voldoen aan een stelsel van beperkingen, die zowel uitgedrukt kunnen worden als ongelijkheden (bijvoorbeeld "grootheid A moet kleiner zijn dan of gelijk zijn aan B") als als gelijkheden (bijvoorbeeld "grootheid C moet exact gelijk zijn aan D"). Belangrijk is dat ten minste één van de functies die het doel of de beperkingen beschrijven, niet-lineair is. Vaak worden ook niet-negativiteitsvoorwaarden voor de variabelen toegevoegd, dat wil zeggen de eis dat hun waarden groter dan of gelijk aan nul zijn.

De verzameling van alle sets variabelewaarden die aan de beperkingen voldoen, vormt het toelaatbare gebied (feasible region).

Verschillen met lineaire programmering

Niet-lineaire programmering verschilt wezenlijk van lineaire programmering (LP):

• Niet-lineariteit: De doelfunctie of de beperkingen (of beide) bevatten niet-lineaire relaties.
• Eigenschappen van het toelaatbare gebied: Het toelaatbare gebied in NLP kan niet-convex zijn (in tegenstelling tot LP, waar het toelaatbare gebied altijd een convex veelvlak is).
• Eigenschappen van het optimum: De optimale oplossing in NLP bevindt zich niet noodzakelijk in een hoekpunt van het toelaatbare gebied; zij kan op de rand of in het inwendige van het gebied liggen. In NLP kunnen lokale optima bestaan die geen globale optima zijn.
• Oplossingsmoeilijkheid: NLP-problemen zijn doorgaans aanzienlijk moeilijker op te lossen dan LP-problemen. Er bestaat geen enkelvoudig universeel algoritme, vergelijkbaar met de simplexmethode, voor alle NLP-problemen.

Belangrijkste moeilijkheden en uitdagingen van NLP

Het oplossen van niet-lineaire programmeringsproblemen gaat gepaard met een aantal moeilijkheden:

• Aanwezigheid van lokale extremen: De meeste NLP-methoden garanderen alleen het vinden van een lokaal optimum (een oplossing die de beste is in een bepaalde omgeving). Het vinden van een globaal optimum (de beste oplossing in het gehele toelaatbare gebied) is een complex probleem, in het bijzonder voor niet-convexe problemen.
• Niet-convexiteit: Als het probleem niet convex is (de doelfunctie of het toelaatbare gebied is niet-convex), kunnen er meerdere lokale optima bestaan en kunnen standaard gradiëntmethoden in een ervan "vast komen te zitten".
• Rekenkundige complexiteit: Algoritmen voor het oplossen van NLP-problemen vereisen vaak aanzienlijk meer rekenkracht in vergelijking met LP.

Belangrijke klassen van NLP-problemen

Ondanks de algemene complexiteit zijn er belangrijke subklassen van NLP-problemen waarvoor efficiënte oplossingsmethoden zijn ontwikkeld:

• Convex programmeren: Het minimaliseren van een convexe functie op een convexe verzameling toelaatbare oplossingen (of het maximaliseren van een concave functie). Sleuteleigenschap: elk lokaal minimum is tevens een globaal minimum. Dit vereenvoudigt de zoektocht naar een optimale oplossing aanzienlijk.
• Kwadratisch programmeren: De doelfunctie is kwadratisch en alle beperkingen zijn lineair.
• Separabel programmeren: De doelfunctie en de beperkingen kunnen worden weergegeven als sommen van functies, waarvan elk slechts van één variabele afhankelijk is.

Oplossingsmethoden voor NLP-problemen

Oplossingsmethoden voor niet-lineaire programmeringsproblemen (NLP)

I. Methoden voor onbeperkte optimalisatie (optimalisatie zonder beperkingen):

• Gradiëntmethoden (methode van de steilste afdaling, methode van geconjugeerde gradiënten);
• De methode van Newton en quasi-Newton-methoden (bijvoorbeeld BFGS);
• Methoden met gebruikmaking van Hessian-benadering.

II. Methoden voor beperkte optimalisatie (optimalisatie met beperkingen):

• Transformatiemethoden:
  • Straffunctiemethode (penalty methods);
  • Barrièrefunctiemethode (barrier methods).
• Methoden voor directe zoekrichtingen:
  • Methode van mogelijke richtingen.
• Methoden gebaseerd op optimaliteitsvoorwaarden:
  • Methoden van Karush-Kuhn-Tucker (KKT-voorwaarden);
  • Methode van Lagrange-multiplicatoren.
• Iteratieve methoden:
  • Sequentieel kwadratisch programmeren (SQP);
  • Inwendigepuntmethoden.

III. Methoden voor globale optimalisatie:

• Heuristische en metaheuristische methoden:
  • Genetische algoritmen;
  • Simulated annealing;
  • Tabu search.
• Deterministische methoden:
  • Branch and bound;
  • Globale optimalisatiealgoritmen voor problemen met een speciale structuur.

Literatuur

• Bazara M., Shetty C. Niet-lineaire programmering. Theorie en algoritmen. — Moskou: Mir, 1982.
• Fiacco A., McCormick G. Niet-lineaire programmering. Methoden voor sequentiële onbeperkte minimalisatie. — Moskou: Mir, 1972.
• Himmelblau D. Toegepaste niet-lineaire programmering. — Moskou: Mir, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

Zie ook

• Operations research
• Optimalisatie
• Lineaire programmering
• Convex programmeren
• Doelfunctie
• Beperkingen
• Toelaatbaar gebied