• hjem
  •  > 
  • Systemadministrasjon
  •  > 
  • Nødvendige og tilstrekkelige forhold for kun tucker. Nødvendige betingelser for minimum av en funksjon

Nødvendige og tilstrekkelige forhold for kun tucker. Nødvendige betingelser for minimum av en funksjon

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 av hverandre 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 betingelsene for stasjonaritet er oppfylt for et tillatt punkt, komplementært 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, problemet med å finne et ekstremum (minimum eller maksimum) objektiv funksjon i et eller annet domene av endelig-dimensjonal vektor ... Wikipedia Wikipedia

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

Kuhn-Tucker-teoremet er en generalisering av løsningsmetoder optimaliseringsproblemer i to retninger:

Lineær programmering til det ikke-lineære tilfellet, som analogt fikk det ikke særlig vellykkede navnet "ikke-lineær programmering";

Ikke-lineære likhetsbegrensninger på ulikhetsbegrensninger.

Karush-Kuhn-Tucker metode og betingelser ( Karush-Kuhn-Tucker-forhold, KKT) er formelt nødvendige betingelser for optimaliteten til et ikke-lineært programmeringsproblem. I tillegg inkluderer de nødvendige forholdene de såkalte regularitetsforholdene for stasjonære punkter - ikke-degenerasjonen av settet med begrensningsgradienter. Metoden er en generalisering av Lagrange-multiplikatormetoden til tilfellet med ulikhetsbegrensninger.

Kuhn og Tucker generaliserte Lagrange-multiplikatormetoden (for bruk til å konstruere optimalitetskriterier for problemer med begrensninger i form av likheter) til saken felles oppgave ikke-lineær programmering med restriksjoner, både i form av likheter og ulikheter.

Hovedmetoden i ikke-lineær programmering er fortsatt bruken av Lagrange-funksjonen oppnådd ved å overføre restriksjoner til objektivfunksjonen. Kuhn-Tucker-forholdene er også avledet fra dette prinsippet.

William Karush i sin diplomarbeid i 1931 fant han nødvendige forhold i den generelle saken om innskrenkninger i likheter og ulikheter. Uavhengig kom Harold Kuhn og Albert Tucker til de samme konklusjonene senere i 1941. Resultatene deres var mer generelle.

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

- stasjonaritet: ;

- komplementær mykhet: ;

- ikke-negativitet:.

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

- enkel tilstand – 1) punktet er stasjonært, 2) betingelsen om komplementær ikke-stivhet er oppfylt, 3) Lagrange-multiplikatorer;

- Slaters tilstand (svakere) – 1) punktet er stasjonært, 2) betingelsen om komplementær ikke-stivhet er oppfylt, 3) .

La oss gå direkte til beviset for Kuhn-Tucker-teoremet.

Hvis en kontinuerlig funksjon av n variabler x = (x1,...,xn) har F(x) i punktet X opt maksimum, så eksisterer det ε > 0 slik at for alle x fra ε-området til punktet X engros

F(x)≤F(x opt)

F(x)-F(x opt)≤0.

La oss velge to typer inkrement x j langs j koordinatene

Δx j =x j -x jopt >0,

Δx j =x j -x jopt<0.



Passerer i disse relasjonene til grensen ved Δ x j→0, vi får:

Av disse relasjonene følger det at

(3.6.1)

En lignende relasjon kan oppnås for tilfellet med en minimumsfunksjon. Dermed er nødvendigheten av betingelser (3.6.1) for å oppnå på punktet x engros maksimum eller minimum funksjon f(x), dvs. hvis det er et ekstremum, er betingelsene (3.6.1) oppfylt. Men likheten til null av alle derivater på punktet x engros sikrer ennå ikke eksistensen av et ekstremum i den, det vil si at forholdene (3.6.1) ikke er tilstrekkelige. Geometrisk betyr dette at i tilfellet med en nullderivert av en funksjon av en variabel kan det være et bøyningspunkt, og ikke et maksimum (eller minimum), og i tilfelle av en funksjon av to variabler, et setepunkt, og ikke et ekstremum osv. Derfor poengene x engros, der relasjoner (3.6.1) er tilfredsstilt kalles stasjonære.

