Teorema Minimax

Teorema minimax se datorează lui von Neumann ^[1] ^[2] . Teorema minimax oferă condiții suficiente pentru ca inegalitatea max-min să fie o egalitate. Teorema constituie nu numai punctul de plecare al teoriei jocurilor , ci și o teoremă a dualității pentru problemele de programare liniară în care regiunea fezabilă este convexă și compactă (închisă și mărginită).

Este ${\displaystyle f:{\mathit {K_{1}}}\times {\mathit {K_{2}}}\to \mathbb {R} }$ ${\ displaystyle {\ displaystyle f: {\ mathit {K_ {1}}} \ times {\ mathit {K_ {2}}} \ to \ mathbb {R}}}$ ${\ displaystyle {\ displaystyle f: {\ mathit {K_ {1}}} \ times {\ mathit {K_ {2}}} \ to \ mathbb {R}}}$ o funcție continuă unde ${\mathit {K_{1}}}\subset \mathbb {R} ^{n}$ ${\ displaystyle {\ mathit {K_ {1}}} \ subset \ mathbb {R} ^ {n}}$ ${\ displaystyle {\ mathit {K_ {1}}} \ subset \ mathbb {R} ^ {n}}$ Și ${\mathit {K_{2}}}\subset \mathbb {R} ^{m}$ ${\ displaystyle {\ mathit {K_ {2}}} \ subset \ mathbb {R} ^ {m}}$ ${\ displaystyle {\ mathit {K_ {2}}} \ subset \ mathbb {R} ^ {m}}$ sunt seturi convexe compacte . De sine $f$ ${\ displaystyle f}$ $f$ este o funcție convex-concavă, adică astfel încât

f(\cdot ,y):{\mathit {K_{1}}}\to \mathbb {R}

{\ displaystyle f (\ cdot, y): {\ mathit {K_ {1}}} \ to \ mathbb {R}}

{\ displaystyle f (\ cdot, y): {\ mathit {K_ {1}}} \ to \ mathbb {R}}

este convex pentru

y

{\ displaystyle y}

y

fix și

f(x,\cdot ):{\mathit {K_{2}}}\to \mathbb {R}

{\ displaystyle f (x, \ cdot): {\ mathit {K_ {2}}} \ to \ mathbb {R}}

{\ displaystyle f (x, \ cdot): {\ mathit {K_ {2}}} \ to \ mathbb {R}}

este concav pentru

X

{\ displaystyle x}

X

fix,

asa de

\min _{x\in {\mathit {K_{1}}}}\max _{y\in {\mathit {K_{2}}}}f(x,y)=\max _{y\in {\mathit {K_{2}}}}\min _{x\in {\mathit {K_{1}}}}f(x,y).

{\ displaystyle \ min _ {x \ in {\ mathit {K_ {1}}}} \ max _ {y \ in {\ mathit {K_ {2}}}} f (x, y) = \ max _ { y \ in {\ mathit {K_ {2}}}} \ min _ {x \ in {\ mathit {K_ {1}}}} f (x, y).}

{\ displaystyle \ min _ {x \ in {\ mathit {K_ {1}}}} \ max _ {y \ in {\ mathit {K_ {2}}}} f (x, y) = \ max _ { y \ in {\ mathit {K_ {2}}}} \ min _ {x \ in {\ mathit {K_ {1}}}} f (x, y).}

Exemple

În teoria jocurilor pentru un joc finit cu două sume zero cu un număr finit de strategii (așa-numitele jocuri simetrice ), este ușor să ne gândim la funcția de plată $f:S_{1}\times S_{2}\rightarrow \mathbb {R}$ ${\ displaystyle f: S_ {1} \ times S_ {2} \ rightarrow \ mathbb {R}}$ ${\ displaystyle f: S_ {1} \ times S_ {2} \ rightarrow \ mathbb {R}}$ ca la o formă biliniară alternativă a cărei proprietate de alternanță $f(s_{1},s_{2})=-f(s_{2},s_{1})$ ${\ displaystyle f (s_ {1}, s_ {2}) = - f (s_ {2}, s_ {1})}$ ${\ displaystyle f (s_ {1}, s_ {2}) = - f (s_ {2}, s_ {1})}$ matematicizează opoziția totală a celor doi jucători, adică faptul că suma plăților este zero. Indicat cu $S_{1}$ ${\ displaystyle S_ {1}}$ $S_1$ Și $S_{2}$ ${\ displaystyle S_ {2}}$ $S_2$ setul de strategii pure ale celor doi jucători și plasarea

f_{1}(s_{1},s_{2}):=f(s_{1},s_{2})

{\ displaystyle f_ {1} (s_ {1}, s_ {2}): = f (s_ {1}, s_ {2})}

{\ displaystyle f_ {1} (s_ {1}, s_ {2}): = f (s_ {1}, s_ {2})}

f_{2}(s_{1},s_{2}):=f(s_{2},s_{1})

{\ displaystyle f_ {2} (s_ {1}, s_ {2}): = f (s_ {2}, s_ {1})}

{\ displaystyle f_ {2} (s_ {1}, s_ {2}): = f (s_ {2}, s_ {1})}

se obține definiția jocului cu sumă zero:

f_{1}(s_{1},s_{2})+f_{2}(s_{1},s_{2})

{\ displaystyle f_ {1} (s_ {1}, s_ {2}) + f_ {2} (s_ {1}, s_ {2})}

