Benders Dekompozíció

általánosítása a Farkas tétel felhasználásával

Csergőffy Tibor V. éves matematikus hallgató

Témavezető: Vizvári Béla docens

ELTE TTK 1998.

Tartalomjegyzék

1 Bevezetés 3 1.1 Dekompozíciós elv . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Farkas és Haar tétele, Farkas lemma . . . . . . . . . . . . . . . 4 1.3 Benders dekompozíció . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Többcélú optimalizálás 12 2.1 Általánosított Benders dekompozíció . . . . . . . . . . . . . . 12

3 Sok lineáris változós feladat 14 3.1 Konvex halmazok . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Projekció . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 Halmazok elválasztása hipersíkkal . . . . . . . . . . . . . . . . 18 3.4 Sokfeltételes Farkas tétel . . . . . . . . . . . . . . . . . . . . . 19 3.5 Általánosított Benders dekompozíció . . . . . . . . . . . . . . 25 3.6 Algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4 Általánosítás konvex, zárt kúpra 29 4.1 Farkas tétel konvex, zárt kúpra . . . . . . . . . . . . . . . . . 29 4.2 Dekompozíció konvex, zárt kúpból vett lineáris változókra . . 30

5 Gyakorlati megfontolások 31

Irodalomjegyzék 34

1 Bevezetés

1.1 Dekompozíciós elv

Az alkalmazott matematikában szép számban fordulnak elő nagy méretű feladatok. Ezen problémák számítási- és tárigényük miatt nehezen vagy egyáltalán nem kezelhetők. Ilyen és hasonló nehézségek kiküszöbölésére találták ki a dekompozíciós eljárásokat.

Ezek lényege, hogy egy nagyobb, esetenként speciális alakú feladatot, több kisebb feladatra osztanak. Különbség adódik a szeparálás módjában. A legismertebb az 1960-ban publikált Dantzig-Wolfe dekompozíció [3]. Ennek lényege abban fogható meg, hogy a feladatot a feltételek mentén vágja fel.

Ezzel szemben a dolgozat címében megjelölt Benders dekompozíció [1] a változók mentén vágja két, illetve iteratíve több részre. Ez az eljárás valójában a Dantzig-Wolfe dekompozíció duálisa, viszont sokkal könnyebben általánosítható nemlineáris feltételeket is tartalmazó feladatokra. A Benders dekompozíció általános kimondásában a változók eleve két részre vannak osztva: egy lineárisra és egy nemlineárisra. A dekompozíció lényege abban van, hogy a feladat megoldása során sok hasonló, azonos alakú, csak a feltételekben módosuló feladatot kell megoldani.

Számítási szempontból a legműveletigényesebb az ún. főfeladat (angolul: master problem). Ez képezi a feladat magját. Itt lényegében a nemlineáris változókat rögzítjük, és csak egy lineáris programot oldunk meg. Valójában a főfeladat - feltételek elhagyásával keletkező - relaxáltjait kell megoldani, majd egy-egy lineáris programozási feladattal ellenőrizni, hogy a relaxált feladat optimális megoldása megengedett megoldása-e a főfeladatnak. Amenynyiben megengedett, akkor a rögzített nemlineáris változóhoz, mely egy optimális megoldás része, egy másik lineáris program segítségével megkeressük az optimális lineáris változót. Amennyiben a relaxált főfeladat megoldása nem megengedett megoldás a főfeladatban, akkor megadja egy korábban megkonstruált kúp extremális irányát, mellyel egy új feltételt írunk fel, amit beveszünk a feltételek közé. Mivel véges sok extremális irány van, ezért az algoritmus azért áll le, mert a feladat nemkorlátos, vagy nincs megengedett megoldása, vagy pedig megtalálta az optimumot.

Az elméleti háttérhez hozzátartozik, hogy a Benders dekompozíció semmi bonyolult eredményt nem használ fel, csak a Farkas tételt. Bár a Benders dekompozíciónak létezik általánosítása, ezek nem a Farkas tétel általánosításait használják, hanem a számítási sebesség csökkentésére irányulnak, közelítő eljárásokról van szó. A legismertebb és a gyakorlatban valóban sokat használt algoritmus a Generalized Benders decompsition eljárás [7], mely Geoffriontól származik. Ismert egy sztochasztikus programozásbeli általánosítása is: a Nested Benders decomposition [12].

Ebben a munkában a Farkas tétel általánosításait felhasználva kiterjesztjük azon feladatok körét, melyekre használható a Benders dekompozíció. Többek között a többcélfüggvényes esetre, végtelen sok lineáris változó esetére, illetve olyan esetre, amikor a lineáris változóról nem csak azt tehetjük fel, hogy a nemnegatív ortánsban van, hanem, hogy egy tetszőleges konvex, zárt kúp eleme.

1.2 Farkas és Haar tétele, Farkas lemma

Az operációkutatás egyik talán legrégibb, de minden bizonnyal a legismertebb tétele a Farkas Gyuláról elnevezett tétel és lemma. Már 1894-ben publikálta ezt az eredményt [4]. Bár a tétel bizonyítása ekkor még hiányos, a teljes bizonyítás megtalálható későbbi publikációiban ([5], [6]). Prékopa András részletes történeti áttekintést ad a tétel fejlődéséről [9].

A Farkas tétel homogén lineáris egyenlőtlenségek megoldhatóságát vizsgálja: 1.1 Tétel: A következők ekvivalensek:

a^{T} x ≦ 0 következménye Ax ≦ 0 -nak ,  (i)
∃\underline{λ} ≧ 0, hogy a^{T} = \underline{λ}^{T} A .  (ii)

Bizonyítás: (i) ⇒ (ii) Tekintsük a következő feladatot:

\begin{aligned}max & a^{T} x \\ & Ax & ≦ & 0 . \end{aligned}  (P)

Ennek a feladatnak létezik optimális megoldása: x = 0, mivel a^{T} x ≦ 0 következik a feltételből. Ebből az is következik, hogy a duálisnak is létezik optimális megoldása, azaz a következő feladatnak:

\begin{aligned}min & 0^{T} y \\ & A^{T} y & = & a \\ & y & ≧ & 0 . \end{aligned}  (D)

Innen az \underline{λ} = y választás megfelel. (ii) ⇒ (i) A feltételből a^{T} x = \underline{λ}^{T} Ax ≦ \underline{λ}^{T} 0 = 0. ⊠

A Haar tétel pedig az inhomogén lineáris egyenlőtlenségek megoldhatóságát vizsgálja: 1.2 Tétel: A következők ekvivalensek:

a^{T} x ≦ b′ következménye A^{T} x ≦ b-nek ,  (i)
∃\underline{λ} ≧ 0 , λ′ ≧ 0 , hogy ∀x ∈ ℝ^{n} : a^{T} x − b′ = \underline{λ}^{T} (A^{T} x − b) − λ′ . (ii)

A Farkas lemma viszont egy alternatíva tétel: 1.3 Tétel: Legyen D ∈ ℝ^{m×n} mátrix, d ∈ ℝ^{m} egy vektor. A két feladat közül pontosan egynek van megoldása:

(i) Dx = d , x ≧ 0  ∥  (ii) y^{T} D ≧ 0^{T} , y^{T} d < 0 .

Bizonyítás: 1. lépés: Egyszerre nem oldhatók meg. Indirekten tegyük fel, hogy az (i)-nek létezik x megoldása és (ii)-nek y . Következésképpen:

y^{T} Dx = (\underbrace{y^{T} D}_{≧0^{T}}) \underbrace{x}_{≧0} ≧ 0 ,

y^{T} Dx = y^{T} d < 0 .

Ez viszont ellentmondás.

2. lépés: Tegyük fel, hogy az (i)-nek nincs megoldása, ekkor elég bizonyítani, hogy (ii)-nek van. Ehhez tekintsük a

max 0^{T} x : Dx = d , x ≧ 0  (P)

és

min d^{T} y : D^{T} y ≧ 0  (D)

primál-duál feladatpárt. A feltevésből jön, hogy (P)-nek nem létezik megengedett megoldása, viszont a (D)-nek létezik (y = 0). Ebből az következik, hogy a duál nemkorlátos, azaz:

∃ y : D^{T} y ≧ 0 , d^{T} y < 0 ,

ami azt jelenti, hogy (ii)-nek van megoldása. ⊠ Hogy bizonyítsuk a Farkas tétel és a Farkas lemma közötti szoros kapcsolatot, megadjuk az előbbi bizonyítását felhasználva az utóbbit. 1.1 Tétel bizonyítása: (i) ⇒ (ii) Legyen D := A^{T} és d := a. Ekkor

Ax ≦ 0 következménye a^{T} x ≦ 0

írható a következő alakban is:

A(−x) ≧ 0 következménye a^{T} (−x) ≧ 0 .

Ez éppen azt jelenti, hogy az 1.3 tétel (ii) alternatívája nem teljesül, azaz (i) teljesül:

∃x : A^{T} x = a , x ≧ 0 ,

ahol \underline{λ} := x választással igazoltuk ezt az irányt. (ii) ⇒ (i) Tudjuk, hogy fennáll:

∃\underline{λ} : A^{T} \underline{λ} = a , \underline{λ} ≧ 0 .

Ez nem más, mint 1.3 tétel (i) alternatívája, így (ii) nem állhat fenn, tehát

∀y : Ay ≧ 0 következménye a^{T} y ≧ 0

igaz. ⊠

1.3 Benders dekompozíció

A következő feladatot akarjuk megoldani:

max c^{T} x + f(y)
Ax + F (y) ≦ b
x ≧ 0  y ∈ S ,

(F)

ahol x, c ∈ ℝ^{n}, y ∈ S ⊆ ℝ^{k}, ahol S tetszőleges, b ∈ ℝ^{m} , F : S → ℝ^{m} , f : S → ℝ, és F (S), f(S) korlátosak.

Tekintsük ehelyett a

max z
z − c^{T} x − f(y) ≦ 0
Ax + F (y) ≦ b
x ≧ 0  y ∈ S

feladatot. Bevezetjük a következő jelöléseket:

C = \{( \begin{matrix}u_{0} \\ u \end{matrix} ) | A^{T} u − cu_{0} ≧ 0 , u_{0} ≧ 0 , u ≧ 0\} ,
C_{0} = {u | A^{T} u ≧ 0 , u ≧ 0} ,
P = {u | A^{T} u − c ≧ 0 , u ≧ 0} .

1.1 Lemma: ∀(z, y) ∈ ℝ × S -re ekvivalensek:

( ∃ x : x ≧ 0 , Ax + F (y) ≦ b , z − f(y) − c^{T} x ≦ 0 ) ,  (1)
( ∀ ( \begin{matrix}u_{0} \\ u \end{matrix} ) ∈ C : u_{0}(z − f(y)) + u^{T} F (y) ≦ u^{T} b ) .  (2)

Bizonyítás: Létezik x, ami kielégíti az (1) rendszert. Ez pontosan akkor áll fenn, ha létezik (v, v_{0}) kiegészítő változó:

Ax + v  = b − F (y)
−c^{T} x  + v_{0} = −z + f(y)
(x, v, v_{0}) ≧ 0 ,

D = ( \begin{matrix}A^{T} & −c \\ E & 0 \\ 0^{T} & 1 \end{matrix} ) jelöléssel (x^{T} , v^{T} , v_{0})D = ( \begin{matrix}Ax + v \\ −c^{T} x + v_{0} \end{matrix} ) .

A Farkas tétel szerint pontosan akkor, ha D ( \begin{matrix}u \\ u_{0} \end{matrix} ) ≧ 0 rendszernek következménye a

( \begin{matrix}b − F (y) \\ −z + f(y) \end{matrix} )^{T} ( \begin{matrix}u \\ u_{0} \end{matrix} ) ≧ 0 .

Az előbbit részletesen kifejtve

\begin{aligned}A^{T} u & − & cu_{0} & ≧ & 0 \\ u & & & ≧ & 0 \\ & & u_{0} & ≧ & 0 \end{aligned} ⟺ ( \begin{matrix}u_{0} \\ u \end{matrix} ) ∈ C ,

míg az utóbbi: b^{T} u ≧ u^{T} F (y) + u_{0}(z − f(y)), és ez az, amit akartunk. ⊠

Vezessük be a

G = ⋂_{(u_{0},u^{T})^{T} ∈C} {(z, y) | u_{0}(z − f(y)) + u^{T} F (y) ≦ u^{T} b , z ∈ ℝ , y ∈ S }

jelölést. Ez alapján a feladatot visszavezettük a következő két feladat megoldására:

max { z | (z, y) ∈ G } .  (Főfeladat)

Használva a (\overline{z}, \overline{y}) = arg max \{ z | (z, y) ∈ G\} jelölést:

max c^{T} x
Ax ≦ b − F (\overline{y})
x ≧ 0 .

(2)

Mivel a (2) egy lineáris programozási feladat, ezért számunkra csupán a főfeladat vizsgálata fontos.

1.4 Tétel: Tegyük fel, hogy G ≠ ∅. Ekkor a főfeladat pontosan akkor nemkorlátos, ha P = ∅. Bizonyítás: (⇐) A feltevés miatt létezik (z, y) ∈ G. Ha P = ∅, C-ben csak olyan vektorok lehetnek, melyekre u_{0} nulla, mert C kúp. Így azt kapjuk (z, y) ∈ G-ből, hogy u^{T} F (y) ≦ u^{T} b . Ebből minden valós z-re a (z, y) ∈ G. Ekkor a főfeladat nyilván nem korlátos, mert G nem függ z-től.

(⇒) Ha viszont P ≠ ∅, akkor létezik ( 1 \overline{u} ) ∈ C, ekkor z − f(y) + \overline{u}^{T} F (y) ≦

\overline{u}^{T} b , ami egy felső becslést ad z-re, mivel F (S), f(S) korlátosak, tehát a főfeladat korlátos. ⊠

1.2 Lemma: Legyen a Q ⊂ C, és legyen

G′ = ⋂_{(u_{0},u^{T})^{T} ∈Q} { (z, y) | u_{0}(z − f(y)) + u^{T} F (y) ≦ u^{T} b , z ∈ ℝ , y ∈ S } .

A főfeladat gyengébb feltételekkel:

max { z | (z, y) ∈ G′ } ,  (MP′)

melynek (\overline{z}, \overline{y}) optimális megoldása. Ekkor a (\overline{z}, \overline{y}) a főfeladat optimális megoldása, akkor és csak akkor, ha

min \{ (b − F (\overline{y}))^{T} u | u ∈ P \} = \overline{z} − f(\overline{y}) .

Bizonyítás: (⇒) (\overline{z}, \overline{y}) optimális, akkor ∀ ( \begin{matrix}u_{0} \\ u \end{matrix} ) ∈ C esetén u_{0}(\overline{z} − f(\overline{y})) ≦

u^{T} (b − F (\overline{y})), azaz

∀u ∈ P esetén:  z − f(\overline{y}) ≦ u^{T} (b − F (\overline{y})) ,
∀u ∈ C_{0} esetén:  0 ≦ u^{T} (b − F (\overline{y})) .

Nézzük most a

min (b^{T} − F (\overline{y})^{T})u
A^{T} u ≧ c
u ≧ 0

(P)

feladatot. Ez nyilván korlátos, mivel P-t a két feltétel definiálja, és a korábbi tétel miatt a főfeladat korlátos, azaz a z − f(\overline{y}) ≦ u^{T} (b − F (\overline{y})) jó korlátot ad a célfüggvényre. Ebből következik, hogy létezik optimális megoldás, így a duálnak is van optimális megoldása, és ezek egyenlők. A duál:

max c^{T} x
Ax ≦ b − F (\overline{y})
x ≧ 0 .

(D)

Tegyük fel, hogy az optimális megoldások: \overline{u} , \overline{x} . Ekkor a célfüggvényértékek egyenlőségéből adódik:

(b^{T} − F (\overline{y})^{T})\overline{u} = c^{T} \overline{x} = \overline{z} − f(\overline{y}) .

(⇐) Nézzük a következő problémát:

min (b^{T} − F (\overline{y})^{T})u  ( = \overline{z} − f(\overline{y}) )
A^{T} u ≧ c
u ≧ 0 .

Mivel a feladat célfüggvénye korlátos, ezért u ∈ C_{0}-ból következik, hogy (b^{T} − F (\overline{y})^{T})u ≧ 0^{T} , azaz minden ( \begin{matrix}0 \\ u \end{matrix} )-ra teljesül, a G-t definiáló egyenlőtlenség,

így a fentiekkel együtt ∀ ( \begin{matrix}u_{0} \\ u \end{matrix} ) ∈ C-re is teljesül u_{0}(\overline{z}−f(\overline{y})) ≦ u^{T} (b−F (\overline{y})). Tehát (\overline{z}, \overline{y}) ∈ G , így optimális is. ⊠

1.4 Algoritmus

Ezek után a megoldási algoritmus így néz ki:

BEGIN

Q := ∅ ; \overline{z} := +∞ ;

\overline{y} ∈ S ; (tetszőleges)

WHILE true DO BEGIN

w := min_{u∈P}(b − F (\overline{y}))T u ; (Az optimalitási feltétel.)

IF w = \overline{z} − f(\overline{y}) THEN BEGIN

\overline{x} := arg max \{ c^{T} x | Ax ≦ b − F (\overline{y}) , x ≧ 0 \} ;

STOP. (Az (\overline{x}, \overline{y}) optimális megoldás.)

END

ELSE BEGIN (Az optimalitási kritérium nem teljesült.)

IF w > −∞ THEN BEGIN

\overline{u} := arg min \{ (b^{T} − F (\overline{y})^{T})u | u ∈ P \} ; Q := Q ∪ \{(1, \overline{u})\} ;

END
ELSE BEGIN

\overline{u} ∈ Ext(P) ; (Ext(P) a P extremális pontjainak halmaza.)1

\overline{v} ∈ (C_{0} extremális irányai) ;

Q := Q ∪ \{(1, \overline{u}), (0, \overline{v}) \} ;

END;
END;

