Konveksna optimizacija

  • Definicija. Množica je konveksna, če za vsaka in vsak velja .

  • Torej: množica je konveksna, če je vsaka daljica s krajišči v množici v celoti vsebovana v .

  • Trditev. Presek konveksnih množic je konveksen: () konveksne konveksna.

  • Dokaz. Preveriti moramo: za vsaka in vsak velja . To je res, ker so množice () konveksne.

Konveksne kombinacije

  • Definicija. Vektor , kjer , , je konveksna kombinacija vektorjev .

  • Za pišemo , , torej .

  • Trditev. Množica je konveksna natanko tedaj, ko je v vsaka konveksna kombinacija vektorjev iz .

Dokaz

  • () Očitno.
  • () Naj bo konveksna kombinacija vektorjev . Naredimo indukcijo na .

    • : .

    • : po definiciji.

    • : če , potem in . Sicer - tedaj naj bo

      • Ker je in , je konveksna kombinacija vektorjev .
      • Po indukcijski predpostavki je , torej je tudi .

Konveksna ogrinjača

  • Definicija. Množica je konveksna ogrinjača (ali konveksna ovojnica) množice .

  • Opomba. Primerjaj z linearno ogrinjačo .

Lastnosti konveksne ogrinjače

Trditev. Naj bosta množici, pri čemer je množica konveksna. Potem velja sledeče.

  • 1. .

  • 2. je konveksna množica.

  • 3. .

  • 4. Če je konveksna množica, potem .

  • 5.

    - tj., množica konveksnih kombinacij vektorjev iz .

Dokaz

  • 1.
  • 2. Presek konveksnih množic je konveksen.
  • 3. Ker je konveksna, sledi iz definicije konveksne ogrinjače.
  • 4. Po 3. je .

Dokaz (2)

5. Naj bo množica konveksnih kombinacij vektorjev iz . Dokažimo .

  • () Po 3. velja , saj:

    • ;

    • je konveksna, ker je vsaka konveksna kombinacija vektorjev

      tudi konveksna kombinacija vektorjev , saj (, ) in , torej .

  • () Ker je vsak konveksna kombinacija vektorjev , za vsako konveksno množico velja , torej in zato . Sledi .

Ekstremne točke

  • Definicija. Naj bo konveksna množica. Točka je ekstremna točka, če velja (tj., ne leži v notranjosti nobene daljice med različnima točkama iz ).

  • Primer. Ekstremne točke so prikazane z rdečo barvo.

  • Ni ekstremnih točk!

Afine množice in kombinacije

  • Definicija. Množica je afina, če velja (tj., vsaka premica skozi različni točki iz je vsebovana v ).

  • Definicija. Vektor , kjer je , je afina kombinacija vektorjev .

Lastnosti afinih množic

  • Trditev. Naj bo neprazna množica. Sledeče trditve so ekvivalentne.

    • 1. Množica je afina.
    • 2. Vsaka afina kombinacija točk iz je v .
    • 3. , linearen podprostor: .

  • Opomba. Primeri afinih množic so premica v , ravnina v , ... - rečemo jim tudi afini podprostori. Definiramo lahko tudi dimenzijo afinega podprostora.

Dokaz (1. 2.)

Naj bo afina kombinacija vektorjev . Naredimo indukcijo na .

  • : .

  • : po definiciji.

  • : brez škode za splošnost vzamemo - tedaj naj bo

    • Ker je , je afina kombinacija vektorjev .
    • Po indukcijski predpostavki je , torej je tudi .

Dokaz (2. 3. 1.)

  • (2. 3.) Naj bo poljuben vektor. Potem je linearen podprostor, saj za vsake ter velja

    saj ter . Velja torej .

  • (3. 1.) Poljubna vektorja iz lahko zapišemo kot in , kjer . Za poljuben velja

