• hjem
  •  > 
  • Systemadministrasjon
  •  > 
  • Økonomiske tolkninger av Kuhn Tucker-vektoren. Formulering og bevis på Kuhn-Tucker-teoremet

Økonomiske tolkninger av Kuhn Tucker-vektoren. Formulering og bevis på Kuhn-Tucker-teoremet

Den sentrale plassen i teorien om ikke-lineær programmering er okkupert av Kuhn-Tucker-teoremet. La et ikke-lineært programmeringsproblem gis:

finne maksimal verdi funksjoner Z=f(x 1, x 2, ..., x n) med restriksjoner

La oss komponere Lagrange-funksjonen for dette problemet:

(4.2)

Hvis regularitetsbetingelsen er oppfylt (eksisterer iht i det minste Et poeng X, for hvilket g i(X)>0 for alle Jeg), så gjelder følgende teorem.

Teorem. Vektor X(0) hvis og bare hvis er en optimal løsning på problem (4.1) når det eksisterer en vektor Λ (0) slik at når for alle

Punktum ( X (0),Λ (0)) kalles sal punkt for funksjon F(X,Λ), og teoremet kalles setepunktssetningen. La oss bevise at betingelsene er tilstrekkelige (4.3).

Bevis. La X(0) >0 og Λ (0) >0 - setepunkt for funksjonen F(X,Λ). Hvis i (4.3) i stedet F(X,Λ) erstatte dens verdi (4.2), får vi

på .

Den rette ulikheten er derfor gyldig for alle

Så fra venstre ulikhet får vi

Siden i dette tilfellet

At f(X (0))>f(X).

Så poenget X (0) tilfredsstiller (4.1) og på alle andre punkter som tilfredsstiller (4.1), tar funksjonen en verdi mindre enn ved X (0).

Denne uttalelsen leder løsningen av NLP-problemet til å finne setepunktene til Lagrange-funksjonen F(X,Λ).

Beviset for nødvendigheten av betingelsene (4.3) vurderes ikke på grunn av dets kompleksitet.



Hvis f(X) Og g i(X)-differensierbare funksjoner, så tilsvarer betingelsene (4.3) de følgende lokale Kuhn-Tucker-forholdene:

Uttrykk

betyr at verdien av den partielle deriverte av Lagrange-funksjonen tas ved punktet ( X (0), Λ (0)), hvor

X (0)=(x 1 (0) , x 2 (0) , ..., x n(0)), Λ (0) =(λ 1 (0) , λ 2 (0) , ..., λ n (0)).

Disse betingelsene kan skrives inn vektorform:

Eksempel. Finn maks Z=-x 1 2 -x 2 2 med restriksjoner

La oss vise at det eksisterer Λ (0) 0 for hvilke Kuhn-Tucker-betingelsene (4.4), (4.5) for funksjonen er oppfylt på det optimale punktet F(X,Λ):

F(X,Λ)=- x 1 2 -x 2 2 +λ 1 (2 x 1 +x 2-2)+A2 (8-2 x 1 -x 2)+λ 3 (6- x 1 -x 2).

I henhold til betingelsene (4.5) skal λ 2 og λ 3 ta null verdier, siden, erstatte x 1 = 0,8 og x 2 = 0,4 i uttrykk

vi har verdier større enn null, og etter tilstand

I henhold til betingelsen kan λ 1 ha en verdi som ikke er null, siden

I samsvar med (2.16), den deriverte

må ta null verdier, siden koordinatene til vektoren X (0) er forskjellig fra null. Vi finner λ 1 =0,8. Derfor, på punktet ( X (0),Λ (0)) Kuhn-Tucker-forholdene er oppfylt, og det er virkelig et ekstremumpunkt.

La oss vurdere Kuhn-Tucker-forholdene i en litt annen form.

La oss ha et optimaliseringsproblem med begrensninger i form av likheter:

z= f(x 1 , x 2 , …, xn) → min

under forhold:

g 1 ( x 1 , x 2 , ... , x n) = 0,

g 2 ( x 1 , x 2 , ... , x n) = 0,

g n(x 1 , x 2 , . . . , x n) = 0.

Betinget minimumspunkt for funksjonen f faller sammen med setepunktet til Lagrange-funksjonen:

I dette tilfellet må setepunktet gi et minimum i sine variabler x i og maksimum over variablene λ j.

Nødvendige betingelser for et stasjonært punkt er at partielle deriverte av første orden med hensyn til alle variabler er lik null:

Merk at den andre ligningen innebærer at bare gyldige poeng vil tilfredsstille de nødvendige betingelsene.

For å få tilstrekkelig tilstand eksistensen av et minimum, er det nødvendig å legge til kravet om at hessiske skal være positivt bestemt objektiv funksjon.

La oss vurdere generell oppgave matematisk programmering:

Z= f(X) → min,

under forhold:

Ulikhetsbegrensninger kan konverteres til likhetsbegrensninger ved å legge til hver av dem svekkelse variabler

La oss danne Lagrange-funksjonen:

Deretter nødvendige forhold minimum har formen:

Den andre ligningen kan transformeres ved å forkaste de dempende variablene og gå over til ulikhetsbegrensninger. La oss få tak i begrensningene for det opprinnelige problemet. Den tredje ligningen kan multipliseres med ui/2 og erstatte svekkelsesvariablene ved å uttrykke dem fra den andre ligningen i systemet.

Det er ett vilkår til som må være oppfylt på minimumspunktet. Denne tilstanden: λ Jeg= 0, som er en konsekvens av analysen fysisk mening koeffisientene til Lagrange-funksjonen.

Det kan vises

Lagrange koeffisient ved minimumspunktet;

f* - optimal verdi funksjoner.

Selvfølgelig, ettersom b øker Jeg den tillatte regionen utvides, noe som betyr at minimumsverdi kan bare avta, det vil si at den deriverte må være negativ (ikke-positiv). Derfor på det betingede minimumspunktet

Vi får endelig de nødvendige betingelsene for det betingede minimum:

Uttrykkene i den andre linjen sikrer at det optimale punktet er gyldig.

Den tredje linjen inneholder følgende informasjon: hvis begrensningen er aktiv (dvs. uttrykket i parentes er lik null), så er den tilsvarende Lagrange-koeffisienten strengt tatt positiv. Positiviteten til Lagrange-koeffisienten betyr at den tilsvarende begrensningen er aktiv, dvs. det faktum at denne begrensningen er knapp er nettopp det som stopper ytterligere forbedring målfunksjon. Hvis begrensningen ikke er aktiv (dvs. uttrykket i parentes er ikke lik null), bør den tilsvarende Lagrange-koeffisienten være lik null, dvs. Denne begrensningen er ikke mangelfull; den påvirker ikke ytterligere forbedring av målfunksjonen.

For det betingede maksimumspunktet endrer Lagrange-koeffisientene fortegn til det motsatte (siden den optimale verdien av objektivfunksjonen ved det betingede maksimumspunktet bør øke).

Betingelsene ovenfor er likeverdige Kuhn-Tuckers teorem og kalles ofte det samme.

En tilstrekkelig betingelse for et minimum (maksimum) er konveksiteten (konkavitet) til objektivfunksjonen på et stasjonært punkt. Dette betyr at hessian må være positiv (negativ) bestemt.

Et sammendrag av materialet i dette kapittelet kan sees i to presentasjoner:

fil "Ikke-lineær programmering";

fil "Kuhn-Tucker Theorem".

Lysbilde 10-14 av presentasjonen "Kuhn-Tucker-teorem" viser et eksempel på løsning av Kuhn-Tucker-problemet.

4.5. Kontrollspørsmål

(Utviklet av Afanasyev M.Yu. og Suvorov B.P.)

Spørsmål 1. Gitt en gyldig funksjon f(X S= . La X 1 og X 2 - poeng av dette segmentet og 0 £ l £ 1.

Hvilken av følgende ulikheter er en betingelse for konveksiteten til en funksjon?

Mulige svar:

Spørsmål 2. Gitt en gyldig funksjon f(x), definert på segmentet av reelle tall S=. La x 1 og x 2 er poengene til dette segmentet og 0 £ l £ 1.

Hvilken av følgende ulikheter er en betingelse for at en funksjon skal være strengt konkavitet?

Mulige svar:

Spørsmål 3. Funksjon

1) konveks;

2) strengt konveks;

3) konkav;

4) strengt konkav;

5) konveks og konkav.

Spørsmål 4. Funksjon

3) konkav; 4) strengt konkav;

5) konveks og konkav.

Spørsmål 5. Funksjon

1) konveks; 2) verken konveks eller konkav;

3) strengt konveks; 4) konkav:

5) konveks og konkav.

Spørsmål 6. Ny modell høyhastighets motorsykkel "Snail" selges av selskapet til en pris på (30 – 2 x) tusen dollar per stykke, hvor X- antall solgte motorsykler. Variable produksjonskostnader er $6 000 per enhet og faste kostnader er $30 000. Maksimer bedriftens fortjeneste for uken.

La oss si at endringen i omsetningsavgiftssatsen resulterte i ytterligere $4000 i merverdiavgift for hver solgte motorsykkel.

Hvordan vil den optimale produksjonen av motorsykler endre seg sammenlignet med utgangssituasjonen?

(Løs ved hjelp av Lagrange-funksjonen.)

Mulige svar:

1) vil øke med 2 ; 2) vil reduseres med 2 ;

3) vil ikke endre seg; 4) vil øke med 1 ;

5) vil reduseres med 1 .

Spørsmål 7. La oss anta at du har 2 uker (14 dager) ferie å tilbringe på Kanariøyene og Nice. La verktøyfunksjonen din ha form 2 KN – 3K 2 – 4N 2, Hvor TIL Og N- antall dager du tilbringer på henholdsvis Kanariøyene og Nice.

Hvor mange dager bør du tilbringe i Nice for å maksimere nyttefunksjonen din?

(For å løse, bruk Lagrange-funksjonen. Avrund resultatet til nærmeste heltall. Sjekk om Kuhn-Tuckers optimalitetsbetingelser er oppfylt.)

