Lexikografisk optimering

Lexikografisk optimering är en sorts multiobjektiv optimering . Generellt handlar multi-objektiv optimering om optimeringsproblem med två eller flera objektiva funktioner som ska optimeras samtidigt. Ofta kan de olika målen rangordnas efter betydelse för beslutsfattaren, så att mål $f_{1}$ är det viktigaste, mål $f_{2}$ är nästa viktigast och så vidare. Lexikografisk optimering förutsätter att beslutsfattaren föredrar ens en mycket liten ökning av ${\displaystyle f_{1}} ,$ till och med en mycket stor ökning av $f_{2}, f_{3},f_{4},$ etc. På liknande sätt föredrar beslutsfattaren även en mycket liten ökning av ${\displaystyle f_{2}} ,$ till och med en mycket stor ökning av $f_{3},f_{4},$ etc. Med andra ord har beslutsfattaren lexikografiska preferenser , rangordnar de möjliga lösningarna enligt en lexikografisk ordning av deras objektiva funktionsvärden. Lexikografisk optimering kallas ibland förebyggande optimering , eftersom en liten ökning av ett objektivt värde förebygger en mycket större ökning av mindre viktiga objektiva värden.

Som ett exempel, ta ett företag som sätter säkerheten framför allt. Så den vill maximera säkerheten för sina anställda och kunder. Med förbehåll för att uppnå maximal säkerhet vill den maximera vinsten. Detta företag utför lexikografisk optimering, där $f_{1}$ anger säkerhet och $f_{2}$ anger vinst.

Som ett annat exempel, inom projektledning, när man analyserar PERT- nätverk, vill man ofta minimera den genomsnittliga färdigställandetiden, och med förbehåll för detta, minimera variansen av färdigställandetiden.

Notation

Ett lexikografiskt maximeringsproblem skrivs ofta som:

$${\begin{aligned}\operatörsnamn {lex} \max &&f_{1}(x) ,f_{2}(x),\ldots ,f_{n}(x)\\{\text{med förbehåll för}}&&x\i X\end{aligned}}$$

där $f_{1},\ldots ,f_{n}$ är funktionerna som ska maximeras, ordnade från de viktigaste till de minst viktiga; $x$ är vektorn för beslutsvariabler; och $X$ är den möjliga uppsättningen - uppsättningen av möjliga värden för $x$ . Ett lexikografiskt minimeringsproblem kan definieras analogt.

Algoritmer

Det finns flera algoritmer för att lösa lexikografiska optimeringsproblem.

Sekventiell algoritm för allmänna mål

Ett leximinoptimeringsproblem med n mål kan lösas med hjälp av en sekvens av n optimeringsproblem med ett enda mål, enligt följande:

• För t = 1,...,n gör
  • Lös följande problem med ett enda mål:
    $${\begin{aligned}\max ~~~f_{t} (x)\\{\text{med förbehåll för}}~~~&x\i X,\\&f_{k}(x)\geq z_{k}{\text{ för alla }}k{\text{ i }}1,\ldots ,t-1.\end{aligned}}$$
  • Om problemet är omöjligt eller obegränsat, sluta och förklara att det inte finns någon lösning.
  • Annars sätter du värdet för den optimala lösningen i $z_{t}$ och fortsätt.
• Slut för

Så i den första iterationen hittar vi det maximala möjliga värdet för det viktigaste målet ${\displaystyle f_{1}(x)} ,$ och sätter detta maximala värde i $z_{1}$ . I den andra iterationen hittar vi det maximalt genomförbara värdet för det näst viktigaste målet ${\displaystyle f_{2}(x)} ,$ med den ytterligare begränsningen att det viktigaste målet måste behålla sitt maximala värde på $z_{1}$ ; och så vidare.

Den sekventiella algoritmen är generell - den kan tillämpas närhelst vi har en lösare för funktionerna med ett mål.

Lexikografisk simplexalgoritm för linjära mål

Linjär lexikografisk optimering är ett specialfall av lexikografisk optimering där målen är linjära och den genomförbara uppsättningen beskrivs av linjära ojämlikheter. Det kan skrivas som:

