La 17-an de julio 1991

Konveksaj aroj kaj funkcioj

Christer Kiselman

Enhavo:

1. Enkonduko

2. La konveksa tegaĵo de aro

3. Apartigaj hiperebenoj

4. Apogaj duonspacoj kaj apogaj hiperebenoj

5. Ekstremaj punktoj

6. La teoremo de Carathéodory

7. La reela akso finizita

8. Konveksaj funkcioj

9. La transformo de Fenchel

10. Dualeco

11. La apoga funkcio de aro

12. La teorio pri ludoj kaj lineara programado Bibliografio

1. Enkonduko La celo de tiuj ĉi notoj estas prezenti la bazajn ecojn de konveksaj aroj kaj funkcioj. Precipe ni pritraktas la teoremojn pri apartigo de aroj kaj la koncepton de ekstrema punkto. La teoremoj pri apartigaj hiperebenoj kondukas nin al studo de dualeco, kiun ni esprimas per la transformo de Fenchel kaj la apoga funkcio.

Mi lekciis pri tiu temo en San Marino en septembro 1990, kadre de la sepa Sanmarina Universitata Sesio de la Akademio Internacia de la Sciencoj.

2. La konveksa tegaĵo de aro Du punktoj a kaj b en R^{n} difinas segmenton

[a, b] = {(1 − t)a + tb; 0 ⩽ t ⩽ 1} ⊂ R^{n}.

Ĝi estas parto de la tuta rekto {(1 − t)a + tb; t ∈ R}. Se a = b, tiam kaj la segmento kaj la rekto kompreneble estas nur punkto. Aro A en R^{n} nomiĝas konveksa se ĝi enhavas la tutan segmenton [a, b] kiam ĝi enhavas a kaj b. Aro nomiĝas afina subspaco se ĝi kune kun a kaj b enhavas la tutan rekton tra a kaj b.

Ni nomas K ⊂ R^{n} konuso se, unue, 0 ∈ K, kaj, due, tx apartenas al K kiam x ∈ K kaj t estas pozitiva nombro. Konuso K sekve estas konveksa ĝuste kiam ĝi enhavas ĉiun punkton sa + tb por ĉiuj a, b ∈ K kaj ĉiuj s, t ⩾ 0. Finfine ni nomas A lineara subspaco de R^{n} se estas tiel ke 0 ∈ A kaj A enhavas sa + tb por ĉiuj a, b ∈ A kaj ĉiuj s, t ∈ R. Ni do povas resumi ĉiujn postulojn per la komuna implico

a, b ∈ A ⇒ sa + tb ∈ A,

sed kun diversaj kondiĉoj sur s, t: por konveksaj aroj s ⩾ 0, t ⩾ 0 kaj s + t = 1; por afinaj subspacoj s, t ∈ R kaj s + t = 1; por konusoj s ⩾ 0, t = 0; por konveksaj konusoj s, t ⩾ 0; por linearaj spacoj s, t ∈ R. Krome ni havas malsamajn postulojn rilate al la malplena aro: evidente Ø estas la plej malgranda konveksa aro kaj la plej malgranda afina subspaco; dum {0} estas la plej malgranda konuso, la plej malgranda konveksa konuso kaj la plej malgranda lineara subspaco. (Ĉie tie regas kompreneble iom da arbitro: ni povus postuli ke konveksa aro estu nemalplena; ni povus akcepti Ø kiel linearan subspacon. Sed estas dezirinde fiksi konvencion, kaj tiu kiun ni alprenis ŝajnas funkcii bone.)

Ni nun havas la implicojn:

konveksa aro  ⇐  afina subspaco
⇑  ⇑
konuso  ⇐  konveksa konuso  ⇐  lineara subspaco

La komunaĵo de familio de konveksaj aroj estas konveksa. Estas facile vidi tion. La konveksa tegaĵo de ajna aro X estas laŭdifine la komunaĵo de ĉiuj konveksaj aroj kiuj enhavas la aron X. Oni notas ĝin per kvt X, do

kvt X = ⋂(A; A konveksas kaj A ⊃ X).

Estas tiam klare ke kvt X estas konveksa aro, kaj krome estas la plej malgranda konveksa aro kiu enhavas la aron X. Same ni povas difini tegaĵojn en pluraj aliaj kazoj. Por iu ajn familio F de aroj ni ja povas meti

(2.1)  h(X) = ⋂(A; A ∈ F kaj A ⊃ X).

Ni nomas la aron h(X) la F-tegaĵo de X. Montriĝas ke la operatoro h ĉiam havas la sekvajn tri ecojn:

1. X ⊂ h(X) (h estas pli granda ol la idento);

2. X ⊂ Y implicas h(X) ⊂ h(Y) (h estas kreskanta);

3. h(h(X)) = h(X) (h estas idempotenta).

Iun ajn operatoron h kun tiuj ecoj oni nomas tega operatoro.

Ni povas difini ekzemple la afinan tegaĵon de X jene: ĝi estas la plej malgranda afina subspaco kiu enhavas la aron X. Same ni povas difini la fermitan tegaĵon: tiam ni prenas por F la aron de ĉiuj fermitaj aroj; temas nun pri topologio kaj ne pri geometrio, sed la tri ecoj de la tega operatoro estas la samaj. (La fermita tegaĵo kutime nomiĝas la fermitaĵo.) Interesan geometrian tegan operatoron ni ekhavas se ni prenas por F la aron de ĉiuj fermitaj duonspacoj (vidu sekcion 3). Tiam la tegaĵo de aro estas la komunaĵo de ĉiuj fermitaj duonspacoj kiuj enhavas ĝin. Ni pruvos ke tiu komunaĵo estas la fermite konveksa tegaĵo. Do malsamaj familioj F povas difini la saman operatoron.

La priskribo de tegaĵo kiel nefinia komunaĵo donas tre simple kelkajn ecojn de la operatoro, sed ĝi ne estas tre geometria. Ni tial deziras pli uzeblan prezenton. La sekva teoremo donos al ni tian.

Teoremo 2.1. Estu X subaro de R^{n}. La diversaj tegaĵoj kiujn ni enkondukis povas esti priskribitaj jene helpe de linearaj kombinaĵoj

(2.2)  ∑_{j=1}^{N} λ_{j}x_{j}

kie λ_{j} ∈ R kaj x_{j} ∈ X:

1. La konveksa tegaĵo egalas al la aro de ĉiuj linearaj kombinaĵoj (2.2) kie N estas entjero ⩾ 1, λ_{j} ⩾ 0 kaj ∑ λ_{j} = 1. (Tiaj linearaj kombinaĵoj nomiĝas konveksaj.)

2. La afina tegaĵo estas la responda aro kun la postuloj N ⩾ 1, λ_{j} ∈ R kaj ∑ λ_{j} = 1. (Ili nomiĝas afinaj linearaj kombinaĵoj.)

3. La konusa tegaĵo (la konuso kiu estas generita de X) ekestas se N ⩾ 0, λ_{1} ⩾ 0 kaj λ_{j} = 0 por j ⩾ 2.

4. La konuse konveksan tegaĵon oni ekhavas se N ⩾ 0 kaj λ_{j} ⩾ 0.

5. La lineara tegaĵo de X egalas al la aro de ĉiuj linearaj kombinaĵoj (2.2) kie N estas entjero ⩾ 0, λ_{j} ∈ R.

Pruvo. Notu unue la diferencon inter la postuloj pri N. Se ni ĉiam postulas ke N estu almenaŭ 1, tiam h(Ø) = Ø; tiel ni faris por la afinaj kaj konveksaj tegaĵoj. Sed se ni kontraŭe permesas ke N = 0 en la sumo de ĉiuj linearaj kombinaĵoj (2.2), tiam h(Ø) egalas al {0}; tio validas por la konusaj, konuse konveksaj kaj linearaj tegaĵoj. La kaŭzo estas ke ∑_{1}^{0} = ∑_{Ø} = 0 povas esti formita se ni permesas N = 0, sed ne se ni postulas ke N ⩾ 1 kaj X estas malplena.

Ni faros la pruvon nur en la kazo de la konveksa tegaĵo; la aliaj kazoj estas similaj (aŭ eĉ pli simplaj). Metu A egalan al la aro de ĉiuj konveksaj linearaj kombinaĵoj de punktoj en X. Evidente A enhavas la aron X: prenu N = 1 kaj λ_{1} = 1. Plue A konveksas, ĉar se ni havas du punktojn a kaj b en A, tiam ekzistas du prezentoj

a = ∑_{1}^{N} λ_{j}x_{j}, b = ∑_{1}^{M} μ_{j}y_{j}

por iuj punktoj x_{j} kaj y_{j} en X. Por pruvi ke A estas konveksa ni montros ke ĉiu punkto c = (1 − t)a + tb kun 0 ⩽ t ⩽ 1 apartenas al A. Tio sekvas el la formulo

c = (1 − t)a + tb = ∑_{1}^{N}(1 − t)λ_{j}x_{j} + ∑_{1}^{M} tμ_{j}y_{j} = ∑_{1}^{N+M} ν_{j}z_{j},

kie ni enkondukis z_{j} = x_{j} kaj ν_{j} = (1 − t)λ_{j} por j = 1, ..., N, dum z_{j} = y_{j−N} kaj ν_{j} = tμ_{j−N} por j = N + 1, ..., N + M. Oni kontrolas ke

∑ ν_{j} = (1 − t) ∑ λ_{j} + t ∑ μ_{j} = (1 − t) + t = 1.

Tio signifas ke A estas konveksa, kaj tial ke A ⊃ kvt X.

Inverse, ni montros ke A ⊂ kvt X. Tio sekvos se ni povas montri ke ĉiu konveksa aro Y kiu enhavas X ankaŭ enhavas A. Ni do montru ke ĉiu konveksa lineara kombinaĵo ∑ λ_{j}x_{j} apartenas al Y se x_{j} ∈ X ⊂ Y. Por N = 1 tio klaras; por N = 2 estas tutsimple la difino de konvekseco. Ni supozu nun ke N ⩾ 3 kaj ke ni jam pruvis la rezulton por N − 1. Se ∑_{1}^{N−1} λ_{j} > 0, ni rajtas skribi

∑_{1}^{N} λ_{j}x_{j} = ∑_{1}^{N−1} λ_{j}x_{j} + λ_{N}x_{N} = ( ∑_{1}^{N−1} λ_{k}) ∑_{1}^{N−1} \frac{λ_{j}}{∑_{1}^{N−1} λ_{k}} x_{j} + λ_{N}x_{N}

= (1 − λ_{N}) ∑_{1}^{N−1} μ_{j}x_{j} + λ_{N}x_{N} = (1 − λ_{N})y + λ_{N}x_{N}.

Ĉi tie ∑ μ_{j} = 1, tiel ke y = ∑_{1}^{N−1} μ_{j}x_{j} ∈ Y laŭ la indukta supozo. Kaj nun ni aplikas la pruvitan rezulton por N = 2 kaj ekhavas (1 − λ_{N})y + λ_{N}x_{N} ∈ Y. Se ∑_{1}^{N−1} λ_{j} = 0, ni havas ∑_{1}^{N} λ_{j}x_{j} = x_{N} ∈ Y. Tio finas la pruvon.

En la pruvo ŝajnas ke la nombro N kreskas senfine: se a povas esti prezentita per N punktoj, kaj b per M punktoj, tiam la intera punkto c estas prezentita per N + M punktoj. Sed povas ja esti ke la nombro N + M estas nenecese granda; eble oni povos iel redukti. Interesa demando tial estas ĉu oni povas limigi la nombron N. La demando gravas, inter alie pro tio ke ni volas havi konveksajn arojn fermitajn. Estu K kompakta aro kaj estu N fiksa nombro. Tiam klaras ke la aro

K_{N} = {∑_{j=1}^{N} λ_{j}x_{j}; λ_{j} ⩾ 0, ∑ λ_{j} = 1 kaj x_{j} ∈ K}

estas kompakta: ĝi estas la bildo de iu kompakta aro per kontinua bildigo. Kaj la konveksa tegaĵo de K estas, kiel ni jam vidis, la kunigaĵo de ĉiuj K_{N} kiam N = 1, 2, 3, ... . Numerebla kunigaĵo de kompaktaj aroj tamen ne ĉiam kompaktas. Tial estas interese scii ke la vico (K_{N}) estas stacia, t. e. ke ekzistas nombro m tia ke la tuta kunigaĵo egalas al K_{m}. Fakte oni povas meti m = n + 1, kie n estas la dimensio de la spaco. Ni pruvos tion en sekcio 6. Ni tamen jam nun notu ke se X estas finia aro, tiam kvt X kompaktas: sufiĉas meti la nombron N egala al la nombro de elementoj en X. Tio jam pruvas la unuan parton de la sekva teoremo.

Teoremo 2.2. La konveksa tegaĵo de finia aro estas kompakta. La konuse konveksa tegaĵo de finia aro estas fermita. Notu ke la konuse konveksa tegaĵo de kompakta aro ne nepre estas fermita (ekzemplo: globo kun la origino ĉe la rando). Pruvo. Restas pruvi ke la konuse konveksa tegaĵo de finia aro estas fermita. Ni faros indukton laŭ la nombro de elementoj de la aro. La rezulto certe validas se N = 0. Ni nun supozu ke la rezulto validas por N − 1 elementoj, kaj ke K estas konveksa konuso generita de N − 1 punktoj. Prenu ankoraŭ unu elementon, ni diru a. Tiam temas pri pruvo ke la aro K_{a} de ĉiuj elementoj de la formo x + λa, kie x ∈ K kaj λ ⩾ 0, estas fermita. Ni supozu tial ke y_{j} = x_{j} + λ_{j}a → y. Ni pruvu ke y ∈ K_{a}. Se la vico de λ_{j} estas barita, tiam ekzistas konverĝa subvico, ni diru λ_{j_{k}} → λ, kaj ni vidas ke la responda subvico de x_{j} konverĝas, ĉar

x_{j_{k}} = y_{j_{k}} − λ_{j_{k}}a → y − λa = x,

kaj x ∈ K pro tio ke x_{j_{k}} ∈ K kaj K estas fermita laŭ la indukta supozo. Do validas ke y = x + λa ∈ K_{a}. Sed povas okazi ke la vico (λ_{j}) estas nebarita, kaj tiam ni pruvos ke K_{a} estas fermita per tute alia rezono. Ni supozu do ke la vico (λ_{j}) estas nebarita. Tiam ekzistas subvico (λ_{j_{k}}) strebanta al plus nefinio, kaj ni rajtas skribi

