Binivåoptimering

Binivåoptimering är en speciell typ av optimering där ett problem är inbäddat (kapslat) i ett annat. Den yttre optimeringsuppgiften hänvisas vanligen till som optimeringsuppgiften på den övre nivån, och den inre optimeringsuppgiften hänvisas vanligen till som optimeringsuppgiften på lägre nivå. Dessa problem involverar två typer av variabler, kallade variabler på övre nivå och variabler på lägre nivå.

Matematisk formulering av problemet

En allmän formulering av bilevel-optimeringsproblemet kan skrivas på följande sätt:

$\min \limits _{x\in X,y\in Y}\;\;F(x,y)$

föremål för: ${\displaystyle G_{i}(x,y)\leq 0} ,$ för $i\in \{1, 2,\ldots ,I\}$

$y\in \arg \min \limits _ {z\in Y}\{f(x,z):g_{j}(x,z)\leq 0,j\in \{1,2,\ldots ,J\}\}$

var

$F,f:R^{n_{x}}\ gånger R^{n_{y}}\to R$

${\displaystyle G_{i},g_{j}:R^{n_{x}}\ gånger R^{n_{y}}\to R} X ⊆$

$displaystyle X\subseteq R^{n_{x}}}$

$Y\subseteq R^{n_{y}}.$

I ovanstående formulering representerar $F$ den övre nivåns objektivfunktion och $f$ representerar den lägre nivån av objektivfunktionen. På liknande sätt $x$ beslutsvektorn på den övre nivån och $y$ representerar beslutsvektorn på lägre nivå. $G_{i}$ och $}}$ representerar funktionerna för ojämlikhetsbegränsningar på de övre respektive nedre nivåerna. Om någon objektiv funktion ska maximeras är det lika med att minimera dess negativa. Formuleringen ovan är också kapabel att representera likhetsbegränsningar, eftersom dessa lätt kan skrivas om i termer av ojämlikhetsbegränsningar: till exempel $h(x)=0$ översättas till $\{h(x)\leq 0,\ -h(x)\leq 0\}$ . Men det är vanligtvis värt att behandla jämställdhetsbegränsningar separat, för att hantera dem mer effektivt på ett dedikerat sätt; i framställningen ovan har de för korthets skull utelämnats.

Stackelbergstävling

Huvudartikel: Stackelbergtävling

Binivåoptimering realiserades först inom spelteorin av en tysk ekonom Heinrich Freiherr von Stackelberg som publicerade Market Structure and Equilibrium (Marktform und Gleichgewicht) 1934 som beskrev detta hierarkiska problem. Det strategiska spelet som beskrivs i hans bok kom att kallas Stackelberg-spelet som består av en ledare och en följare. Ledaren kallas vanligtvis för en Stackelberg-ledare och anhängaren kallas vanligtvis för en Stackelberg-följare. I ett Stackelberg-spel tävlar spelets spelare med varandra, så att ledaren gör det första draget, och sedan reagerar följaren optimalt på ledarens agerande. Denna typ av hierarkiska spel är asymmetriskt till sin natur, där ledaren och anhängaren inte kan bytas ut. Ledaren vet på förhand att följaren observerar dess handlingar innan han svarar på ett optimalt sätt. Därför, om ledaren vill optimera sitt mål, måste den förutse följarens optimala svar. I den här inställningen innehåller ledarens optimeringsproblem en kapslad optimeringsuppgift som motsvarar följarens optimeringsproblem. I Stackelberg-spelen kallas optimeringsproblemet på den övre nivån vanligtvis som ledarproblemet och optimeringsproblemet på den lägre nivån brukar kallas för följarens problem.

Om följaren har mer än ett optimalt svar på ett visst urval av ledaren finns det två möjliga alternativ: antingen den bästa eller den sämsta följarens lösning med avseende på ledarens objektiva funktion antas, dvs följaren antas agera antingen i ett kooperativt sätt eller på ett aggressivt sätt. Det resulterande binivåproblemet kallas optimistiskt binivåprogrammeringsproblem eller pessimistiskt binivåprogrammeringsproblem .

Ansökningar