Konveksni stožci in Farkaseva lema

  • Definicija. Množica je konveksen stožec, če velja .

  • Opomba. Če za vsaka velja

    • , potem je linearen podprostor;
    • , potem je konveksen stožec;
    • , potem je množica afina; in
    • , potem je množica konveksna.

    Vsak konveksen stožec je konveksna množica; obratno ne velja.

Konveksen stožec, napet na vektorjih

  • Definicija. Množica

    je konveksen stožec, napet na vektorjih .

  • Trditev. Množica je konveksen stožec.

  • Dokaz. Naj bodo . Potem velja

    saj ().

Primeri

  • :
  • :

Primeri (2)

:

Dualni stožec

  • Definicija. Naj bo . Množici

    (tj., množici vektorjev, ki tvorijo ostri kot z vsemi vektorji iz ) pravimo dualni stožec množice .

Lastnosti dualnega stožca

  • Trditev. Dualni stožec množice je konveksen stožec.

  • Dokaz. Vzemimo poljubne in . Potem za vsak velja

    torej .

  • Trditev. .

  • Opomba. V splošnem ne velja (npr. če ni konveksen stožec).

  • Dokaz. Vzemimo poljuben . Potem za vsak velja , torej velja tudi .

Farkaseva lema

  • Izrek (Farkaseva lema - geometrijska oblika). .

  • Dokaz.

    • () Po prejšnji trditvi.

    • () Naj bo matrika s stolpci in . Definirajmo linearni program in njegov dual :

Dokaz (2)

  • Ker je dopustna rešitev , je ta dopusten; pokazali bomo, da je tudi omejen.

  • Naj bo dopustna rešitev za , torej velja oziroma

  • Potem za poljubne velja

  • Vektor torej tvori ostri kot z vsemi vektorji iz in zato .

Dokaz (3)

  • Ker velja , sledi , torej je omejen in zato optimalen.

  • Po krepkem izreku o dualnosti je tudi optimalen, torej oziroma

    iz česar sledi .

  • Opomba. Farkasevo lemo se da dokazati tudi neposredno, krepki izrek o dualnosti sledi iz nje. Imamo torej ekvivalenco Farkas KID.

Farkaseva lema - algebraična oblika

  • Dokaz.

    1. Naj bodo stolpci matrike . Potem je izjava ekvivalentna izjavi , ki sledi iz geometrijske oblike Farkaseve leme.

Dokaz (nadaljevanje)

Obravnavamo linearna programa:

  • 2.

  • 3.

  • 4.

  • V vseh primerih ekvivalenco dokažemo tako:

    • () Sledi iz šibkega izreka o dualnosti.
    • () Dualni linearni program ima dopustno rešitev , po predpostavki pa je to tudi optimalna rešitev. Po krepkem izreku o dualnosti je tudi optimalen, torej ima dopustno rešitev.

Primeri

1. Ali obstaja nenegativna rešitev sistema linearnih enačb ?

  • Če obstaja, jo zapišemo. Če ne obstaja, poiščemo , da velja , .

  • Dokažimo, da zgornji sistem nima nenegativnih rešitev.

  • Ustrezen oziroma lahko poiščemo s simpleksno metodo.

Primeri (2)

2. Pokažimo, da linearni program nima dopustne rešitve.

Primeri (3)

3. Enakovredna izjava: .

  • Pri linearni algebri dokazujemo z Gaussovo eliminacijo.

Opomba

  • Ekvivalentna trditev Farkasevi lemi:

  • Torej (): če ni v konveksnem stožcu, napetem na , potem ne tvori ostrega kota z - med in je tako neka hiperravnina.

Konveksne funkcije

Konveksne funkcije so "obrnjene navzgor", npr .

Definicija

  • Naj bo konveksna množica.

  • Funkcija je konveksna, če velja

    Torej: graf funkcije leži pod zveznicami točk na grafu.

  • Funkcija je konkavna, če velja

    Torej: je konkavna je konveksna.

  • Funkcija je strogo konveksna, če velja

  • Funkcija je strogo konkavna, če velja