{\ displaystyle f_ {1} (s_ {1}, s_ {2}) + f_ {2} (s_ {1}, s_ {2})}

≡

0

{\ displaystyle 0}

{\ displaystyle 0}

pentru fiecare

s_{1}\in S_{1}

{\ displaystyle s_ {1} \ în S_ {1}}

{\ displaystyle s_ {1} \ în S_ {1}}

și pentru fiecare

s_{2}\in S_{2}

{\ displaystyle s_ {2} \ în S_ {2}}

{\ displaystyle s_ {2} \ în S_ {2}}

În jocurile finite este imediat să vedem că cele două seturi

S_{1}

{\ displaystyle S_ {1}}

S_1

Și

S_{2}

{\ displaystyle S_ {2}}

S_2

se dovedesc a fi compacte, deoarece sunt finite și, prin urmare, nu au puncte de acumulare. Funcțiile plăților

f_{i}

{\ displaystyle f_ {i}}

f_ {i}

sunt definite pe seturi fără puncte de acumulare, deci seturi constând doar din puncte izolate, adică puncte în care cele două funcții

f_{i}

{\ displaystyle f_ {i}}

f_ {i}

se dovedesc a fi continuu (mai uniform continuu ). În ceea ce privește cererea ca cele două seturi

S_{1}

{\ displaystyle S_ {1}}

S_1

Și

S_{2}

{\ displaystyle S_ {2}}

S_2

sunt convexe, este suficient să se ia în considerare politopul lor ( anvelopă convexă ) odată ce conceptul de strategie mixtă a fost introdus ca un tuplu de numere non-negativ

({\tilde {s}}_{1},\ldots ,{\tilde {s}}_{n})

{\ displaystyle ({\ tilde {s}} _ {1}, \ ldots, {\ tilde {s}} _ {n})}

{\ displaystyle ({\ tilde {s}} _ {1}, \ ldots, {\ tilde {s}} _ {n})}

astfel încât

{\tilde {s}}_{1}+...+{\tilde {s}}_{n}=1

{\ displaystyle {\ tilde {s}} _ {1} + ... + {\ tilde {s}} _ {n} = 1}

{\ displaystyle {\ tilde {s}} _ {1} + ... + {\ tilde {s}} _ {n} = 1}

. Domeniul variației strategiilor mixte este mai extins decât cel al strategiilor pure: pentru acestea din urmă, de fapt, domeniul este un set finit simplu de

n

{\ displaystyle n}

n

tupluri ordonate, în timp ce strategiile mixte sunt definite pe un subset al spațiului vectorial dimensional

n

{\ displaystyle n}

n

constând din toate combinațiile liniare convexe de

n

{\ displaystyle n}

n

strategii pure și ca atare este convexă și având o dimensiune finită egală cu

n+1

{\ displaystyle n + 1}

n + 1

. Plicul convex este compact deoarece este construit pe setul compact de strategii pure. De sine

f_{1}(\cdot ,{\tilde {s}}_{2})

{\ displaystyle f_ {1} (\ cdot, {\ tilde {s}} _ {2})}

{\ displaystyle f_ {1} (\ cdot, {\ tilde {s}} _ {2})}

se dovedește a fi convex în ceea ce privește

{\tilde {s}}_{1}

{\ displaystyle {\ tilde {s}} _ {1}}

{\ displaystyle {\ tilde {s}} _ {1}}

pentru

{\tilde {s}}_{2}

{\ displaystyle {\ tilde {s}} _ {2}}

{\ displaystyle {\ tilde {s}} _ {2}}

fix și de atunci

f_{1}=-f_{2}

{\ displaystyle f_ {1} = - f_ {2}}

{\ displaystyle f_ {1} = - f_ {2}}

, asa de

f_{2}({\tilde {s}}_{1},\cdot )

{\ displaystyle f_ {2} ({\ tilde {s}} _ {1}, \ cdot)}

{\ displaystyle f_ {2} ({\ tilde {s}} _ {1}, \ cdot)}

se dovedește a fi concav în ceea ce privește

{\tilde {s}}_{2}

{\ displaystyle {\ tilde {s}} _ {2}}

{\ displaystyle {\ tilde {s}} _ {2}}

pentru

{\tilde {s}}_{1}

{\ displaystyle {\ tilde {s}} _ {1}}

{\ displaystyle {\ tilde {s}} _ {1}}

fix, astfel încât să fie îndeplinite condițiile teoremei minimax.

Valoarea unui joc simetric cu suma zero pentru doi jucători extins la strategii mixte are o valoare zero ^[3] . Valoarea unui joc prin definiție este

\min _{{\tilde {s}}_{1}}\max _{{\tilde {s}}_{2}}f({\tilde {s}}_{1},{\tilde {s}}_{2})=v^{*}=\max _{{\tilde {s}}_{2}}\min _{{\tilde {s}}_{1}}f({\tilde {s}}_{1},{\tilde {s}}_{2})

{\ displaystyle \ min _ {{\ tilde {s}} _ {1}} \ max _ {{\ tilde {s}} _ {2}} f ({\ tilde {s}} _ {1}, { \ tilde {s}} _ {2}) = v ^ {*} = \ max _ {{\ tilde {s}} _ {2}} \ min _ {{\ tilde {s}} _ {1}} f ({\ tilde {s}} _ {1}, {\ tilde {s}} _ {2})}