G(Q) := ⋂_{(u_{0},u^{T})^{T} ∈Q} {(z, y) | y ∈ S, u_{0}(z − f(y)) + u^{T} F (y) ≦ u^{T} b};

IF G(Q) = ∅ THEN STOP. (Nincs megengedett megoldás.)

ELSE (\overline{z}, \overline{y}) := arg max \{ z | (z, y) ∈ G(Q) \}; ^{2}

END; (Vége a WHILE ciklusnak. )

END.

1A szimplex módszer leállásakor szolgáltatott \overline{u} extremális pont és \overline{v} extremális irány veendő be a Q-ba.

2A relaxált feladat optimális megoldása. Ez a WHILE ciklus elejére kerül, ahol ellenőrizzük, hogy a főfeladatnak megengedett megoldása-e?

1.5 Tétel: A fenti algoritmus véges lépésben végetér. Bizonyítás: Vegyük észre, hogy az eljárás során a Q-t mindig a C_{0} extremális irányával és/vagy P extremális pontjával bővítettük. Mivel ezekből végessok van, így az eljárás véges. ⊠

2 Többcélú optimalizálás

2.1 Általánosított Benders dekompozíció

Legyen S egy tetszőleges nemüres halmaz. Legyenek p, m, n pozitív egészek és f : S → ℝ^{p} és g : S → ℝ^{m} függvények, továbbá C_{p×n} , A_{m×n} , b_{m×1} mátrixok.

A következő többcélú optimalizálási feladatra fogunk Benders dekompozíciót készíteni:

max Cx + f(y)
Ax + g(y) ≦ b
x ≧ 0,  y ∈ S.

(1)

Legyen z ∈ ℝ^{p} a célfüggvény vektorváltozója. Ekkor a feladat a következő alakra hozható:

max z
z − Cx − f(y) ≦ 0
Ax + g(y) ≦ b
x ≧ 0,  y ∈ S.

Legyen G olyan (z, y) párok halmaza, melyekhez létezik megengedett x megoldás, azaz

G = { (z, y) | z ∈ ℝ^{p}; y ∈ S; ∃x ∈ ℝ_{+}^{n} : z − f(y) ≦ Cx , Ax ≦ b − g(y) } .

Mint az egycélfüggvényes dekompozíciónál itt is fontos szerepe lesz a

C = \{ ( \begin{matrix}s \\ t \end{matrix} ) | − C^{T} s + A^{T} t ≧ 0 , s ≧ 0 , t ≧ 0 \}

kúpnak.

2.1 Tétel: A (z, y) pár akkor és csak akkor eleme a G halmaznak, ha a

(−z + f(y))^{T} s + (b − g(y))^{T} t ≧ 0

egyenlőség fenáll minden ( \begin{matrix}s \\ t \end{matrix} ) ∈ C -re.

Bizonyítás: A (z, y) pár pontosan akkor eleme a G halmaznak, ha léteznek x ∈ ℝ_{+}^{n} , u ∈ ℝ_{+}^{m} és w ∈ ℝ_{+}^{p} vektorok, melyek kielégítik a

-z + f(y) = -Cx  + w
b – g(y) = Ax + u

egyenlőségeket. Ez ekvivalens a következő mátrixegyenlőséggel:

( \begin{matrix}−z + f(y) \\ b − g(y) \end{matrix} ) = ( \begin{matrix}−C & 0 & I_{p} \\ A & I_{m} & 0 \end{matrix} ) ( \begin{matrix}x \\ u \\ w \end{matrix} ) ,  (2)

ahol I_{m} és I_{p} az m × m-es illetve p × p-es egységmátrixok. A Farkas tétel alapján:

(−z + f(y)^{T} s + (b − g(y))^{T} t ≧ 0  (3)

következménye a következő rendszernek:

\begin{aligned}−C^{T} s & + & A^{T} t & ≧ & 0 \\ & & I_{m}t & ≧ & 0 \\ I_{p}s & & & ≧ & 0 , \end{aligned}  (4)

mivel (3) a (2) egyenlet bal oldalán álló vektor, míg (2) jobboldalán álló mátrix éppen a (4) rendszert adja. ⊠

2.2 Tétel: Tegyük fel, hogy az (1) feladatnak van legalább egy megoldása. Legyen k(1 ≦ k ≦ p) egy tetszőleges index és

C_{k} = \{ ( \begin{matrix}s \\ t \end{matrix} ) ∈ C; s_{k} > 0 \} .

Ha C_{k} = ∅ akkor a feladat k-dik célfüggvénye nem korlátos. Bizonyítás: A feltételekből következik, hogy C minden elemére s_{k} = 0. A 2.1 tétel miatt minden (z, y) ∈ G-re igaz:

∀ ( \begin{matrix}s \\ t \end{matrix} ) ∈ C : (−z + f(y))^{T} s + (b − g(y))^{T} t ≧ 0 .

Legyen λ > 0 tetszőleges pozitív valós szám. Ekkor (z + λe_{k}, y) ∈ G, ahol e_{k} a k-dik egységvektort jelöli, mivel

∀ ( \begin{matrix}s \\ t \end{matrix} ) ∈ C : (−z−λe_{k}+f(y))^{T} s+(b−g(y))^{T} t = (−z+f(y))^{T} s+(b−g(y))^{T} t ≧ 0,

így a 2.1 tétel miatt (z + λe_{k}, y) ∈ G, amiből az állítás következik. ⊠

3 Sok lineáris változós feladat

3.1 Konvex halmazok

3.1 Carathèodory tétel: Legyen U ⊂ ℝ^{n} U ≠ ∅. ∀u ∈ convU előállítható n + 1-nél nem több U-beli vektor konvex kombinációjaként. Bizonyítás:

u ∈ convU ⇒ u = ∑_{i=1}^{m} α_{i}u_{i} , ∑_{i=1}^{m} α_{i} = 1 , α_{i} ≧ 0 , u_{i} ∈ U , ∀i = 1, …, m.

Legyen m > n + 1 és ∀i = 1, …, m -re α_{i} > 0. Vegyük az

ū_{i} ∈ ℝ^{n+1} , ū_{i} = (u_{i}, 1) ∀i = 1, …, m  (1)

vektorokat. Mivel m > n + 1 , {ū_{i}}_{i=1}^{m} lineárisan összefüggők, ezt kifejtve:

∃γ_{i} , i = 1, …, m : ∑_{i=1}^{m} |γ_{i}| ≠ 0 , ∑_{i=1}^{m} γ_{i}ū_{i} = 0 ,

vagyis

∑_{i=1}^{m} γ_{i}u_{i} = 0 , ∑_{i=1}^{m} γ_{i} = 0 .

Innét

u = ∑_{i=1}^{m} α_{i}u_{i} = ∑_{i=1}^{m} α_{i}u_{i} − t \underbrace{∑_{i=1}^{m} γ_{i}u_{i}}_{=0} = ∑_{i=1}^{m}(α_{i} − tγ_{i})u_{i} .

Ha t elég kicsi, akkor α_{i} − tγ_{i} ≧ 0 és ∑_{i=1}^{m} |γ_{i}| ≠ 0 , ∑_{i=1}^{m} γ_{i} = 0 ⇒ ∃γ_{i} > 0.

Jelölje

t := \frac{α_{s}}{γ_{s}} = min_{γ_{i}>0} \frac{α_{i}}{γ_{i}} .

Innen α_{i} − tγ_{i} ≧ 0 , ∀i = 1, …, m, miközben α_{s} − tγ_{s} = 0, így

u = ∑_{i=1,i≠s}^{m}(α_{i} − tγ_{i})u_{i} ,

azaz az u-t előállító vektorok száma eggyel csökkent. Ez a csökkentés mindaddig folytatható az előbbiek szerint, amíg az (1) vektorrendszer lineáris összefüggősége meg nem szűnik, azaz az előállító komponensek száma legfeljebb n + 1. ⊠

3.2 Tétel: Ha U ⊂ ℝ^{n} kompakt, akkor convU is kompakt. Bizonyítás: Azt kell belátnunk, hogy convU korlátos és zárt. U korlátossága azt jelenti, hogy létezik R > 0 úgy, hogy

U ⊂ B(0, R) = {u ∈ ℝ^{n} | ∥u∥ ≦ R} .

B(0, R) konvex, ezért convU ⊂ B(0, R), hiszen convU a legszűkebb U-t tartalmazó konvex halmaz, azaz convU is korlátos. Legyen u a convU torlódási pontja. Ekkor léteznek u_{k} ∈ convU , k = 1, 2, … vektorok, melyekre lim_{k→∞} u_{k} = u. Carathèodory tétele alapján

léteznek u_{k}^{i} ∈ U és α_{k}^{i} ≧ 0 , i = 1, …, n + 1 úgy, hogy

u_{k} = ∑_{i=1}^{n+1} α_{k}^{i}u_{k}^{i} .

A következőkben az ún. átlós eljárást alkalmazzuk. U korlátos, így alkalmas R-re ∥u_{k}^{i}∥ ≦ R és 0 ≦ α_{k}^{i} ≦ 1, így {u_{k}^{1}} , {α_{k}^{1}}-ből kiválaszthatók konvergens {u_{k_{1}}^{1}} és {α_{k_{1}}^{1}} részsorozatok, melyekre

u_{k_{1}}^{1} ⟶_{k_{1}→∞} ũ_{1} ∈ U , α_{k_{1}}^{1} ⟶_{k_{1}→∞} α_{1} ,

az {u_{k_{1}}^{2}} , {α_{k_{1}}^{2}}-ből kiválasztható {u_{k_{2}}^{2}} , {α_{k_{2}}^{2}} konvergens részsorozatok, hogy

u_{k_{2}}^{2} ⟶_{k_{2}→∞} ũ_{2} ∈ U , α_{k_{2}}^{2} ⟶_{k_{2}→∞} α_{2} ,

és így folytatva, végül {u_{k_{n}}^{n+1}} , {α_{k_{n}}^{n+1}}-ből kiválaszthatók {u_{k_{n+1}}^{n+1}} , {α_{k_{n+1}}^{n+1}} konvergens részsorozatok, hogy

u_{k_{n+1}}^{n+1} ⟶_{k_{n+1}→∞} ũ_{n+1} ∈ U , α_{k_{n+1}}^{n+1} ⟶_{k_{n+1}→∞} α_{n+1} .

Nyilván a {k_{n+1}} indexhalmazhoz tartozó elemekre

u_{k_{n+1}}^{i} ⟶_{k_{n+1}→∞} ũ_{i} ∈ U , α_{k_{n+1}}^{i} ⟶_{k_{n+1}→∞} α_{n+1} , i = 1, …, n + 1 ,

így

u_{k_{n+1}} = ∑_{i=1}^{n+1} α_{k_{n+1}}^{i}u_{k_{n+1}}^{i} ⟶_{k_{n+1}→∞} ∑_{i=1}^{n+1} α_{i}ũ_{i} = u ∈ convU

és

1 = ∑_{i=1}^{n+1} α_{k_{n+1}}^{i} ⟶_{k_{n+1}→∞} ∑_{i=1}^{n+1} α_{i} .

Ezzel beláttuk, hogy convU zárt. ⊠

3.2 Projekció

3.1 Definíció: Legyen U ⊂ ℝ^{n} és u ∈ ℝ^{n}. Az u pont vetülete az U halmazra az u-hoz legközelebbi U-beli pont, azaz p = Proj_{U}(u) ∈ U, ha

∥u − p∥ = inf_{v∈U} ∥u − v∥ = δ .

3.3 Tétel: Legyen U ⊂ ℝ^{n} zárt, konvex halmaz. Akkor ∀u ∈ ℝ^{n}-re p = Proj_{U}(u) létezik és egyértelmü.

Bizonyítás: Ha u ∈ U , akkor nyilvánvalóan Proj_{U}(u) = u. Legyen u ∉ U . Az infimum definíciója szerint létezik egy {u_{k}} ⊂ U sorozat úgy, hogy

lim_{k→∞} ∥u_{k} − u∥ = δ .

Legyen ϵ > δ tetszőleges szám. Ekkor egy N küszöbindextől minden k-ra ∥u_{k} − u∥ ≦ ϵ. Innen látjuk, hogy az {u_{k}}_{k=N}^{∞} ⊂ U ∩ O_{ϵ}(u) kompakt halmaz része. A sorozatból kiválasztható egy konvergens részsorozat:

lim_{i→∞} u_{k_{i}} = p ∈ U .

A norma folytonossága miatt ∥p − u∥ = δ. Tegyük fel, hogy a projekció nem egyértelmű, azaz

∃p_{1}, p_{2} ∈ U, p_{1} ≠ p_{2} és ∥p_{1} − u∥ = ∥p_{2} − u∥ = δ .

U konvex, ezért z = \frac{1}{2}p_{1} + \frac{1}{2}p_{2} ∈ U és

∥z − u∥ = ∥\frac{1}{2}(p_{1} − u) + \frac{1}{2}(p_{2} − u)∥ < \frac{1}{2}∥p_{1} − u∥ + \frac{1}{2}∥p_{2} − u∥ = δ ,

ami ellentmond δ definíciójának. A fenti egyenlőtlenség azért szigorú, mert a normára vonatkozó háromszögegyenlőtlenség miatt egyenlőség akkor és csak akkor áll fenn, ha a mi esetünkben \frac{1}{2}(p_{1} − u) = r\frac{1}{2}(p_{2} − u), valamely r ∈ ℝ számra fennáll. De ez p_{1} ≠ p_{2} és ∥p_{1} − u∥ = ∥p_{2} − u∥ miatt nem lehet. ⊠

3.4 Tétel: Legyen az U ∈ ℝ^{n} konvex, zárt halmaz. Pontosan akkor igaz, hogy p = Proj_{U}(u) , ha

∀v ∈ U : ⟨u − p, v − p⟩ ≦ 0 .

Bizonyítás: Szükségesség. Legyen p = Proj_{U}(u) és v ∈ U tetszőleges. Tekintsük a z = αv + (1 − α)p pontot. Mivel U konvex, ezért z ∈ U ∀α ∈ [0, 1]-re.

∥z−u∥^{2} = ∥α(v−p)+(p−u)∥^{2} = α^{2}∥v−p∥^{2} +2α⟨v−p, p−u⟩+∥p−u∥^{2} .

Felhasználva, hogy p = Proj_{U}(u) , definíció alapján: ∥p − u∥ ≦ ∥z − u∥. Ezt és a fenti egyenlőséget összevetve azt kapjuk, hogy

α^{2}∥v − p∥^{2} + 2α⟨v − p, p − u⟩ ≧ 0 ∀α ∈ [0, 1] ,

azaz

⟨u − p, v − p⟩ ≦ \frac{1}{2}α∥v − p∥^{2} ∀α ∈ (0, 1] .

α → 0 esetén a tételbeli egyenlőtlenséget kapjuk. Elégségesség. A tételbeli feltétel miatt minden v ∈ U-ra

∥v−u∥^{2} = ∥(v−p)+(p−u)∥^{2} = ∥v−p∥^{2}−2⟨v−p, u−p⟩+∥p−u∥^{2} ≧ ∥p−u∥^{2} ,

azaz ∥p − u∥ a minimális távolság az u és U pontjai között. ⊠

3.3 Halmazok elválasztása hipersíkkal

3.2 Definíció: Legyen U, V ∈ ℝ^{n}. A ⟨c, u⟩ = γ hipersík c ≠ 0 normálvektorral ténylegesen elválasztja U és V halmazokat, ha

⟨c, u⟩ ≧ γ ∀u ∈ U és ⟨c, v⟩ ≦ γ ∀v ∈ V ,

emellett

∃u_{0} ∈ U , v_{0} ∈ V , melyre ⟨c, v_{0}⟩ < ⟨c, u_{0}⟩ .

3.3 Definíció: Legyen U, V ∈ ℝ^{n}. A ⟨c, u⟩ = γ hipersík c ≠ 0 normálvektorral szigorúan elválasztja U és V halmazokat, ha

sup_{v∈V} ⟨c, v⟩ < γ < inf_{u∈U} ⟨c, u⟩ , ∀u ∈ U , ∀v ∈ V .

3.5 Tétel: Legyen U ⊂ ℝ^{n} konvex, zárt halmaz, U ≠ ∅. Legyen továbbá v ∉ U tetszőleges ℝ^{n}-beli vektor. Létezik c ≠ 0 vektor és γ ∈ ℝ szám, hogy ⟨c, x⟩ = γ hipersík szigorúan elválasztja v-t U-tól.

Bizonyítás: A 3.3 tétel alapján legyen p = Proj_{U}(v) ∈ U és a 3.4 tétel alapján

⟨p − v, u − p⟩ ≧ 0 ∀u ∈ U .

Legyen c = p − v . Ekkor c ≠ 0 és

⟨c, u − v⟩ = \underbrace{⟨p − v, u − p⟩}_{≧0} + \underbrace{∥c∥^{2}}_{>0} ≧ ∥c∥^{2} ∀u ∈ U .  (∗)

Legyen γ = ⟨c, v⟩ + \frac{1}{2}∥c∥^{2} . A fenti egyenlőtlenséget figyelembe véve ⟨c, x⟩ = γ szigorúan elválasztja v-t és U-t. ⊠

3.6 Tétel: Legyen U ⊂ ℝ^{n} konvex, zárt, V ⊂ ℝ^{n} konvex, kompakt halmaz és tegyük fel, hogy U ∩ V = ∅. Akkor U és V szigorúan elválasztható. Bizonyítás: Legyen X = U − V . Legyen x az X halmaz egy torlódási pontja. Akkor létezik {x_{k}} ⊂ X, melyre x_{k} → x .

x_{k} ∈ X ⇒ ∃u_{k} ∈ U , v_{k} ∈ V : x_{k} = u_{k} − v_{k} .

V kompakt, ezért {v_{k}}-ból kiválasztható konvergens {v_{k_{m}}} részsorozat, azaz v_{k_{m}} → v ∈ V . Akkor U zártsága miatt u_{k_{m}} = x_{k_{m}} + v_{k_{m}} → x + v = u ∈ U . Ezért x = u − v , u ∈ U , v ∈ V , azaz X = U − V zárt halmaz. A U ∩ V = ∅ feltétel miatt 0 ∉ X = \overline{X}. A 3.5 tételben láttuk, hogy 0 és X szigorúan elválaszthatóak a ⟨c, x⟩ = γ hipersíkkal, ahol

c = Proj\overline{X}(0) és ⟨c, x⟩ ≧ ∥c∥^{2} , ∀x ∈ X ,

illetve (∗) alapján

⟨c, u⟩ ≧ ⟨c, v⟩ + ∥c∥^{2} ∀u ∈ U , v ∈ V .

Innen

inf_{u∈U} ⟨c, u⟩ ≧ sup_{v∈V} ⟨c, v⟩ + ∥c∥^{2} ∀u ∈ U , v ∈ V .

Legyen γ egy tetszőleges eleme a ( sup_{v∈V} ⟨c, v⟩, inf_{u∈U} ⟨c, u⟩) intervallumnak. Akkor a ⟨c, x⟩ = γ hipersík szigorúan elválasztja U-t és V -t. ⊠

3.4 Sokfeltételes Farkas tétel

3.1 Lemma: Legyen B ⊂ ℝ^{n} kompakt halmaz. Létezik s ∈ ℝ^{n} vektor, hogy max_{b∈B} b^{T} s < 0 ekvivalens a 0 ∉ convB állítással.

Bizonyítás: (⇒) Amennyiben a 0 ∈ convB, akkor a 0 előáll véges sok Bbeli vektor konvex lineáris kombinációjaként. Mivel minden B-beli vektorra a b^{T} s < 0 a feltételezés miatt igaz, ezért lineáris kombinációjukra, a 0 vektorra is, tehát 0 = 0^{T} s < 0 is igaz. Ez ellentmondás. (⇐) Mivel B kompakt, ezért 3.2 tétel miatt convB is kompakt. Így 3.5 tétel miatt szigorúan elválasztható 0-tól egy ⟨c, x⟩ = γ hipersíkkal. Részletesen ez azt jelenti, hogy

⟨c, b⟩ < γ , ha b ∈ convB ,  (a)

illetve

⟨c, 0⟩ > γ .  (b)

A (b) sorból azt kapjuk, hogy γ negatív, azaz az (a) sor azt mondja, hogy minden convB-beli b vektorra a c^{T} b < 0 . Ez azt jelenti, hogy s = c választás megfelel. ⊠ A következő tétel bizonyítással együtt megtalálható [10]-ben.

3.7 Tétel: Legyenek A, B ⊂ ℝ^{n} kompakt halmazok. Tegyük fel, hogy létezik olyan s ∈ ℝ^{n} , hogy

max_{b∈B} b^{T} s < 0 .  (1)

Ekkor a következő két állítás ekvivalens:

max_{a∈A} a^{T} x ≧ 0 , következménye max_{b∈B} b^{T} x ≦ 0 -nak ;  (i)

\begin{matrix}∃t_{0} ∈ ℤ : 1 ≦ t_{0} ≦ n + 1 és ∃t ∈ ℤ : 0 ≦ t ≦ n, \\ ∃a^{i} ∈ A, és ∃μ^{i} ∈ ℝ, μ^{i} ≧ 0, i = 1, …, t_{0}, ∑_{i=1}^{t_{0}} μ^{i} = 1, \\ ∃b^{j} ∈ B, és ∃λ^{j} ∈ ℝ, λ^{j} ≧ 0, j = 1, …, t, hogy \\ ∑_{i=1}^{t_{0}} μ^{i}a^{i} + ∑_{j=1}^{t} λ^{j}b^{j} = 0 . \end{matrix} \} (ii)