Primeri

  • Množica je konveksna natanko tedaj, ko je množica interval.

  • Trdimo: je konveksna funkcija (za vsak interval ).

Primeri (2)

  • Afina funkcija (ali ) je konveksna:

  • Funkcija je tudi konkavna.

  • Da se dokazati, da je funkcija konveksna in konkavna natanko tedaj, ko je afina.

Primeri (3)

  • Norma je funkcija s sledečimi lastnostmi:

    • ,
    • (trikotniška neenakost)

  • Primer: dolžina vektorja

  • Norma je konveksna:

Lastnosti konveksnih funkcij

  • Trditev. Naj bo konveksna množica ter konveksni funkciji. Potem velja sledeče.

    1. Če , potem je konveksna funkcija.
    2. Funkcija je konveksna.
    3. Če je funkcija afina, je slika konveksna množica.

  • Trditev. Naj bo konveksna množica ter in konveksni funkciji. Denimo, da velja vsaj eno od sledečega.

    • Funkcija je afina, ali
    • funkcija je naraščajoča.

    Potem je kompozitum konveksna funkcija.

Dokaz

  • 1.

  • 2.

  • 3. Funkcija je konveksna in konkavna, za velja . Ker je , velja

Dokaz (2)

  • Trdimo, da velja

  • Prva neenakost velja zaradi konveksnosti funkcije .

  • Če je funkcija naraščajoča, potem velja tudi druga neenakost.

  • Če pa je funkcija afina, velja enakost v prvi in posledično tudi v drugi neenakosti.

  • V obeh primerih zadnja neenakost sledi zaradi konveksnosti funkcije .

Neprimeri

  • Produkt konveksnih funkcij ni nujno konveksna funkcija: , , .

  • Kompozitum konveksnih funkcij ni nujno konveksna funkcija: , , .

  • Slika konveksne množice s konveksno funkcijo ni nujno konveksna množica:

    čč

Konveksne funkcije in optimizacija

  • Definicija. Naj bo in . Funkcija ima v točki :

    • globalni maksimum, če ;
    • globalni minimum, če ;
    • lokalni maksimum, če ; in
    • lokalni minimum, če .

  • Trditev. Naj bo konveksna množica ter konveksna funkcija. Če ima v lokalni minimum, ima v tudi globalni minimum.

Dokaz

  • Naj bo tak, da velja .

  • Če ni globalni minimum, potem obstaja tak , da velja .

  • Tedaj za vsak velja

  • Za dovolj majhen je poljubno blizu :

    č

  • Torej: če je , je in tedaj , protislovje.

Odvodi

  • Preverjanje konveksnosti po definiciji je v splošnem težko. Večinoma je lažje preverjati konveksnost z odvodi.

  • Naj bo konveksna funkcija. Njen graf potem leži nad vsako tangento (kriterij 1. odvoda), torej
    za vsaka .

  • Primer. Naj bo . Preverimo, ali za vsaka velja

    • Res:

Odvodi (2)

  • Smerni koeficienti tangent na graf konveksne funkcije naraščajo - njen odvod je torej naraščajoča funkcija, torej za vsak (kriterij 2. odvoda).

  • Primer. Naj bo . Potem je .

Kriterij 1. odvoda

  • Naj bo odprta konveksna množica, ter funkcija, ki ima vse parcialne odvode ().
    • Parcialne odvode zapišemo v gradient .
  • Potem je funkcija konveksna natanko tedaj, ko za vsaka velja .

Dokaz ()

  • Naj bodo in poljubni ter pišimo .

  • Potem velja:

  • Funkcija je torej konveksna.

Dokaz ()

  • Za fiksna je funkcija v - zanima nas njen odvod pri .

  • Funkcija je definirana na za nek .

  • Naj bo tak, da je množica (tj., krogla s središčem v in polmerom ) vsebovana v .

  • Zadostuje, da za vse velja

  • Vzamemo lahko torej .

Dokaz (, 2)

  • Izračunajmo .

  • Velja torej .

