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.