Binivåoptimeringsproblem finns vanligtvis i ett antal verkliga problem. Detta inkluderar problem inom området transport , ekonomi , beslutsvetenskap , företag , teknik , miljöekonomi etc. Några av de praktiska binivåproblem som studeras i litteraturen diskuteras kort.

Problem med inställning av vägtull

Inom transportområdet förekommer dubbelnivåoptimering vanligtvis i problemet med vägtullsättning. Överväg ett nätverk av motorvägar som drivs av regeringen. Regeringen vill maximera sina intäkter genom att välja den optimala vägavgiftsinställningen för motorvägarna. Regeringen kan dock maximera sina intäkter endast genom att ta hänsyn till motorvägstrafikanternas problem. För en given skattestruktur löser väganvändarna sina egna optimeringsproblem, där de minimerar sina resekostnader genom att välja mellan att använda motorvägarna eller en alternativ väg. Under dessa omständigheter måste regeringens problem formuleras som ett dubbelt optimeringsproblem. Den övre nivån utgörs av regeringens mål och begränsningar och den nedre nivån utgörs av vägtrafikanternas mål och begränsningar för en given skattestruktur. Det är anmärkningsvärt att regeringen kommer att kunna identifiera intäkterna som genereras av en viss skattestruktur endast genom att lösa problemet på lägre nivå som avgör i vilken utsträckning motorvägarna används.

Strukturell optimering

Strukturella optimeringsproblem består av två nivåer av optimeringsuppdrag och kallas vanligtvis matematiska programmeringsproblem med jämviktsbegränsningar ( MPEC ). Det övre målet i sådana problem kan innebära kostnadsminimering eller viktminimering med förbehåll för gränser för förskjutningar, spänningar och kontaktkrafter. Beslutsvariablerna på den övre nivån är vanligtvis strukturens form, materialval, materialmängd etc. För varje given uppsättning av övernivåvariabler kan dock tillståndsvariablerna (förskjutning, spänningar och kontaktkrafter) bara räknas ut. genom att lösa det potentiella energiminimeringsproblemet som framstår som en jämviktstillfredsställelserestriktion eller lägre nivåminimeringsuppgift till problemet på den övre nivån.

Försvarsansökningar

Binivåoptimering har ett antal tillämpningar inom försvaret, som strategisk design av offensiv och defensiv styrka, strategisk bombplansstyrka och allokering av taktiska flygplan till uppdrag. Den offensiva enheten i det här fallet kan betraktas som en ledare och den defensiva enheten i det här fallet kan anses vara en följare. Om ledaren vill maximera skadan på motståndaren, så kan det bara uppnås om ledaren tar hänsyn till följarens reaktioner. En rationell följare kommer alltid att reagera optimalt på ledarnas offensiv. Ledarens problem framstår därför som en optimeringsuppgift på den övre nivån, och det optimala svaret från följaren på ledarens handlingar bestäms genom att lösa optimeringsuppgiften på lägre nivå.

Ansökningar om personal och personal

Binivåoptimering kan fungera som ett beslutsstödsverktyg för företag i verkliga miljöer för att förbättra besluten om personalstyrka och personal. Den första nivån speglar företagets mål att maximera lönsamheten. Den andra nivån återspeglar medarbetarnas mål att minimera klyftan mellan önskad lön och en föredragen arbetsplan. Bilevel-modellen ger en exakt lösning baserad på en blandad heltalsformulering och presenterar en beräkningsanalys baserad på förändrade anställdas beteenden som svar på företagets strategi, och visar på så sätt hur problemets parametrar påverkar beslutspolicyn.

Lösningsmetoder

Binivåoptimeringsproblem är svåra att lösa. En lösningsmetod är att omformulera dubbelnivåoptimeringsproblem till optimeringsproblem för vilka robusta lösningsalgoritmer finns tillgängliga. Extended Mathematical Programming (EMP) är ett tillägg till matematiska programmeringsspråk som tillhandahåller flera nyckelord för problem med binivåoptimering. Dessa anteckningar underlättar den automatiska omformuleringen till matematiska program med jämviktsbegränsningar ( MPEC) för vilka det finns mogen lösningsteknik. EMP är tillgängligt inom GAMS .

KKT omformulering