Mulige svar:

1) 3 ; 2) 4 ; 3) 5 ; 4) 6 ; 5) 7 .

Spørsmål 8. For oppgaven i spørsmål 7, finn verdien av det doble estimatet av begrensningen.

(Rund resultatet til nærmeste heltall.)

Mulige svar:

1) 41 ; 2) 34; 3) 29 ; 4) 39 ; 5) 44 .

Spørsmål 9. Monopolisten planlegger et produksjons- og salgsprogram for neste periode. Priser: R 1 = 14 – 0,25x 1 (per produkt 1); R 2 = 14 – 0,5X 2 (per produkt 2), hvor x 1 og X 2 - salgsvolum av produkter. La oss anta at alle produserte produkter selges. Maksimalt totale salgsvolum er 57.

Hva er den optimale utgivelsen av produkt 2?

Mulige svar:

1) 36,4 ; 2) 30,7 ; 3) 26,3 ; 4) 20,6 ; 5) 41,8 .

Spørsmål 10. Eieren av et lite foretak har 100 tusen rubler for neste måned, som han kan bruke på å øke anleggsmidler TIL(kjøp av utstyr) til en pris på 1 tusen rubler per enhet eller for kjøp av ekstra arbeidskraft L til en pris av 50 rub./time. Økning i ferdige produkter som kan selges for 10 tusen rubler. per enhet, bestemt av produksjonsfunksjonen F(K, L)= L 2/7 K 2/5.

Hvor mye penger bør brukes på å øke anleggsmidler?

Mulige svar:

1) 74,36 tusen gni.; 2) 58,33 tusen rubler.; 3) 63,44 tusen rubler.;

4) 45,66 tusen rubler.; 5) 39,77 tusen rubler.

Svar på spørsmål:

1 -4,2 - 1,3 -4,4 - 5,

5 -2, 6 -5,7- 4,8- 2,9- 4,10- 2.

I forrige avsnitt ble Kuhn-forholdene konstruert-Tucker for oppgaver betinget optimalisering. Ved å bruke Lagrange multiplikatormetoden ble det oppnådd en intuitiv idé om at Kuhn-Tanker-forholdene er nært knyttet til de nødvendige optimalitetsforholdene. I denne seksjonen Det vurderes strenge formuleringer av nødvendige og tilstrekkelige betingelser for optimal løsning av et ikke-lineært programmeringsproblem.

Teorem 1. Nødvendigheten av Kuhn-Tucker-betingelsene

La oss vurdere det ikke-lineære programmeringsproblemet (0) - (2). La være differensierbare funksjoner, og x* være en tillatt løsning på dette problemet. La oss si det. Videre, la dem være lineært uavhengige. Hvis x* - optimal løsning ikke-lineært programmeringsproblem, så eksisterer det et par vektorer som er en løsning på Kuhn-Tucker-problemet (3) - (7).

Betingelsen om at de må være lineært uavhengige er kjent som tilstanden lineær uavhengighet og representerer i hovedsak en eller annen regularitetstilstand gyldig område, som nesten alltid er tilfredsstilt for optimaliseringsproblemer som oppstår i praksis. Generelt er det imidlertid svært vanskelig å sjekke om betingelsen for lineær uavhengighet er oppfylt, siden det kreves at den optimale løsningen på problemet er kjent på forhånd. Samtidig er betingelsen for lineær uavhengighet alltid oppfylt for ikke-lineære programmeringsproblemer som har følgende egenskaper.

  • 1. Alle restriksjoner i form av likheter og ulikheter inneholder lineære funksjoner.
  • 2. Alle ulikhetsbegrensninger inneholder konkave funksjoner, alle likhetsbegrensninger inneholder lineære funksjoner, og det er minst ett mulig punkt x, som er lokalisert i det indre av regionen definert av ulikhetsbegrensningene. Med andre ord, det er et punkt x slik at

Hvis betingelsen for lineær uavhengighet på det optimale punktet ikke er oppfylt, kan det hende at Kuhn-Tucker-problemet ikke har en løsning.

Minimer

under restriksjoner

I fig. 1 område vist tillatte løsninger ikke-lineært problem formulert ovenfor. Det er klart at det finnes en optimal løsning på dette problemet. La oss vise at betingelsen for lineær uavhengighet ikke er oppfylt på det optimale punktet.

Ris.

Det er lett å se at vektorene er lineært avhengige, dvs. betingelsen for lineær uavhengighet på punktet er ikke oppfylt.

La oss skrive ned Kuhn-Tucker-betingelsene og sjekke om de er oppfylt ved punkt (1, 0). Betingelsene (3), (6) og (7) har følgende form;

At, følger det av ligning (11) at mens ligning (14) gir, Derfor er det optimale punktet ikke et Kuhn-Tucker-punkt.

Merk at brudd på den lineære uavhengighetsbetingelsen ikke nødvendigvis betyr at Kuhn-Tucker-punktet ikke eksisterer. For å bekrefte dette, la oss erstatte objektivfunksjonen fra dette eksemplet med funksjonen. I dette tilfellet oppnås det optimale fortsatt ved punkt (1,0), hvor betingelsen for lineær uavhengighet ikke er oppfylt. Kuhn-Tucker-forholdene (12) - (16) forblir uendret, og ligning (11) har formen