K ∋ \frac{x_{j_{k}}}{λ_{j_{k}}} = \frac{y_{j_{k}}}{λ_{j_{k}}} − a → −a,

kio montras ke −a ∈ K. Tio implicas ke K_{a} = K + Ra, t. e. la vektora sumo de la konuso K kaj la rekto Ra. Nun ni povas uzi la induktan supozon por vidi ke K + Ra estas fermita. Estu π: R^{n} → R^{n} lineara bildigo kun nulejaro π^{−1}(0) ekzakte egala al Ra. Tiam K + Ra = π^{−1}(π(K)). Plue π(K) estas generita de N − 1 elementoj, do fermita laŭ la indukta supozo, kaj K + Ra = π^{−1}(π(K)) estas fermita kiel malbildo de fermita aro per kontinua bildigo. Tio pruvas la teoremon.

3. Apartigaj hiperebenoj Hiperebeno estas afina subspaco de kodimensio 1. Tio signifas ke ĝi estas donita per unu sola ekvacio ξ · x = b, kie ξ ne nulas. En koordinata formo tio fariĝas

H = {x ∈ R^{n}; ξ_{1}x_{1} + ⋯ + ξ_{n}x_{n} = b},

kie ne ĉiuj koeficientoj ξ_{j} nulas. La kodimensio estas la komplementa dimensio, t. e. ĝi egalas al dim R^{n} − dim H = n − (n − 1) = 1. Hiperebeno ĉiam dividas la spacon R^{n} en du duonebenojn:

D^{+} = {x ∈ R^{n}; ξ · x ⩾ b}  kaj  D^{−} = {x ∈ R^{n}; ξ · x ⩽ b}.

Ilia komunaĵo D^{+} ∩ D^{−} kompreneble egalas al la hiperebeno H. Plue la randoj estas ∂D^{+} = ∂D^{−} = H. La interno de D^{+} (notita (D^{+})^{∘}) estas difinita per la strikta neegalaĵo ξ · x > b. Se ni volas esti pli precizaj ni nomas la duonspacon D^{+} fermita duonspaco kaj ĝian internon (D^{+})^{∘} malfermita duonspaco. Ni havas ∂(D^{+})^{∘} = ∂(D^{−})^{∘} = H kaj (D^{+})^{∘} ∩ (D^{−})^{∘} = Ø.

Hiperebeno ne unike determinas sian ekvacion. Se ni anstataŭe uzas la ekvacion (−ξ) · x = −b, tiam D^{+} kaj D^{−} interŝanĝiĝas, ĉar la signo ja estas difinita per ξ. Do H ne determinas pri tio kiu el la du duonebenoj estos D^{+}. La sekva difino enhavas tian komplikaĵon pri signo, sed tiu ĉi apenaŭ povas estigi problemojn.

Difino 3.1. Estu donitaj du aroj X kaj Y en R^{n}, kaj estu H hiperebeno kun la ekvacio ξ · x = b. Oni diras ke H apartigas X kaj Y se validas ke

ξ · x ⩽ b ⩽ ξ · y por ĉiuj x ∈ X, y ∈ Y.

Ni diras ke H strikte apartigas X kaj Y se validas ke

ξ · x < b < ξ · y por ĉiuj x ∈ X, y ∈ Y.

Ni povas finfine diri (per esprimmaniero pli porokaza) ke H tre strikte apartigas X kaj Y se ekzistas du nombroj b_{1} kaj b_{2} tiaj ke

ξ · x ⩽ b_{1} < b < b_{2} ⩽ ξ · y por ĉiuj x ∈ X, y ∈ Y.

Apartigo do signifas ke X kaj Y situas ĉiu en sia duonspaco, komprenite kiel fermitan duonspacon por la ordinara (nestrikta) apartigo, kaj kiel malfermitan duonspacon por la strikta apartigo. Se Y = {y} konsistas el nur unu punkto ni kompreneble diros ke H apartigas X kaj y se H apartigas X kaj {y}. Tiu speciala kazo estas verdire ekvivalenta al la ĝenerala. Ni notu per H_{b} la hiperebenon kiu estas difinita per ξ · x = b. Oni facile vidas ke H_{b} apartigas X kaj Y por iu nombro b se kaj nur se H_{0} apartigas X − Y = {x − y; x ∈ X & y ∈ Y } kaj la originon. Por la apartigo strikta estas iomete alie: se H_{b} apartigas X kaj Y strikte, tiam ni nur ekhavas ke H_{0} apartigas X − Y kaj la originon (nestrikte). Kaj se H_{0} strikte apartigas X − Y kaj la originon, tiam H_{b} tre strikte apartigas la arojn X kaj Y por iu nombro b. Tio povas iriti, sed la diferenco inter tre strikta kaj strikta apartigo ofte malaperas. Se unu el la aroj kompaktas estas tutsimple neniu diferenco.

Ni volas trovi multajn hiperebenojn – sufiĉe multajn por pruvi ke ĉiu fermita konveksa aro estas komunaĵo de fermitaj duonspacoj (teoremo 3.7), kaj sufiĉe multajn por pruvi ke ĉiu konveksa kompakta aro estas la konveksa tegaĵo de siaj ekstremaj punktoj (sekcio 5).

En la teorio pri konvekseco ekzistas du gravaj teoremoj pri apartigo:

Teoremo 3.2. Se F estas fermita konveksa aro en R^{n} kaj y ∉ F, tiam ekzistas hiperebeno kiu tre strikte apartigas F kaj y.

Teoremo 3.3. Se A estas konveksa aro en R^{n} kaj y ∉ A, tiam ekzistas hiperebeno kiu apartigas A kaj y. La samo validas se y ∈ ∂A. El tiuj ĉi du teoremoj tuj sekvas teoremoj pri apartigo de du aroj:

Teoremo 3.4. Se F kaj K estas du fermitaj konveksaj aroj disaj en R^{n} kaj K krome estas barita, tiam ekzistas hiperebeno kiu tre strikte apartigas F kaj K. Teoremo 3.4 sekvas el teoremo 3.2 pro tio ke ni povas strikte apartigi F − K kaj la originon. Nome, oni vidas ke F − K estas fermita konveksa aro kiu ne enhavas la originon.

Teoremo 3.5. Se X kaj Y estas du konveksaj aroj disaj en R^{n}, tiam ekzistas hiperebeno kiu apartigas X kaj Y. Teoremo 3.5 sekvas el teoremo 3.3 per formado de A = X − Y kiu estas konveksa aro kiu ne enhavas la originon.

Teoremo 3.2 kombine kun teoreomo 2.2 donas la faman lemon de Farkas:

Teoremo 3.6. Estu A finia aro en R^{n} kaj y ∈ R^{n}. Tiam y ne apartenas al la konuse konveksa tegaĵo de A se kaj nur se ekzistas lineara formo ξ tia ke ξ(a) ⩾ 0 por ĉiuj a ∈ A kaj ξ(y) < 0.

Pruvo. Ni aplikas teoremon 3.2 al la konuse konveksa tegaĵo F de A; ni scias dank’al teoremo 2.2 ke F estas fermita. Ni ekhavas ξ(y) < b < ξ(λa) por ĉiu a ∈ A kaj ĉiu λ > 0. Strebigante λ nulen ni vidas ke b ⩽ 0 kaj sekve ξ(y) < 0; strebigante λ nefinien ni vidas ke ξ(a) ⩾ 0.

La geometria signifo de teoremo 3.6 estas ke la konuse konveksa tegaĵo F de finia aro A povas esti priskribita per duonspacoj. Nome, estu

D_{ξ} = {x ∈ R^{n}; ξ(x) ⩾ 0}

la duonspaco difinita per lineara formo ξ ≠ 0. Tiam teoremo 3.6 diras ke y ∉ F se kaj nur se ekzistas ξ tia ke D_{ξ} ⊃ A kaj y ∉ D_{ξ}. Ekvivalentas ke F egalas al la komunaĵo de ĉiuj D_{ξ} ⊃ A, t. e. ke la konuse konveksa tegaĵo de finia aro estas la komunaĵo de ĉiuj duonspacoj kiuj enhavas la aron kaj havas la originon ĉerande. (Eblas doni pli mallongan pruvon de teoremo 3.6 per la metodo jam uzita en la pruvo de teoremo 2.2, sed teoremo 3.2 estas kompreneble pli ĝenerala kiam oni jam konas teoremon 2.2.)

Alia formo de la lemo de Farkas estas la jena: sistemo de ekvacioj

∑_{k=1}^{n} a_{jk}x_{k} = b_{j}, j = 1, ..., m,

havas solvon kun x_{k} ⩾ 0 se kaj nur se ∑ u_{j}b_{j} ⩾ 0 por ĉiuj vektoroj (u_{1}, ..., u_{m}) kun ∑ u_{j}a_{jk} ⩾ 0 por k = 1, ..., n. En unu direkto tio estas facile pruvebla: se ekzistas solvo x kun la menciita eco, tiam

∑ u_{j}b_{j} = ∑_{j} u_{j} ∑_{k} a_{jk}x_{k} = ∑_{k} ( ∑_{j} u_{j}a_{jk})x_{k} ⩾ 0

se nur ∑ u_{j}a_{jk} ⩾ 0. Por la pruvo en la alia direkto ni supozu ke ne ekzistas solvo x kun la menciita eco, kaj ni apliku teoremon 3.6. Rigardu la konuson F en R^{m} kiu konsistas el ĉiuj vektoroj y = (y_{1}, ..., y_{m}) kun y_{j} = ∑ a_{jk}x_{k} por iu x ∈ R^{n} kun x_{k} ⩾ 0. La aro F estas do la konuse konveksa tegaĵo de la punktoj a^{k} = (a_{1k}, ..., a_{mk}) ∈ R^{m}, k = 1, ..., n, kaj povas cetere esti priskribita kiel la bildo en R^{m} de la pozitiveda konuso en R^{n} per la lineara bildigo kiu estas difinita per la matrico (a_{jk}). La supozo ke ne ekzistas solvo x kun la menciita pozitivedeco signifas ĝuste ke b ne apartenas al la konuso F. Laŭ teoremo 3.6 tiam ekzistas lineara formo ξ tia ke ξ(b) < 0 kaj ξ(∑ a_{jk}x_{k}) ⩾ 0 por ĉiuj x_{k} ⩾ 0. Kaj ξ nepre havas la formon ξ(y) = ∑ u_{j}y_{j} por iu elekto de u_{j}. Finfine ni notas ke la eco ∑ u_{j}a_{jk}x_{k} ⩾ 0 por ĉiuj x_{k} ⩾ 0 ekvivalentas al la eco ∑ u_{j}a_{jk} ⩾ 0 por ĉiu k. Tio finas la pruvon de la aserto.

Ni povas reformuli la lastan formon de la lemo de Farkas jene. Ni konsideru la du sistemojn

(S)  ∑_{k=1}^{n} a_{jk}x_{k} = b_{j}, j = 1, ..., m;  x_{k} ⩾ 0, k = 1, ..., n.

kaj

(S^{∗})  ∑_{j=1}^{m} u_{j}a_{jk} ⩾ 0, k = 1, ..., n;  ∑_{j=1}^{m} u_{j}b_{j} < 0.

En matrica formo ni povas skribi ilin