Dokaz (, 3)

  • Po definiciji odvoda nadalje velja

  • Velja torej .

Kriterij 2. odvoda za funkcije ene spremenljivke

  • Naj bo dvakrat odvedljiva funkcija.

  • Potem je funkcija konveksna natanko tedaj, ko za vsak velja .

  • Dokaz (). Naj bo in tak, da .

    • Zaradi konveksnosti funkcije potem velja:

    • Z dvakratno uporabo L'Hôpitalovega pravila potem izpeljemo

Dokaz ()

  • Naj bosta (brez škode za splošnost privzamemo ) ter . Postavimo .

  • Po Lagrangeevem izreku velja

Dokaz (, 2)

  • Ker velja in , sledi (tj., funkcija narašča, ker je njen odvod nenegativen).

  • Velja torej:

Lastni vektorji in vrednosti

  • Pri Algebri 1 se naučite: je lastni vektor matrike , če obstaja lastna vrednost , da velja .

  • Matrika je diagonalizabilna, če obstaja linearno neodvisnih lastnih vektorjev.

  • Primer. Matrika ni diagonalizabilna:

    • Imamo torej samo en linearno neodvisen lastni vektor.

Diagonalizacija

  • Lastne vrednosti poiščemo kot ničle karakterističnega polinoma . Lastni vektorji so neničelne rešitve enačbe za lastne vrednosti .

  • Realna matrika ima lahko kompleksne lastne vrednosti in lastne vektorje:

  • Če je diagonalizabilna matrika, jo lahko zapišemo kot , kjer je obrnljiva matrika, katere stolpci so linearno neodvisni lastni vektorji, pa diagonalna matrika z ustreznimi lastnimi vrednostmi na diagonali.

Simetrične matrike

  • Definicija. Matrika je simetrična, če velja .

  • Izrek. Simetrična matrika ima realne lastne vrednosti in je diagonalizabilna v ortonormirani bazi (tj., lastni vektorji imajo normo in so drug na drugega pravokotni).

    • Tedaj lahko pišemo , kjer je ortogonalna matrika (tj., oziroma ) z lastnimi vektorji v stolpcih.

Definitnost

Definicija. Naj bo simetrična matrika.

  • je pozitivno semidefinitna (), če ima same nenegativne lastne vrednosti.
  • je pozitivno definitna (), če ima same pozitivne lastne vrednosti.
  • je negativno semidefinitna (), če ima same nepozitivne lastne vrednosti.
  • je negativno definitna (), če ima same negativne lastne vrednosti.
  • je nedefinitna, če ima tako pozitivne kot negativne lastne vrednosti.

Kvadratne forme

  • Definicija. Naj bo simetrična matrika. Kvadratna forma, ki pripada , je

  • Primera.

    • Kvadratna forma za matriko je .
    • Kvadratna forma ustreza matriki

Definitnost in kvadratne forme

Trditev.

  • ,
  • ,
  • ,
  • ,
  • je nedefinitna natanko tedaj, ko doseže tako pozitivne kot negativne vrednosti.

Dokaz

  • Vzemimo in diagonalizirajmo .

  • Če je , potem je . Sicer pišimo , posledično velja tudi .

  • Potem velja

  • Matrika ima tako vse lastne vrednosti nenegativne/pozitivne/nepozitivne/negativne natanko tedaj, ko je za vsak zgornja vrednost .

Primer

  • Naj bo simetrična matrika dimenzij :

  • Potem velja:

Preverjanje definitnosti

  • Definicija. Glavne poddeterminante matrike so vrednosti ().

  • Trditev. Naj bo simetrična matrika. Potem velja:

    • natanko tedaj, ko so vse glavne poddeterminante pozitivne.
    • natanko tedaj, ko glavne poddeterminante alternirajo med negativnimi in pozitivnimi vrednostmi.