Det er lett å sjekke at punktet er et Kuhn-Tucker-punkt, dvs. tilfredsstiller Kuhn-Tucker-betingelsene.

Teoremet om nødvendigheten av Kuhn-Tucker-forholdene lar oss identifisere ikke-optimale punkter. Med andre ord kan teorem 1 brukes til å bevise at et gitt gjennomførbart punkt som tilfredsstiller den lineære uavhengighetsbetingelsen ikke er optimal hvis det ikke tilfredsstiller Kuhn-Tucker-betingelsene. På den annen side, hvis Kuhn-Tucker-forholdene på dette tidspunktet er oppfylt, er det ingen garanti for at den optimale løsningen på det ikke-lineære problemet er funnet. Som et eksempel kan du vurdere følgende ikke-lineære programmeringsproblem.

Følgende teorem etablerer betingelsene under hvilke Kuhn-Tucker-punktet automatisk tilsvarer den optimale løsningen på et ikke-lineært programmeringsproblem.

Teorem 2. Tilstrekkelighet av Kuhn-Tucker-betingelsene

La oss vurdere det ikke-lineære programmeringsproblemet (0) - (2). La den objektive funksjonen være konveks, alle ulikhetsbegrensninger inneholder konkave funksjoner, og likhetsbegrensninger inneholder lineære funksjoner. Så hvis det er en løsning som tilfredsstiller Kuhn-Tucker-betingelsene (3) - (7), så er x* den optimale løsningen på det ikke-lineære programmeringsproblemet.

Hvis betingelsene i teorem 2 er oppfylt, gir det å finne Kuhn-Tucker-punktet en optimal løsning på det ikke-lineære programmeringsproblemet.

Teorem 2 kan også brukes til å bevise optimaliteten denne avgjørelsen ikke-lineære programmeringsproblemer. For å illustrere, tenk på eksemplet igjen:

Minimer

under restriksjoner

Ved hjelp av teorem 2 beviser vi at løsningen er optimal. Vi har

Siden matrisen er positiv semibestemt for alle x, viser funksjonen seg å være konveks. Den første ulikhetsbegrensningen inneholder lineær funksjon, som er både konveks og konkav på samme tid. For det

for å vise at funksjonen er konkav, regner vi

Fordi matrisen er negativ bestemt, er funksjonen konkav. Funksjonen er inkludert i den lineære begrensningen i likhet. Følgelig er alle betingelsene i teorem 2 oppfylt; hvis vi viser at det er Kuhn-Tucker-punktet, vil vi faktisk fastslå optimaliteten til løsningen. Kuhn-Tucker-betingelsene for eksempel 2 har formen

Punktet tilfredsstiller begrensningene (24) - (26) og er derfor tillatt. Ligningene (22) og (23) har følgende form:

Setter vi det, får vi og. Dermed tilfredsstiller løsningen x*=(1, 5) Kuhn-Tucker-betingelsene. Siden betingelsene i teorem 2 er oppfylt, er den optimale løsningen på problemet fra eksempel 3. Merk at det også finnes andre verdier av og som tilfredsstiller system (22) - (29).

Notater

  • 1. For problemer som oppstår i praksis, er betingelsen om lineær uavhengighet vanligvis oppfylt. Hvis alle funksjoner i problemet er differensierbare, bør Kuhn-Tucker-punktet betraktes som mulig poeng optimal. Dermed konvergerer mange av de ikke-lineære programmeringsmetodene til Kuhn-Tucker-punktet. (Her er det på sin plass å trekke en analogi med saken ubetinget optimalisering, når de tilsvarende algoritmene lar en bestemme et stasjonært punkt.)
  • 2. Hvis betingelsene i teorem 2 er oppfylt, viser Kuhn-Tucker-punktet seg samtidig å være et globalt minimumspunkt. Dessverre er det svært vanskelig å kontrollere tilstrekkelige forhold, og i tillegg har anvendte problemer ofte ikke de nødvendige egenskapene. Det skal bemerkes at tilstedeværelsen av minst én ikke-lineær begrensning i form av likhet fører til et brudd på forutsetningene i teorem 2.
  • 3. De tilstrekkelige betingelsene etablert av setning 2 kan generaliseres til problemer med ikke-konvekse funksjoner inkludert i begrensninger i form av ulikheter, ikke-konvekse objektive funksjoner og ikke-lineære likhetsbegrensninger. I dette tilfellet brukes slike generaliseringer av konvekse funksjoner som kvasi-konvekse og pseudo-konvekse funksjoner.

Teorem 7.2. For det konvekse programmeringsproblemet (7.4)–(7.6), hvis sett med tillatte løsninger har regularitetsegenskapen, er planen optimal plan hvis og bare hvis det finnes en vektor slik at
– setepunkt for Lagrange-funksjonen.