Vissa binivåprogram, särskilt de som har en konvex lägre nivå och som uppfyller ett regularitetstillstånd (t.ex. Slaters tillstånd ), kan omformuleras till en nivå genom att ersätta problemet på lägre nivå med dess Karush-Kuhn-Tucker-tillstånd . Detta ger ett matematiskt program på en nivå med komplementaritetsbegränsningar, dvs MPEC. Om problemet på lägre nivå inte är konvext, med detta tillvägagångssätt förstoras den möjliga uppsättningen av bilevel-optimeringsproblemet med lokala optimala lösningar och stationära punkter på den lägre nivån, vilket innebär att det ennivåproblem som erhålls är en relaxation av den ursprungliga bileveln problem.

Optimal värdeomformulering

Betecknar med

$\phi (x)=\min \ gränser _{z\in Y}\{f(x,z):g_{j}(x,z)\leq 0,j\in \{1,2,\ldots ,J\}\}$

den så kallade optimala värdefunktionen , en möjlig ennivåomformulering av bilevelproblemet är

$\min \limits _{x\in X,y\in Y}\;\;F(x,y)$

föremål för: ${\displaystyle G_{i}(x,y)\leq 0} ,$ för $i\in \{1, 2,\ldots ,I\}$

$g_{j}(x,y)\leq 0,j\in \{1,2,\ldots ,J\ }$

$f(x,y)\leq \phi (x).$

Detta är ett ojämnt optimeringsproblem eftersom den optimala värdefunktionen i allmänhet inte är differentierbar, även om alla begränsningsfunktioner och objektivfunktionen i problemet på lägre nivå är jämna.

Heuristiska metoder

För komplexa dubbelnivåproblem kan klassiska metoder misslyckas på grund av svårigheter som icke-linjäritet , diskretitet , icke- differentiering , icke- konvexitet etc. I sådana situationer kan heuristiska metoder användas. Bland dem utgör evolutionära metoder, även om de är beräkningskrävande, ofta ett alternativt verktyg för att kompensera några av dessa svårigheter som man stöter på med exakta metoder, om än utan att erbjuda någon optimalitetsgaranti för de lösningar de producerar.

Multi-objektiv bilevel optimering

Ett binivåoptimeringsproblem kan generaliseras till ett multiobjektivt binivåoptimeringsproblem med flera mål på en eller båda nivåerna. Ett allmänt multi-objektiv bilevel optimeringsproblem kan formuleras enligt följande:

$\min \limits _ {x\in X,y\in Y}\;\;F(x,y)=(F_{1}(x,y),F_{2}(x,y),\ldots ,F_{p} (x,y))$ I Stackelberg-spelen: Ledarproblem

föremål för: ${\displaystyle G_{i}(x,y)\leq 0} ,$ för $i\in \{1, 2,\ldots ,I\}$ ;

$y\in \arg \min \limits _{z\in Y}\{f(x,z)=(f_{1}(x ,z),f_{2}(x,z),\ldots ,f_{q}(x,z)):g_{j}(x,z)\leq 0,j\in \{1,2, \ldots ,J\}\}$ I Stackelberg-spelen: Följerproblem

var

$F:R^{n_{x}}\ gånger R^{n_{y}}\to R^{p}$

$f:R^{n_{x}}\ gånger R^{n_{y}}\to R^{q}$

${\displaystyle G_{i},g_{j}:R^{n_{x}}\ gånger R^{n_{y}}\to R} X ⊆ R n x {\displaystyle$

${ n_{x}}}$

$Y\subseteq R^{n_{y}}.$

I ovanstående formulering representerar $F$ den övre nivån av objektivvektorn med $p$ -objektiv och $f$ representerar den lägre nivån av objektivvektorn med $q$ -objektiv. På liknande sätt $x$ beslutsvektorn på den övre nivån och $y$ representerar beslutsvektorn på lägre nivå. $G_{i}$ och $}}$ representerar funktionerna för ojämlikhetsbegränsningar på de övre respektive nedre nivåerna. Jämlikhetsbegränsningar kan också förekomma i ett binivåprogram, men de har utelämnats för korthetens skull.

externa länkar

• Ordlista för matematisk programmering