Hessejeva matrika

  • Definicija. Naj bo odprta množica in funkcija, za katero obstajajo vsi drugi parcialni odvodi ().
  • Hessejeva matrika funkcije je .
    • Če so vsi drugi parcialni odvodi zvezni (), velja , torej je simetrična.

Kriterij 2. odvoda

  • Naj bo odprta konveksna množica, ter funkcija iz .

  • Potem je funkcija konveksna natanko tedaj, ko za vsak velja .

  • Dokaz. Trdimo, da je funkcija konveksna natanko tedaj, ko za vsaka obstaja tak , da je funkcija , konveksna in .

    • Dokažimo najprej to trditev.

Dokaz ()

  • Ker je množica odprta, obstaja tak , da je funkcija z zgornjim predpisom dobro definirana.

  • Ker velja , velja tudi .

  • Dokažimo še, da je konveksna funkcija.

  • Vzemimo torej poljubne in .

  • Ker je konveksna, velja:

Dokaz ()

  • Ker je za vsaka funkcija konveksna, za vsak velja:

  • Funkcija je torej konveksna.

Dokaz (nadaljevanje)

Za poljubna lahko torej zapišemo:

Dokaz (zaključek)

  • Velja torej:

  • Opomba. Taylorjev razvoj funkcije več spremenljivk lahko zapišemo kot

    čš

    • Če je v lokalni minimum, potem velja , .
    • Če velja in , potem je v lokalni minimum.

Stroga konveksnost in ekstremne točke

  • Iz dokazov za kriterij 2. odvoda lahko ugotovimo, da če za vsak velja , potem je strogo konveksna.

    • Obratno ne velja v splošnem (npr. ).

  • Trditev. Naj bo konveksna množica, ter strogo konveksna funkcija. Če je globalni maksimum funkcije , potem je ekstremna točka za .

  • Dokaz. Predpostavimo, da ni ekstremna točka, torej obstajajo ter , da velja . Potem velja

    protislovje.

Neprimer

  • Naj bo in , .

  • Funkcija je konveksna, saj velja (lastni vrednosti sta in ).

  • Funkcija ni strogo konveksna, saj za vse velja

  • Globalni maksimumi funkcije so doseženi v točkah iz .

  • Množica nima ekstremnih točk.

Konveksne funkcije in vezani ekstremi

  • Naj bo odprta množica.

  • Problem vezanih ekstremov z neenačbami (VEN) definiramo kot

  • Množica dopustnih rešitev je torej

Primer

  • Iščemo maksimum in minimum funkcije v območju med in .

  • Imamo torej:

1. način

  • V notranjosti:

  • Dobimo kandidata in , ki pa nista v (relativna notranjost ).

1. način (2)

Na zgornjem robu: ,

1. način (3)

  • Na spodnjem robu: ,

  • Na stičiščih obeh robov: ,

  • Globalni maksimum je torej v , globalni minimum pa v .

2. način

  • V notranjosti: kot prej.
  • Na zgornjem robu: .

    • Definirajmo Lagrangeevo funkcijo

      kjer je Lagrangeev množitelj (multiplikator).

2. način (zgornji rob)

  • Poiščimo parcialne odvode Lagrangeeve funkcije:

  • Sistem enačb ima rešitvi in .

2. način (spodnji rob)

  • Sistem enačb ima rešitev .

2. način (stičišči robov)

  • Sistem enačb ima rešitvi in .

3. način

  • Ločimo primere:
    • , : notranjost
    • , : zgornji rob
    • , : spodnji rob
    • , : stičišči robov

Lagrangeeva funkcija

  • Za problem vezanih ekstremov z neenačbami lahko torej zapišemo Lagrangeevo funkcijo

  • Lokalni ekstremi so doseženi pri

  • Ločimo na primerov glede na oziroma in posledično ().

Karush-Kuhn-Tuckerjevi pogoji

  • Definicija. Vrednosti ustrezajo Karush-Kuhn-Tuckerjevim (KKT) pogojem za problem vezanega ekstrema z neenačbami, če velja

  • Ali so Karush-Kuhn-Tuckerjevi pogoji za zadoščeni natanko tedaj, ko je globalni ekstrem?

    • V splošnem NE.
    • Bo pa odgovor pritrdilen za konveksne optimizacijske probleme.