$${\begin{aligned}\operatörsnamn {lex} \max &&c_{1}\ cdot x,c_{2}\cdot x,\ldots ,c_{n}\cdot x\\{\text{med förbehåll för}}&&A\cdot x\leq b,x\geq 0\end{aligned}}$$

där $c_{1},\ldots ,c_{n}$ är vektorer som representerar de linjära målen att maximera, ordnade från de mest till de minst viktiga; $x$ är vektorn för beslutsvariabler; och den möjliga mängden bestäms av matrisen $A$ och vektorn $b$ .

Isermann utökade teorin om linjär programmeringsdualitet till lexikografiska linjära program och utvecklade en lexikografisk simplexalgoritm . I motsats till den sekventiella algoritmen, tar denna simplexalgoritm alla objektiva funktioner samtidigt.

Vägt medelvärde för linjära mål

Sherali och Soyster bevisar att det för alla linjära lexikografiska optimeringsproblem finns en uppsättning vikter $w_{1}>w_{2}>\cdots >w_{n}$ så att uppsättningen av lexikografiskt optimala lösningar är identisk med uppsättningen av lösningar på följande enobjektiva problem:

$${\begin{aligned}\max &&w_{1}f_{1}(x)+\cdots +w_ {n}f_{n}(x)\\{\text{subject to}}&&x\in X\end{aligned}}$$

Om vi ​​kunde beräkna dessa vikter skulle vi kunna reducera det lexikografiska optimeringsproblemet till ett optimeringsproblem med ett enda mål. Det kan dock vara svårare att hitta dessa vikter än att lösa problemet med den sekventiella algoritmen; därför hävdar författarna att deras metod huvudsakligen är av teoretiskt intresse.

Cococcioni, Pappalardo och Sergeyev visar att, givet en dator som kan göra numeriska beräkningar med infinitesimals , är det möjligt att välja vikter som är infinitesimals (specifikt: $w_{1}=1$ ; ${\ displaystyle w_{2}}$ är infinitesimal; $w_{3}$ är infinitesimal-kvadrat, etc.), och reducerar därmed linjär lexikografisk optimering till enobjektiv linjär programmering med infinitesimaler. De presenterar en anpassning av simplexalgoritmen till infinitesimals, och presenterar några löpande exempel.

Egenskaper

(1) Unikhet . I allmänhet kan ett lexikografisk optimeringsproblem ha mer än en optimal lösning. Men om $x^{1}$ och $x^{2}$ är två optimala lösningar, måste deras värde vara detsamma, det vill säga $f_{i}(x^{1})=f_{i}(x^{2})$ för alla $i\in [n]$ . Dessutom, om den genomförbara domänen är en konvex uppsättning , och de objektiva funktionerna är strikt konkava , så har problemet högst en optimal lösning, eftersom om det fanns två olika optimala lösningar, skulle deras medelvärde vara en annan genomförbar lösning där objektivet fungerar. uppnå ett högre värde - vilket motsäger optimaliteten hos de ursprungliga lösningarna.

(2) Delbelopp . Givet en vektor $f_{1},\ldots ,f_{n}$ av funktioner för att optimera, för alla t i 1,..., n , definiera $f_{1..t}:=\summa _{i=1}^{t}f_{i}$ = summan av alla funktioner från den viktigaste till t - det viktigaste. Då är det ursprungliga lexikografiska optimeringsproblemet likvärdigt med följande:

$${\begin{aligned}\operatörsnamn {lex } \max &&f_{1...1}(x),f_{1..2}(x),\ldots ,f_{1..n}(x)\\{\text{med förbehåll för}}&&x \in X\end{aligned}}$$

I vissa fall kan det andra problemet vara lättare att lösa.

Se även

• Lexikografisk max-min-optimering är en variant av lexikografisk optimering där alla mål är lika viktiga, och målet är att maximera det minsta målet, sedan det näst minsta målet, och så vidare.
• I spelteorin definieras kärnan som en lexikografiskt-minimal lösningsuppsättning.