{\ displaystyle \ min _ {{\ tilde {s}} _ {1}} \ max _ {{\ tilde {s}} _ {2}} f ({\ tilde {s}} _ {1}, { \ tilde {s}} _ {2}) = v ^ {*} = \ max _ {{\ tilde {s}} _ {2}} \ min _ {{\ tilde {s}} _ {1}} f ({\ tilde {s}} _ {1}, {\ tilde {s}} _ {2})}

Luați în considerare mai întâi partea stângă a celor doi egali tocmai scrise

v*=\min _{{\tilde {s}}_{1}}\max _{{\tilde {s}}_{2}}f({\tilde {s}}_{1},{\tilde {s}}_{2})

{\ displaystyle v * = \ min _ {{\ tilde {s}} _ {1}} \ max _ {{\ tilde {s}} _ {2}} f ({\ tilde {s}} _ {1 }, {\ tilde {s}} _ {2})}

{\ displaystyle v * = \ min _ {{\ tilde {s}} _ {1}} \ max _ {{\ tilde {s}} _ {2}} f ({\ tilde {s}} _ {1 }, {\ tilde {s}} _ {2})}

, prin ipoteză este

f({\tilde {s}}_{1},{\tilde {s}}_{2})=-f({\tilde {s}}_{2},{\tilde {s}}_{1})

{\ displaystyle f ({\ tilde {s}} _ {1}, {\ tilde {s}} _ {2}) = - f ({\ tilde {s}} _ {2}, {\ tilde {s }} _ {1})}

{\ displaystyle f ({\ tilde {s}} _ {1}, {\ tilde {s}} _ {2}) = - f ({\ tilde {s}} _ {2}, {\ tilde {s }} _ {1})}

asa de

v^{*}=\min _{{\tilde {s}}_{1}}\max _{{\tilde {s}}_{2}}f({\tilde {s}}_{1},{\tilde {s}}_{2})=\min _{{\tilde {s}}_{1}}\max _{{\tilde {s}}_{2}}[-f({\tilde {s}}_{2},{\tilde {s}}_{1})]=-\max _{{\tilde {s}}_{1}}\min _{{\tilde {s}}_{2}}f({\tilde {s}}_{2},{\tilde {s}}_{1})

{\ displaystyle v ^ {*} = \ min _ {{\ tilde {s}} _ {1}} \ max _ {{\ tilde {s}} _ {2}} f ({\ tilde {s}} _ {1}, {\ tilde {s}} _ {2}) = \ min _ {{\ tilde {s}} _ {1}} \ max _ {{\ tilde {s}} _ {2}} [-f ({\ tilde {s}} _ {2}, {\ tilde {s}} _ {1})] = - \ max _ {{\ tilde {s}} _ {1}} \ min _ {{\ tilde {s}} _ {2}} f ({\ tilde {s}} _ {2}, {\ tilde {s}} _ {1})}

{\ displaystyle v ^ {*} = \ min _ {{\ tilde {s}} _ {1}} \ max _ {{\ tilde {s}} _ {2}} f ({\ tilde {s}} _ {1}, {\ tilde {s}} _ {2}) = \ min _ {{\ tilde {s}} _ {1}} \ max _ {{\ tilde {s}} _ {2}} [-f ({\ tilde {s}} _ {2}, {\ tilde {s}} _ {1})] = - \ max _ {{\ tilde {s}} _ {1}} \ min _ {{\ tilde {s}} _ {2}} f ({\ tilde {s}} _ {2}, {\ tilde {s}} _ {1})}

.

Deoarece setul de strategii pentru cei doi jucători este identic

S_{1}=S_{2}

{\ displaystyle S_ {1} = S_ {2}}

{\ displaystyle S_ {1} = S_ {2}}

, schimbând

{\tilde {s}}_{1}

{\ displaystyle {\ tilde {s}} _ {1}}

{\ displaystyle {\ tilde {s}} _ {1}}

cu

{\tilde {s}}_{2}

{\ displaystyle {\ tilde {s}} _ {2}}

{\ displaystyle {\ tilde {s}} _ {2}}

primesti

-\max _{{\tilde {s}}_{1}}\min _{{\tilde {s}}_{2}}f({\tilde {s}}_{2},{\tilde {s}}_{1})=-\max _{{\tilde {s}}_{2}}\min _{{\tilde {s}}_{1}}f({\tilde {s}}_{1},{\tilde {s}}_{2})=-v^{*}

{\ displaystyle - \ max _ {{\ tilde {s}} _ {1}} \ min _ {{\ tilde {s}} _ {2}} f ({\ tilde {s}} _ {2}, {\ tilde {s}} _ {1}) = - \ max _ {{\ tilde {s}} _ {2}} \ min _ {{\ tilde {s}} _ {1}} f ({\ tilde {s}} _ {1}, {\ tilde {s}} _ {2}) = - v ^ {*}}

{\ displaystyle - \ max _ {{\ tilde {s}} _ {1}} \ min _ {{\ tilde {s}} _ {2}} f ({\ tilde {s}} _ {2}, {\ tilde {s}} _ {1}) = - \ max _ {{\ tilde {s}} _ {2}} \ min _ {{\ tilde {s}} _ {1}} f ({\ tilde {s}} _ {1}, {\ tilde {s}} _ {2}) = - v ^ {*}}

.

Pentru comparație, se dovedește

v^{*}=-v^{*}

{\ displaystyle v ^ {*} = - v ^ {*}}

{\ displaystyle v ^ {*} = - v ^ {*}}

și, prin urmare, în mod necesar, valoarea jocului este

v^{*}=0