Primera

  • Tak problem je neomejen - globalnega minimuma ni!

  • Vseeno lahko najdemo točko, ki ustreza Karush-Kuhn-Tuckerjevim pogojem:

Primera (2)

  • Globalni minimum je v točki .

Zadostnost pogojev KKT

  • Izrek. Naj bo odprta konveksna množica ter konveksne odvedljive funkcije. Če zadošča Karush-Kuhn-Tuckerjevim pogojem, potem je globalni minimum funkcije , kjer je (tj., je optimalna rešitev ustreznega problema vezanih ekstremov z neenačbami).

  • Opomba. Pri pogojih iz zgornjega izreka so torej Karush-Kuhn-Tuckerjevi pogoji zadostni za optimalnost rešitve.

  • Dokaz. Vzemimo poljuben . Zaradi konveksnosti (kriterij 1. odvoda) velja:

Potrebnost pogojev KKT

  • Izrek. Naj bo odprta množica ter funkcije, pri čemer je funkcija odvedljiva. Če je globalni minimum funkcije za in velja vsaj eno od sledečega:

    • funkcije so afine; ali
    • množica je konveksna, ter funkcije so konveksne; ali
    • funkcije so odvedljive ter je zaporedje linearno neodvisnih vektorjev,

    potem obstaja tak , da ustreza Karush-Kuhn-Tuckerjevim pogojem.

  • Dokaz izpustimo. V dokazu se uporabi Farkaseva lema.

  • Opomba. Pri pogojih iz zgornjega izreka so torej Karush-Kuhn-Tuckerjevi pogoji potrebni za optimalnost rešitve.

Konveksni problemi

  • Posledica. Naj bo odprta konveksna množica ter konveksne odvedljive funkcije, tako da velja . Potem je globalni minimum problema vezanih ekstremov z neenačbami natanko tedaj, ko obstaja tak , da ustreza Karush-Kuhn-Tuckerjevim pogojem.

  • Opomba. Takemu problemu rečemo konveksni problem oziroma problem konveksne optimizacije.

    • Čim najdemo eno rešitev Karush-Kuhn-Tuckerjevih pogojev, smo našli optimalno rešitev takega problema (tj., globalni minimum).

Primer

  • Globalni minimum je v točki , kjer pa Karush-Kuhn-Tuckerjevi pogoji niso izpolnjeni. Velja namreč:

Konveksne funkcije in konveksne množice

  • Trditev. Naj bo konveksna množica, konveksna funkcija, ter . Potem je množica konveksna.

  • Dokaz. Vzemimo poljubne ter . Potem velja

    • Velja torej , zato je množica konveksna.

  • Opomba. Če je množica konveksna in so funkcije konveksne ter , potem je množica konveksna.

    • Na primer, za imamo , torej je konveksna funkcija in je tako konveksna množica.

Primer

  • To je konveksni problem:

Primer (pogoji KKT)

Primer (1.)

:

Primer (1.1.)

: ,

Primer (1.2.)

, :

  • Po zgornji posledici je globalni minimum.
  • Ostalih možnosti nam ni potrebno preverjati.

KKT za linearni program

  • Primer. Uporabimo Karush-Kuhn-Tuckerjeve pogoje za linearni program .

  • Zgornji linearni program zapišimo kot problem vezanega ekstrema z neenačbami.

  • Ciljna funkcija in vezi so konveksne, torej imamo konveksni problem.

KKT za linearni program (2)

  • Zapišimo Lagrangeevo funkcijo in Karush-Kuhn-Tuckerjeve pogoje.
    • Ker velja , vektor ustreza ravno spremenljivkam dualnega linearnega programa .
    • Iz izreka o dualnem dopolnjevanju sledi, da je optimalna rešitev linearnega programa in optimalna rešitev njegovega duala natanko tedaj, ko ustreza Karush-Kuhn-Tuckerjevim pogojem.