(S)  \{ \begin{matrix}Ax = b \\ x ⩾ 0 \end{matrix}

kaj

(S^{∗})  \{ \begin{matrix}A^{T} u ⩾ 0 \\ b^{T} u < 0. \end{matrix}

(Ni uzas ĉi tie superan indicon T por indiki la operacion de transpono.) La dirita nun signifas ke la sistemo (S) estas solvebla se kaj nur se (S^{∗}) estas nesolvebla. Ekzistas pluraj similaj asertoj kun la strukturo ke unu sistemo de egalaĵoj kaj neegalaĵoj estas solvebla ĝuste kiam alia sistemo, nomita la duala sistemo, estas nesolvebla. La sistemo (S) konsistas el m egalaĵoj kaj n nestriktaj neegalaĵoj kaj difinas fermitan pluredron P en R^{n}, dum (S^{∗}) konsistas el n nestriktaj neegalaĵoj kaj unu sola strikta neegalaĵo kaj difinas pluredron P^{∗} en R^{m}. Kaj la rezulto diras ke ekzakte unu el la pluredroj estas malplena.

Grava konsekvenco de la teoremoj pri apartigo estas ke ni nun havas novan priskribon de la fermite konveksa tegaĵo ankaŭ de nefinia aro.

Teoremo 3.7. Se X estas ajna aro en R^{n}, tiam ĝia fermite konveksa tegaĵo \overline{kvt X} egalas al la komunaĵo de ĉiuj fermitaj duonspacoj kiuj enhavas X. (Speciale: fermita konveksa aro egalas al tiu komunaĵo.)

Pruvo. La komunaĵo de ĉiuj tiaj fermitaj duonspacoj estas fermita konveksa aro, kaj tial devas enhavi F = \overline{kvt X}. Inverse, se x ∉ F, tiam ekzistas laŭ teoremo 3.2 fermita duonspaco D kiu enhavas F sed ne x. Tial la komunaĵo egalas al F.

Oni povas diri ke teoremo 3.7 priskribas la fermite konveksan tegaĵon elekstere, dum teoremo 2.1 priskribas la konveksan tegaĵon elinterne.

Ni nun pruvu la teoremojn pri apartigo. Pruvo de teoremo 3.2. Ni povas supozi ke x = 0 (translaciu) kaj ke F ≠ Ø. Ni studu la funkcion φ(x) = |x| = \sqrt{x · x} sur F kaj ĝian infimon

d = inf(φ(x); x ∈ F).

Evidentas ke 0 < d < +∞: la unua neegalaĵo pro tio ke F estas fermita kaj ne enhavas la originon; la dua pro tio ke F ne estas malplena. Ni scias ke kontinua funkcio – kaj φ estas kontinua – sur fermita barita aro alprenas sian infimon. Nun F ne nepre estas barita, sed en tiu ĉi kazo tio ne estas danĝero. Nome ni povas studi

K = {x ∈ F; |x| ⩽ 2d},

kiu estas kompakta, kaj tiam φ alprenas sian infimon sur K. Sed tiu infimo devas esti la sama kiel la infimo sur F: la valoroj en F \ K ne povas konkurenci kun tiuj en K. Estu do a punkto en F tia ke φ(a) = d. (Verdire a estas unika, sed tion ni ne bezonas scii nun.) Tiu punkto difinas hiperebenon H per la ekvacio a · x = b = a · a kaj fermitan duonspacon D per la neegalaĵo a · x ⩾ a · a. Alivorte, H estas tutsimple la ebeno kiu estas orta al la radio de rigardo el la origino al la plej proksima punkto en F, kaj kiu enhavas tiun punkton. Ni nun volas aserti ke b ⩽ a · x por ĉiuj x ∈ F. Tio signifas ke

0 = a · 0 < c < b ⩽ a · x

por ĉiu x ∈ F kaj ĉiu nombro c kun 0 < c < b, tiel ke ĉiu hiperebeno a · x = c kun tia c estas strikte apartiga. Ni do pruvu ke F estas ene de la duonspaco D. Ni prenu ajnan punkton x ∈ F. Tiam ni scias ke la tuta segmento [a, x] estas en F, ĉar F konveksas. Punkto (1 − t)a + tx en tiu segmento devas havi distancon almenaŭ d al la origino laŭ la difino de d. Tio signifas ke

d^{2} = |a|^{2} = φ(a)^{2} ⩽ φ((1 − t)a + tx)^{2} = ((1 − t)a + tx) · ((1 − t)a + tx)
= (1 − t)^{2}|a|^{2} + 2(1 − t)ta · x + t^{2}|x|^{2}.

Ni studu la funkcion f(t) = φ((1 − t)a + tx)^{2}. Ĝi devas havi pozitivedan derivaĵon en la origino, ĉar se f′(0) < 0, tiam sekvas ke f(t) < f(0) por malgrandaj pozitivaj t, kio ne eblas. Sed ni povas facile kalkuli la derivaĵon:

f′(t) = 2(1 − t)(−1)|a|^{2} + 2(−1)ta · x + 2(1 − t)a · x + 2t|x|^{2}.

Ni metu t = 0: tio donas 0 ⩽ f′(0) = −2|a|^{2} + 2a · x. Do validas a · x ⩾ |a|^{2}, kio estas la dezirataĵo.

Estas eble pli facile fari kontraŭdiran pruvon: se oni supozas ke ekzistas x ∈ F kun a · x < |a|^{2}, tiam f(t) < f(0) por malgrandaj pozitivaj t. Faru desegnaĵon! Pruvo de teoremo 3.3. Ni kompreneble povas supozi ke y = 0. Elektu numereblan densan aron {x_{j}} en A, kaj notu per A_{m} la konveksan tegaĵon de la finia aro {x_{1}, ..., x_{m}}. Ĉar A_{m} estas fermita (teoremo 2.2) kaj ne enhavas la originon, ni povas apliki teoremon 3.2 kaj ekhavas apartigan hiperebenon kun la ekvacio ξ_{m} · x = c_{m} kiu apartigas A_{m} kaj la originon (strikte). La responda ebeno tra la origino, kun la ekvacio ξ_{m} · x = 0, tiam estas apartiga. Kio okazos kiam m → +∞? Se ni elektas ξ_{m} kiel la plej proksiman punkton en A_{m}, tiam povas tre bone esti ke ξ_{m} strebas nulen, kaj tio ne taŭgas. Ni tial normigu, tiel ke |ξ_{m}| = 1. Tiam do ξ_{m} apartenas al la unueva sfero S, kiu estas konata kompakta aro, kaj ni scias ke iu subvico de (ξ_{m}) konverĝas. Estu ξ limeso. Ni rajtas nun esperi ke la hiperebeno

H = {x; ξ · x = 0}

apartigos A de la origino, t. e. ke A situas je unu flanko de ĝi. Ni povas elekti la signojn tiel ke A_{m} estas en la duonspaco

D_{m} = {x; ξ_{m} · x ⩾ 0},

kaj ni tiam montru ke ξ ·x ⩾ 0 por ĉiuj x ∈ A. Supozu ke tio malveras, do ke ekzistas x ∈ A tia ke ξ · x < 0. Tiam ekzistas punktoj x_{k} ajne proksimaj al x kaj same ξ_{m} ajne proksimaj al ξ. Tial ankaŭ validas ξ_{m} · x_{k} < 0 por taŭgaj indicoj m kaj k, kaj ankaŭ por iuj tiaj kun m ⩾ k, kio kontraŭdiras la konstruon kun x_{k} en la duonspaco D_{m} por m ⩾ k.

Se nun y ∈ ∂A, tiam ekzistas punktoj y_{k} kiuj ne estas en A kaj kiuj konverĝas al y. Se ni konsideras duonspacon D_{k} kiu apartigas y_{k} disde A, tiam ni povas kiel en la rezono ĵus farita trovi subvicon de tiaj duonspacoj kiuj konverĝas al duonspaco D kiu enhavas A kaj sur kies rando troviĝas y.

4. Apogaj duonspacoj kaj apogaj hiperebenoj

Difino 4.1. Estu A konveksa aro en R^{n}. Fermita duonspaco D nomiĝas apoga al A se A estas inkludita en D kaj ekzistas komuna randa punkto en A kaj D. Hiperebeno H nomiĝas apoga al A se unu el la du fermitaj duonspacoj kiuj estas difinitaj per H estas apoga al A. Apoga hiperebeno estas do karakterizita per tio ke la aro A kuŝas je unu flanko de H kaj ke H enhavas randopunkton de A.

Se ni konsideras hiperebenon H kiu havas la aron A je unu flanko sia, ni diru ke ξ · a ⩾ b por ĉiuj a ∈ A, kaj H ne estas apoga, tiam povas okazi ke iu hiperebeno ξ · x = b + ε estas apoga (la konstanto b estis tutsimple tro malgranda). Sed povas ankaŭ okazi ke neniu el la duonspacoj ξ · x ⩾ b + ε kun ε > 0 enhavas A. Tiam ne ekzistas apoga hiperebeno kun normalo ξ. Ekzemplo de tio estas A egala al la aro de ĉiuj x ∈ R^{2} kun x_{1} > 0 kaj x_{1}x_{2} ⩾ 1. Tiam la rekto x_{2} = 0 estas hiperebeno kiu ne estas apoga, sed ankaŭ ne ekzistas iu paralela hiperebeno kiu estas apoga.

Fermita duonspaco kiu inkludas donitan konveksan aron do ne nepre estas paralele ŝovebla tiel ke ĝi fariĝas apoga. Per tio fariĝas interese demandi ĉu oni en teoremo 3.7 povas kontentiĝi je apogaj duonspacoj. Ke la demando estas jesa spite al la ĵus prezentita ekzemplo sekvas el la laboro kiun ni jam faris por montri teoremon 3.2. Ni formulas la teoremon tiel:

Teoremo 4.2. Estu F fermita konveksa aro. Tiam F egalas al la komunaĵo de ĉiuj apogaj duonspacoj al F.

Pruvo. Klaras ke la komunaĵo de ĉiuj apogaj duonspacoj inkludas F. Estu nun y ∉ F. Laŭ teoremo 3.2 ekzistas hiperebeno kiu strikte apartigas F kaj y. Tia hiperebeno, kiel ni vidis, ne nepre estas apoga, kaj eble oni ankaŭ ne povas paralele ŝovi ĝin tiel ke ĝi fariĝas apoga. Sed se ni rigardas la pruvon de teoremo 3.2 ni vidas ke ni faris ion pli bonan. La punkto a en F kiun ni trovis, kaj kiu estas la plej proksima punkto en F rigardite el y, difinas hiperebenon kiu trairas a kaj havas F je unu flanko, kaj kiu do estas apoga al F. La pruvo de teoremo 4.2 do estas jam farita en la pruvo de teoremo 3.2.

5. Ekstremaj punktoj La ekstremaj punktoj estas la primoj de la teorio pri konvekseco. Ni memorigu pri tio ke, unuflanke, la primoj estas sufiĉe abundaj por ke ĉiu entjero estu produto de primoj, kaj, aliflanke, ili mem ne povas esti dismetitaj kiel produto de entjeroj alie ol triviale (p = p · 1 = 1 · p = (−p) · (−1) = (−1) · (−p)). En la teorio pri konvekseco al la produto respondas la konveksaj linearaj kombinaĵoj, tiel ke ĉiuj punktoj en la segmento [a, b] estas prezentitaj pere de a kaj b, nome kiel x = (1−t)a+tb. Prezento estas konsiderata triviala se x = a aŭ x = b. Tio okazas se t = 0 aŭ t = 1, sed ankaŭ se a = b. Tio kio respondas al primo estas do punkto kiu ne povas esti prezentita netriviale. Tiu analogio gvidas nin al la sekva difino:

Difino 5.1. Estu donita konveksa aro X. Tiam punkto x nomiĝas ekstrema punkto de X se x ∈ X kaj x ne povas esti prezentita netriviale pere de punktoj en X, t. e. se la ekvacio x = (1 − t)a + tb povas validi kun a, b ∈ X kaj 0 ⩽ t ⩽ 1 nur se x = a aŭ x = b. Ni skribos E(X) por la aro de ĉiuj ekstremaj punktoj de X. Ni tuj vidas ke malfermitaj konveksaj aroj malhavas ekstremajn punktojn se la dimensio pozitivas. Sed ankaŭ fermitaj duonspacoj en dimensio pli alta ol 1 malhavas ekstremajn punktojn. Tial estas nature studi nur fermitajn baritajn arojn. Kaj tiam montriĝas ke la ekstremaj punktoj estas sufiĉe multaj por taŭgi en prezento de la tuta aro. Al la fakto ke ĉiu entjero estas produto de primoj respondas do la sekva teoremo.

Teoremo 5.2. Estu K konveksa kompakta aro. Tiam la konveksa tegaĵo de E(K) egalas al K.

Pruvo. Ĉar E(K) ⊂ K kaj K konveksas, klaras ke kvt E(K) ⊂ K. Ni nun faru indukton laŭ la dimensio por montri ke kvt E(K) ⊃ K. Por n = 0 aŭ n = 1 klaras ke la teoremo veras. Se x estas ajna punkto en K ni desegnas iun rekton tra x kaj trafas du punktojn x_{0} kaj x_{1} kiuj estas randaj en K. (Ili povas kunfandiĝi; tio ne gravas.) Ĉar x ∈ [x_{0}, x_{1}], sufiĉas pruvi ke x_{0}, x_{1} ∈ kvt E(K). Tra x_{0} iras apartiga, do apoga, hiperebeno H laŭ teoremo 3.3. Kaj la indukta supozo diras ke H ∩K estas konveksa kompakta aro kiu egalas al la konveksa tegaĵo de siaj ekstremaj punktoj, ĉar ĝi ja situas en H kiu havas pli malaltan dimension. La problemo do estas identigi la ekstremajn punktojn de H ∩ K.

Mi asertas ke E(H ∩K) ⊂ H ∩E(K). (Verdire validas egaleco, sed ni ne bezonas tion ĉi tie.) Ni prenu punkton y kiu estas ekstrema en H ∩ K. Ni pruvu ke ĝi tiam estas ekstrema ankaŭ en K. Se y situas en la segmento [a, b] ⊂ K, tiam sekvas ke a kaj b devas esti je la sama flanko de H. Ili tiam povas prezenti la punkton y netriviale nur se ili ambaŭ situas en H. Sed ĉar y estas ekstrema en H ∩ K ne ekzistas iu tia netriviala prezento. Tio signifas ke y estas ekstrema en K.

Ni nun scias ke E(H ∩ K) ⊂ H ∩ E(K), kaj ke x_{0} estas elemento de la konveksa tegaĵo de E(H ∩ K). Do x_{0} situas en la konveksa tegaĵo de E(K). La samo validas por x_{1}, kaj do por ĉiu punkto en la segmento [x_{0}, x_{1}], kiu ja enhavas la ajne donitan punkton x ∈ K.

6. La teoremo de Carathéodory Ni nun revenu al la demando kiu restis senresponda en la diskuto antaŭ teoremo 2.2, nome kiom da punktoj en X necesas por formi la konveksan tegaĵon de X. La respondo estas ke la nombro N dependas de la dimensio de la spaco, kaj ke en R^{n} ĉiam sufiĉas n + 1 punktoj. La rezulto do estas la jena teoremo:

Teoremo 6.1. (La teoremo de Carathéodory.) Se X estas aro en R^{n}, tiam ĉiu punkto a en la konveksa tegaĵo de X havas prezenton

a = ∑_{j=1}^{n+1} λ_{j}x_{j}

kie x_{j} ∈ X, 0 ⩽ λ_{j} ⩽ 1 kaj ∑ λ_{j} = 1.

Pruvo. Ni faros indukton laŭ la dimensio, kaj utiligos la ekziston de apartiga hiperebeno. La aserto certe validas en R^{0} = {0} (kaj estas facile pruvebla ankaŭ en R^{1}). Ni supozu ke ĝi veras en R^{n−1}. Se a estas ajna punkto en kvt X ni scias laŭ teoremo 2.1 ke ekzistas prezento

a = ∑_{1}^{N} λ_{j}x_{j}

de la dezirata formo, krom ke la nombro N povas esti tro granda. Estu Y la finia aro {x_{1}, ..., x_{N}}. Evidente validas ke a ∈ kvt Y = K. Ni prenu punkton y ∈ Y. Se y = a ni pretas; se ne, ni desegnas rekton de y tra a kaj nefinien. Ĉar K kompaktas (laŭ teoremo 2.2), tiu rekto nepre enhavas punkton z ∈ ∂K je la alia flanko de a, tiel ke a ∈ [y, z]. Ĉar z estas randa en K, ekzistas laŭ teoremo 3.3 hiperebeno H tra z kun la aro K je unu flanko. Nun H ∩ kvt Y = kvt(H ∩ Y), ĉar se punkto povas esti prezentita kiel konveksa lineara kombinaĵo de punktoj en Y, do je unu flanko de H, tiam ĉiuj tiuj punktoj kiuj fakte estas uzataj situas en H. Tio signifas ke z ∈ kvt(H ∩ Y), kaj ĉar H ∩ Y estas aro en la spaco H de dimensio n − 1, ekzistas laŭ la indukta supozo prezento de z kiel konveksa lineara kombinaĵo de n punktoj en Y, ni diru y_{1}, ..., y_{n}. Finfine la punkto a situas laŭkonstrue en la segmento [y, z], tiel ke la n + 1 punktoj y_{1}, ..., y_{n} kaj y sufiĉas por prezento de a.

Teoremo 6.2. Se K estas kompakta aro en R^{n}, tiam ankaŭ kvt K kompaktas.

Pruvo. Ni notis jam antaŭ teoremo 2.2 ke por ĉiu N la aro

K_{N} = {∑_{j=1}^{N} λ_{j}x_{j}; λ_{j} ⩾ 0, ∑ λ_{j} = 1 kaj x_{j} ∈ K}

estas kompakta ĉar ĝi estas la bildo de kompakta aro per kontinua bildigo. Ni nun scias ke kvt K = K_{n+1}.

7. La reela akso finizita Kiam oni okupiĝas pri reele valoraj funkcioj, tiam oni ofte faras operaciojn, ekzemple formadon de supremo, kiuj rezultigas ekster la reelaj nombroj. Tio kondukas onin al konsidero de +∞ kaj −∞ kiel permesitaj valoroj. Se oni havas nur unu el la nefinioj, tio kutime ne estas tre malfacila, sed se ambaŭ aperas, oni devas akcepti ke la sumo (+∞) + (−∞) ne estas bone difinita, kaj tio devigas onin fari esceptojn en kelkaj asertoj, esceptoj kiuj estas malfacile memoreblaj. Tial havas ioman intereson krei konvenciojn kiuj komfortigas la pritrakton de la esceptoj. Unu tia konvencio estas la enkonduko de la supra kaj malsupra adicioj.

La reela akso finizita estas notita [−∞, +∞] kaj konsistas el ĉiuj reelaj nombroj kaj du novaj elementoj −∞ kaj +∞. Ĝi estas ordigita per la preskribo ke −∞ < x < +∞ por ĉiuj x ∈ R. Tial la supremo kaj infimo fariĝas bone difinitaj operacioj, kaj ni ekhavas i. a.

sup_{x∈Ø} f(x) = −∞,  inf_{x∈Ø} f(x) = +∞

por ĉiuj funkcioj f: X → [−∞, +∞], sekve ankaŭ se ekzemple f estas idente +∞.

Oni nomas la aron [−∞, +∞] dupunkta kompaktigaĵo de R, ĉar ĝi estiĝas per aldono de du punktoj +∞ kaj −∞, kaj ĉar ĝi estas kompakta (ĉiu vico havas akumuliĝan punkton). (Ekzistas ankaŭ unupunkta kompaktigaĵo R ∪ {∞} de R, kiun oni konstruas aldonante nur unu novan punkton ∞. Ĝi ne povas esti ordigita, kaj oni povas ĝin estigi el [−∞, +∞] per kunfando de +∞ kaj −∞.)

La supra adicio estas difinita kiel tiu vastigo de la kutima adicio kie +∞ ĉiam gajnas super −∞, t. e. en kazo de dubo oni elektu +∞. Tio signifas ke

a + · b = lim sup_{\begin{matrix}(x,y)→(a,b) \\ (x,y)∈R^{2} \end{matrix}} x + y ∈ [−∞, +∞] , (a, b) ∈ [−∞, +∞]^{2} .

(La limesa supremo (lim sup) estas ĉi tie laŭ la topologio de [−∞, +∞]^{2}; tiel + · fariĝas supren duonkontinua funkcio de [−∞, +∞]^{2} al [−∞, +∞], vastigaĵo de +.)

Analoge ni difinas la malsupran adicion per la limesa infimo, kaj kompreneble ekhavas a + · b = −((−a) + · (−b)). Finfine ni skribas a + b por a + · b se a + · b = a + · b.

Ni tiam trovas ke nenio estas ŝanĝita por la reelaj nombroj, ke (+∞) + (+∞) = +∞ kaj ke (−∞) + (−∞) = −∞. Plue (+∞) + · (−∞) = +∞ dum (+∞) + · (−∞) = −∞. La du lastaj formuloj estas do la solaj kie la punkto necesas.

Iuj reguloj por trakti + · kaj + · estas tiuj ĉi: ni havas a ⩽ b se kaj nur se

a + · (−b) ⩽ 0, kaj a < b se kaj nur se a + · (−b) < 0. Plue validas

(7.1)  inf_{x∈X}(a + · f(x)) = a + · inf_{x∈X} f(x)

kaj

(7.2)  sup_{x∈X}(a + · f(x)) = a + · sup_{x∈X} f(x)

sen escepto. Por pruvi tiujn formulojn oni kontrolu ilin en la kazoj a = +∞, a = −∞ kaj X = Ø. Por la infimo en kombino kun la malsupra adicio kaj la supremo en kombino kun la supra adicio la reguloj tute ne estas tiel simplaj, kaj cetere preskaŭ neeblas ilin memori.

8. Konveksaj funkcioj La difino de konveksa aro estas ja tre simpla: se a, b ∈ A, tiam la tuta segmento [a, b] situas en A. Ni difinos la koncepton de konveksa funkcio tiel ke ĝi estos same simpla. Tial ni al funkcio volas asocii aron kiu estas konveksa precize kiam la funkcio konveksas.

Difino 8.1. Se f: X → [−∞, +∞] estas donita funkcio sur ajna aro X, tiam ĝia epigrafo estas la aro

epi f = {(x, t) ∈ X × R; t ⩾ f(x)}.

Difino 8.2. Se f: X → [−∞, +∞] estas donita funkcio difinita en aro X en R^{n}, ni nomas ĝin konveksa precize kiam ĝia epigrafo estas konveksa aro (en R^{n+1}). Se ni vastigas f al funkcio difinita sur la tuta R^{n} per meto de g(x) = f(x) kiam x ∈ X kaj g(x) = +∞ kiam x ∈ R^{n} \ X, tiam ni vidas ke f kaj g konveksas samtempe: ili havas la saman epigrafon. Tial ni ĉiam povas supozi ke konveksa funkcio estas difinita en la tuta spaco.

Oni vidas ke la konstantoj +∞ kaj −∞ estas konveksaj, ĉar iliaj epigrafoj estas Ø respektive la tuta R^{n+1}. Plue oni vidas ke max(f_{1}, ..., f_{m}) estas konveksa se f_{1}, ..., f_{m} estas konveksaj: tio respondas al tio ke la epigrafo de la unue menciita funkcio estas la komunaĵo de la konveksaj aroj epi f_{j}. Por montri ekzemple ke la sumo de konveksaj funkcioj konveksas estas tamen bone havi iun testeblan neegalaĵon, tiun kiu diras ke la grafo pendas sub la ŝnuro.

Propozicio 8.3. Funkcio f: R^{n} → [−∞, +∞] konveksas se kaj nur se

(8.1)  f((1 − t)x_{0} + tx_{1}) ⩽ (1 − t)f(x_{0}) + · tf(x_{1})

por ĉiuj x_{0}, x_{1} ∈ R^{n} kaj ĉiuj nombroj t kun 0 < t < 1.

Se unu el la valoroj f(x_{0}) kaj f(x_{1}) estas +∞, la neegalaĵo nenion postulas. Sed se ekzemple f(x_{0}) = −∞ kaj f(x_{1}) < +∞, tiam la neegalaĵo diras ke f((1−t)x_{0}+tx_{1}) = −∞ por ĉiuj t kun 0 < t < 1. La neegalaĵo (8.1) enhavas kompreneble, ĝenerale dirite, fortajn restriktojn sur la funkciaj valoroj. Sed en kelkaj situacioj la libero estas tre granda. Estu ekzemple g tute ajna funkcio sur la unueva sfero. Tiam ni povas ĝin vastigi al konveksa funkcio f per la preskribo f(x) = g(x) kiam |x| = 1, f(x) = +∞ kiam |x| > 1 kaj f(x) = −∞ (aŭ egala al la konstanto inf g) kiam |x| < 1. Sur la sfero do tute ne ekzistas kondiĉoj kiujn devas plenumi la valoroj de la funkcioj. Speciale, konveksaj funkcioj ne nepre estas kontinuaj. Sed se ni konsideras kubon, tiam la malvastigaĵo de konveksa funkcio devas esti konveksa en ĉiu faco de la kubo.

Propozicio 8.4. Se f, g: R^{n} → [−∞, +∞] estas du konveksaj funkcioj, tiam ankaŭ f + · g konveksas. Sed f + · g ne nepre konveksas se f kaj g estas konveksaj.

Difino 8.5. Se f, g: R^{n} → [−∞, +∞] estas du konveksaj funkcioj, tiam ni difinas ilian infiman kunfaldaĵon f ⊓ ⊔ g per

f ⊓ ⊔ g(x) = inf_{y∈R^{n}} (f(y) + · g(x − y)), x ∈ R^{n}.

La ordinara kunfaldo estas difinita per

f ∗ g(x) = ∫_{R^{n}} f(y)g(x − y)dy, x ∈ R^{n}.

La infima kunfaldo havas plurajn ecojn kiuj estas la samaj kiel – aŭ analogaj al – la kutima kunfaldo. En ambaŭ kazoj la sumo de la argumentoj de f kaj g egalas al la argumento de la kunfaldaĵo. Ofte oni povas kompari e^{−f} ∗ e^{−g} kun exp(−(f ⊓ ⊔ g)):

(exp(−f) ∗ exp(−g))(x) = ∫_{R^{n}} exp(−f(y) − g(x − y))dy
≈ sup_{y} exp(−f(y) − g(x − y)) = (exp(−(f ⊓ ⊔ g))(x).

La proksimumigo ∫ ≈ sup estas foje surprize bona.

Propozicio 8.6. La infima kunfaldo estas komuta kaj asocieca.

Pruvo. La komuteco sekvas el tio ke + · estas komuta. Por la asocieco ni bezonas la regulon (7.1):

(f ⊓ ⊔ g) ⊓ ⊔ h(x) = inf_{y} ( inf_{z}[f(z) + · g(y − z)] + · h(x − y))

= inf_{y} inf_{z} (f(z) + · g(y − z) + · h(x − y))

= inf_{z} (f(z) + · inf_{y}[g(y − z) + · h(x − y)]) = f ⊓ ⊔ (g ⊓ ⊔ h)(x).

La infima kunfaldo estas ĝeneraligo de la vektora adicio de aroj (la adicio de Minkowski). Nome, ni havas

i_{X} ⊓ ⊔ i_{Y} = i_{X+Y}

kie i_{X} estas la indika funkcio de aro X; ĝi estas difinita per tio ke i_{X}(x) = 0 se x ∈ X kaj i_{X}(x) = +∞ aliloke. Alia ligo kun la vektora adicio – kaj kiu taŭgas por difino de la infima kunfaldo – estiĝas se ni difinas la striktan epigrafon per

epi_{s} f = {(x, t) ∈ X × R; t > f(x)},

do kun strikta neegalaĵo. Tiam validas tutsimple

epi_{s}(f ⊓ ⊔ g) = epi_{s}(f) + epi_{s}(g)

kun vektora adicio en R^{n+1}. Tiu egalaĵo kondukas al geometria interpreto de la infima kunfaldo. Faru figurojn! Ekzemplo. La funkcio i_{{0}} estas la idento por la infima kunfaldo: f ⊓ ⊔ i_{{0}} = f por ĉiu funkcio f. Ekzemplo. Se g estas afina funkcio, tiam validas f ⊓ ⊔ g = g + C por iu konstanto C = C_{f,g} ∈ [−∞, +∞] (kiu?). Ekzemplo. Ni metu g_{k}(x) = k|x|, x ∈ R^{n}, kie k estas pozitiva konstanto, kaj studu la infiman kunfaldon f_{k} = f ⊓ ⊔ g_{k}. Ni supozu por simpleco ke f estas barita. Oni povas facile pruvi ke f_{k} estas Lipschitz-e kontinua kun konstanto k, t. e. ke

|f_{k}(x) − f_{k}(y)| ⩽ k|x − y|, x, y ∈ R^{n},

uzante ke g_{k} posedas tiun econ. Tio signifas ke la bonan kontinuecon heradas la kunfaldo f ⊓ ⊔ g_{k} spite al tio ke f mem ne nepre posedas ĝin. Plue validas ke f_{k} ⩽ f kaj ke f_{k} ↗ f kiam k → +∞ se f kontinuas (verdire f bezonas esti nur malsupren duonkontinua; por la difino de tiu eco vidu teoremon 9.6). Ni tiel ekhavas komfortan metodon alproksimigi al tia funkcio per Lipschitz-e kontinuaj funkcioj. Ekzemplo. Per fizike inspirita lingvo ni povas prezenti partiklon kun pozicio λ_{j} kaj disperso σ_{j} per la funkcio

f_{j}(x) = \frac{1}{2σ_{j}} (x − λ_{j})^{2}, x ∈ R^{n}.

Tiam (ekzemple) rekta kalkulado montras ke f_{1} ⊓ ⊔ f_{2} = f_{3} kie λ_{3} = λ_{1} + λ_{2} kaj σ_{3} = σ_{1} + σ_{2}, t. e. pozicio kaj disperso adiciiĝas. La kazo σ_{1} = 0 respondas al f_{1} = i_{{λ_{1}}}, t. e. akra partiklo. Tio estas komparenda al la kutima kunfaldaĵo de la funkcioj

g_{j} = (2πσ_{j})^{−n/2}e^{−f_{j}}

kiuj ankaŭ rajtas prezenti partiklojn. Nome, tiam validas g_{1} ∗ g_{2} = g_{3} kun la samaj rilatoj por pozicio kaj disperso kiel antaŭe. La komparo kiun ni faris antaŭe inter ⊓ ⊔ kaj ∗ nun estas tute ekzakta: la malprecizan egalaĵon

exp(−f_{1}) ∗ exp(−f_{2}) ≈ exp(−(f_{1} ⊓ ⊔ f_{2})) = exp(−f_{3})

anstataŭas la ekzakta rilato g_{1} ∗ g_{2} = g_{3} dank’al la faktoroj (2πσ_{j})^{−n/2}. La kazo σ_{1} = 0 respondas ĉi tie al la Dirac-a mezuro δ_{λ_{1}} en la punkto λ_{1}, denove akra partiklo. La kunfaldaĵo g_{1} ∗ g_{2} povas esti kalkulita per la transformo de Fourier, samkiel la kunfaldaĵo f_{1} ⊓ ⊔ f_{2} povas esti kalkulita per la transformo de Fenchel kiun ni ekondukos en la venonta sekcio.

Propozicio 8.7. Funkcio f: R^{n} → [−∞, +∞] konveksas se kaj nur se f_{s} ⊓ ⊔ f_{t} ⩾ f_{s+t} por ĉiuj s, t > 0, kie f_{s}(x) = sf(x/s) por x ∈ R^{n} kaj s > 0. Ni notu ke la neegalaĵo f_{s} ⊓ ⊔ f_{t} ⩽ f_{s+t} ĉiam validas. La konveksaj funkcioj estas do tiuj kiuj solvas la funkcialan ekvacion f_{s} ⊓ ⊔ f_{t} = f_{s+t}. Pruvo. Se f konveksas, tiam validas

f_{s}(y) + · f_{t}(x − y) = sf(y/s) + · tf((x − y)/t) ⩾ (s + t)f(\frac{y}{s + t} + \frac{x − y}{s + t} ) = f_{s+t}(x).

Se ni nun variigas y, sekvas ke f_{s} ⊓ ⊔ f_{t} ⩾ f_{s+t}. Inverse, ni supozu ke tiu neegalaĵo validas. Tiam ni povas konkludi, skribante x_{t} = (1 − t)x_{0} + tx_{1}, ke

f(x_{t}) = f_{1}(x_{t}) ⩽ f_{1−t} ⊓ ⊔ f_{t}(x_{t}) ⩽ f_{1−t}(y) + · f_{t}(x_{t} − y)

por ĉiuj y. Ni nun povas elekti y = (1 − t)x_{0}:

f(x_{t}) ⩽ f_{1−t}((1 − t)x_{0}) + · f_{t}(x_{t} − (1 − t)x_{0}) = (1 − t)f(x_{0}) + · tf(x_{1}),

kio signifas ke f konveksas.

Teoremo 8.8. Se f kaj g konveksas, tiam ankaŭ h = f ⊓ ⊔ g.

Pruvo. Oni vidas ke (f ⊓ ⊔ g)_{s} = f_{s} ⊓ ⊔ g_{s}. Ni tial bezonas nur kalkuli:

h_{s} ⊓ ⊔ h_{t} = (f ⊓ ⊔ g)_{s} ⊓ ⊔ (f ⊓ ⊔ g)_{t} = (f_{s} ⊓ ⊔ g_{s}) ⊓ ⊔ (f_{t} ⊓ ⊔ g_{t})
= (f_{s} ⊓ ⊔ f_{t}) ⊓ ⊔ (g_{s} ⊓ ⊔ g_{t}) ⩾ f_{s+t} ⊓ ⊔ g_{s+t} = (f ⊓ ⊔ g)_{s+t} = h_{s+t}.

Ĉi tie ni uzis la asociecon kaj komutecon de la infima kunfaldo (propozicio 8.6). Ni vidas ke la teoremo sekvas el la karakterizo de propozicio 8.7.

9. La transformo de Fenchel Ĉiuj afinaj funkcioj x ↦ ξ·x+c konveksas. Ili estas la plej simplaj konveksaj funkcioj, kaj estas nature demandi ĉu aliaj konveksaj funkcioj povas esti prezentitaj per ili. Finiaj supremoj de afinaj funkcioj ja tre gravas en la lineara programado – pluredro estas subnivela aro de tia funkcio – kaj en la konveksa optimumado estas same grave studi ne nepre finiajn supremojn de afinaj funkcioj.

Ni do demandas ĉu ni povas trovi familion A de afinaj funkcioj, t. e. de paroj (ξ, c), tian ke

f(x) = sup_{(ξ,c)∈A}(ξ · x + c)

por tiu familio. Tiam evidente ξ · x + c ⩽ f(x) por ĉiuj x ∈ R^{n} kaj ĉiuj (ξ, c) ∈ A, t. e. c ⩽ f(x) − ξ · x, de kio

c ⩽ inf_{x∈R^{n}}(f(x) − ξ · x), (ξ, c) ∈ A.

Oni ne havas intereson preni la konstanton c pli malgrandan ol tiu infimo, ĉar tiaj c ne konkurencas efike en la formado de la supremo. Ni do povas limigi nin al meto de c egala al tiu infimo. Tio signifas, kiel ni baldaŭ vidos, ke la solaj interesaj afinaj malpliedantoj de f estas tiuj kiuj havas la formon f ⊓ ⊔ ξ por iu lineara funkcio ξ. Pro certaj kaŭzoj kiuj estos evidentaj post momento estas praktike anstataŭe konsideri −c; tiun konstanton ni notos f̃(ξ). Esplice do:

Difino 9.1. Se f: R^{n} → [−∞, +∞] estas ajna funkcio sur R^{n}, tiam

(9.1)  f̃(ξ) = sup_{x∈R^{n}} (ξ · x − f(x)),  ξ ∈ R^{n},

nomiĝas la transformaĵo de Fenchel de f. Alia nomo por f̃ estas la transformaĵo de Legendre aŭ la al f konjugita konveksa funkcio.

La funkcio x ↦ f ⊓ ⊔ ξ(x) = ξ · x − f̃(ξ) estas afina, malpliedas ol f, kaj estas la plej granda afina malpliedanto de f kies lineara parto estas ξ. (Ĉi tie per ξ ni notas kaj vektoron kaj la linearan funkcion x ↦ ξ · x.) La geometria interpreto de la transformaĵo estas la jena: ni fiksu ξ kaj konsideru ĉiujn afinajn malpliedantojn x ↦ ξ·x+c de la funkcio f, kaj faru c kiel eble plej granda, t. e. ni ŝovu la hiperebenon kiel eble plej supren sed tiel ke neniu punkto de la grafo de f estas sub ĝi. Tiam f̃(ξ) estas −c, t. e. la valoro de la transformaĵo estas minus la ordinato en la origino de la hiperebeno.

Ni notas ke en (9.1) punktoj kie f(x) = +∞ ne ludas rolon: ili neniam povas kontribui al la supremo. Oni difinas la efektivan argumentaron de f per

(9.2)  dom f = {x ∈ R^{n}; f(x) < +∞},

kaj ni vidas ke

(9.3)  f̃(ξ) = sup_{x∈M} (ξ · x − f(x))

por ĉiu aro M tia ke dom f ⊂ M ⊂ R^{n}.

Kun la difino c = −f̃(ξ) la supremo de ĉiuj afinaj malpliedantoj de f fariĝas ekzakte

(9.4)  sup_{ξ∈R^{n}} (ξ · x − f̃(ξ)) = sup_{ξ∈R^{n}}(f ⊓ ⊔ ξ)(x),  x ∈ R^{n}.

Nun ni povas fari interesan observon: la formado de la supremo estas precize la transformaĵo de Fenchel de f̃. Ni povas do skribi la maldekstran flankon de (9.4) kiel

(f̃) = ˜ f̃. La demando ĉu f estas supremo de afinaj funkcioj ekvivalentas do al la

demando ĉu ˜ f̃ = f. Ni baldaŭ respondos al ĝi, sed ni unue notu kelkajn simplajn ecojn de la transformo.

Propozicio 9.2. Se f, g: R^{n} → [−∞, +∞] estas du funkcioj sur R^{n} kun f ⩽ g, tiam

f̃ kaj g̃ konveksas kaj f̃ ⩾ g̃. Plue ˜ f̃ egalas al la supremo de ĉiuj afinaj malpliedantoj de f:

˜f̃(x) = sup_{ξ∈R^{n}}(f ⊓ ⊔ ξ)(x), x ∈ R^{n};

speciale, ˜ f̃ konveksas kaj ˜ f̃ ⩽ f. Finfine la tria transformaĵo ( ˜f̃) = f ĉiam egalas al f̃.

Notu ke f̃ neniam alprenas la valoron −∞ krom kiam f̃ = −∞ idente; tiam f = +∞

idente. La neegalaĵo ˜ f̃ ⩽ f sekvas el tio ke

(9.5)  ξ · x ⩽ f(x) + · f̃(ξ),  x ∈ R^{n}, ξ ∈ R^{n},

neegalaĵo kiun oni kutime nomas la neegalaĵon de Fenchel.

Per kelkaj ekzemploj ni montru kiel oni povas kalkuli transformaĵojn de Fenchel. Ekzemplo. Se f(x) = ax^{2} + bx + c por x ∈ R kun a > 0 kaj b kaj c reelaj, tiam ni povas kalkuli f̃ per la diferenciala kalkulo. Nome, ni havas

f̃(ξ) = sup_{x∈R}[ξx − ax^{2} − bx − c], ξ ∈ R,

kaj klaras ke la esprimo kies supremon ni serĉas estas kontinua funkcio de x kiu krome strebas al −∞ kiam x → ±∞, kio implicas ke la supremo estas alprenita en iu punkto, kaj ke tiu punkto povas esti trovita per meto de la derivaĵo egala al nulo. La derivaĵo estas ξ − 2ax − b, kaj havas unikan nulejon, nome x = (ξ − b)/2a. Nun ni metas tiun valoron de x en la esprimon kaj ekhavas

f̃(ξ) = ξx − ax^{2} − bx − c = ξ \frac{ξ − b}{2a} − a\frac{(ξ − b)^{2}}{4a^{2}} − b\frac{ξ − b}{2a} − c

= \frac{ξ^{2}}{4a} − \frac{bξ}{2a} + \frac{b^{2}}{4a} − c = \frac{(ξ − b)^{2}}{4a} − c.

Do ankaŭ f̃ estas duagrada polinomo. Ni povas vidante tiun esprimon diveni kelkajn ecojn de la transformo, kiuj estas facile pruveblaj.

Se g(x) = f(x) + c, tiam g̃(ξ) = f̃(ξ) − c, t e., se ni adicias reelan konstanton al f, tiam ĝi eliras kun la mala signo. Tio kompreneble veras en ĉiuj dimensioj.

Se g(x) = f(x)+α·x, tiam g̃(ξ) = f̃(ξ −α), t. e. se ni adicias linearan funkcion al f, tiam la transformaĵo estas translaciita je vektoro kies komponantoj estas ekzakte la koeficientoj de la lineara funkcio. Tion oni montras per facila kalkulo:

g̃(ξ) = sup_{x}[ξ · x − g(x)] = sup_{x}[ξ · x − f(x) − α · x]

= sup_{x}[(ξ − α) · x − f(x)] = f̃(ξ − α).

Se, aliflanke, g(x) = f(x − a), tiam g̃(ξ) = f̃(ξ) + a · ξ, t. e. se ni translacias funkcion, tiam tio respondas al adicio je lineara funkcio al ĝia transformaĵo.

Se ni multiplikas funkcion je pozitiva konstanto, t. e. se g(x) = af(x) kun a > 0, tiam la transformaĵo estas g̃(ξ) = af̃(ξ/a). Ankaŭ tion oni montras per facila kalkulo:

g̃(ξ) = sup_{x}[ξ · x − af(x)] = a sup_{x}[(ξ/a) · x − f(x)] = af̃(ξ/a).

Per uzo de tiuj reguloj de kalkulado (adicio je konstanto, adicio je lineara funkcio kaj multipliko je pozitiva konstanto), ni vidas ke se ni konas la transformaĵon de f(x) = x^{2}/2, x ∈ R, (ĝi estas f̃(ξ) = ξ^{2}/2, do la sama funkcio), tiam ni povas konkludi ke f(x) = ax^{2} + bx + c havas la transformaĵon f̃(x) = (ξ − b)^{2}/4a − c. Ekzemplo. Se ni metas

f(x) = \frac{|x|^{1+p}}{1 + p} , x ∈ R,

kun pozitiva konstanto p, tiam

f(ξ) = \frac{|ξ|^{1+1/p}}{1 + 1/p} , ξ ∈ R.

Ankaŭ tio estas facile kalkulebla per la diferenciala kalkulo kiam ξ ≠ 0, kaj por ξ = 0 la rezulto evidentas. Oni povas montri ke la formulo validas ankaŭ en R^{n}. Ekzemplo. La diferenciala kalkulo ne ĉiam helpas. Se f(x) = |x|, x ∈ R, tiam f̃(ξ) = 0 kiam |x| ⩽ 1 kaj f̃(ξ) = +∞ kiam |x| > 1. Tion oni komprenas rigardante la esprimon ξx − |x|, kaj konstatante ke ĝi estas supren nebarita kiam |ξ| > 1, dum ĝi estas supren barita kiam |ξ| ⩽ 1, kun supremo egala al 0. Do f̃ = i_{[−1,1]}, la indika funkcio por la intervalo [−1, 1]. Se ni metas f kiel la indika funkcio de intervalo [a, b], tiam ni vidas ke f̃(ξ) fariĝas aξ por ξ ⩾ 0 kaj bξ por ξ ⩽ 0. Speciale, se la intervalo estas ĝuste [−1, 1], tiam f̃(ξ) = |ξ|. Ekzemplo. Se f(x) = |x| + x^{2}/2, x ∈ R, ni bezonas uzi kombinon de la rezono en la lasta ekzemplo kaj la diferenciala kalkulo. Nome, se |ξ| ⩽ 1, tiam oni vidas ekzakte kiel en la antaŭa ekzemplo ke f̃(ξ) = 0. Sed se |ξ| > 1, tiam ni povas serĉi la maksimumon de la esprimo ξx − |x| − x^{2}/2 per la diferenciala kalkulo. La derivaĵo estas por x > 0 egala al ξ −1−x kaj havas unikan nulejon x = ξ −1 > 0 se ni supozas ke ξ > 1. Tio donas la valoron ξx−x−x^{2}/2 = \frac{1}{2}(ξ −1)^{2}. Pro simetrio f̃(−ξ) = f̃(ξ), tiel ke ni ne bezonas speciale konsideri ξ < −1, sed povas resumi la esploron per la formulo f̃(ξ) = \frac{1}{2}((|ξ| − 1)^{+})^{2}, ξ ∈ R. Kaj f kaj f̃ estas kunmetitaj de pecoj de duagradaj polinomoj, sed en la kunmeto oni procedas en malsamaj manieroj. Ekzemplo. Se f(x) = x^{3}, tiam f̃(ξ) = +∞ por ĉiuj ξ. Ĉi tie ne ekzistas afinaj malpliedantoj. Ekzemplo. Se f(x) = e^{x}, x ∈ R, ni povas kalkuli f̃ per la diferenciala kalkulo kiam ξ > 0, dum ni povas rezoni pli rekte kiam ξ ⩽ 0. Ni trovas ke

f̃(ξ) = \{ \begin{matrix}ξ log ξ − ξ, & ξ > 0; \\ 0, & ξ = 0; \\ +∞, & ξ < 0. \end{matrix}

La formulo de Stirling do montras ke f̃(ξ) ≈ log(ξ!) kiam ξ ≫ 0:

exp f̃(ξ) = sup_{x∈R} \frac{e^{ξx}}{e^{e^{x}}} = ξ^{ξ}e^{−ξ} ≈ (2πξ)^{−1/2}ξ!, ξ > 0.

Similajn proksimumajn egalaĵojn oni povas ekhavi ankaŭ per proksimumigo al la supremo per integraĵo:

exp f̃(ξ) = sup_{x∈R} \frac{e^{ξx}}{e^{e^{x}}} ≈ ∫_{R} e^{ξx−e^{x}}dx = ∫_{0}^{+∞} t^{ξ−1}e^{−t}dt = (ξ − 1)!, ξ > 0,

aŭ

exp f̃(ξ) = sup_{t>0} t^{ξ}e^{−t} ≈ ∫_{0}^{+∞} t^{ξ}e^{−t}dt = ξ!, ξ > 0.

La inversiga formulo (vidu sube teoremon 10.1) diras ke ˜ f̃ = f kaj per tio

e^{e^{x}} = exp f(x) = exp ˜ f̃(x) = sup_{ξ∈R} exp(ξx − f̃(ξ)) = sup_{ξ⩾0} \frac{e^{ξx}}{ξ^{ξ}e^{−ξ}} ≈ ∑_{k=0}^{∞} \frac{e^{kx}}{k!} = e^{e^{x}}.

La sola surprizo ĉi tie estas ke la proksimumigo fakte donas ekzaktan egalaĵon. Ĉu ekzistas klarigo? Ekzemplo. Ni metu f(x) = x_{1}^{2}/2 + x_{2}^{3}/3 por x ∈ R^{2}, x_{2} ⩾ 0; f(x) = +∞ por x_{2} < 0. Sekvas ke f̃(ξ) = ξ_{1}^{2}/2 + \frac{2}{3}ξ_{2}^{3/2} kiam ξ_{2} ⩾ 0, kaj f̃(ξ) = ξ_{1}^{2}/2 kiam ξ_{2} < 0. Por ξ_{2} > 0 ni povas trovi tion per la diferenciala kalkulo, ĉar la gradiento de la esprimo ξ · x − x_{1}^{2}/2 − x_{2}^{3}/3 estas ξ − (x_{1}, x_{2}^{2}), kiu havas unikan nulejon x = (ξ_{1}, \sqrt{ξ_{2}}) kiam ξ_{2} > 0, x_{2} > 0. Tiu valoro donas, se ni metas ĝin en la esprimon, ξ ·x−x_{1}^{2}/2−x_{2}^{3}/3 = ξ_{1}^{2} + ξ_{2}\sqrt{ξ_{2}} − ξ_{1}^{2}/2 − ξ_{2}^{3/2}/3 = ξ_{1}^{2} + \frac{2}{3}ξ_{2}^{3/2}. Se ξ_{2} ⩽ 0, tiam ni vidas ke la supremo de la esprimo estas alprenita kiam x_{2} = 0, kaj tiam temas pri la jam konata transformaĵo de Fenchel de x_{1}^{2}/2. Ekzemplo. Se f(x) = \frac{1}{2} ∑ x_{j}a_{jk}x_{k} kie A = (a_{jk}) estas reela simetria kaj pozitiva matrico, kaj x = (x_{1}, ..., x_{n})^{T} vertikala vektoro, do skribite per matrica multipliko

f(x) = \frac{1}{2}x^{T} Ax, x ∈ R^{n},

tiam ni ekhavas

f̃(ξ) = \frac{1}{2}ξA^{−1}ξ^{T} , ξ = (ξ_{1}, ..., ξ_{n}).

(En la speciala kazo de n = 1 ni ekhavas f(x) = \frac{1}{2}ax^{2}, f̃(ξ) = \frac{1}{2}ξ^{2}/a.) Se A estas nur pozitiveda oni anstataŭe ekhavas

f̃(ξ) = \{ \begin{matrix}\frac{1}{2}ξBξ^{T} & kiam ξ apartenas al la horizontaleva spaco de A \\ +∞ & alikaze, \end{matrix}

kie B estas simetria kvazaŭinverso de A, t. e. ABA = A. Tion oni ankaŭ povas formuli tiel:

f̃(ξ) = \{ \begin{matrix}f(x) & se ξ = x^{T} A por iu x ∈ R^{n}, \\ +∞ & se ξ ne estas de la formo x^{T} A. \end{matrix}

La pruvo konsistas el tiu ĉi kalkulo:

f̃(ξ) = f̃(x^{T} A) = sup_{y} (x^{T} Ay − \frac{1}{2}y^{T} Ay) = sup_{y} (\frac{1}{2}x^{T} Ax − \frac{1}{2}(x − y)^{T} A(x − y))

= sup_{y} (f(x) − f(x − y)) = f(x) − inf_{y} f(x − y) = f(x);

la lasta egalaĵo validas ĉar f(x − y) ⩾ 0 kaj alprenas la valoron 0 kiam y = x. Ni do vidas ke la problemo kalkuli f̃ ekvivalentas al la problemo kalkuli la inverson de simetria matrico en tiu ĉi kazo.

Propozicio 9.3. Por ĉiuj funkcioj f, g: R^{n} → [−∞, +∞] validas

(f ⊓ ⊔ g) = f̃+ · g̃.

Pruvo. Facila kalkulo dank’al la regulo (7.2).

Notu ke ni havas la malsupran adicion en propozicio 9.3. Ni scias ke f̃+ · g̃ konveksas. Montriĝas nun ke f̃+ · g̃ = f̃+ · g̃ krom kiam f̃+ · g̃ estas konstanta.

Propozicioj 9.2 kaj 9.3 kune donas ĉenon de neegalaĵoj:

(9.6)  (f + · g) ⩽ ( ˜f̃+ · ˜ g̃) = (f̃ ⊓ ⊔ g̃)˜ ⩽ f̃ ⊓ ⊔ g̃.

(Apliku la propozicion 9.3 al f̃kaj g̃.) En la teorio pri lineara programado oni volonte havus egalecon la tutan vojon ĉi tie, t. e. oni volas ke validu la regulo

(9.7)  (f + · g) = f̃ ⊓ ⊔ g̃

kiu estas duala al propozicio 9.3. Ĝi ne ĉiam validas, sed ni povas noti la sekvan rezulton:

Korolario 9.4. Se ˜ f̃ = f kaj ˜ g̃ = g, tiam validas

(f + · g) = (f̃ ⊓ ⊔ g̃)˜ .

Povas tre bone okazi ke estas strikta neegaleco en la lasta loko de (9.6) eĉ sub la supozoj de tiu ĉi korolario: Ekzemplo. Ni difinu du funkciojn f, g: R^{2} → [−∞, +∞] per la preskriboj

f(x) = \{ \begin{matrix}0 & x_{1} = 0 \\ +∞ & alikaze; \end{matrix}

g(x) = \{ \begin{matrix}0 & x_{1} = 1 \\ +∞ & alikaze. \end{matrix}

Tiam f̃(ξ) = 0 kiam ξ_{2} = 0 kaj +∞ alikaze, dum g̃(ξ) = ξ_{1} kiam ξ_{2} = 0 kaj +∞ alikaze. Tio implicas ke f + · g = +∞ idente, dum f̃ ⊓ ⊔ g̃(ξ) alprenas la valoron −∞

kiam ξ_{2} = 0. Tial (f + · g) = (f̃ ⊓ ⊔ g̃)˜ = −∞ idente, dum f̃ ⊓ ⊔ g̃(ξ) = +∞ kiam ξ_{2} ≠ 0. Tio signifas ke (9.7) ne validas. Ekzemplo. Aliajn ekzemplojn oni povas konstrui helpe de la indika funkcio tiel: ni difinu f̃ = i_{X} kaj g̃ = i_{Y} (tiam X kaj Y estas aŭtomate konveksaj kaj fermitaj). Tiam validas f̃ ⊓ ⊔ g̃ = i_{X+Y}, kaj oni povas pruvi (vidu teoremon 10.1 sube) ke (f̃ ⊓ ⊔ g̃)˜ = i\overline{X+Y}, la indika funkcio de la fermitaĵo de X + Y. Nun estas facile trovi fermitajn konveksajn arojn X kaj Y tiajn ke ilia vektora sumo ne estas fermita. Tipa ekzemplo estas

X = {x ∈ R^{2}; x_{2} > 0, x_{1}x_{2} ⩾ 1}, Y = {x ∈ R^{2}; x_{2} = 0},

X + Y = \{x ∈ R^{2}; x_{2} > 0\}, \overline{X + Y} = \{x ∈ R^{2}; x_{2} ⩾ 0\}.

Tiam f̃ ⊓ ⊔ g̃ ≠ (f̃ ⊓ ⊔ g̃)˜ . Ekzemplo. Se

f_{j}(x) = \frac{1}{2σ_{j}} (x − λ_{j})^{2}, x ∈ R^{n},

tiam

f̃_{j}(ξ) = \frac{σ_{j}}{2} ξ^{2} + λ_{j} · ξ, ξ ∈ R^{n},

kaj f̃_{1} + f̃_{2} = f̃_{3}, kie λ_{3} = λ_{1} + λ_{2}, σ_{3} = σ_{1} + σ_{2}. Do validas

(f_{1} ⊓ ⊔ f_{2}) = f̃_{1} + f̃_{2} = f̃_{3}

el kio sekvas ke (f_{1} ⊓ ⊔ f_{2})˜ = (f̃_{1} + f̃_{2}) = ˜ f̃_{3}. Ni jam vidis ke f_{1} ⊓ ⊔ f_{2} = f_{3} en pli frua ekzemplo. Oni povas pruvi ankaŭ rekte ke f_{1} ⊓ ⊔ f_{2} estas kontinua, kio kune kun la konvekseco donas ke f_{1} ⊓ ⊔ f_{2} = (f_{1} ⊓ ⊔ f_{2})˜ = f_{3} (teoremo 10.1 sube). Komparu kun la Fourier-a aŭ Laplace-a transformaĵo de g_{j} = (2πσ_{j})^{−n/2}e^{−f_{j}}. Tio ilustras la analogion inter, unuflanke, la infima kunfaldo kaj la transformo de Fenchel, kaj, aliflanke, la (ordinara) kunfaldo kaj la transformo de Fourier aŭ Laplace. Ni povas liberiĝi de la speciala fomro de f. Estu f_{j}(x) = σ_{j}f((x − λ_{j})/σ_{j}) la prezento de partiklo kun pozicio λ_{j} kaj disperso σ_{j}, sed kie f nun estas ajna funkcio. Tiam ni ekhavas ke

f̃_{j}(ξ) = σ_{j}f̃(ξ) + λ_{j} · ξ,

tiel ke denove f̃_{1} + f̃_{2} = f̃_{3} kun la samaj rilatoj inter pozicio kaj disperso kiel antaŭe, se ni nur supozas ke f̃ alprenas alian valoron ol 0 kaj ±∞ (tiel ke oni povas determini σ_{j} kaj λ_{j} de f̃_{j}). Se f konveksas kun reelaj valoroj, tiam validas ke f_{1} ⊓ ⊔ f_{2} = f_{3} (komparu kun propozicio 8.7).

Ni konstatis post propozicio 8.3 ke konveksa funkcio ne bezonas havi iun ajn kontinuecon. Sed la ekzemplo estis tia ke f alprenis la valoron +∞ apud la punktoj de nekontinueco. Tio ne estis hazardo: ni vidos ke konveksaj funkcioj kontinuas en la interno de dom f (vidu (9.2)).

Teoremo 9.5. Estu f: R^{n} → [−∞, +∞] konveksa kaj estu Ω = (dom f)^{∘} la interno de la aro kie f(x) < +∞. Tiam f aŭ estas konstante −∞ en Ω aŭ reele valora funkcio kontinua en Ω.

Pruvo. Ni unue konstatas ke se f ne estas konstante −∞ en Ω, tiam f devas esti reele valora tie (vidu la diskuton post propozicio 8.3). Ni faros induktan pruvon. La teoremo certe veras se la dimensio estas nulo. Ni supozas ke ni jam pruvis ĝin por n − 1 kaj utiligos la neegalaĵon (8.1) en du manieroj por dimensie supreniri. Ni skribas la variablojn kiel x = (x′, x_{n}) kie x′ ∈ R^{n−1} (kiam n = 1 ni tute malatentu x′). Ni supozu ke 0 ∈ Ω. Por sufiĉe malgranda pozitiva ε ni havas f(0, ε) < ∞ kaj

f(x) ⩽ (1 − λ)f(y′, 0) + λf(0, ε)

kiam y′ estas elektita tiel ke x estas konveksa lineara kombinaĵo de (y′, 0) kaj (0, ε):

x = (1 − λ)(y′, 0) + λ(0, ε).

Same validas

f(z′, 0) ⩽ (1 − μ)f(x) + μf(0, −ε)

se

(z′, 0) = (1 − μ)x + μ(0, −ε).

Ĉi tie λ = x_{n}/ε estas determinita de x_{n} kaj ε, samkiel μ. Ni kombinas la neegalaĵojn jene:

\frac{f((1 − μ)x′, 0)}{1 − μ} − \frac{μ}{1 − μ}f(0, −ε) ⩽ f(x) ⩽ (1 − λ)f(\frac{x′}{1 − λ}, 0) + λf(0, ε).

Tio validas por 0 ⩽ x_{n} < ε; simila neegalaĵo validas por −ε < x_{n} ⩽ 0. Laŭ la indukta supozo f(x′, 0) estas kontinua funkcio de la n − 1 variabloj x′ = (x_{1}, ..., x_{n−1}), kaj ni povas konstati ke f(x) estas kunpremita inter du esprimoj kiuj kontinue dependas de x kaj havas limeson f(0) kiam x → 0, ĉar λ, μ → 0 kiam x_{n} → 0. Tial f estas kontinua en la origino, kio pruvas la teoremon.

Rande de Ω konveksa funkcio povas esti nekontinua. Montriĝos ke certa formo de duonkontinueco gravas:

Teoremo 9.6. Por ajna funkcio f: R^{n} → [−∞, +∞] la sekvaj ecoj ekvivalentas:

1. f estas malsupren duonkontinua, t. e. lim inf_{y→x} f(y) = f(x) por ĉiuj x ∈ R^{n};

2. epi f estas fermita aro en R^{n+1};

3. Por ĉiu reela a la subnivela aro {x ∈ R^{n}; f(x) ⩽ a} estas fermita.

Pruvo. Se 1 validas kaj (x_{j}, t_{j}) estas vico en epi f kiu konverĝas al (x, t), ni vidas ke

t = lim inf t_{j} ⩾ lim inf_{j→+∞} f(x_{j}) ⩾ lim inf_{y→x} f(y) = f(x)

kio signifas ke (x, t) ∈ epi f. Do epi f estas fermita.

Se ni metas la subnivelan aro en punkto 3 je la nivelo a en R^{n+1}, tiam ni ekhavas

{x ∈ R^{n}; f(x) ⩽ a} × {a} = epi f ∩ {(x, t) ∈ R^{n+1}; t = a}.

Se epi f estas fermita, tiam la lasta aro ĉi tie estas la komunaĵo de du fermitaj aroj. Do 2 implicas la econ 3.

Se, finfine, 3 validas, ni vidas ke por a < f(x) validas ankaŭ a < f(y) por ĉiuj y proksime al x, pro kio

lim inf_{y→x} f(y) ⩾ a.

El tio sekvas ke lim inf_{y→x} f(y) ⩾ f(x); la inversa neegaleco ĉiam validas. Tio montras ke la eco 1 validas.

10. Dualeco Ni nun studu kiam validas la ekvacio ˜ f̃ = f. Kiel ni jam konstatis komence de sekcio 9 tio ekvivalentas al la demando ĉu f estas supremo de afinaj funkcioj. Per sia

difino ˜ f̃ estas supremo de afinaj funkcioj, kaj ĝi egalas al la supremo de ĉiuj afinaj malpliedantoj de f. La respondo estas donita de:

Teoremo 10.1. (La inversiga formulo por la transformo de Fenchel.) Estu f

funkcio sur R^{n} kun valoroj en [−∞, +∞]. Tiam validas ˜ f̃ = f se kaj nur se f havas la jenajn tri ecojn: A. f estas konveksa; B. f estas malsupren duonkontinua; C. Se f alprenas la valoron −∞, tiam f egalas al −∞ idente. La nomo ”inversiga formulo” venas de tio ke funkcio kiu plenumas la kondiĉojn povas esti rekonstruita de sia transformaĵo de Fenchel; la transformo estas sia propra inverso:

f(x) = ˜ f̃(x) = sup_{ξ}(ξ · x − f̃(ξ)), x ∈ R^{n}.

Pruvo. Ni unue konstatas ke ĉiu transformaĵo de Fenchel devas havi la tri ecojn. Ekzemple ĉiu transformaĵo estas supremo de afinaj, do kontinuaj, funkcioj, kaj ajna supremo de malsupren duonkontinuaj funkcioj estas malsupren duonkontinua. Spe-

ciale, ni vidas ke f devas havi la ecojn A, B, C se f = ˜ f̃.

Ni nun montru la inversan implicon. Ĝi baziĝas sur la ekzisto de apartigaj hiperebenoj (teoremo 3.2) kiu donis la teoremon 3.7 kie ĉiu fermita konveksa aro prezentiĝas kiel komunaĵo de fermitaj duonspacoj. Estu do f konveksa funkcio kun fermita epigrafo. Se f alprenas la valoron −∞, la rezulto validas, ĉar (−∞) = +∞ kaj (+∞) = −∞. Tial ni ekde nun povas supozi ke −∞ < f ⩽ +∞. Krome la teoremo validas se f egalas al +∞ idente. Estu nun (x_{0}, t_{0}) ajna punkto ekster la epigrafo, t. e. kun f(x_{0}) > t_{0}. Ĉar la epigrafo estas fermita, ekzistas laŭ teoremo 3.2 hiperebeno en R^{n+1} kiu strikte apartigas epi f kaj (x_{0}, t_{0}). Hiperebeno en R^{n+1} havas ekvacion

ξ · x + bt = c

por iuj elektoj de ξ ∈ R^{n} kaj b ∈ R, kaj duonspaco estas aŭ la epigrafo de afina funkcio (kiam b < 0) aŭ vertikala (b = 0), aŭ, finfine, la hipografo de afina funkcio (b > 0). La lasta tipo de duonspaco povas enhavi epigrafon nur malplenan, kaj tial aperas nur kiam f egalas al +∞ idente; tiam la teoremo validas kiel ni jam konstatis. La problemo estas pruvi ke la vertikalaj duonspacoj, kiuj fakte povas aperi, ne influas la komunaĵon.

Ke la hiperebeno estas strikte apartiga signifas ke ekzistas nombro ε tia ke

ξ · x + bt ⩽ c < c + ε ⩽ ξ · x_{0} + bt_{0}

por ĉiuj (x, t) ∈ epi f. Se ekzistas iu punkto kie f(x) < +∞ (kaj se tio ne veras, f identas al plus nefinio kaj la rezulto validas), tiam ni vidas ke ni devas havi b ⩽ 0 (strebigu t ⩾ f(x) al plus nefinio). Se nun b < 0, estas facile fini la pruvon: ni tutsimple dividas per −b kaj ekhavas

(−ξ/b) · x − f(x) ⩽ −c/b < −(c + ε)/b ⩽ (−ξ/b) · x_{0} − t_{0}.

El tio rezultas ke f̃(−ξ/b) ⩽ (−ξ/b) · x_{0} − t_{0} kaj tial

˜f̃(x_{0}) ⩾ (−ξ/b) · x_{0} − f̃(−ξ/b) ⩾ t_{0}.

Tio signifas ke ˜ f̃(x_{0}) pliedas ol ĉiu t_{0} kiu malplias ol f(x_{0}), t. e. ke ˜ f̃(x_{0}) ⩾ f(x_{0}). Speciale, ni vidas ke se f(x_{0}) < +∞, tiam b devas esti negativa kaj la jam farita rezono validas. Sed povas okazi ke b = 0; tio respondas al tio ke la hiperebeno en R^{n+1} vertikalas: ĝi tiam ne estas la grafo de iu afina funkcio sur R^{n}. En tiu ĉi kazo f(x_{0}) = +∞ kaj ni uzos specialan trukon por iomete rotaciigi la vertikalan hiperebenon. Kiam b = 0 ni scias ke

ξ · x ⩽ c < c + ε ⩽ ξ · x_{0}

por ĉiuj x tiaj ke ekzistas t kun (x, t) en la epigrafo, t. e. por ĉiuj x kun f(x) < +∞. Tio donas al ni laŭ la difino de la transformo de Fenchel ke

f̃(θ + sξ) = sup_{x∈dom f}(θ · x + (sξ) · x − f(x)) ⩽ f̃(θ) + sup_{x∈dom f}(sξ) · x ⩽ f̃(θ) + sc,

por ĉiuj s > 0, ĉar en la difino (9.1) de f̃ klaras ke nur punktoj x kun f(x) < +∞ necesas: vidu (9.3). Ni tial ekhavas

(10.1) ˜ f̃(x_{0}) ⩾ (θ + sξ) · x_{0} − f̃(θ + sξ) ⩾ (θ + sξ) · x_{0} − f̃(θ) − sc ⩾ θ · x_{0} + sε − f̃(θ).

Ĉi tie ni nun elektas θ tian ke f̃(θ) < +∞; tio eblas kiel ni vidis en la unua parto de la pruvo kie ni supozis ke f(x_{0}) < +∞. Se ni strebigas s al +∞ en (10.1), ni vidas

ke ˜ f̃(x_{0}) = +∞, la dezirataĵo.

Teoremo 10.2. Ni supozu ke ˜ f̃ = f kaj ˜ g̃ = g, kaj ke f̃ ⊓ ⊔ g̃ estas malsupren duonkontinua kaj aŭ nenie egalas al minus nefinio aŭ identas al minus nefinio (tiel estas se ekzemple f̃ ⊓ ⊔ g̃ ĉie reele valoras). Tiam validas ke

(f + · g) = f̃ ⊓ ⊔ g̃,

kaj, speciale, se ni konsideras la valoron en la origino

− inf_{x}(f(x) + · g(x)) = inf_{ξ}(f̃(ξ) + · g̃(−ξ)).

Pruvo. Ni bezonas nur kombini la korolarion 9.4 kun la teoremoj 9.5 kaj 10.1.

11. La apoga funkcio de aro Helpe de la apoga funkcio demandoj pri konveksaj aroj povas esti tradukitaj al demandoj pri homogenaj konveksaj funkcioj. Montriĝos ke la apoga funkcio estas speciala kazo de transformaĵo de Fenchel. La difino estas la jena:

Difino 11.1. Estu X ajna aro en R^{n}. Tiam ni difinas ĝian apogan funkcion H_{X} per

H_{X}(ξ) = sup_{x∈X} ξ · x, ξ ∈ R^{n}.

Klaras ke se ni skribas f = i_{X} por la indika funkcio de aro X (ĝi nulas en X kaj egalas al +∞ en ĝia komplemento), tiam H_{X} = f̃. Ĉio kion ni faris en sekcioj 9 kaj 10 tial validas en tiu speciala kazo. Estas tamen ne seninterese trarigardi la teoremojn tie por vidi kiel ili aspektas en tiu ĉi kazo. Ni unue konstatas ke i_{X} plenumas la kondiĉojn A, B, C de teoremo 10.1 se kaj nur se X estas fermita kaj konveksa.

Propozicio 11.2. La apoga funkcio H_{X} de aro X estas malsupren duonkontinua kaj alprenas la valoron −∞ nur kiam X = Ø. Se X ≠ Ø, tiam validas H_{X}(0) = 0 kaj H_{X} estas pozitive homogena konveksa funkcio. Se X estas barita kaj nemalplena, tiam H_{X} estas reele valora kaj per tio ĉie kontinua.

Pruvo. Tio kio novas kompare al la jam sciata pri transformaĵoj de Fenchel estas la homogeneco. Tiu ĉi signifas ke H_{X}(tξ) = tH_{X}(ξ) por ĉiuj pozitivaj nombroj t, kaj estas facile pruvebla. Oni bezonas nur skribi

H_{X}(tξ) = sup_{x∈X}(tξ) · x = t sup_{x∈X} x · ξ = tH_{X}(ξ).

Teoremo 11.3. Se h: R^{n} → [−∞, +∞] estas pozitive homogena konveksa funkcio donita, plenumanta h(0) = 0, ni metas

(11.1)  X = {x ∈ R^{n}; ξ · x ⩽ h(ξ) por ĉiuj ξ}.

Tiam la indika funkcio de X egalas al la transformo de Fenchel de h. Se h krome estas malsupren duonkontinua, tiam la apoga funckio de X egalas al h.

Pruvo. Se x ∈ X, validas ξ · x − h(ξ) ⩽ 0 por ĉiuj ξ kaj do h̃(x) estas negativeda; se ni metas ξ = 0, ni vidas ke ni devas havi h̃(x) = 0. Se aliflanke x ∉ X, tiam ekzistas ξ tia ke ξ · x − h(ξ) > 0, kaj se ni anstataŭigas ξ per tξ kaj strebigas t nefinien, ni vidas ke ni devas havi h̃(x) = +∞, ĉar

h̃(x) ⩾ (tξ) · x − h(tξ) = t(ξ · x − h(ξ))

pro la homogeneco. Tio montras ke h̃ = i_{X}.

La lasta aserto estas tutsimple la inversiga formulo por la transformo de Fenchel:

ni ja scias ke ˜ h̃ = h sub la menciitaj supozoj. Per tio la teoremo estas pruvita.

Ni do identigis la arojn kies indikaj funkcioj estas transformoj de Fenchel: ili estas la fermitaj konveksaj aroj. Same la pozitive homogenaj funkcioj kiuj estas transformoj: ili estas la malsupren duonkontinuaj, konveksaj kaj pozitive homogenaj funkcioj kiuj plenumas h(0) = 0, plus la konstanto −∞. La transformo de Fenchel fariĝas en tiuj ĉi kazoj la operacio preni la apogan funkcion de aro, kaj en la alia direkto la operacio (11.1).

Ni nun povas specialigi la rezultojn de sekcioj 9 kaj 10 al indikaj funkcioj kaj homogenaj funkcioj. Ekzemple diras propozicio 9.3, specialigita al f = i_{X} kaj g = i_{Y}, ke la apoga funkcio de vektora sumo estas la malsupra sumo de la apoga funkcio de ĉiu aro:

H_{X+Y} = H_{X} + · H_{Y} .

Ĉi tie la punkto necesas nur kiam unu el la aroj malplenas: ambaŭ flankoj tiam fariĝas idente minus nefinio. En ĉiuj aliaj kazoj ni povas skribi ordinaran plus-signon sen risko de miskompreno.

Se f = i_{X} kaj g = i_{Y}, tiam f + · g = f + g = i_{X∩Y}. Se X kaj Y estas fermitaj kaj konveksaj, tiam la korolario 9.4 do diras ke la apoga funkcio de X ∩ Y estas (H_{X} ⊓ ⊔ H_{Y})˜ . Tiu funkcio povas esti priskribita kiel la plej granda malsupren duonkontinua malpliedanto de H_{X} ⊓ ⊔ H_{Y} se X ∩ Y ≠ Ø, kaj egalas al la konstanto −∞ se X ∩ Y malplenas.

12. La teorio pri ludoj kaj lineara programado Ni nun montru ke la ĉefa teoremo de la teorio pri ludoj sekvas el la teorio pri dualeco kiun ni evoluigis en la antaŭa sekcio.

En la teorio pri ludoj oni konsideras du ludantojn kiuj elektas elementojn el du aroj: ludanto 1 elektas el finia aro I, kaj ludanto 2 el finia aro J. La elektoj ne estas konataj al la alia ludanto. Se la elektoj estas i ∈ I kaj j ∈ J, tiam ludanto 1 pagu al ludanto 2 la sumon a_{ij}. (Se a_{ij} estas negativa, tio kompreneble signifas ke ludanto 2 pagu al ludanto 1 la sumon −a_{ij}.) Ni supozas ke ambaŭ ludantoj partoprenas kun la celo maksimumigi sian gajnon. Povas okazi ke ekzistas elementoj i_{0} ∈ I kaj j_{0} ∈ J tiaj ke

a_{ij_{0}} ⩾ a_{i_{0}j_{0}} ⩾ a_{i_{0}j}

por ĉiuj (i, j) ∈ I × J. Tiam ludanto 1 elektu i_{0} kaj ludanto 2 la elementon j_{0}, ĉar se ludanto 2 elektas j_{0}, tiam ludanto 1 ne povas pagi malpli elektante alian elementon ol i_{0}. Same ludanto 2 ne povas ricevi pli elektante alian elementon ol j_{0}, se 1 konservas sian elekton. Pro tio ĉiu situacio (i_{0}, j_{0}) kiu plenumas la menciitan neegalaĵon nomiĝas ekvilibro. Sed ĝenerale ne ekzistas iu tia paro (i_{0}, j_{0}); la plej simpla ekzemplo estas

A = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) .

Tiam la ludantoj povas elekti elementojn laŭ certa probablo. Se ludanto 1 elektas elementon i kun probablo x_{i}, kaj 2 elementon j kun probablo y_{j}, tiam mezvalore la pago estos

F (x, y) = ∑ a_{ij}x_{i}y_{j}.

La pago do estas stokasta variablo kun tiu ekspekto. La probabloj kompreneble devas plenumi x_{i} ⩾ 0 kaj ∑ x_{i} = 1, kaj simile pri y_{j}. Geometrie tia aro nomiĝas simplekso. Montriĝas nun ke ekzistas selopunkto, t. e. paro (x̂, ŷ) tia ke

F (x̂, y) ⩽ F (x̂, ŷ) ⩽ F (x, ŷ)

por ĉiuj x kaj ĉiuj y. Tio signifas ke se ludanto 1 elektas la strategion x̂, tiam ŝi mezvalore ne bezonas pagi malpli al 2 ol se ŝi elektas iun ajn alian strategion x, ĉar F (x, ŷ) ⩾ F (x̂, ŷ). Same se ludanto 2 elektas strategion ŷ ŝi ne povas ricevi pli elektante alian strategion. Do, kvankam ne ekzistas ekvilibro, la ludantoj povas stokaste elekti laŭ la selopunkta problablo, kaj ĝi stokaste estas ekvilibro. La ekzisto de selopunkto pro tio estas grava. Oni povas montri ke se ekzistas selopunkto, tiam la valoro de F en tiu punkto nepre estas

F (x̂, ŷ) = inf_{x∈X} sup_{y∈Y} F (x, y) = sup_{y∈Y} inf_{x∈X} F (x, y).

Ni rigardu la esprimojn en tiu ĉi egalaĵo. Se ludanto 1 elektas strategion x, tiam ŝi devas en la plej malbona kazo pagi la sumon f(x) = sup_{y} F (x, y) al 2, se 2 elektas la por ŝi plej bonan strategion. Estas do en la intereso de 1 elekti strategion x tian ke f(x) estas minimuma, kaj la pago al 2 tiam estas inf_{x} f(x) = inf_{x} sup_{y} F (x, y). Ludanto 1 povas certi ke ŝi ne bezonas pagi pli ol tiun sumon al 2 (la maldekstra flanko de (12.1) sube). Analoge, se 2 elektas la strategion y, ŝi povas certi ke ŝi ricevas almenaŭ h(y) = inf_{x} F (x, y) de 1, kaj ŝia intereso sekve estas elekti strategion y tian ke h estas maksimuma, t. e. sup_{y} h(y) = sup_{y} inf_{x} F (x, y) (la dekstra flanko de (12.1) sube). Kaj nun la ĉefa teoremo diras ke tiuj du pagoj estas egalaj. Ni pruvu tion.

Ni do konsideru ludon kun du ludantoj kaj paga funkcio

F (x, y) = ∑_{i,j} x_{i}a_{ij}y_{j}

kie x ∈ X, y ∈ Y kaj X kaj Y estas simpleksoj:

X = {x ∈ R^{n}; x_{i} ⩾ 0 kaj ∑ x_{i} = 1},
Y = {y ∈ R^{m}; y_{j} ⩾ 0 kaj ∑ y_{j} = 1}.

Teoremo 12.1. (La ĉefteoremo de la teorio pri ludoj.) Estu A = (a_{ij}) donita reela matrico kaj estu X kaj Y la simpleksoj kiujn ni ĵus difinis. Tiam validas

(12.1)  inf_{x∈X} sup_{y∈Y} F (x, y) = sup_{y∈Y} inf_{x∈X} F (x, y),

kaj ekzistas selopunkto (x̂, ŷ) kie tiu valoro estas alprenita.

Pruvo. Ni difinu funkcion f per

f(x) = sup_{y∈Y} F (x, y) = sup_{y∈Y} ∑ x_{i}a_{ij}y_{j} = max_{j} ∑ x_{i}a_{ij} = max_{j}(x · a_{j}),

kie a_{j} = (a_{1j}, ..., a_{nj})^{T} estas la j-a vertikalo de la matrico A. La funkcio f reele valoras kaj konveksas kiel la maksimumo de finia nombro de linearaj funkcioj. Ni povas kalkuli ĝian transformaĵon de Fenchel: f̃(ξ) = 0 kiam ξ situas en la konveksa

tegaĵo de la punktoj a_{1}, ..., a_{m}, kaj = +∞ ekster tiu aro. Oni ankaŭ vidas ke ˜ f̃ = f. Plue ni difinas g kiel la indikan funkcion de X, t. e. g nulas en X kaj egalas al +∞ ekster ĝi. Ni povas kalkuli la transformaĵon de Fenchel ankaŭ por g kaj trovas ke g̃(ξ) = max ξ_{j}. Speciale, g̃ estas ĉie finia, kaj per tio ankaŭ f̃ ⊓ ⊔ g̃. Ni povas kontroli ke ˜ g̃ = g. Teoremo 10.2 tiam diras ke

(12.2)  inf_{x}(f(x) + g(x)) = − inf_{ξ}(f̃(ξ) + g̃(−ξ)).

Ni nun bezonas nur rigardi kion diras tiu egalaĵo. Estas evidente ke

inf_{x∈X} sup_{y∈Y} F (x, y) = inf_{x∈X} f(x) = inf_{x∈R^{n}}(f(x) + g(x)),

t. e. la maldektra flanko de (12.1) egalas al la maldektra flanko de (12.2). La dekstra flanko de (12.2) estas

− inf_{ξ}(f̃(ξ) + g̃(−ξ)) = − inf_{ξ}(g̃(−ξ); f̃(ξ) = 0) = − inf_{ξ}(max_{j}(−ξ_{j}); f̃(ξ) = 0)

= sup_{ξ}(min_{j} ξ_{j}; f̃(ξ) = 0) = sup_{ξ}( inf_{x∈X} x · ξ; f̃(ξ) = 0).

La kondiĉo f̃(ξ) = 0 signifas ke ξ havas la formon ∑ a_{ij}y_{j} por iu y ∈ Y, tiel ke la dekstra flanko de (12.2) fariĝas

sup_{ξ}( inf_{x∈X} x · ξ; f̃(ξ) = 0) = sup_{y∈Y} inf_{x∈X} ∑ x_{i}a_{ij}y_{j} = sup_{y∈Y} inf_{x∈X} F (x, y).

Sekve la dekstra flanko de (12.2) egalas al la dekstra flanko de (12.1), kaj ni vidas ke (12.1) estas speciala kazo de teoremo 10.2. Tio montras ke la valoro de la ludo estas la sama el la vidpunkto de ambaŭ ludantoj.

Por trovi selopunkton ni uzas kompaktecon: ekzistas punkto x̂ tia ke f(x̂) = inf_{x} f(x) kaj punkto ŷ tia ke h(ŷ) = sup_{y} h(y), kie ni nun metis h(y) = inf_{x} F (x, y). Sekvas ke

inf_{x} sup_{y} F (x, y) = inf_{x} f = f(x̂),

dum

sup_{y} inf_{x} F (x, y) = sup_{y} h = h(ŷ).

Plue validas

F (x̂, y) ⩽ sup_{y} F (x̂, y) = f(x̂) kaj h(ŷ) = inf_{x} F (x, ŷ) ⩽ F (x, ŷ).

Sed (12.2) kiun ni ĵus pruvis ja diras ke f(x̂) = h(ŷ); do sekvas ke

F (x̂, y) ⩽ f(x̂) = h(ŷ) ⩽ F (x, ŷ).

Per elekto de y = ŷ respektive x = x̂ ĉi tie ni ekhavas

F (x̂, y) ⩽ F (x̂, ŷ) = f(x̂) = h(ŷ) ⩽ F (x, ŷ)

por ĉiuj x ∈ X kaj ĉiuj y ∈ Y, kio signifas ke (x̂, ŷ) estas selopunkto.

Teoremo 12.2. (La teoremo pri dualeco en lineara programado.) Problemo de lineara programado

inf_{Ax⩾b} cx  kaj ĝia dualaĵo  sup_{\begin{matrix}A^{T} y=c^{T} \\ y⩾0 \end{matrix}} b^{T} y

havas la saman valoron krom en la kazo ke ambaŭ pluredroj malplenas. Ni ĉi tie mencias nur unu paron de dualaj problemoj (en ĝenerala formo respektive kanona formo). Vidu Borell & Lindahl, paĝoj 32–33, aŭ Best & Ritter, paĝo 88, pri aliaj variantoj. Pruvo. Ni metu f_{i}(x) = 0 kiam ∑_{j} a_{ij}x_{j} ⩾ b_{i}, i = 1, ..., m, kaj f_{i}(x) = +∞ alikaze. Tio signifas ke f_{i} estas la indika funkcio de duonspaco, nome tiu kiu estas difinita per a_{i} · x ⩾ b_{i}, kie a_{i} estas la vektoro (a_{i1}, ..., a_{in}). Ni povas facile kalkuli ĝian transformaĵon de Fenchel: f̃_{i}(ξ) = −tb_{i} kiam ξ = −ta_{i} por iu t ⩾ 0, kaj f̃_{i}(ξ) = +∞ ĉie ekster tiu ĉi radio. Tiam f = f_{1} + ⋯ + f_{m} estas la indika funkcio de la pluredro P en la unua LP-problemo, kaj la apoga funkcio de la pluredro estas H_{P} = f̃. La valoro de la LP-problemo estas tutsimple v = −f̃(−c) = −H_{P} (−c).

Korolario 9.4 (aŭ tre precize ties ĝeneraligo al pluraj termoj) diras ke

H_{P} = f̃ = (f_{1} + ⋯ + f_{m}) = (f̃_{1} ⊓ ⊔ ⋯ ⊓ ⊔ f̃_{m})˜ .

Laŭ la difino de la infima kunfaldo validas

g(ξ) = f̃_{1} ⊓ ⊔ ⋯ ⊓ ⊔ f̃_{m}(ξ) = inf_{y} ( ∑(−y_{i}b_{i}); ∑(−y_{i}a_{i}) = ξ kaj y_{i} ⩾ 0).

Kiam ξ = −c, tiu nombro estas ekzakte minus la valoro de la duala LP-problemo, do v^{∗} = −g(−c). Resume, ni havas

v = −f̃(−c) = −˜g̃(−c) ⩾ −g(−c) = v^{∗}.

(La aserto ke v ⩾ v^{∗} kutime nomiĝas la malforta dualeca teoremo kaj estas per tio jam nun pruvita.) Ni vidas ke la teoremo pri dualeco estas reduktita al la demando ĉu ˜ g̃ = g en la punkto ξ = −c. Ni scias ke ˜ g̃ = f̃ = H_{P}, el kio sekvas ke g̃ = f = i_{P}.

Estu nun K la konuse konveksa tegaĵo de la vektoroj −a_{i}, i = 1, ..., m. Ĝi estas fermita konveksa konuso (teoremo 2.2) kaj evidente g = +∞ ekster K. Se P ne malplenas, la neegalaĵo g ⩾ ˜ g̃ = f̃ = H_{P} > −∞ diras ke g nenie alprenas la valoron −∞. La demando ĉu g = ˜ g̃ estas tiam nur demando ĉu g estas malsupren duonkontinua. El teoremo 9.5 ni vidas ke g kontinuas en la interno de K, tiel ke tie certe validas ˜ g̃(ξ) = g(ξ) (cetere K egalas al la tuta spaco se P estas barita). Kiel estos pri la rando de K? Ĉi tie teoremo 2.2 helpos nin. Nome, konsideru la m vektorojn (−a_{i}, −b_{i}) en R^{n} × R. Ilia konuse konveksa tegaĵo L estas laŭ teoremo 2.2 fermita. Ni vidas ke g tutsimple estas la malsupra limo de tiu konuso. Plue K estas la bildo de L per la projekcio kiu forgesas la lastan koordinaton. Sekvas ke g kontinuas sur K, kaj per tio ke ˜ g̃ = g.

Se, kontraŭe, P malplenas, montriĝas ke g = −∞ en K (sed daŭre egalas al +∞ ekstere). Tial ˜ g̃ devas esti −∞ idente, tiel ke ˜ g̃ = g en K sed g > ˜ g̃ en la komplemento. Ni vidas ke v = v^{∗} = +∞ se −c ∈ K, dum v = +∞ > v^{∗} = −∞ se −c ∉ K, t. e. kiam la pluredro de la duala problemo malplenas. Tio estas la escepto en la teoremo. Por vidi ke g vere estas −∞ en K ni povas rezoni jene: se P malplenas, ekzistas nombroj t_{i} ⩾ 0 tiaj ke ∑ t_{i}a_{i} = 0 dum ∑ t_{i}b_{i} > 0. Tio donas

g(ξ) ⩽ ∑(−y_{i} − st_{i})b_{i} = ∑(−y_{i}b_{i}) − s ∑ t_{i}b_{i} → −∞

kiam s → +∞, kondiĉe ke ξ ∈ K tiel ke ekzistas prezento ξ = ∑(−y_{i}a_{i}).

Ankaŭ la dualeca teoremo en la teorio pri lineara programado estas do konsekvenco de la dualeco inter la adicio kaj la infima kunfaldo.

Bibliografio

Best, Michael J., & Ritter, Klaus

1985 Linear Programming. Englewood Cliffs: Prentice-Hall.

Borell, Christer, & Lindahl, Lars-Åke

1979 Linjär och konvex optimering. Upsalo: Upsala Universitato.

Kiselman, Christer O. 1986 Konvekseco en kompleksa analitiko unu-dimensia. Lekciaj notoj 1986:LN2. Upsalo: Upsala Universitato.

Rockafellar, R. Tyrrell

1970 Convex Analysis. Princeton University Press.

Adreso de la verkinto: Upsala Universitato, Matematika Instituto,

Thunbergsvägen 3, 752 38 Uppsala, Svedujo.

Telefono: +46 – 18 - 18 32 16; +46 – 18 - 30 07 08. Fakso: 018 - 18 32 01. Komputilreta adreso: matck @ seudac21 . bitnet.