Forutsatt at den objektive funksjon
og funksjoner er kontinuerlige og differensierbare, så kan Kuhn-Tucker-teoremet suppleres med analytiske uttrykk som bestemmer nødvendig og tilstrekkelig betingelse for punktet
var setepunktet for Lagrange-funksjonen, dvs. var en løsning på det konvekse programmeringsproblemet. Disse uttrykkene har følgende form:

Hvor Og er verdiene til de tilsvarende partielle deriverte av Lagrange-funksjonen beregnet på setepunktet.

Kuhn-Tucker-teoremet inntar en sentral plass i teorien om ikke-lineær programmering. Den er også gyldig for såkalte kvadratiske programmeringsproblemer, dvs. hvor er den objektive funksjonen
med restriksjoner:

.

I det generelle tilfellet med å løse ikke-lineære programmeringsproblemer for å bestemme problemets globale ekstremum, er det ingen effektiv beregningsmetode hvis det ikke er kjent at noe lokalt ekstremum også er globalt. Således, i et konveks og kvadratisk programmeringsproblem, er settet med gjennomførbare løsninger konveks, så hvis objektivfunksjonen er konkav, er ethvert lokalt maksimum også globalt.

Eksempel 7.3. Ved å bruke Kuhn-Tucker teoremet finner vi
under restriksjoner

Vi løser grafisk (fig. 7.2) og finner:
;
;
(se løsning nedenfor for flere detaljer). La oss vise at det er en vektor Y 0 0, hvor Kuhn-Tucker-forholdene er oppfylt på det optimale punktet. La oss komponere Lagrange-funksjonen:

Løsning
finner vi fra systemet:
. Fra den andre ligningen
erstatte inn i den første ligningen i systemet. Differensiere ved :
. I uttrykk Og erstatte verdiene
Og
. Vi har verdier av partielle deriverte større enn null, og i henhold til betingelsen må de være lik null, da =0 Og =0. På den andre siden, kan ta verdier som ikke er null, fordi
herfra
; Alle
de. Kuhn-Tucker-forholdene er oppfylt, derfor er dette punktet et ekstremum.

Fig.7.2. Grafisk løsning på det ikke-lineære problemet

programmeringseksempel 7.3

Nødvendig betingelse for optimalitet for et ikke-lineært programmeringsproblem kan formuleres som følger. La
er den optimale løsningen på problem (7.4)–(7.6), og funksjonene
,
,
differensierbar på dette tidspunktet. Hvis
er et ikke-singular punkt i det tillatte settet med problem (7.4)–(7.6), så er det et Kuhn-Tucker poeng av dette problemet.

Således, hvis et tillatt sett
problem (7.4)-(7.6) har ingen entallspunkter, og funksjonene F(M),g Jeg (M), (
) differensierbar på alle punkter
, så bør den optimale løsningen på dette problemet søkes blant Kuhn-Tucker-punktene.

Som kjent fra matematisk analyse, spesielt poeng sett med tillatte løsninger til et system med lineære ligninger og ulikheter i formen

dvs. sett med gjennomførbare løsninger

hvis på punktet
gradientene til disse funksjonene er lineært avhengige
, som i det blir til . For eksempel,
– enkeltpunkt i settet

Egentlig,

Dermed er det et lineært avhengig system.

Gradientfunksjon
er en vektor hvis koordinater er henholdsvis lik verdiene til de partielle deriverte av funksjonen
på punktet M 0 . Denne vektoren viser retningen for den raskeste veksten av funksjonen.

Den nødvendige optimalitetsbetingelsen er til liten nytte for å løse de fleste ikke-lineære programmeringsproblemer, fordi Bare i sjeldne tilfeller er det mulig å finne alle Kuhn-Tucker-punktene til et ikke-lineært programmeringsproblem.

Tilstrekkelig tilstand for optimalitet for et ikke-lineært programmeringsproblem: if
er setepunktet for Lagrange-funksjonen for problem (7.4)–(7.6), da
er den optimale løsningen på dette problemet.

Denne betingelsen er ikke nødvendig i det generelle tilfellet: Lagrange-funksjonen har kanskje ikke setepunkter samtidig originalt problem ikke-lineær programmering har en optimal løsning.

Ulike metoder er kjent som lar en finne den optimale løsningen på et ikke-lineært programmeringsproblem omtrent. Imidlertid gir disse metodene en ganske god tilnærming bare for det konvekse programmeringsproblemet, der hvert lokale ekstremum også er globalt. Generelt, under gradient metoder forstå metoder der bevegelsen til det optimale punktet for en funksjon faller sammen med retningen til gradienten til denne funksjonen, dvs. starter fra et tidspunkt
en sekvensiell overgang utføres til noen andre punkter inntil en akseptabel løsning på det opprinnelige problemet er identifisert. I dette tilfellet kan gradientmetoder deles inn i 2 grupper.

TIL først Denne gruppen inkluderer metoder der punktene som studeres ikke går utover rekkevidden av mulige løsninger på problemet. Den vanligste av disse metodene er metoden Frank-Wolf (Ulv). Slike metoder inkluderer metoden projiserte Rosen-gradienter, metode gyldig veibeskrivelse til Zeutendijk.