Fisherjev model trga

  • Imamo kupcev in dobrin.
  • Naj bo:
    • kapital, ki ga ima na voljo -ti kupec,
    • količina -te dobrine na trgu, ter
    • zadovoljstvo -tega kupca z enoto -te dobrine (, ).
  • Imamo torej , in .
  • Predpostavimo še, da:
    • si vsak kupec želi vsaj ene dobrine (torej ),
    • si vsake dobrine želita vsaj dva kupca (torej ).

Pogoji

  • Iščemo:
    • cene -te dobrine,
    • količine -te dobrine, ki jo kupi -ti kupec (, )
  • Iščemo torej in , da velja:
    • oziroma (vsak kupec porabi ves svoj kapital)
    • oziroma (vsaka dobrina se proda v celoti)
    • pri cenah je zadovoljstvo -tega kupca maksimalno
  • Definicija. Cene so ravnovesne, če obstaja , da so izpolnjeni zgornji pogoji.

Primer

  • Ali so cene ravnovesne?

Primer (2)

  • Pogoji niso kompatibilni, zato cene niso ravnovesne.

  • Vaja. Dokaži, da so cene ravnovesne.

Optimalni sveženj

  • Trditev. Če ravnovesne cene obstajajo, potem so pozitivne in (tj., vse dobrine se prodajo za ves kapital na voljo).

  • Dokaz. Denimo, da za nek velja .

    • Ker obstajata taka različna , da velja , sta kupca in najbolj zadovoljna, če dobita vso dobrino , protislovje.
    • Nadalje velja .

  • Definicija. Zadovoljstvo -tega kupca z -to dobrino na denarno enoto je (, ).

    • Naj bo .
    • Optimalni sveženj -tega kupca je množica .

Optimalni sveženj in ravnovesnost

  • Trditev. Naj bosta in takšna, da velja in . Če vsak kupec kupuje samo iz svojega optimalnega svežnja (tj., ), potem so cene ravnovesne.

  • Primer.

    • Pokažimo, da so cene ravnovesne.

Dokaz

  • Če vsak kupec kupuje samo iz svojega optimalnega svežnja, potem velja . Za vsak torej velja

    • Naj bo neka druga dopustna izbira kupljenih količin. Ker velja , za vsak sledi

    • Vrednosti so torej optimalne za vsak .

  • Vprašanji:

    • Ali ravnovesne cene obstajajo? JA.
    • Kako jih poiščemo? S Karush-Kuhn-Tuckerjevimi pogoji.

Eisenberg-Galeov konveksni program (EGP)

  • Brez škode za splošnost lahko predpostavimo, da za vsak velja (oziroma ) - tj., celotna količina vsake dobrine je enota.

    • Če temu ni tako, lahko -ti stolpec matrike pomnožimo s staro vrednostjo (in podobno za dobljeno rešitev ).

  • Pri Fisherjevem modelu trga želimo maksimizirati zadovoljstvo vseh kupcev.

  • Kako iz funkcij dobimo eno? Kako iz števil dobimo eno? Nekaj možnosti:

    • - aritmetična sredina
    • - utežena aritmetična sredina ()
    • - geometrijska sredina ()
    • - utežena geometrijska sredina

Ciljna funkcija

  • Izkaže se, da je "prava" funkcija

  • Iskali bomo torej maksimum te funkcije.

  • Za lažje delo bomo funkcijo logaritmirali; da jo obravnavamo kot ciljno funkcijo konveksnega problema, pa tudi negirali in iskali njen minimum.

Konveksnost ciljne funkcije

  • Trditev. Funkcija

    je konveksna.

  • Dokaz. Pišemo lahko .

    • Funkcija je konveksna (saj ), za vsak pa je funkcija afina in .
    • Potem je za vsak funkcija konveksna.
    • Funkcija je torej vsota konveksnih funkcij in je tako konveksna.

