Ikke-lineær optimalisering

I optimalisering , sett på som en gren av matematikken , handler ikke-lineær optimalisering (på engelsk: nonlinear programming - NLP) hovedsakelig med optimaliseringsproblemer hvis data, dvs. funksjonene og settene som definerer disse problemene, er ikke-lineære, men kan også skille seg så mange ganger som nødvendig for etablering av teoretiske verktøy, slik som optimalitetsbetingelsene , eller for riktig funksjon av oppløsningsalgoritmene som blir introdusert og analysert deri. Denne subdisiplinen med optimalisering, med en dårlig definert grense og en noe kunstig innføring, har også sin eksistens knyttet til fellesskapet av forskere som har spesialisert seg på disse fagene og til den type resultater som er oppnådd.

Det utfyller ikke-jevn (eller ikke-differensierbar) optimalisering , som også er knyttet til et fellesskap av spesialiserte forskere. Disse to fag kommer sammen for å danne det som kalles kontinuerlig optimalisering , som i sin tur ligger inntil andre sub-disipliner som kombinatorisk (eller diskret) optimalisering, stokastisk optimalisering , etc. .

Matematisk formulering

Vi har en funksjon , med . Målet er å bestemme vektoren x definert av:

.

Tilsvarende kan vi finne verdien som f er maksimalt for:

.

Oppløsningsmetoder

Hvis funksjonen er konveks eller konkav , og settet med begrensninger er konveks, er det spesialiserte metoder, kalt konvekse optimaliseringsmetoder .

Ellers er det flere løsninger. For eksempel ved å bruke prinsippet om separasjon og evaluering for å dele og behandle flere parametere hver for seg.

Algoritmen kan også stoppes før den når suksess, hvis det kan bevises at ingen påfølgende løsning vil være bedre innenfor en viss toleranseterskel. De Karush-Kuhn-Tucker (KKT) betingelser at en således oppnådde løsning er optimal.

Vi bruker oppløsningsalgoritmer som:

Begrensninger

Hvis begrensningene uttrykkes i form av ulikheter

"logaritmisk barriere" -metoden kan brukes. Hvis ƒ er funksjonen som skal minimeres, definerer vi funksjonen

Når x nærmer seg grensen, vil verdien av ln ( h ) således ha en tendens til –∞ , som straffer området. Vi utfører flere søk ved å få μ til å gå mot 0.

Eksempler

I dimensjon 2

Et enkelt problem kan stilles som følger:

x 1 ≥ 0 x 2 ≥ 0 x 1 2 + x 2 2 ≥ 1 x 1 2 + x 2 2 ≤ 2

der vi prøver å maksimere funksjonen

f ( x 1 , x 2 ) = x 1 + x 2

I dimensjon 3

Vi kan formulere et problem som følger:

x 1 2 - x 2 2 + x 3 2 ≤ 2 x 1 2 + x 2 2 + x 3 2 ≤ 10

der vi prøver å maksimere funksjonen:

f ( x 1 , x 2 , x 3 ) = x 1 x 2 + x 2 x 3

Merknader og referanser

  1. Numerisk optimalisering , Mark S. Gockenbach, Michigan Tech

Se også

Relaterte artikler

Bibliografi

Eksterne linker

Dokumentasjon Implementeringer