Icke-linjär programmering

Icke-linjär programmering (NLP) — är en gren av matematisk programmering och operationsanalys som behandlar optimeringsproblem där målfunktionen och/eller minst en av bivillkoren är icke-linjära funktioner av beslutsvariablerna.

NLP är en generalisering av linjär programmering och möjliggör modellering av en bredare klass av verkliga system och processer, där sambanden mellan variablerna inte är strikt proportionella (dvs. beskrivs av kurvor snarare än räta linjer).

Ämne och syfte

Icke-linjär programmering används för att finna optimala lösningar i situationer där:

• Beroendet av ett målvärde (vinst, kostnader, effektivitet osv.) på styrda parametrar är icke-linjärt (t.ex. avtagande skalavkastning, kvadratiska kostnader).
• Begränsningar på resurser eller teknologiska processer beskrivs av icke-linjära samband (t.ex. kemiska reaktioner, fysikaliska lagar, ekonomiska beroenden).

NLP-problem uppstår inom många områden:

• Teknisk konstruktion (optimering av konstruktioner och processer).
• Ekonomi och finans (portföljoptimering med hänsyn till risk, marknadsmodellering).
• Kemiteknik (optimering av reaktordrift).
• Machine Learning (träning av Neural Networks, metoden för stödvektorer).
• Styrning av produktionsprocesser. Logistik (med hänsyn till icke-linjära kostnader).

Matematisk formulering av NLP-problemet

Det allmänna problemet inom icke-linjär programmering formuleras enligt följande:

Målet är att finna en uppsättning värden på beslutsvariablerna som maximerar eller minimerar en icke-linjär målfunktion. Variabelvärdena måste uppfylla ett system av bivillkor, vilka kan uttryckas antingen som olikheter (t.ex. "storhet A ska vara mindre än eller lika med B") eller som likheter (t.ex. "storhet C ska exakt vara lika med D"). Det är avgörande att minst en av de funktioner som beskriver målet eller bivillkoren är icke-linjär. Ofta läggs även villkor om icke-negativitet till för variablerna, dvs. ett krav på att deras värden ska vara större än eller lika med noll.

Mängden av alla variabelvärdeuppsättningar som uppfyller bivillkoren bildar det tillåtna området (TA).

Skillnader från linjär programmering

Icke-linjär programmering skiljer sig väsentligt från linjär programmering (LP):

• Icke-linjäritet: Målfunktionen eller bivillkoren (eller båda) innehåller icke-linjära beroenden.
• Egenskaper hos TA: Det tillåtna området i NLP kan vara icke-konvext (till skillnad från LP, där TA alltid är en konvex polytop).
• Optimumets egenskaper: Den optimala lösningen i NLP befinner sig inte nödvändigtvis i ett hörn av TA — den kan ligga på gränsen eller inuti området. I NLP kan det förekomma lokala optima som inte är globala.
• Lösningskomplexitet: NLP-problem är i allmänhet betydligt svårare att lösa än LP-problem. Det finns ingen universell algoritm, liknande simplexmetoden, för alla NLP-problem.

Huvudsakliga svårigheter och utmaningar inom NLP

Lösning av icke-linjära programmeringsproblem är förenad med ett antal svårigheter:

• Förekomst av lokala extremvärden: De flesta NLP-metoder garanterar endast att ett lokalt optimum hittas (en lösning som är bäst i någon omgivning). Att finna det globala optimumet (den bästa lösningen i hela TA) är ett svårt problem, särskilt för icke-konvexa problem.
• Icke-konvexitet: Om problemet inte är konvext (målfunktionen eller TA är icke-konvexa) kan det finnas flera lokala optima, och standardgradientmetoder kan "fastna" i ett av dem.
• Beräkningskomplexitet: Algoritmer för NLP kräver ofta betydligt större beräkningsresurser jämfört med LP.

Viktiga klasser av NLP-problem

Trots den allmänna komplexiteten finns det viktiga underklasser av NLP-problem för vilka effektiva lösningsmetoder har utvecklats:

• Konvex programmering: Problemet att minimera en konvex funktion över en konvex mängd av tillåtna lösningar (eller att maximera en konkav funktion). Nyckelegenskap: varje lokalt minimum är även ett globalt minimum. Detta förenklar avsevärt sökandet efter den optimala lösningen.
• Kvadratisk programmering: Målfunktionen är kvadratisk och alla bivillkor är linjära.
• Separabel programmering: Målfunktionen och bivillkoren kan representeras som summor av funktioner, där var och en bara beror på en variabel.

Lösningsmetoder för NLP-problem

Lösningsmetoder för icke-linjära programmeringsproblem (NLP)

I. Metoder för obetingad optimering (optimering utan bivillkor):

• Gradientmetoder (metoden för brantaste nedstigning, metoden för konjugerade gradienter);
• Newtons metod och kvasinewtonska metoder (t.ex. BFGS);
• Metoder som använder approximation av Hessian.

II. Metoder för betingad optimering (optimering med bivillkor):

• Transformationsmetoder:
  • Straffunktionsmetoder (penalty methods);
  • Barriärfunktionsmetoder (barrier methods).
• Metoder för direkt riktningssökning:
  • Metoden för tillåtna riktningar.
• Metoder baserade på optimalitetsvillkor:
  • Karush-Kuhn-Tucker-metoder (KKT-villkor);
  • Lagrangemultiplikatormetoden.
• Iterativa metoder:
  • Sekventiell kvadratisk programmering (SQP);
  • Inrepunktsmetoder.

III. Metoder för global optimering:

• Heuristiska och metaheuristiska metoder:
  • Genetiska algoritmer;
  • Simulerad avkylning (imitation av härdning);
  • Tabu search.
• Deterministiska metoder:
  • Förgrening och begränsning (branch and bound);
  • Algoritmer för global optimering för problem med speciell struktur.

Litteratur

• Bazara M., Shetty C. Nonlinear Programming. Theory and Algorithms. — M.: Mir, 1982.
• Fiacco A., McCormick G. Nonlinear Programming. Sequential Unconstrained Minimization Techniques. — M.: Mir, 1972.
• Himmelblau D. Applied Nonlinear Programming. — M.: Mir, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

Se även

• Operationsanalys
• Optimering
• Linjär programmering
• Konvex programmering
• Målfunktion
• Bivillkor
• Tillåtet område