Co. sekund Denne gruppen inkluderer metoder der punktene som studeres kan eller ikke tilhører regionen med gjennomførbare løsninger. Imidlertid, som et resultat av implementeringen av den iterative prosessen, finner man et punkt i regionen med gjennomførbare løsninger som bestemmer en akseptabel løsning.

Av disse metodene er den mest brukte metoden straffefunksjoner eller metode Pil-Hurwitz.

Når man finner løsninger på problemer ved bruk av gradientmetoder, inkludert de som er nevnt ovenfor, utføres den iterative prosessen frem til gradienten til funksjonen
ved neste punkt
vil ikke bli lik null eller til
, Hvor – et ganske lite positivt tall som karakteriserer nøyaktigheten til den resulterende løsningen.

Å løse komplekse ikke-lineære programmeringsproblemer ved hjelp av gradientmetoder innebærer en stor mengde beregninger og anbefales kun ved bruk av en datamaskin.

Ved å bruke et eksempel vil vi vise den generelle betydningen av gradientmetoder for å løse ikke-lineære programmeringsproblemer.

La det være en funksjon av to variabler
. La startverdiene til variablene være
, og verdien av funksjonen
. Hvis
er ikke et ekstremum, så bestemmes slike nye verdier av variablene
Og
slik at neste verdi av funksjonen
viste seg å være nærmere det optimale enn den forrige.

Hvordan bestemmes størrelsen på inkrementene? Og ? For å gjøre dette, på punkter Og Retningen for endring av funksjonen mot ekstremum bestemmes ved hjelp av gradienten. Jo større verdi av den partielle deriverte, jo raskere endres funksjonen mot ekstremumet. Derfor trinnene Og velges proporsjonalt med verdien av partielle derivater Og på poeng
Og
. Dermed,
Og
, Hvor – en verdi kalt trinn, som setter endringsskalaen Og .

Eksempel 7.4.

La det være nødvendig å maksimere funksjonen

(maksimum ved punkt (3;2))


.

På punktet
,
på
vi har

;
,

La oss gjøre en gjentakelse til. På punktet
,
på
vi har

;
,

Fig.7.3. Geometrisk tolkning av to trinn

gradientmetode for eksempel 7.4

I fig. 7.3 viser bevegelsen langs stigningen, som ble utført i i dette eksemplet. Holdning angir retningen for endring av funksjonen mot maksimum. Hvis vi tar gradienten med et minustegn, vil vi bevege oss mot minimum.

Et spesifikt problem med gradientmetoder er valg av trinnstørrelse t. Hvis vi tar små steg, vil vi lete etter det optimale i svært lang tid. Hvis du velger verdien for stor, kan du "overskyte" det optimale. Det mellomliggende problemet med å velge den optimale trinnstørrelsen løses ved hjelp av passende metoder. Hvis trinn t bestemt tilnærmet, da faller de som regel ikke inn i det optimale, men i sin sone. Gradientmetoder gir bestemmelse av lokale optima. Når du søker etter et globalt optimum ved hjelp av en gradient, er det ofte tvil om at det funnet optimum er globalt. Dette er ulempen med denne metoden når du løser ikke-konvekse programmeringsproblemer.

Selvtest spørsmål

    Uttalelse av det ikke-lineære programmeringsproblemet.

    Prosessen med å finne en løsning på et ikke-lineært programmeringsproblem ved å bruke dens geometriske tolkning.

    Algoritme av Lagrange-metoden for å løse et ikke-lineært programmeringsproblem.

    Anvendelse av Lagrange-metoden for å løse et ikke-lineært programmeringsproblem i tilfellet hvor tilkoblingsforholdene er ulikheter.

    Hjelpedefinisjoner og teoremer som er nødvendige for å vurdere det sentrale teoremet for ikke-lineær programmering - Kuhn-Tucker-teoremet.

    Kuhn-Tuckers teorem.

    Nødvendig og tilstrekkelig optimalitetsbetingelse for et ikke-lineært programmeringsproblem.

    Den generelle betydningen av gradientmetoder for tilnærmet løsning av ikke-lineære programmeringsproblemer.

    Grupper av gradientmetoder for tilnærmet løsning av ikke-lineære programmeringsproblemer.

Kuhn-Tucker-teoremer er et generisk navn for utsagn som representerer generaliseringer

anvendelse av Lagranges teorem på optimeringsproblemer med begrensninger i form av ulikheter, dvs. problemer

følgende type:

gj(x) > 0, j = 1, .

M, (?)

x = (x1, . . . , xn) 2 X.

Her f: X 7! R - (i samsvar med etablert terminologi) objektiv funksjon, gr: X 7! R,

r = 1, . . . ,m, er begrensningsfunksjoner, X _ Rn er et åpent sett.

Teorem 196 (Johns teorem når det gjelder et setepunkt):

La funksjonene f( ), g1( ), . . . , gn( ) er konkave og?x er en løsning på problemet (?), slik at?x 2 intX.

Så er det Lagrange-multiplikatorer _j >

X er en løsning på problemet

Vi presenterer disse utsagnene for tilfellet når funksjonene f, gr er differensierbare (teoremer av Ku-

on-Tucker i differensialform).