Konveksni program

  • Zapišimo torej Eisenberg-Galeov konveksni program (EGP).

  • Opazimo:

    • za vsak je linearna funkcija (torej afina in zvezna), tako da je konveksna odprta množica
    • ciljna funkcija je konveksna in odvedljiva
    • vse vezi so afine (torej konveksne in odvedljive)

Optimalnost EGP

  • Karush-Kuhn-Tuckerjevi pogoji so torej potrebni in zadostni za optimalnost rešitve.

  • Spomnimo se: množica je kompaktna, ko je zaprta in omejena.

    • Zvezna funkcija na kompaktni množici doseže minimum in maksimum.

  • Izrek. Eisenberg-Galeov konveksni program je dopusten in optimalen.

  • Dokaz. Pokažimo najprej, da je (, ) dopustna rešitev.

    • Res, velja (), () in (, ).

Dokaz

  • Naj bo

    množica dopustnih rešitev.

  • Za definirajmo še množico

  • Množica je omejena (saj ) in zaprta, torej je kompaktna.

  • Funkcija je zvezna, torej doseže minimum na .

  • Vrednost bomo izbrali tako, da bo in .

    • To bo pomenilo, da funkcija doseže minimum na .

Dokaz (2)

  • Da bo , mora veljati

  • Poleg tega bomo zahtevali še

  • Naj bo . Potem za nek velja . Z logaritmiranjem tako dobimo

Dokaz (3)

  • Ker za vsak velja , velja tudi

  • Če k prejšnji neenakosti prištejemo zgornjo za vsak , dobimo

  • Ker so vse zgornje meje za pozitivne, lahko torej izberemo tak , da veljajo zgornji pogoji.

  • Funkcija tako doseže minimum na , zato je konveksni problem optimalen.

Pogoji KKT za EGP

Zapišimo Karush-Kuhn-Tuckerjeve pogoje za Eisenberg-Galeov konveksni program:

Ekvivalentnost FMT in EGP

Izrek. Naj bosta in . Sledeči trditvi sta ekvivalentni.

  1. je optimalna razdelitev za Fisherjev model trga s cenami , kjer vsak kupec kupuje le dobrine iz svojega optimalnega svežnja.

  2. in zadošča Karush-Kuhn-Tuckerjevim pogojem, kjer ustreza

    čč

    (tj., so Lagrangeevi množitelji za vezi ()).

Dokaz (1. 2.)

  • Pogoji , , () ter , (, ) so očitno izpolnjeni.

  • Za vsaka ločimo dva primera, pri čemer bomo upoštevali .

    • Če je , potem je . Ker je , velja , torej

    • Če je , potem velja .

      • Ker velja , velja tudi .

  • Za torej veljajo Karush-Kuhn-Tuckerjevi pogoji.

Dokaz (2. 1.)

  • Ker za vsako dobrino obstaja kupec, ki si je želi, za vsak obstaja , da velja in posledično - tj., vsaka dobrina se proda v celoti.

  • Sledi tudi .

  • Če velja , potem velja in velja enakost v prejšnji neenakosti - tj., vsak kupec kupuje le dobrine iz svojega optimalnega svežnja.

  • Nazadnje za vsak izpeljemo še

  • Velja torej - tj., vsak kupec je porabil ves svoj kapital.

Poenostavljeni pogoji KKT za EGP

Zapišimo še poenostavljene Karush-Kuhn-Tuckerjeve pogoje za Eisenberg-Galeov konveksni program:

Primer

  • S Karush-Kuhn-Tuckerjevimi pogoji dobimo sledečo rešitev:

  • Trdimo, da so tudi ravnovesne cene.

Primer (2)

  • Ravnovesne cene torej niso enolične!
  • V tem primeru prvi kupec kupuje tudi izven svojega optimalnega svežnja.

Primer (3)

Izkaže se, da so pri teh podatkih vse možne ravnovesne cene