Bizonyítás: (i) ⇒ (ii) Létezik egy s ∈ ℝ^{n}, hogy max_{b∈B} b^{T} s < 0. A lemma alapján 0 ∉ convB. A conv B a korábbi lemmák alapján kompakt és konvex halmaz. Ehhez a conv B halmazhoz konstruálunk egy

Z = {z ∈ ℝ^{n} | z = −γb, b ∈ convB, γ ≧ 0}  (2)

halmazt, amely természetesen konvex, sőt belátjuk, hogy zárt is.

3.1 Állítás: A fenti Z halmaz zárt. Bizonyítás: Minden z ∈ Z-hez létezik b ∈ convB, hogy z = −γb valamilyen nemnegatív γ-ra. Ha z és b között fennáll a fenti kapcsolat, akkor nevezzük őket párnak. Legyen {z_{i}}_{i=1}^{∞} ⊂ Z egy tetszőleges sorozat, mely tart z-hez. Be kell látnunk, hogy z Z-ben van. A {z_{i}} sorozathoz tatozik egy {b_{i}} ⊂ convB sorozat, amelyre igaz, hogy minden i ∈ {1, 2, …}-re z_{i} és b_{i} párt alkotnak. A convB kompakt, így létezik {b_{i_{k}}} részsorozat, mely konvergens és egy b vektorhoz tart. Állítom, hogy z és b párt alkotnak. Tegyük fel, hogy nem.

Ekkor létezik a z-nek és az e = {x ∈ ℝ^{n} | x = δb, δ ∈ ℝ } egyenesnek diszjunkt környezeteik ( U_{z}, ill. U_{e}). Az U_{e} valójában egy olyan körkúp, melynek tengelye b irányú. Léteznek az N(U_{z}) és N(U_{e}) küszöbindexek, hogy

∀k ≧ N(U_{z}) : z_{i_{k}} ∈ U_{z},  (3a)
∀k ≧ N(U_{e}) : b_{i_{k}} ∈ U_{e}.  (3b)

Legyen N = max {N(U_{z}), N(U_{e})}. Ekkor (3a) miatt minden N-nél nagyobb k-ra z_{i_{k}} ∈ U_{z} és z_{i_{k}} = δ_{k}b_{i_{k}}. Illetve (3b) miatt b_{i_{k}} ∈ U_{e}, de ekkor az U_{e} kúpnak eleme δ_{k}b_{i_{k}} is. Ami ellentmondás, hisz z_{i_{k}} ∈ U_{z} ∩ U_{e}. •

3.2 Állítás: convA ∩ Z nem üres. Bizonyítás: Tegyük fel indirekten, hogy a metszet üres. A convA-ról tudjuk, hogy konvex és kompakt. A szeparációs tétel miatt létezik egy convA-t és Z-t szigorúan elválasztó hipersík {x ∈ ℝ^{n} | c^{T} x = α, c ≠ 0}, azaz

∀a ∈ convA :  c^{T} a < α;  (4a)
∀z ∈ Z :  c^{T} z > α .  (4b)

A z = 0 ∈ Z választással (4b)-ből azt kapjuk, hogy α < 0. Így (4a) alapján minden a ∈ convA-ra c^{T} a < 0. Továbbá

max_{a∈A} c^{T} a ≦ max_{a∈convA} c^{T} a < 0 .  (5)

Másrészről c^{T} z = −γc^{T} b és (4b) alapján fennáll:

c^{T} z = −γc^{T} b > α ,  ∀b ∈ convB , ∀γ ≧ 0 .  (6)

Ha c^{T} b > 0 valamilyen b ∈ B-re, akkor elég nagy γ-t választva c^{T} z = −γcb ≦ α, ami ellentmond (6)-nak. Tehát azt kaptuk, hogy minden b ∈ Bre c^{T} b ≦ 0 igaz. Ez azt jelenti, hogy

max_{b∈B} c^{T} b ≦ 0 .  (7)

(7)-ből felhasználva (i)-t, azt kapjuk, hogy

max_{a∈A} c^{T} a ≧ 0 ,

ami ellentmond (5)-nek. •

Létezik egy a^{0} eleme convA-nak, mely benne van a Z kúpban is, ami azt jelenti, hogy létezik egy γ^{0} ≧ 0 és b^{0} ∈ convB, hogy

a^{0} = −γ^{0}b^{0}.  (8)

A Carathèodory tétel miatt b^{0} előáll legfeljebb n + 1 B-beli pont konvex kombinációjaként:

\begin{matrix}∃b^{j} ∈ B , ∃ϑ^{j} ∈ [0, 1] , j = 1, …, n + 1 : \\ b^{0} = ∑_{j=1}^{n+1} ϑ^{j}b^{j} , ahol ∑_{j=1}^{n+1} ϑ^{j} = 1. \end{matrix}  (9)

Mivel B ⊂ ℝ^{n}, ezért ami előáll n + 1 darab B-beli vektor konvex kombinációjaként, az előáll n darab B-beli vektor nemnegatív lineáris kombinációjaként is. (8)-ból a következő rendszert kapjuk:

\begin{matrix}−a^{0} & = & ∑_{j=1}^{t} λjb^{j} , \\ λ^{j} & ≧ & 0 ,  j = 1, …, t , \\ 0 & ≦ & t ≦ n . \end{matrix}  (10)

Ha az a^{0} ∈ convA helyére beírjuk az n + 1 darab A-beli vektoros konvex lineáris kombinációként való előállítását, akkor éppen (ii)-t kapjuk. (ii) ⇒ (i) Ez az irány nagyon egyszerű. Tudjuk:

∑_{j=1}^{t} λ^{j}b^{j} = − ∑_{i=1}^{t_{0}} μ^{i}a^{i} ,  (11)

innen, ha max_{b∈B} b^{T} x ≦ 0, akkor

0 ≧ ∑_{j=1}^{t} λ^{j}(b^{j})^{T} x = − ∑_{i=1}^{t_{0}} μ^{i}(a^{i})^{T} x .  (12)

Ha max_{a∈A} a^{T} x < 0, akkor (12) jobboldala pozitív. Ez viszont ellentmondás. ⊠

Az fentiekben megismert Farkas tétel egy lényegesen gyengébb változatát használjuk fel. Pontosabban azt a speciális esetet, amikor A = {a} ⊂ ℝ^{n} egyelemű halmaz. Ekkor a tétel így szól:

3.7’ Tétel: Legyen a ∈ ℝ^{n} vektor és B ⊂ ℝ^{n} kompakt halmaz. Tegyük fel, hogy létezik olyan s ∈ ℝ^{n}, hogy

min_{b∈B} b^{T} s > 0 .  (1)

Ekkor a két állítás ekvivalens:

a^{T} x ≧ 0 , következménye min_{b∈B} b^{T} x ≧ 0 -nak ;  (i)

\begin{matrix}∃t ∈ ℤ : 0 ≦ t ≦ n, \\ ∃b^{j} ∈ B, és ∃λ^{j} ∈ ℝ, λ^{j} ≧ 0, j = 1, …, t, hogy \\ ∑_{j=1}^{t} λ^{j}b^{j} = a . \end{matrix} \}  (ii)

A 3.1 lemma mutatja, hogy az (1) feltétel nagyon erős, hiszen ekvivalens azzal, hogy 0 ∉ convB. A 3.8 tétel egy gyengébb feltétel mellett bizonyít ekvivalenciát.

3.8 Tétel: A 3.7′ tétel jelöléseit alkalmazva (i) és (ii)ekvivalensek, feltéve:

0-nak létezik n − 1 dimenziós környezete convB-ben, vagy 0 ∉ convB. (1′)

Bizonyítás: (ii) ⇒ (i) Ehhez az irányhoz nem kell a feltétel, tehát nem kell újra belátnunk.

(i) ⇒ (ii) Ha a 0 vektor teljesíti (1′)-et, akkor három eset lehetséges.

1. eset: 0 ∉ convB. Ezt az esetet tárgyalja a 3.7′ tétel.

2. eset: 0 ∈ int(convB) . Ez esetben a 3.7 tételben definiált Z halmaz éppen az ℝ^{n}. A tétel bizonyítása azon múlik, hogy Z ∩ {a} nemüres, ami itt triviálisan teljesül.

3. eset: 0 ∈ ∂(convB) és teljesíti (1′)-et, akkor Z egy zárt féltér lesz, melynek határolólapja éppen az (1′)-ben megkövetelt környezetet tartalmazó hipersík. A bizonyítás innen ugyanúgy történik, mint a 3.7 tételben, használható a szétválasztási tétel Z-re és convA-ra. ⊠

A következő példa azt mutatja meg, hogy a 3.8 tételben kimondott (1′) feltételen nem lehet sokat javítani.

1. kép: A példa

3.1 Példa: Legyen a 3.8 tétel jelöléseit alkalmazva

n = 2 , B = { x ∈ ℝ^{2} | ∥x − (0, 1)∥ ≦ 1 } A = {(1, 0)} .

Mivel A egyelemű ezért A = convA. Mivel B konvex, kompakt, ezért B = convB. Megmutatjuk, hogy a 3.7 tétel (i) állítását a példa teljesíti, de a (ii) mégsem igaz rá. Lényegében csak egyetlen x vektor a (0, −1) (és pozitív konstansszorosai) elégíti ki a

max_{b∈B} b^{T} x ≦ 0  (i1)

feltételt. Ebből következik, hogy

max_{a∈A} a^{T} x ≧ 0 ,  (i2)

azaz (1, 0)∗(0, −1) skaláris szorzat nempozitív. Tehát (0, −1) kielégíti (i)-et. (ii) azt mondja ki, hogy

∃t ≦ n, λ^{j} ∈ ℝ , b^{j} ∈ B j = 1, …, t : −(1, 0) = ∑_{j=1}^{t} λ^{j}b^{j}  (ii∗)

Szorozzuk be mindkét oldalt skalárisan (0, −1)-gyel. A baloldal értéke 0 lesz, míg a jobboldal (i) miatt nemnegatív. Egyetlen B-beli vektorra lehet a skalárszorzat 0, ez pedig a (0, 0) vektor. Tehát (ii∗) jobboldali szummájában minden j-re b^{j} = 0 , azaz a szumma maga is a 0 vektor, viszont a baloldalon nem az áll. Ez azt jelenti, hogy (ii) nem lehet igaz.

Ebben a példában egyébként a Z halmaz azon vektorokból álló féltér, melyek második koordinátájukban negatívak, továbbá a (0, 0) vektor. Jól látszik, hogy Z nem zárt. ⊠

3.5 Általánosított Benders dekompozíció

3.7’ tétel segítségével erre a feladatra is használható a dekompozíció:

max  c^{T} x + f(y)
Kx + F (y) ≦ b
x ∈ X ,  y ∈ S ,

(2)

X = { x ∈ ℝ_{+}^{κ} | x-nek csak véges sok komponense pozitív } .

Továbbá c ∈ ℝ^{κ} , S ⊂ ℝ^{k} tetszőleges, F : S → ℝ^{m} , f : S → ℝ , b ∈ ℝ^{m} , K ∈ ℝ_{m×κ}, ahol κ legfeljebb kontinuum számosság és F (S), f(S) korlátosak. Vegyük észre, hogy az X halmaz kúp. Később látjuk, hogy fel kell tennünk még, hogy létezik u ∈ ℝ^{m} minden komponensében pozitív vektor, melyre K^{T} u > c . Hasonlóan az eredeti Benders dekompozícióhoz a C kúp itt is fontos szerepet tölt be:

C = \{( \begin{matrix}u_{0} \\ u \end{matrix} ) | K^{T} u − u_{0}c ≧ 0 , u ≧ 0 , u_{0} ≧ 0 \} .

Bevezetjük a z célfüggvényváltozót, és ahogyan ezt korábban is tettük egy új feltételt: z − c^{T} x − f(y) ≦ 0 . A főfeladat megfogalmazásához a következő lemma szükséges:

3.2 Lemma: Minden (z, y) ∈ ℝ×S párra ekvivalens a következő két állítás, feltéve, hogy (K^{T} , −c) sorai ℝ^{m+1}-ben kompakt halmazt alkotnak.

(∃x : x ∈ X , Kx + F (y) ≦ b , z − f(y) − c^{T} x ≦ 0) ,  (a)
(∀ ( \begin{matrix}u_{0} \\ u \end{matrix} ) ∈ C : b^{T} u ≧ F (y)^{T} u + u_{0}(z − f(y))) .  (b)

Bizonyítás: Ha létezik x, ami (a)-t kielégíti, akkor létezik v, v_{0} slack változó, hogy

Kx + v  = b − F (y)
−c^{T} x  + v_{0} = −z + f(y)
(x, v, v_{0}) ≧ 0 .

Ez az egyenlőségrendszer felírható mátrixegyenlőségként:

( v^{T} , v_{0}, x^{T} ) \underbrace{( \begin{matrix}I_{m} & 0 \\ 0^{T} & 1 \\ K^{T} & −c \end{matrix} )}_{=D} = ( \begin{matrix}b − F (y) \\ −z + f(y) \end{matrix} )^{T} .

A D ∈ ℝ_{κ×m+1} , ezért alkalmazható rá az általánosított Farkas tétel. A mátrixegyenlőség szerint a Farkas tétel (ii) állítása igaz, tehát (i) is teljesül. Vegyük észre, hogy ez éppen lemmánk (b) állítása, ha D sorai az ℝ^{m+1}- ben kompakt halmazt alkotnak, de ez a feltétel miatt teljesül. Nem szabad elfelejteni, hogy csak akkor volt jogos 3.7′ tételt alkalmazni, ha (1) feltétel teljesül:

∃0 < ( \begin{matrix}u \\ u_{0} \end{matrix} ) ∈ ℝ^{m+1} : D ( \begin{matrix}u \\ u_{0} \end{matrix} ) > 0 ⇔ K^{T} \frac{u}{u_{0}} > c ,

amit korábban fel is tettünk. ⊠

Ezen lemma alapján felírhatjuk a főfeladatot:

max {z | (z, y) ∈ G} ,

ahol

G = ⋂_{(u_{0},u^{T})^{T} ∈C} {(z, y) | b^{T} u ≧ F (y)^{T} u + u_{0}(z − f(y))} .

Ha az optimális \overline{z}, \overline{y} a kezünkben van, akkor az optimális \overline{x}-et ez a feladat találja meg:

max c^{T} x
Kx ≦ b − F (y)
x ∈ X .