{\ displaystyle v ^ {*} = 0}

{\ displaystyle v ^ {*} = 0}

.

Matricea asociată cu funcția de plăți $f$ ${\ displaystyle f}$ $f$ este o matrice antisimetrică și are doar zerouri ca elemente ale diagonalei principale, deoarece dă $f(s_{1},s_{2})=-f(s_{2},s_{1})$ ${\ displaystyle f (s_ {1}, s_ {2}) = - f (s_ {2}, s_ {1})}$ ${\ displaystyle f (s_ {1}, s_ {2}) = - f (s_ {2}, s_ {1})}$ pentru fiecare $s_{1}$ ${\ displaystyle s_ {1}}$ $s_ {1}$ , $s_{2}$ ${\ displaystyle s_ {2}}$ $s_ {2}$ rezultă imediat că este $f(s_{1},s_{1})=0$ ${\ displaystyle f (s_ {1}, s_ {1}) = 0}$ ${\ displaystyle f (s_ {1}, s_ {1}) = 0}$ pentru fiecare $s_{1}$ ${\ displaystyle s_ {1}}$ $s_ {1}$ odată ales $s_{1}=s_{2}$ ${\ displaystyle s_ {1} = s_ {2}}$ ${\ displaystyle s_ {1} = s_ {2}}$ .

Teorema min-max și programarea convexă

Teorema care stă la baza jocurilor antagonice poate fi luată ca un punct de uniune între teoria dualității și problemele programării convexe, în special cele ale programării liniare . Perechile de probleme constituite de problema primară și de problema sa duală sunt de fapt strâns legate de problema determinării punctelor de șa $(\mathbf {x} ^{\ast },\mathbf {y} ^{\ast })$ ${\ displaystyle (\ mathbf {x} ^ {\ ast}, \ mathbf {y} ^ {\ ast})}$ ${\ displaystyle (\ mathbf {x} ^ {\ ast}, \ mathbf {y} ^ {\ ast})}$ a funcției Lagrangiene ${\mathcal {L}}(\mathbf {x} ,\mathbf {y} )$ ${\ displaystyle {\ mathcal {L}} (\ mathbf {x}, \ mathbf {y})}$ ${\ displaystyle {\ mathcal {L}} (\ mathbf {x}, \ mathbf {y})}$ . De sine $\mathbf {x} ^{\ast }$ ${\ displaystyle \ mathbf {x} ^ {\ ast}}$ ${\ displaystyle \ mathbf {x} ^ {\ ast}}$ este soluția problemei primare de maximizare și dacă $\mathbf {y} ^{\ast }$ ${\ displaystyle \ mathbf {y} ^ {\ ast}}$ ${\ displaystyle \ mathbf {y} ^ {\ ast}}$ este soluția problemei de minimizare duală, atunci valoarea optimă a funcției lagrangiene a problemei primare, $maxmin{\mathcal {L}}$ ${\ displaystyle maxmin {\ mathcal {L}}}$ ${\ displaystyle maxmin {\ mathcal {L}}}$ , coincide cu valoarea optimă a funcției lagrangiene a problemei duale, $minmax{\mathcal {L}}$ ${\ displaystyle minmax {\ mathcal {L}}}$ ${\ displaystyle minmax {\ mathcal {L}}}$ . Cu alte cuvinte, relația de dualitate este adevărată:

\max _{x\in {\mathit {K_{1}}}}\min _{y\in {\mathit {K_{2}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {y} )={\mathcal {L}}(\mathbf {x} ^{\ast },\mathbf {y} ^{\ast })=\min _{y\in {\mathit {K_{2}}}}\max _{x\in {\mathit {K_{1}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {y} )

{\ displaystyle \ max _ {x \ in {\ mathit {K_ {1}}}} \ min _ {y \ in {\ mathit {K_ {2}}}} {\ mathcal {L}} (\ mathbf { x}, \ mathbf {y}) = {\ mathcal {L}} (\ mathbf {x} ^ {\ ast}, \ mathbf {y} ^ {\ ast}) = \ min _ {y \ in {\ mathit {K_ {2}}}} \ max _ {x \ in {\ mathit {K_ {1}}}} {\ mathcal {L}} (\ mathbf {x}, \ mathbf {y})}

{\ displaystyle \ max _ {x \ in {\ mathit {K_ {1}}}} \ min _ {y \ in {\ mathit {K_ {2}}}} {\ mathcal {L}} (\ mathbf { x}, \ mathbf {y}) = {\ mathcal {L}} (\ mathbf {x} ^ {\ ast}, \ mathbf {y} ^ {\ ast}) = \ min _ {y \ in {\ mathit {K_ {2}}}} \ max _ {x \ in {\ mathit {K_ {1}}}} {\ mathcal {L}} (\ mathbf {x}, \ mathbf {y})}

În general, cel puțin unul dintre cele două seturi ${\mathit {K_{1}}}$ ${\ displaystyle {\ mathit {K_ {1}}}}$ ${\ displaystyle {\ mathit {K_ {1}}}}$ sau ${\mathit {K_{2}}}$ ${\ displaystyle {\ mathit {K_ {2}}}}$ ${\ displaystyle {\ mathit {K_ {2}}}}$ este un set nelimitat, prin urmare nu este compact: acesta este motivul pentru care teorema lui von Neumann nu este aplicată pe scară largă în programarea convexă ^[4] .

Exemplu

Într-un joc generic cu două persoane pentru suma maximă a jucătorului, avem următoarea problemă principală:

\max _{x\in {\mathit {K_{1}}}}v

{\ displaystyle \ max _ {x \ in {\ mathit {K_ {1}}}} v}

{\ displaystyle \ max _ {x \ in {\ mathit {K_ {1}}}} v}

sub rezerva constrângerilor:

\left\{{\begin{array}{l}{\begin{matrix}\sum _{j=1}^{n}a_{i,j}\cdot x_{j}\end{matrix}}\geq v\quad \forall i=1,...,m\\{\begin{matrix}\sum _{j=1}^{n}x_{j}\end{matrix}}=1\\x_{j}\geq 0\quad \forall j=1,...,n\\\end{array}}\right.

{\ displaystyle \ left \ {{\ begin {array} {l} {\ begin {matrix} \ sum _ {j = 1} ^ {n} a_ {i, j} \ cdot x_ {j} \ end {matrix }} \ geq v \ quad \ forall i = 1, ..., m \\ {\ begin {matrix} \ sum _ {j = 1} ^ {n} x_ {j} \ end {matrix}} = 1 \\ x_ {j} \ geq 0 \ quad \ forall j = 1, ..., n \\\ end {array}} \ right.}

{\ displaystyle \ left \ {{\ begin {array} {l} {\ begin {matrix} \ sum _ {j = 1} ^ {n} a_ {i, j} \ cdot x_ {j} \ end {matrix }} \ geq v \ quad \ forall i = 1, ..., m \\ {\ begin {matrix} \ sum _ {j = 1} ^ {n} x_ {j} \ end {matrix}} = 1 \\ x_ {j} \ geq 0 \ quad \ forall j = 1, ..., n \\\ end {array}} \ right.}

Funcția Lagrangiană asociată cu această problemă este:

{\mathcal {L}}(\mathbf {x} ,\mathbf {y} )=v+\left\langle \mathbf {y} ,A\mathbf {x} -\mathbf {v} \right\rangle

{\ displaystyle {\ mathcal {L}} (\ mathbf {x}, \ mathbf {y}) = v + \ left \ langle \ mathbf {y}, A \ mathbf {x} - \ mathbf {v} \ right \ rangle}

{\ displaystyle {\ mathcal {L}} (\ mathbf {x}, \ mathbf {y}) = v + \ left \ langle \ mathbf {y}, A \ mathbf {x} - \ mathbf {v} \ right \ rangle}

unde este $\mathbf {v} =\left(v,\cdots ,v\right)$ ${\ displaystyle \ mathbf {v} = \ left (v, \ cdots, v \ right)}$ ${\ displaystyle \ mathbf {v} = \ left (v, \ cdots, v \ right)}$ , in timp ce $\mathbf {y} =(y_{1},\cdots ,y_{m})$ ${\ displaystyle \ mathbf {y} = (y_ {1}, \ cdots, y_ {m})}$ ${\ displaystyle \ mathbf {y} = (y_ {1}, \ cdots, y_ {m})}$ ele reprezintă multiplicatorii lagrange și constituie strategiile mixte ale jucătorului advers.

Am observat că funcția Lagrangiană ${\mathcal {L}}(\mathbf {x} ,\mathbf {y} )=v+\left\langle \mathbf {y} ,A\mathbf {x} -\mathbf {v} \right\rangle$ ${\ displaystyle {\ mathcal {L}} (\ mathbf {x}, \ mathbf {y}) = v + \ left \ langle \ mathbf {y}, A \ mathbf {x} - \ mathbf {v} \ right \ rangle}$ ${\ displaystyle {\ mathcal {L}} (\ mathbf {x}, \ mathbf {y}) = v + \ left \ langle \ mathbf {y}, A \ mathbf {x} - \ mathbf {v} \ right \ rangle}$ se dovedește a fi o funcție convexă în variabilă $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ pe ansamblu ${\mathit {K_{1}}}=\left\{x\in \mathbb {R} ^{n}|\sum _{j=1}^{n}x_{j}\cdot \alpha _{j}\quad |\quad \alpha _{j}=1,\quad \sum _{j=1}^{n}x_{j}=1,\quad x_{j}\geq 0\quad \forall j\right\}$ ${\ displaystyle {\ mathit {K_ {1}}} = \ left \ {x \ in \ mathbb {R} ^ {n} | \ sum _ {j = 1} ^ {n} x_ {j} \ cdot \ alpha _ {j} \ quad | \ quad \ alpha _ {j} = 1, \ quad \ sum _ {j = 1} ^ {n} x_ {j} = 1, \ quad x_ {j} \ geq 0 \ quad \ forall j \ right \}}$ ${\ displaystyle {\ mathit {K_ {1}}} = \ left \ {x \ in \ mathbb {R} ^ {n} | \ sum _ {j = 1} ^ {n} x_ {j} \ cdot \ alpha _ {j} \ quad | \ quad \ alpha _ {j} = 1, \ quad \ sum _ {j = 1} ^ {n} x_ {j} = 1, \ quad x_ {j} \ geq 0 \ quad \ forall j \ right \}}$ , că Lagrangianul ${\mathcal {L}}(\mathbf {x} ,\mathbf {y} )$ ${\ displaystyle {\ mathcal {L}} (\ mathbf {x}, \ mathbf {y})}$ ${\ displaystyle {\ mathcal {L}} (\ mathbf {x}, \ mathbf {y})}$ este în mod clar o funcție liniară în $\mathbf {y}$ ${\ displaystyle \ mathbf {y}}$ ${\ mathbf {y}}$ , prin urmare se dovedește a fi banal concav în interior $\mathbf {y}$ ${\ displaystyle \ mathbf {y}}$ ${\ mathbf {y}}$ deoarece fiecare funcție liniară este atât concavă, cât și convexă și că cele două seturi ${\mathit {K_{1}}}$ ${\ displaystyle {\ mathit {K_ {1}}}}$ ${\ displaystyle {\ mathit {K_ {1}}}}$ Și ${\mathit {K_{2}}}$ ${\ displaystyle {\ mathit {K_ {2}}}}$ ${\ displaystyle {\ mathit {K_ {2}}}}$ sunt compacte, se deduce că relația dualității

\max _{x\in {\mathit {K_{1}}}}\min _{y\in {\mathit {K_{2}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {y} )=\min _{y\in {\mathit {K_{2}}}}\max _{x\in {\mathit {K_{1}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {y} )

{\ displaystyle \ max _ {x \ in {\ mathit {K_ {1}}}} \ min _ {y \ in {\ mathit {K_ {2}}}} {\ mathcal {L}} (\ mathbf { x}, \ mathbf {y}) = \ min _ {y \ in {\ mathit {K_ {2}}}} \ max _ {x \ in {\ mathit {K_ {1}}}} {\ mathcal { L}} (\ mathbf {x}, \ mathbf {y})}

{\ displaystyle \ max _ {x \ in {\ mathit {K_ {1}}}} \ min _ {y \ in {\ mathit {K_ {2}}}} {\ mathcal {L}} (\ mathbf { x}, \ mathbf {y}) = \ min _ {y \ in {\ mathit {K_ {2}}}} \ max _ {x \ in {\ mathit {K_ {1}}}} {\ mathcal { L}} (\ mathbf {x}, \ mathbf {y})}

este o consecință directă a teoremei minimax.

Formularea explicită a dublei probleme se obține luând în considerare

\min _{y\in {\mathit {K_{2}}}}\max _{x\in {\mathit {K_{1}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {y} )

{\ displaystyle \ min _ {y \ in {\ mathit {K_ {2}}}} \ max _ {x \ in {\ mathit {K_ {1}}}} {\ mathcal {L}} (\ mathbf { x}, \ mathbf {y})}

{\ displaystyle \ min _ {y \ in {\ mathit {K_ {2}}}} \ max _ {x \ in {\ mathit {K_ {1}}}} {\ mathcal {L}} (\ mathbf { x}, \ mathbf {y})}

Mai întâi maximizăm Lagrangianul pentru $\mathbf {y}$ ${\ displaystyle \ mathbf {y}}$ ${\ displaystyle \ mathbf {y}}$ fix și $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ ${\ displaystyle \ mathbf {x}}$ variabilă în ${\mathit {K_{1}}}$ ${\ displaystyle {\ mathit {K_ {1}}}}$ ${\ displaystyle {\ mathit {K_ {1}}}}$

\max _{x\in {\mathit {K_{1}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {y} )=\max _{x\in {\mathit {K_{1}}}}\left[v-\left\langle \mathbf {y} ,\mathbf {v} \right\rangle +\left\langle \mathbf {y} ,A\mathbf {x} \right\rangle \right]

{\ displaystyle \ max _ {x \ in {\ mathit {K_ {1}}}} {\ mathcal {L}} (\ mathbf {x}, \ mathbf {y}) = \ max _ {x \ in { \ mathit {K_ {1}}}} \ left [v- \ left \ langle \ mathbf {y}, \ mathbf {v} \ right \ rangle + \ left \ langle \ mathbf {y}, A \ mathbf {x } \ right \ rangle \ right]}

{\ displaystyle \ max _ {x \ in {\ mathit {K_ {1}}}} {\ mathcal {L}} (\ mathbf {x}, \ mathbf {y}) = \ max _ {x \ in { \ mathit {K_ {1}}}} \ left [v- \ left \ langle \ mathbf {y}, \ mathbf {v} \ right \ rangle + \ left \ langle \ mathbf {y}, A \ mathbf {x } \ right \ rangle \ right]}

Fiind $\sum _{j=1}^{n}x_{j}=1$ ${\ displaystyle \ sum _ {j = 1} ^ {n} x_ {j} = 1}$ ${\ displaystyle \ sum _ {j = 1} ^ {n} x_ {j} = 1}$ poti sa scrii $v=v\cdot 1=v{\dot {\left(\sum _{j=1}^{n}x_{j}\right)}}=vx_{1}+\cdots +vx_{n}=\left\langle \mathbf {v} ,\mathbf {x} \right\rangle$ ${\ displaystyle v = v \ cdot 1 = v {\ dot {\ left (\ sum _ {j = 1} ^ {n} x_ {j} \ right)}} = vx_ {1} + \ cdots + vx_ { n} = \ left \ langle \ mathbf {v}, \ mathbf {x} \ right \ rangle}$ ${\ displaystyle v = v \ cdot 1 = v {\ dot {\ left (\ sum _ {j = 1} ^ {n} x_ {j} \ right)}} = vx_ {1} + \ cdots + vx_ { n} = \ left \ langle \ mathbf {v}, \ mathbf {x} \ right \ rangle}$ unde este $\mathbf {v} =\left(v,\cdots ,v\right)$ ${\ displaystyle \ mathbf {v} = \ left (v, \ cdots, v \ right)}$ ${\ displaystyle \ mathbf {v} = \ left (v, \ cdots, v \ right)}$ . Mi-am amintit asta $\left\langle \mathbf {y} ,A\mathbf {x} \right\rangle =\left\langle A^{t}\mathbf {y} ,\mathbf {x} \right\rangle$ ${\ displaystyle \ left \ langle \ mathbf {y}, A \ mathbf {x} \ right \ rangle = \ left \ langle A ^ {t} \ mathbf {y}, \ mathbf {x} \ right \ rangle}$ ${\ displaystyle \ left \ langle \ mathbf {y}, A \ mathbf {x} \ right \ rangle = \ left \ langle A ^ {t} \ mathbf {y}, \ mathbf {x} \ right \ rangle}$ primesti

\max _{x\in {\mathit {K_{1}}}}\left[-\left\langle \mathbf {y} ,\mathbf {v} \right\rangle +\left\langle \mathbf {v} ,\mathbf {x} \right\rangle +\left\langle A^{t}\mathbf {y} ,\mathbf {x} \right\rangle \right]=-\left\langle \mathbf {y} ,\mathbf {v} \right\rangle +\max _{x\in {\mathit {K_{1}}}}\left[\left\langle \mathbf {v} +A^{t}\mathbf {y} ,\mathbf {x} \right\rangle \right]

{\ displaystyle \ max _ {x \ in {\ mathit {K_ {1}}}} \ left [- \ left \ langle \ mathbf {y}, \ mathbf {v} \ right \ rangle + \ left \ langle \ mathbf {v}, \ mathbf {x} \ right \ rangle + \ left \ langle A ^ {t} \ mathbf {y}, \ mathbf {x} \ right \ rangle \ right] = - \ left \ langle \ mathbf {y}, \ mathbf {v} \ right \ rangle + \ max _ {x \ in {\ mathit {K_ {1}}}} \ left [\ left \ langle \ mathbf {v} + A ^ {t} \ mathbf {y}, \ mathbf {x} \ right \ rangle \ right]}

{\ displaystyle \ max _ {x \ in {\ mathit {K_ {1}}}} \ left [- \ left \ langle \ mathbf {y}, \ mathbf {v} \ right \ rangle + \ left \ langle \ mathbf {v}, \ mathbf {x} \ right \ rangle + \ left \ langle A ^ {t} \ mathbf {y}, \ mathbf {x} \ right \ rangle \ right] = - \ left \ langle \ mathbf {y}, \ mathbf {v} \ right \ rangle + \ max _ {x \ in {\ mathit {K_ {1}}}} \ left [\ left \ langle \ mathbf {v} + A ^ {t} \ mathbf {y}, \ mathbf {x} \ right \ rangle \ right]}

.

Atâta timp cât $x_{j}\geq 0$ ${\ displaystyle x_ {j} \ geq 0}$ ${\ displaystyle x_ {j} \ geq 0}$ pentru tot ij din $1$ ${\ displaystyle 1}$ $1$ la $m$ ${\ displaystyle m}$ $m$ , vei avea $\left\langle \mathbf {v} +A^{t}\mathbf {y} ,\mathbf {x} \right\rangle >0$ ${\ displaystyle \ left \ langle \ mathbf {v} + A ^ {t} \ mathbf {y}, \ mathbf {x} \ right \ rangle> 0}$ ${\ displaystyle \ left \ langle \ mathbf {v} + A ^ {t} \ mathbf {y}, \ mathbf {x} \ right \ rangle> 0}$ de sine $\mathbf {v} +A^{t}\mathbf {y} >0$ ${\ displaystyle \ mathbf {v} + A ^ {t} \ mathbf {y}> 0}$ ${\ displaystyle \ mathbf {v} + A ^ {t} \ mathbf {y}> 0}$ sau $\left\langle \mathbf {v} +A^{t}\mathbf {y} ,\mathbf {x} \right\rangle \leq 0$ ${\ displaystyle \ left \ langle \ mathbf {v} + A ^ {t} \ mathbf {y}, \ mathbf {x} \ right \ rangle \ leq 0}$ ${\ displaystyle \ left \ langle \ mathbf {v} + A ^ {t} \ mathbf {y}, \ mathbf {x} \ right \ rangle \ leq 0}$ de sine $\mathbf {v} +A^{t}\mathbf {y} \leq 0$ ${\ displaystyle \ mathbf {v} + A ^ {t} \ mathbf {y} \ leq 0}$ ${\ displaystyle \ mathbf {v} + A ^ {t} \ mathbf {y} \ leq 0}$ .

Deci avem:

\min _{y\in {\mathit {K_{2}}}}\max _{x\in {\mathit {K_{1}}}}{\mathcal {L}}(\mathbf {x} ,\mathbf {y} )=\min _{y\in {\mathit {K_{2}}}}\left[\left\langle \mathbf {y} ,\mathbf {v} \right\rangle \right]=\min _{y\in {\mathit {K_{2}}}}-v

{\ displaystyle \ min _ {y \ in {\ mathit {K_ {2}}}} \ max _ {x \ in {\ mathit {K_ {1}}}} {\ mathcal {L}} (\ mathbf { x}, \ mathbf {y}) = \ min _ {y \ in {\ mathit {K_ {2}}}} \ left [\ left \ langle \ mathbf {y}, \ mathbf {v} \ right \ rangle \ right] = \ min _ {y \ in {\ mathit {K_ {2}}}} - v}

{\ displaystyle \ min _ {y \ in {\ mathit {K_ {2}}}} \ max _ {x \ in {\ mathit {K_ {1}}}} {\ mathcal {L}} (\ mathbf { x}, \ mathbf {y}) = \ min _ {y \ in {\ mathit {K_ {2}}}} \ left [\ left \ langle \ mathbf {y}, \ mathbf {v} \ right \ rangle \ right] = \ min _ {y \ in {\ mathit {K_ {2}}}} - v}

pentru

\mathbf {v} +A^{t}\mathbf {y} \leq 0

{\ displaystyle \ mathbf {v} + A ^ {t} \ mathbf {y} \ leq 0}

{\ displaystyle \ mathbf {v} + A ^ {t} \ mathbf {y} \ leq 0}

iar problema duală are următoarea formulare:

\min _{y\in {\mathit {K_{2}}}}-v

{\ displaystyle \ min _ {y \ in {\ mathit {K_ {2}}}} - v}

{\ displaystyle \ min _ {y \ in {\ mathit {K_ {2}}}} - v}

sub rezerva constrângerilor:

\left\{{\begin{array}{l}{\begin{matrix}\sum _{i=1}^{m}a_{i,j}\cdot y_{i}\end{matrix}}\leq -v\quad \forall j=1,...,n\\{\begin{matrix}\sum _{i=1}^{m}y_{i}\end{matrix}}=1\\y_{i}\geq 0\quad \forall i=1,...,m\\\end{array}}\right.

{\ displaystyle \ left \ {{\ begin {array} {l} {\ begin {matrix} \ sum _ {i = 1} ^ {m} a_ {i, j} \ cdot y_ {i} \ end {matrix }} \ leq -v \ quad \ forall j = 1, ..., n \\ {\ begin {matrix} \ sum _ {i = 1} ^ {m} y_ {i} \ end {matrix}} = 1 \\ y_ {i} \ geq 0 \ quad \ forall i = 1, ..., m \\\ end {array}} \ right.}

{\ displaystyle \ left \ {{\ begin {array} {l} {\ begin {matrix} \ sum _ {i = 1} ^ {m} a_ {i, j} \ cdot y_ {i} \ end {matrix }} \ leq -v \ quad \ forall j = 1, ..., n \\ {\ begin {matrix} \ sum _ {i = 1} ^ {m} y_ {i} \ end {matrix}} = 1 \\ y_ {i} \ geq 0 \ quad \ forall i = 1, ..., m \\\ end {array}} \ right.}

Loc ${\tilde {v}}=-v$ ${\ displaystyle {\ tilde {v}} = - v}$ ${\ displaystyle {\ tilde {v}} = - v}$ da ai

\min _{y\in {\mathit {K_{2}}}}{\tilde {v}}

{\ displaystyle \ min _ {y \ in {\ mathit {K_ {2}}}} {\ tilde {v}}}

{\ displaystyle \ min _ {y \ in {\ mathit {K_ {2}}}} {\ tilde {v}}}

\left\{{\begin{array}{l}{\begin{matrix}-A^{t}\cdot \mathbf {y} \mathbf {} \end{matrix}}\geq -{\tilde {v}}\\{\begin{matrix}\sum _{i=1}^{m}y_{i}\end{matrix}}=1\\y_{i}\geq 0\quad \forall i=1,...,m\\\end{array}}\right.

{\ displaystyle \ left \ {{\ begin {array} {l} {\ begin {matrix} -A ^ {t} \ cdot \ mathbf {y} \ mathbf {} \ end {matrix}} \ geq - {\ tilde {v}} \\ {\ begin {matrix} \ sum _ {i = 1} ^ {m} y_ {i} \ end {matrix}} = 1 \\ y_ {i} \ geq 0 \ quad \ forall i = 1, ..., m \\\ end {array}} \ right.}

{\ displaystyle \ left \ {{\ begin {array} {l} {\ begin {matrix} -A ^ {t} \ cdot \ mathbf {y} \ mathbf {} \ end {matrix}} \ geq - {\ tilde {v}} \\ {\ begin {matrix} \ sum _ {i = 1} ^ {m} y_ {i} \ end {matrix}} = 1 \\ y_ {i} \ geq 0 \ quad \ forall i = 1, ..., m \\\ end {array}} \ right.}

Notă

^ J. von Neumann, Zur Theorie der Gesselschaftsspiele , Math. Ann. 100, 1928, p. 295-320.
^ J. von Neumann, Contribuții la teoria jocurilor. Vol. IV, Analele. of Mathematics Studies, nr.40 , Princeton Univ. Press, 1959, p. 13-42.
^ E. Burger, Introducere în teoria jocurilor , Prentice-Hall, Inc., 1959, p. 74.
^ EG Goldstein, Theory of Convex Progrmamming , Providence, SUA, American Mathematical Society, 1972, p. 7.

[1] J. von Neumann, Zur Theorie der Gesselschaftsspiele , Math. Ann. 100, 1928, p. 295-320.

[2] J. von Neumann, Contribuții la teoria jocurilor. Vol. IV, Analele. of Mathematics Studies, nr.40 , Princeton Univ. Press, 1959, p. 13-42.

[3] E. Burger, Introducere în teoria jocurilor , Prentice-Hall, Inc., 1959, p. 74.

[4] EG Goldstein, Theory of Convex Progrmamming , Providence, SUA, American Mathematical Society, 1972, p. 7.

[1]

[2]

[3]

[4]