Merk at betingelse (3.6.1) ble oppnådd takket være muligheten til å tilordne en variabel X trinn på to tegn, som er der de to ulikhetene oppsto ved og ved . Hvis det gyldige området X begrenset til ikke-negative verdier X≥0, deretter innenfor området hvor X> 0, betingelse (3.6.1) forblir gyldig, siden økninger av begge tegn er tillatt der. På grensen til regionen X≥ 0, hvor X= 0, kun positiv økning Δ er tillatt X>0, vi kan bare snakke om en ensidig derivat, og fra (3.6.1) følger følgende nødvendige betingelse for et maksimum:

Følgelig den nødvendige betingelsen for et minimum på grensen av regionen x j= 0 vil bli skrevet som

b) Betinget ekstremumproblem

Når du bestemmer det betingede ekstremumet til en funksjon, når det er nødvendig å bestemme maksimum (eller minimum) for funksjonen F(x) under begrensende forhold:

g i (x) = bi, i = 1, ..., m,

f(x)=maks;

gi (x)=bi;

Metoden til Lagrange-multiplikatorer brukes også, som, som i tilfellet med klassisk variasjonsregning, består i å introdusere Lagrange-funksjonen

(3.6.2)

hvor λ i er de ubestemte Lagrange-multiplikatorene.



Forutsatt at funksjonen er et spesialtilfelle av det funksjonelle, får vi at de nødvendige betingelsene for ekstremum finnes ved direkte differensiering av relasjon (3.6.2) og skrives i formen


Hvis vi introduserer vektorer

relasjoner (17-8) og (17-9) vil bli omskrevet som

grad Φ = grad F - λ grad φ = 0; (3.6.6)

hvor likheten av vektorer til null forstås komponentvis.



 Figur 3.6.1 - Forklaring av det betingede ekstremumproblemet

Når n= 2 og m = 1 geometrisk problem om å finne et betinget ekstremum kommer ned (fig. 17-6) til å finne tangenspunktet A til kurven φ = b til en av kurvene for konstant nivå f= konst.

Teorem 7.2. For det konvekse programmeringsproblemet (7.4)–(7.6), settet tillatte løsninger som har egenskapen regularitet, 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 ikke-null verdier, 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
– optimal løsning problemer (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-punkt for 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 lik henholdsvis 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 gjør at man omtrent kan finne den optimale løsningen på et ikke-lineært programmeringsproblem. 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
på 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, desto raskere endres funksjonen mot ekstremumet. Derfor trinnene Og velges proporsjonalt med verdien av de partielle derivatene 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 det optimale "overskrides". Det mellomliggende problemet med å velge den optimale trinnstørrelsen løses ved hjelp av passende metoder. Hvis trinn t bestemmes tilnærmet, da faller de som regel ikke inn i det optimale, men inn i sonen. 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 omtrentlig løsning av ikke-lineære programmeringsproblemer.

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

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* er den optimale løsningen på et ikke-lineært programmeringsproblem, så er 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 den lineære uavhengighetstilstanden og er egentlig en slags regularitetstilstand gyldig område, som nesten alltid er tilfredsstilt for optimaliseringsproblemer som oppstår i praksis. Generelt er det imidlertid svært vanskelig å kontrollere oppfyllelsen av betingelsen om lineær uavhengighet, 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 også iht. i det minste, 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. Figur 1 viser området med gjennomførbare løsninger på det ikke-lineære problemet 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, det følger 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 likhetsligningen. 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.

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

anvendelse av Lagranges teorem i tilfellet med optimaliseringsproblemer 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, 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 tilfredsstilt 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, så uten tap av generalitet kan vi 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.