A 3.8 tétel segítségével bővebb feladatosztályra is elvégezhető a dekompozíció, de nehezebb ellenőrizni az (1′) feltételt a D mátrix soraiból alkotott halmaz konvex burkára.

Vegyük észre, hogy az 1.4 tétel itt is érvényes a

P = {u | K^{T} u ≧ 0 , u ≧ 0 }

jelöléssel. Nemcsak a tételkimondás, hanem a bizonyítás is szóról szóra megegyezik.

Szükségünk lesz még az 1.2 lemma analogonjára is az algoritmushoz.

3.3 Lemma: Legyen Q ⊂ C, és legyen

G(Q) = ⋂_{(u_{0},u^{T})^{T} ∈Q} { (z, y) | u_{0}(z − f(y)) + u^{T} F (y) ≦ u^{T} b , z ∈ ℝ , y ∈ S } .

A főprobléma gyengébb feltételekkel:

max { z | (z, y) ∈ G(Q) } ,

melynek (\overline{z}, \overline{y}) optimális megoldása. Ekkor a (\overline{z}, \overline{y}) a főfeladat optimális megoldása, akkor és csak akkor, ha

min \{ (b − F (\overline{y}))^{T} u | u ∈ P \} = \overline{z} − f(\overline{y}).  (∗)

Bizonyítás: (⇒) Feltesszük, hogy (\overline{z}, \overline{y}) , a relaxált főfeladat optimális megoldása a főfeladatnak is megengedett, így optimális megoldása. Ez azt jelenti, hogy minden C-beli vektorra fennáll: u_{0}(\overline{z} − f(\overline{y})) + u^{T} F (\overline{y}) ≦ u^{T} b . Ha u_{0} = 0 , akkor a kapott feltétel nem ad Z-re megkötést, ha pedig u_{0} > 0 , akkor az egyenlőtlenség mindkét oldala leosztható u_{0}-val. Amit kapunk az az \frac{u}{u_{0}} ∈ P-vel felírt egyenlőtlenség. Ennek következtében a G-t leíró egyenlőtlenségrendszer ekvivalens a

min_{u∈P} u^{T} (b − F (\overline{y})) ≧ \overline{z} − f(\overline{y})  (∗∗)

rendszerrel. Ha itt az egyenlőtlenség szigorú, az azt jelenti, hogy \overline{z} növelhető anélkül, hogy a feltételrendszer sérülne. Ez azt jelenti, hogy (\overline{z}, \overline{y}) nem lehetett a relaxáltnak optimális megoldása, de még a főfeladatnak sem. (⇐) Elég megmutatnunk, hogy (\overline{z}, \overline{y}) ∈ G. A másik irány bizonyításában láttuk, hogy G feltételrendszere ekvivalens (∗∗)-gal. (\overline{z}, \overline{y}) teljesíti (∗)-ot, így (∗∗)-ot is. ⊠

3.6 Algoritmus

Az algoritmus lefuttatása előtt eldöntjük, hogy P üres-e? Amennyiben nemüres, lefuttatjuk az alábbi algoritmust. Az algoritmus alapötletét megtaláljuk [11]-ben. Mivel κ végtelen számosság, ezért C-ről nem lehet állítani, hogy véges sok extremális iránya van (még κ = ℵ_{0} esetén sem). Ez két problémát vet fel. A kevésbé lényeges, hogy az algoritmus nem lesz véges. Ami nagyobb gond, hogy amennyiben Q elemei nem feszítik ki C-t, akkor előfordulhat, hogy az algoritmus elvéti az optimumot. Tehát biztosítani kell, hogy a cone(Q) = C egyenlőség fennálljon, hacsak végtelen sok lépés után is.

BEGIN

Q_{0} := ∅ ;

Q_{1} := ∅ ;

\overline{z} := +∞ ;

\overline{y} ∈ S ; (tetszőleges)

    WHILE true DO BEGIN

w := min_{u∈P}(b − F (\overline{y}))T u ; (Az optimalitási feltétel.)

     IF w = \overline{z} − f(\overline{y}) THEN BEGIN

\overline{x} := arg max \{ c^{T} x | Kx ≦ b − F (\overline{y}) , x ≧ 0 \} ;

STOP. (Az (\overline{x}, \overline{y}) optimális megoldás.)

       END

ELSE BEGIN (Az optimalitási kritérium nem teljesült.) U := \{ u | (b − F (\overline{y}))^{T} u < \overline{z} − f(\overline{y}) \} ; (A fentiek miatt U ≠ ∅) \overline{u} ∈ U ; (tetszőleges) û_{0} := \frac{1}{∥(1,\overline{u}^{T})^{T} ∥} ; (normálás)

û := \frac{\overline{u}}{∥(1,\overline{u}^{T})^{T} ∥} ;

\overline{v} := arg max \{ α | α ≦ ∥u − \frac{(1,v^{T})^{T}}{∥(1,v^{T})^{T} ∥}∥ , u ∈ Q_{1} , v ∈ P \};

v̂_{0} := \frac{1}{∥(1,\overline{v}^{T})^{T} ∥} ; (normálás)

v̂ := \frac{\overline{v}}{∥(1,\overline{v}^{T})^{T} ∥} ;

\overline{w} := arg max \{ α | α ≦ ∥u − \frac{(1,w^{T})^{T}}{∥(1,w^{T})^{T} ∥}∥ , u ∈ Q_{0} , w ∈ C_{0} \};

ŵ := \frac{\overline{w}}{∥\overline{w}∥} ; (normálás)

Q_{1} := Q_{1} ∪ {(û_{0}, û) , (v̂_{0}, v̂)};

Q_{0} := Q_{0} ∪ {(0, ŵ)}; Q := Q_{0} ∪ Q_{1} ;

G(Q) := ⋂_{(u_{0},u^{T})^{T} ∈Q} {(z, y) | u_{0}(z − f(y)) + u^{T} F (y) ≦ u^{T} b};

IF G(Q) = ∅ THEN STOP. (A relaxáltnak sincs megengedett megoldása. )

ELSE (\overline{z}, \overline{y}) := arg max \{ z | (z, y) ∈ G(Q) \};

       END;

END; (Vége a WHILE ciklusnak. )

END.

3.9 Tétel: Ha C zárt kúp, akkor \overline{z} konvergál az optimális megoldás célfüggvényértékéhez. Bizonyítás: Legyen T a C és az egységgömb metszete. T zárt, korlátos halmaz, ezért kompakt. C minden eleme rávetíthető normálással a T halmazra. Az algoritmus biztosítja, hogy coneQ mindenütt sűrű C-ben. ⊠

4 Általánosítás konvex, zárt kúpra

4.1 Farkas tétel konvex, zárt kúpra

4.1 Definíció: Legyen K ∈ ℝ^{n} tetszőleges kúp. Ekkor K adjungált kúpja:

K^{∗} = {c ∈ ℝ^{n} | c^{T} x ≧ 0 , ∀x ∈ K} .

Könnyen ellenőrízhető, hogy K^{∗} is kúp.

4.1 Tétel: Tegyük fel, hogy K ⊂ ℝ^{n} konvex, zárt kúp, A ∈ ℝ_{n×m} , b ∈ ℝ^{m}. A következő két állítás ekvivalens:

∃x ∈ K : Ax = b ,  (i)
y^{T} A ∈ K^{∗}-nak következménye y^{T} b ≧ 0 .  (ii)

Bizonyítás: (i) ⇒ (ii) Tegyük fel, hogy a tétel (i) állítása fennáll, de indirekten van olyan y ∈ ℝ^{m}, hogy

y^{T} A ∈ K^{∗}  (1a)
y^{T} b < 0 .  (1b)

(1a) miatt y^{T} Ax ≧ 0 , míg (1b) miatt y^{T} Ax = y^{T} b < 0 . Ez ellentmondás.

(ii) ⇒ (i) Tegyük fel, hogy (ii) teljesül, de nem létezik K-beli x , melyre Ax = b . Ekkor A(K) = {Ax | x ∈ K} konvex, zárt kúp és b vektor ℝ^{m}-ben hipersíkkal elválaszthatók. Azaz

∃y ∈ ℝ^{m} (y ≠ 0) : y^{T} Ax ≧ 0 ∀x ∈ K , y^{T} b < 0 .

Ez ellentmond (ii)-nek. ⊠

4.2 Dekompozíció konvex, zárt kúpból vett lineáris változókra

Legyen K ⊂ ℝ^{n} tetszőleges konvex, zárt kúp, S ⊂ ℝ^{m} tetszőleges halmaz, A ∈ ℝ_{m×n}, L ⊂ ℝ^{m} konvex, zárt kúp. Tekintsük a

max  c^{T} x + f(y)
b −  Ax − F (y) ∈ L
x ∈ K  y ∈ S

feladatot. Bevezetve a z célfüggvényváltozót

max z
z − c^{T} x − f(y) ≦ 0
b −  Ax − F (y) ∈ L
x ∈ K  y ∈ S

feladatra transzformáljuk. Azt a kérdést szeretnénk megválaszolni, hogy milyen rögzített (z, y) értékre létezik kiegészítő, megengedett x vektor. Ha ilyen x létezik, akkor a