Husk at funksjonen

L(x,_) = _0f(x) +

kalles Lagrange-funksjonen (Lagrangian) for dette problemet, og koeffisientene _j er multiplikatorer

Lagrange.

Følgende uttalelse gjelder.

Teorem 197 (Johns teorem for differensierbare funksjoner):

La?x være en løsning på problemet (?), slik at?x 2 intX og funksjonene f( ), g1( ), . . . , gn( ) differensial

er kvantifiserbare ved punkt?x.

Så er det Lagrange-multiplikatorer _j > 0, j = 0, . . . ,m, er ikke alle lik null, slik at

følgende relasjoner er oppfylt (Kuhn-Tucker-betingelser):

0, i = 1, . . . , n

J = 0 (komplementære betingelser

ikke-stivhet).

Merk at vilkårene for komplementær slakkhet kan skrives i skjemaet

gj(?x)_j = 0, j = 1, . . . , m.

Fra disse betingelsene følger det at hvis Lagrange-multiplikatoren er positiv (_j > 0), så den tilsvarende

begrensningen for å løse problemet (ved x = ?x) er oppfylt som en likhet (dvs. gj(?x) = 0). Andre

med andre ord, denne begrensningen er aktiv. På den annen side, i tilfellet når gj(?x) > 0, så den tilsvarende

Lagrange-multiplikatoren _j er lik null.

Hvis i problemet (?) noen av restriksjonene har form av restriksjoner på ikke-negativiteten til noen xi,

så for dem kan du ikke introdusere Lagrange-multiplikatorer ved å skrive følgende restriksjoner separat:

gj(x) > 0, j = 1, . . . , m, (??)

xi > 0, i 2 P _ (1, . . . , n). Ved det indre punktet (i betydningen at 1 ? x 2 intX) er førsteordensbetingelsene for i 2 P da

vil se slik ut:

For i /2 P her, som i tilfellet med å representere problemet i formen (?), den deriverte av Lagrange-funksjonen

for den variabelen vil se ut som @L(?x,_)

I tillegg er betingelsene for komplementær ikke-stivhet også oppfylt

Fra den andre av disse betingelsene følger det at for?xi > 0 (i 2 P)

På den annen side, hvis @L(?x,_)/@xi En annen modifikasjon av teoremet er assosiert med tilstedeværelsen av begrensninger i form av likheter i problemet. Betegnelse

la oss definere settet med tilsvarende indekser gjennom E. Problemet har følgende form:

gj(x) > 0, j 2 (1, . . . ,m)\E,

gj(x) = 0, j 2 E, (???)

xi > 0, i 2 P _ (1, . . . , n).

Samtidig fjerner Johns teorem betingelsen om at alle Lagrange-multiplikatorer er ikke-negative -

Lagrangemultiplikatorer _j for j 2 E kan ha et vilkårlig fortegn.

Johns teorem garanterer ikke at Lagrange-multiplikatoren til objektivfunksjonen, _0, ikke er null.

Imidlertid, hvis _0 = 0, karakteriserer Kuhn-Tucker-forholdene ikke løsningen på problemet under vurdering, men

strukturen til settet av restriksjoner ved punktet?x og teoremet har ingen direkte sammenheng med interessen

vår nåværende oppgave med å maksimere funksjonen f( ), siden gradienten til funksjonen f( ) i seg selv forsvinner. fra

Kuhn-Tucker forhold.

Derfor er det viktig å karakterisere forholdene som garanterer at _0 > 0.

Slike tilstander kalles regularitetstilstander.

I tilfellet når problemet under vurdering er konveks, er en av betingelsene for regularitet

den såkalte Slater-tilstanden har formen:

I tilfellet når den objektive funksjonen og begrensningene til problemet er differensierbare, er det enkleste

Regelmessighetsbetingelsen er formulert i form av gradienter av begrensningsfunksjoner og har formen:

gradientene til aktive begrensninger ved punkt?x er lineært uavhengige. (Blant begrensningene som vurderes er

restriksjoner på ikke-negativitet bør også inkluderes.)

La oss angi med A settet med indekser for de begrensningene som er aktive på det optimale punktet?x

(inkludert indekser av alle begrensninger i form av likheter), dvs.

gj(?x) = 0, j 2 A.

Så hvis begrensningsgradientene er vektorer

er lineært uavhengige2, deretter _0 > 0. Denne tilstanden kalles Kuhn-Tucker-regularitetstilstanden.

Merk at hvis _0 > 0, kan vi uten tap av generalitet anta _0 = 1, noe som vanligvis gjøres.

Det tilsvarende teoremet kalles (direkte) Kuhn-Tucker-teoremet. Teorem 198 (Direkte Kuhn-Tucker-teorem, nødvendig betingelse for optimalitet):

La funksjonene f( ), g1( ), . . . , gn( ) er differensierbare, og?x er en løsning på problemet (?), slik at

X 2 intX og Kuhn-Tuckers regularitetstilstand er oppfylt.

Så er det Lagrange-multiplikatorer _j > 0, j = 1, . . . ,m, slik at når _0 = 1 er tilfredsstilt

følgende forhold:

0, i = 1, . . . , n

Det er lett å omformulere denne teoremet for problemer (??) og (???). De samme egenskapene kreves her.

modifikasjon av Kuhn-Tucker-forholdene, som i Johns teorem.

0, i = 1, . . . , n

kan skrives om som:

Dette forholdet viser at ved det optimale punktet er gradienten til objektivfunksjonen en lineær kom-

kombinasjon av antigradienter av restriksjoner, og alle koeffisientene til denne lineære kombinasjonen er ikke-negative

verdifulle. Ris. Figur 17.1 illustrerer denne egenskapen. Intuitivt er ideen bak denne eiendommen det

hvis en koeffisient for en lineær kombinasjon var negativ, ville det være mulig

øke verdien av målfunksjonen ved å bevege seg langs denne begrensningen. En av de inverse versjonene av Kuhn-Tucker-teoremet sier at når funksjoner er konkavitet

f( ), (gk( )) oppfyllelse av disse betingelsene i en tillatt løsning?x (dvs. et punkt som tilfredsstiller begrensningen

verdier) for noen Lagrange-multiplikatorer som tilfredsstiller kravene til det direkte teoremet,

garanterer at?x er en løsning på problemet.

Teorem 199 (Invers Kuhn-Tucker teorem /tilstrekkelig betingelse for optimalitet/):

La f( ) være en differensierbar konkav funksjon, g1( ), . . . , gn( ) - differensierbar

kvasi-konkave funksjoner, mengden X er konveks og punktet?x er tillatt i oppgaven (?), og?x 2

La i tillegg eksistere Lagrange-multiplikatorer _j > 0, j = 1, . . . ,m, slik at når

0 = 1 er følgende relasjoner tilfredsstilt:

0, i = 1, . . . , n

Da er?x løsningen på problemet (?).

Teoremet kan omformuleres på en åpenbar måte for problemer (??) og (???). For oppgaven (???)

begrensninger i form av likheter kan bare være lineære (dette skyldes det faktum at begrensningen i formen

likheter, gj(x) = 0, skal representeres ved å bruke to restriksjoner i form av ulikheter, gj(x) > 0

og?gj(x) > 0, som hver er gitt av en kvasi-konkav funksjon; dette kan bare skje hvis

begrensningen er lineær).

I en annen versjon av den tilstrekkelige optimalitetstilstanden, antas det at målet er konkavitet

funksjonen erstattes av antakelsen om kvasi-konkavitet med tillegg av betingelsen rf(?x) 6= 0.

Formulering av problemet

La oss vurdere et ikke-lineært optimaliseringsproblem. La det være funksjoner

Under forhold.

William Karush fant i sin oppgave de nødvendige betingelsene i det generelle tilfellet når de pålagte betingelsene kan inneholde både likninger og ulikheter. Uavhengig kom Harold Kuhn og Albert Tucker til de samme konklusjonene.

Nødvendige betingelser for minimum av en funksjon

Hvis det under de pålagte restriksjonene er en løsning på problemet, er det en vektor som ikke er null av Lagrange-multiplikatorer slik at for Lagrange-funksjonen betingelsene er oppfylt:

Tilstrekkelige forhold for minimum av en funksjon

De oppførte nødvendige betingelsene for minimum av en funksjon er ikke tilstrekkelige i det generelle tilfellet. Det er flere alternativer tilleggsbetingelser, som gjør dem tilstrekkelige.

Enkel formulering

Hvis betingelsene for stasjonaritet, komplementær ikke-stivhet og ikke-negativitet, samt λ 1 > 0, er oppfylt for et tillatt punkt, er .

Svakere forhold

Hvis for et tillatt punkt betingelsene for stasjonaritet, komplementære til ikke-stivhet og ikke-negativitet, samt ( Slaters tilstand), Det.


Wikimedia Foundation. 2010.

Se hva "Karush-Kuhn-Tucker-forholdene" er i andre ordbøker:

    I optimaliseringsteori er Karush Kuhn Tucker-betingelser (KKT) nødvendige forutsetninger for å løse et ikke-lineært programmeringsproblem. For at løsningen skal være optimal, må visse ting gjøres... ... Wikipedia

    I optimaliseringsteori er Karush Kuhn Tucker-betingelser (KKT) nødvendige forutsetninger for å løse et ikke-lineært programmeringsproblem. For at en løsning skal være optimal, må noen regularitetsbetingelser være oppfylt.... ... Wikipedia

    William Karush William Karush Fødselsdato: 1. mars 1917 (1917 03 01) Fødested: Chicago, USA Dødsdato ... Wikipedia

    Dette begrepet har andre betydninger, se Optimalisering. Optimalisering i matematikk, informatikk og operasjonsforskning er problemet med å finne ekstremum (minimum eller maksimum) av en objektiv funksjon i et eller annet domene av en endelig dimensjonal vektor ... Wikipedia Wikipedia

    Lagrange multiplikatormetode, metode for å finne betinget ekstremum funksjoner f(x), hvor, i forhold til m begrensninger, i varierer fra en til m. Innhold 1 Beskrivelse av metoden ... Wikipedia