( \begin{matrix}−c^{T} & 0^{T} & 1 \\ A & I_{m} & 0 \end{matrix} ) ( \begin{matrix}x \\ v \\ v_{0} \end{matrix} ) = ( \begin{matrix}f(y) − z \\ b − F (y) \end{matrix} ) , ahol x ∈ K , v ∈ L , v_{0} ≧ 0 (2)

kiegészítő változókat tartalmazó mátrixegyenlőségnek is van megoldása. A Farkas tételben szereplő kúp: F = {(x, v, v_{0}) | x ∈ K , v ∈ L , v_{0} ≧ 0}. Ez nyílván konvex és zárt. A (2) egyenlőség éppen a Farkas tétel (i) pontja, így igaz (ii) is. Legyen

C = \{( \begin{matrix}u_{0} \\ u \end{matrix} ) | ( u_{0}, u^{T} ) ( \begin{matrix}−c^{T} & 0^{T} & 1 \\ A & I_{m} & 0 \end{matrix} ) ∈ F^{∗}\} .

A Farkas tétel (ii) állítása alapján pontosan akkor létezik kiegészítő x , ha

∀ ( \begin{matrix}u_{0} \\ u \end{matrix} ) ∈ C-ra ( u_{0}, u^{T} ) ( \begin{matrix}f(y) − z \\ b − F (y) \end{matrix} ) ≧ 0

igaz. Ekkor a főfeladat a következő alakot ölti:

max {z | (z, y) ∈ G} ,

ahol

G = ⋂_{(u_{0},u^{T})^{T} ∈C} \{(z, y) | (u_{0}, u^{T}) ( \begin{matrix}f(y) − z \\ b − F (y) \end{matrix} ) ≧ 0 , z ∈ ℝ , y ∈ S\} .

Ha (\overline{z}, \overline{y}) optimális megoldása a főfeladatnak, akkor

max  c^{T} x
b − Ax − F (\overline{y}) ∈ L
x  ∈ K

kúpprogramozási feladat megadja az optimális \overline{x}-et.

5 Gyakorlati megfontolások

Gyakorlati, számítási szempontból egy algoritmusnak azontúl, hogy véges sok lépésben véget kell érnie, ha megállítják – valamilyen technikai okból, vagy az iterációk nagy száma, vagy a hosszú futási idő miatt – szolgálnia kell részeredménnyel. Az 1. fejezet végén ismertetett algoritmus ezzel a tulajdonsággal nem rendelkezik, de kis módosítással elérhető, hogy a megszakítás után az eddig talált legjobb megengedett megoldást megadja. A módosítás megtalálható [8]-ban. A probléma azért merül fel, mivel mindig egy relaxált feladatot oldunk meg, melynek megoldásairól rendre kiderül, hogy a főfeladatnak nemmegengedett megoldásai. A megoldás kulcsa, hogy a célfüggvényre nem csak felső, hanem alsó becslést is számontartunk. Ezt alapozza meg a következő lemma.

5.1 Lemma: Tekintsük a

min (b^{T} − F (\overline{y})^{T})u
A^{T} u ≧ c
u ≧ 0 ,

(P)

max c^{T} x
Ax ≦ b − F (\overline{y})
x ≧ 0

(D)

primál-duál feladatpárt.

a) Ha a (P) feladat célfüggvénye nem korlátos, akkor az \overline{y} vektorhoz nem található olyan \overline{x} vektor, hogy az első fejezetben (F)-fel jelölt eredeti feladatnak megengedett megoldása legyen (\overline{x}, \overline{y}) .

b) Ha a (P) feladatnak optimális megoldása van, akkor az adott \overline{y} mellett az (F) feladat lehető legjobb célfüggvényértékét az az \overline{x} vektor adja, mely rendelkezésünkre áll, ha a (P) feladatot módosított szimplex módszerrel oldjuk meg és a

f(\overline{y}) + u^{T} (b − F (\overline{y}))

érték az (F) feladat optimális célfüggvényének alsó becslése. Bizonyítás: a) Ebben az esetben a dualitás tétel szerint (D) feladatnak nincs megengedett megoldása, tehát nincs kiegészítő \overline{x} vektor sem.

b) Szintén a dualitás tétel miatt (D)-nek optimális megoldása van (\overline{x} ). Ez azt jelenti, hogy (\overline{x}, \overline{y}) megengedett megoldás, célfüggvényértéke alsó becslés az optimumra. ⊠

A lemma felhasználásával könnyen beépíthető néhány új változó, melyekben a célfüggvény aktuális alsó becslését, illetve az aktuális megengedett (\overline{x}, \overline{y}) megoldást tároljuk. Az algoritmust csak kiegészíteni kell egy szubrutinnal, melyet akkor kell lefuttatni, ha az 1.4 alfejezetben leírt algoritmus jelölései alapján w > −∞. A szubrutin azt ellenőrzi le, hogy az új \overline{y} és így a módosított szimplex módszer adta, plusz számítást nem igénylő \overline{x} által adott célfüggvényérték, nevezetesen c^{T} \overline{x}+f(\overline{y}) = f(\overline{y})+u^{T} (b−F (\overline{y})) nagyobb-e, mint a tárolt érték. Amennyiben a válasz igenlő, akkor kicseréli a megfelelő változókat az új értékekre, különben azokat változatlanul hagyja.

Az algoritmus során tárolt alsó illetve felső becslések arra is lehetőséget adnak, hogy leállási kritériumot adjunk meg. Az alábbiakban megadunk néhány lehetséges leállási kritériumot:

• az elért alsó becslés kellően nagy, egy korlát fölött van;

• a felső és alsó becslés eltérése egy küszöb alá esik;

• az előző két kritérium kiegészítve egy időkorláttal.

Ezen kritériumok beépítése a számítási időt lerövidíti, melyre [8]-ban találunk példákat.

Köszönetnyilvánítás

Köszönettel tartozom Kassay Gábornak^{3}, aki értékes megjegyzésekkel segítette a dolgozat elkészítését, és hozzájárult a tételek élesítéséhez. Továbbá köszönetet mondok Kovács Margitnak^{4}, akinek Nemlineáris programozás és Konvex analízis előadása nélkül ez a dolgozat nem készülhetett volna el. Köszönet illeti témavezetőmet, Vizvári Bélát^{5}, aki rendkívüli alapossággal tanulmányozta át újra meg újra a dolgozatot, értékes tanácsaival hozzájárult, hogy a dolgozat mind tartalmilag, mind szerkezetileg folyamatosan csiszolódjon, és elnyerje végső formáját.

3Babes-Bólyai Egyetem, Analízis és Operációkutatási Tanszék, 3400 Cluj-Napoca, Kogalniceanu 1., Romania

4Eötvös Loránd Tudományegyetem, Operációkutatási Tanszék, H-1088 Budapest, Múzeum krt. 6-8., margo@cs.elte.hu

5Eötvös Loránd Tudományegyetem, Operációkutatási Tanszék, H-1088 Budapest, Múzeum krt. 6-8., vizvari@cs.elte.hu

Irodalomjegyzék

[1] Benders J. F., Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik 4 (1962), 238-252.

[2] Craven B.D., Koliha J.J., Generalizations of Farkas‘ Theorem, SIAM J. Math. Anal., 8 (1977), 983-997.

[3] Dantzig G.B., Wolfe P., Decomposition principle for linear programs, Operations Research 8 (1960), 101-111.

[4] Farkas Gyula, A Fourier-féle mechanikai elv alkalmazásai, Matematikai és Természettudományi Értesítő 12 (1894), 457-472.

[5] Farkas Gyula, A Fourier-féle mechanikai elv alkalmazásának alapja, Matematikai és Természettudományi Értesítő 16 (1898), 361-364.

[6] Farkas Gyula, Theorie der einfachen Ungleichungen, J. für Reine und Angewandte Mathematik 124 (1901), 1-27.

[7] Geoffrion A.M., Generalised Benders decomposition, Journal of Optimization Theory and Applications, 10 (1972), 237-260.

[8] Hoffer János, Megengedett megoldások vizsgálatával bővített Benders dekompozíciós algoritmus, Alkalmazott Matematikai Lapok, 5 (1979), 177-190.

[9] Prékopa András, On the development of optimization theory, Amer. Math. Monthly 87 (1980), 527-542.

[10] Shimizu K., Aiyoshi E., Katayama R., Generalized Farkas‘ Theorem

and Optimization of Infinitely Constrained Problem, Journal of Optimization Theory and Applications, 40 (1983) 451-463.

[11] Vizvári Béla, Benders Decomposition for cone programming, A. Göpfert, J. Seeländer, Chr. Tammer (eds.) Proceedings of the 6th Workshop of the DGOR-Working Group Multicriteria Optimization and Decision Theory Alexisbad 1996, Deutsche Hochschuleschriften 2398, Verlag Hänsel-Hohenhausen, Engelsbach/Frankfurt/Washington, (1997), 109-116.

[12] Wittrock R. J., Advances in a nested decomposition algorithm for solving staircase linear programs, Technical Report SOL 83-2, System Optimization Laboratory, Stanford University (1983)