25 Lineer Programlama ve İki-Kişilik Oyunlar

Köşe çözümleri, max-flow min-cut dualitesi ve von Neumann minimax

Bölüm bilgisi

Bu ders optimizasyonun özel ama merkezî bir sınıfını işler: doğrusal hedef + doğrusal kısıtlar (lineer programlama). Anahtar kavram dualite — max-flow = min-cut ve iki-kişilik sıfır-toplamlı oyunların minimax dengesi hep aynı ilkedir. Strang’in Ders 24 videosu (≈53 dk) ve OCW Lecture 24 temel alınmıştır. Okuma süresi ≈34 dk; önkoşul Ders 23 (gradient descent, momentum, kondisyon).

25.1 Bu Derste Ne Var?

Bu derste beş sonuç var:

LP: $\min\ c^{T}x$, kısıt $Ax = b$ ve $x \geq 0$ (eşitsizlik kısıtı LP’yi “özel” yapar). Çözüm bir köşededir.
Algoritmalar: simplex (Dantzig, köşeden köşeye) ve iç-nokta (Karmarkar, feasible set içinden).
Max-flow min-cut: ağın maksimum akışı = minimum kesim kapasitesi — klasik dualite örneği.
Dualite: her akış ≤ her kesim; maksimum = minimum olduğunda optimal.
İki-kişilik oyun: payoff matrisi; $x$ satır seçer, $y$ sütun; saddle point yoksa karma strateji (mixed strategy) + minimax.

“Linear programming is a very famous part of optimization.” — Strang, 1:57

flowchart TD
    M["LP + dualite + oyunlar"]

    M --> A["LP: min c^T x, Ax = b, x &gt;= 0<br/>(esitsizlik = ozel hal)"]
    M --> B["cozum bir KOSEDE<br/>(dogrusal maliyet)"]
    M --> C["simplex: koseden koseye<br/>ic-nokta: iceriden (Karmarkar)"]
    M --> D["max-flow = min-cut<br/>(dualite)"]
    M --> E["iki-kisilik oyun:<br/>payoff matrisi"]

    G["karma strateji + minimax<br/>(von Neumann)"]
    H["minimax = GAN / adversarial"]
    P["Ders 18 KKT + Ders 19 maxmin koprusu"]

    E --> G
    G --> H

    classDef merkez fill:#1f4e79,stroke:#13243a,stroke-width:2px,color:#ffffff;
    classDef dal fill:#2e75b6,stroke:#1f4e79,stroke-width:1.5px,color:#ffffff;
    classDef sky fill:#9dc3e6,stroke:#2e75b6,stroke-width:1.5px,color:#1f4e79;

    class M merkez;
    class A,B,C,D,E dal;
    class G,H,P sky;

Şekil 25.1: Ders 24 kavram haritasi — lineer programlama, max-flow min-cut dualitesi ve iki-kisilik oyunlar tek bir minimax cercevesinde bulusur.

Şekil 25.1 dersin iskeletini gösterir: merkezdeki “LP + dualite + oyunlar” fikri, eşitsizlik kısıtının LP’yi özel kıldığı doğrusal hedeften, doğrusal maliyetin çözümü bir köşeye ittiği geometriden, simplex (köşeden köşeye) ile iç-nokta (Karmarkar) algoritma ikiliğinden, max-flow = min-cut dualitesinden ve payoff matrisli iki-kişilik oyundan dallanır; ayrı düğümlerde karma strateji + minimax (von Neumann), minimax = GAN/adversarial köprüsü ve Ders 18 (KKT) + Ders 19 (maxmin) bağı durur.

Builder Notu — Her Min’in Bir Maks İkizi

Dualite = optimizasyonun kalbi — her minimizasyon probleminin bir maksimizasyon ikizi vardır; ikisi eşitse optimal kanıtlanmıştır (max-flow min-cut, primal-dual).
LP ∈ P — polinom zamanda çözülür (ellipsoid, Khachiyan); simplex ortalama-durumda hızlı (Spielman smoothed analysis).
Minimax = GAN — iki-kişilik sıfır-toplamlı oyun; üretici-ayırıcı (Ders 23) ve adversarial eğitim aynı minimax yapısı.
Geriye köprü: Ders 18 (KKT, Lagrange kısıtlı optimizasyon), Ders 19 (maxmin/minimax — özdeğer versiyonu), Ders 21 (konvekslik, feasible set). Paralel: 6.006 Ders 16 (ağırlıklı en kısa yol — LP dualitesi).

25.2 Lineer Programlama Nedir?

Optimizasyonun en ünlü özel sınıfı:

“Linear programming is a very famous part of optimization.” — Strang, 1:57

Doğrusal bir maliyet fonksiyonunu, doğrusal kısıtlar altında minimize et:

\[\min\ c^{T}x \quad \text{s.t.}\quad Ax = b, \quad x \geq 0\]

$x$ bilinmeyen ($n\times 1$), $c$ maliyet vektörü, $A$ ise $m\times n$ ($m < n$, kare-tersinir DEĞİL). Maliyet doğrusal, eşitlik kısıtları doğrusal — ama $x \geq 0$ (vektör eşitsizliği: her $x_{i} \geq 0$) işi doğrusal-olmayan, “özel” yapar. Bu iki kısıt birlikte uygunluk kümesi (feasible set) $K$’yi tanımlar.

Builder Notu — Eşitsizlik Köşe Yaratır

“$x \geq 0$ eşitsizliği LP’yi özel kılar” — eşitsizlik kısıtları çözümü kısıt bölgesinin sınırına/köşesine iter. ML köprüsü: negatif-olmama kısıtı her yerde (olasılıklar, ağırlıklar, kaynaklar ≥ 0); LP, kaynak tahsisi, üretim planlama ve (dual formda) SVM gibi problemlerin temelidir.

25.3 Geometri: Çözüm Bir Köşededir

$n = 3$’te görselleştir. $x \geq 0$ → uzayın 1/8’i (oktant). Tek kısıt ($Ax = b$) bir düzlem; oktantla kesişimi bir üçgen. Örnek: $\min x_{1} + 2x_{2} + 5x_{3}$, kısıt $x_{1} + x_{2} + x_{3} = 3$, $x \geq 0$. Düzlem eksenleri $(3,0,0)$, $(0,3,0)$, $(0,0,3)$’te keser. Maliyet doğrusal olduğundan minimum bir köşededir:

“…one of these three corners is the winner.” — Strang, 8:15

Üç köşenin maliyeti: $(3,0,0)\to 3$, $(0,3,0)\to 6$, $(0,0,3)\to 15$. Kazanan $x^{*} = (3,0,0)$, maliyet 3. Doğrusal fonksiyon uçlarda (köşelerde) ekstremumdadır — iç noktada değil.

Kod

from mpl_toolkits.mplot3d import Axes3D
from mpl_toolkits.mplot3d.art3d import Poly3DCollection

# Motor: köşeler ve maliyetler doğrulanmış
costs, win, win_corner, x, fun = lp_corner_demo([1, 2, 5], 3)
V = [(3, 0, 0), (0, 3, 0), (0, 0, 3)]

fig = plt.figure(figsize=(7.5, 5.5))
ax = fig.add_subplot(projection="3d")

# Üçgen yüzey (oktant ∩ düzlem x1+x2+x3=3)
tri = Poly3DCollection([V], alpha=0.3, facecolor=COL_PRIMARY, edgecolor=COL_PRIMARY, linewidths=2)
ax.add_collection3d(tri)

# Köşe maliyet etiketleri
labels = ["maliyet 3", "6", "15"]
for (vx, vy, vz), lab, cst in zip(V, labels, costs):
    ax.scatter([vx], [vy], [vz], color=COL_PRIMARY, s=45, depthshade=False)
    ax.text(vx, vy, vz + 0.25, lab, color=COL_TEXT, fontsize=11, fontweight="bold", ha="center")

# Kazanan köşe (3,0,0) turuncu büyük marker
wx, wy, wz = win_corner
ax.scatter([wx], [wy], [wz], color=COL_VEC3, s=180, depthshade=False, zorder=10, edgecolor=COL_TEXT, linewidth=1.2)

# Maliyet azalma yönü -c oku (kazanan köşeye doğru kaçar)
ax.quiver(1.3, 1.3, 0.4, -1.0, -0.5, -0.3, color=COL_VEC3, linewidth=2.5, arrow_length_ratio=0.18)
ax.text(1.4, 1.4, 0.55, "-c yönü", color=COL_VEC3, fontsize=10, fontweight="bold")

ax.set_xlabel("x₁"); ax.set_ylabel("x₂"); ax.set_zlabel("x₃")
ax.set_xlim(0, 3.2); ax.set_ylim(0, 3.2); ax.set_zlim(0, 3.4)

# Pane sadeleştir
ax.xaxis.pane.set_alpha(0.0); ax.yaxis.pane.set_alpha(0.0); ax.zaxis.pane.set_alpha(0.0)
ax.xaxis.pane.set_edgecolor(COL_STEEL_300); ax.yaxis.pane.set_edgecolor(COL_STEEL_300); ax.zaxis.pane.set_edgecolor(COL_STEEL_300)
ax.tick_params(colors=COL_TEXT)
ax.xaxis.label.set_color(COL_TEXT); ax.yaxis.label.set_color(COL_TEXT); ax.zaxis.label.set_color(COL_TEXT)
ax.view_init(elev=22, azim=35)

ax.set_title("Feasible set = oktant ∩ duzlem = ucgen; dogrusal maliyet koseye kacar: kazanan (3,0,0), maliyet 3",
             color=COL_TEXT, fontsize=10.5, fontweight="bold", pad=12)

fig.tight_layout()
plt.show()

Şekil 25.2: Feasible set = oktant ∩ duzlem (x₁ + x₂ + x₃ = 3) = üçgen. Doğrusal maliyet köşeye kaçar: köşe maliyetleri (3,0,0)→3, (0,3,0)→6, (0,0,3)→15; kazanan köşe (3,0,0), maliyet 3 (linprog çözümü birebir köşede).

Şekil 25.2 LP’nin temel teoremini görselleştirir: feasible set, oktant ($x \geq 0$) ile düzlemin ($x_{1}+x_{2}+x_{3}=3$) kesişimi olan bir üçgendir; üç köşenin maliyeti $3 / 6 / 15$ ve doğrusal maliyet köşeye kaçtığı için kazanan köşe $(3,0,0)$ (turuncu marker), minimum maliyet 3 — linprog çözümü bu köşeyle birebir aynı çıkar.

Builder Notu — Doğrusal Maliyet Uçlara Kaçar

“Doğrusal maliyet → köşede optimal” LP’nin temel teoremi: optimum daima bir köşede (vertex) bulunur. ML köprüsü: bu, LASSO’nun (ℓ¹ regülarizasyon, Ders 8/16) neden seyrek çözüm verdiğini açıklar — ℓ¹ topu köşelidir, optimum köşeye (çok sıfırlı) düşer. Köşe = seyreklik geometrisi.

25.4 Algoritmalar: Simplex ve İç-Nokta

Köşeyi bulmak yeter — ama büyük $m, n$’de üstel sayıda köşe var, hepsini sayamayız. İki algoritma ailesi:

Simplex (Dantzig): bir köşeden başla, maliyeti düşüren bir kenar boyunca yürü, sonraki köşeye var, tekrarla — kenarlar üzerinde steepest descent.

“…the simplex method, which finds a corner.” — Strang, 10:45

İç-nokta (interior point, Karmarkar): kenarlardan değil, uygunluk kümesinin içinden geç; bir arama yönü seç, sınıra çarpmadan dur, Newton/kalkülüsle minimize et.

“…interior point method.” — Strang, 13:46

Karmarkar’ın 1984’teki yöntemi (New York Times’a çıkacak kadar ses getirdi) iç-nokta fikrini popülerleştirdi. Karmaşıklık: simplex en-kötü durumda üstel ama ortalama-durumda polinom (Spielman smoothed analysis); ayrıca LP’nin P sınıfında olduğu kanıtlandı (ellipsoid yöntemi, Khachiyan — ünlü Rus sonucu).

Kod

fig, ax = plt.subplots(figsize=(7, 4.6))

# --- Şematik politop (kapalı çokgen) ---
verts = [(0, 0), (4, 0), (5.5, 2), (4.5, 4.5), (2, 5), (0, 3)]
poly = plt.Polygon(verts, closed=True, facecolor=COL_ACCENT, alpha=0.2,
                   edgecolor=COL_PRIMARY, linewidth=1.8, zorder=2)
ax.add_patch(poly)

# --- Simplex yolu: kenarda köşeden köşeye (turuncu oklar) ---
simplex_path = [(0, 0), (4, 0), (5.5, 2), (4.5, 4.5)]
for (x0, y0), (x1, y1) in zip(simplex_path[:-1], simplex_path[1:]):
    ax.annotate("", xy=(x1, y1), xytext=(x0, y0),
                arrowprops=dict(arrowstyle="-|>", color=COL_VEC3, lw=2.4,
                                shrinkA=4, shrinkB=4), zorder=5)
for (x, y) in simplex_path:
    ax.plot(x, y, "o", color=COL_VEC3, markersize=7, zorder=6)
ax.plot([], [], "-", color=COL_VEC3, lw=2.4, marker="o",
        label="simplex: kenarda köşeden köşeye")

# --- İç-nokta yolu: içeriden kıvrılan çizgi (navy) ---
interior_path = np.array([(1, 1), (2.5, 2), (3.6, 3.2), (4.3, 4.2)])
ax.plot(interior_path[:, 0], interior_path[:, 1], "-o", color=COL_PRIMARY,
        lw=2.2, markersize=6, zorder=4,
        label="iç-nokta: içeriden (Karmarkar)")

# --- Optimal köşe (teal yıldız) ---
ax.plot(4.5, 4.5, "*", color=COL_TEAL, markersize=22,
        markeredgecolor=COL_PRIMARY, markeredgewidth=1.2, zorder=7)

apply_style(ax)
ax.set_xlim(-0.6, 6.2); ax.set_ylim(-0.6, 5.6)
ax.set_aspect("equal")
ax.set_xticks([]); ax.set_yticks([])
for sp in ax.spines.values(): sp.set_visible(False)
ax.grid(False)
ax.legend(loc="lower right", fontsize=9, framealpha=0.92)
ax.set_title("İki strateji aynı köşeye: simplex kenarda yürür (Dantzig),\niç-nokta içeriden geçer (1984, NYT)",
             color=COL_PRIMARY, fontsize=11.5, fontweight="bold")

fig.tight_layout()
plt.show()

Şekil 25.3: İki strateji aynı köşeye varır. Şematik politopun kenarı boyunca simplex (turuncu oklar) köşeden köşeye sıçrar — Dantzig’in yöntemi. İç-nokta yolu (navy) ise politopun içinden kıvrılarak aynı optimum köşeye (teal yıldız) yaklaşır — Karmarkar’ın 1984 yaklaşımı. Aynı çözüm, iki ayrı geometri.

Şekil 25.3 iki algoritma stratejisini aynı politopta karşılaştırır: simplex (turuncu oklar) feasible kümenin kenarı boyunca köşeden köşeye sıçrar (Dantzig), iç-nokta yolu (navy) ise politopun içinden kıvrılarak aynı optimum köşeye (teal yıldız) yaklaşır (Karmarkar, 1984) — aynı çözüm, iki ayrı geometri.

Builder Notu — Kenardan mı İçinden mi

Simplex (kenar) vs iç-nokta (iç) ikiliği, optimizasyonun iki büyük stratejisini temsil eder. ML köprüsü: simplex’in “kenarda steepest descent”i, gradient descent’in (Ders 22) kısıtlı versiyonu; iç-nokta yöntemleri Newton’ı (Ders 21) kısıt bölgesi içinde kullanır. Modern büyük-ölçek LP/QP çözücüleri (SVM eğitimi dahil) iç-nokta tabanlıdır.

25.5 Max-Flow Problemi

LP’nin en güzel örneği: bir ağda kaynaktan (source) hedefe (sink) maksimum akış gönder. Her kenarın bir kapasitesi var; o kenardaki akış kapasiteyi aşamaz:

\[\max\ (\text{sink akisi}) \quad \text{s.t.}\quad 0 \leq (\text{kenar akisi}) \leq (\text{kapasite})\]

Bu bir tamsayı (integer) LP’dir ama dikkat çekici bir özelliği var: kesirli akışa izin versen bile optimal akış tamsayı çıkar — yani tamsayı kısıtını “güvenle gevşetebilirsin” (LP rahatlatması), simplex/iç-nokta uygulayabilirsin. Bu, max-flow’u verimli çözülebilir kılar.

Şekil 25.4 motor ağında max-flow = min-cut = 14 sonucunu çizer; aşağıda dualite bölümünde optimal akışların tamsayı çıktığını ve kesim kümelerinin akışı nasıl sınırladığını ayrıntılandıracağız.

Builder Notu — Tamsayı Bedava Çıkar

Max-flow’un “LP optimumu tamsayı çıkar” özelliği (tümleşik-modülerlik, total unimodularity) nadir ve değerlidir: genelde tamsayı programlama NP-zordur, ama max-flow polinomdur. ML köprüsü: graf-kesim (graph cut) görüntü segmentasyonu, ikili etiketleme (binary labeling) ve enerji minimizasyonu max-flow’a indirgenir — bilgisayarlı görüde standart araç.

25.6 Dualite: Max-Flow = Min-Cut

Bir akışın en fazla ne kadar olabileceğini nasıl sınırlarız? Kesim (cut) ile: ağı kaynak-tarafı ve hedef-tarafı düğümlere ayır; tüm akış bu kesimi geçmek zorunda. Kesimin kapasitesi = onu geçen kenarların toplamı. Her akış ≤ her kesim kapasitesi.

“…that’s what duality is, that any flow has [to be ≤ the capacity of any cut].” — Strang, 37:32

Maksimum akış ile minimum kesim çakıştığında optimal kanıtlanır:

“The maximum flow turned out to be 14[, and the minimum cut turned out to be 14].” — Strang, 34:45

\[\max\ \text{flow} = \min\ \text{cut}\]

İşte dualite: bir minimizasyon (en küçük kesim) ile bir maksimizasyon (en büyük akış) aynı sayıya varır. Akış 14’ü geçebiliyorsam ve hiçbir kesim 14’ün altında değilse, 14 optimaldir. Büyük ağda min-cut görünmez ama hızlı bulunabilir.

Kod

# --- Max-flow min-cut: motor ağı (s,a,b,t), LP çözümü flows=[8,6,1,7,7], değer=14 ---
import networkx as nx

flows, mf = max_flow_lp()
mc = min_cut()

fig, ax = plt.subplots(figsize=(8.5, 4.6))

G = nx.DiGraph()
pos = {0: (0, 0.5), 1: (1, 1), 2: (1, 0), 3: (2, 0.5)}
labels = {0: "s", 1: "a", 2: "b", 3: "t"}
for (u, v, cap) in EDGES:
    G.add_edge(u, v)

nx.draw_networkx_nodes(G, pos, node_color=COL_PRIMARY, node_size=1400, ax=ax)
nx.draw_networkx_labels(G, pos, labels=labels, font_color=COL_WHITE, font_size=15, font_weight="bold", ax=ax)
nx.draw_networkx_edges(G, pos, edge_color=COL_ACCENT, width=2.2, arrowsize=22,
                       node_size=1400, ax=ax, connectionstyle="arc3,rad=0.0")

edge_labels = {(u, v): "{:.0f}/{:.0f}".format(flows[k], cap) for k, (u, v, cap) in enumerate(EDGES)}
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_color=COL_TEXT,
                             font_size=11, font_weight="bold", label_pos=0.5,
                             bbox=dict(boxstyle="round,pad=0.15", fc=COL_BG, ec=COL_STEEL_300, alpha=0.95), ax=ax)

# min-cut {s} ayırıcı kavisli kesik çizgi (x ~ 0.5)
yy = np.linspace(-0.05, 1.05, 60)
xx = 0.5 + 0.10 * np.sin((yy - 0.5) * np.pi)
ax.plot(xx, yy, color=COL_VEC3, lw=2.5, ls="--", zorder=1)
ax.text(0.5, 1.18, "min-cut = {:.0f}".format(mc[1]), color=COL_VEC3,
        fontsize=12, fontweight="bold", ha="center")

ax.set_title(
    "[motor agi] Max-flow = min-cut = {:.0f}: optimal akislar TAMSAYI {}\n"
    "(Strang derste de 14 bulur)".format(mf, [int(round(x)) for x in flows]),
    color=COL_TEXT, fontsize=12, fontweight="bold",
)
ax.set_xlim(-0.35, 2.35); ax.set_ylim(-0.2, 1.4)
ax.axis("off")
plt.show()

Şekil 25.4: [motor ağı] Max-flow = min-cut = 14: optimal akışlar TAMSAYI [8, 6, 1, 7, 7], kesim {s} en dar boğaz (Strang derste de 14 bulur). Her kenarda “akış/kapasite” etiketi; turuncu kesik eğri {s} kesimini ayırır.

Şekil 25.4 dualiteyi somut bir ağda gösterir: kaynak $s$’ten hedef $t$’ye giden LP-optimal akışlar tamsayı $[8, 6, 1, 7, 7]$ çıkar, her kenarda “akış/kapasite” etiketi durur, turuncu kesik eğri $\{s\}$ kesimini ayırır ve max-flow = min-cut = 14. Bu motor ağıdır — Strang’ın derste çizdiği ağ farklı olabilir, ama o da aynı 14 değerine varır; dualite mesajı birebir aynıdır.

Kod

cuts = all_cuts()
labels = ["{s}", "{s,a}", "{s,b}", "{s,a,b}"]
caps = [cap for _, cap in cuts]
max_flow = max_flow_lp()[1]

fig, ax = plt.subplots(figsize=(7, 4.2))
apply_style(ax)

min_idx = int(np.argmin(caps))
colors = [COL_PRIMARY if i == min_idx else COL_VEC2 for i in range(len(caps))]
x = np.arange(len(caps))
bars = ax.bar(x, caps, color=colors, edgecolor=COL_TEXT, linewidth=0.8, width=0.6, zorder=3)

for i, (b, cap) in enumerate(zip(bars, caps)):
    ax.text(b.get_x() + b.get_width() / 2, cap + 0.25, f"{cap:.0f}",
            ha="center", va="bottom", color=COL_TEXT, fontsize=11, fontweight="bold")

ax.text(bars[min_idx].get_x() + bars[min_idx].get_width() / 2, caps[min_idx] / 2,
        "min-cut", ha="center", va="center", color=COL_WHITE, fontsize=11, fontweight="bold", rotation=90)

ax.axhline(max_flow, color=COL_VEC3, linewidth=2.2, linestyle="--", zorder=4)
ax.text(len(caps) - 0.5, max_flow + 0.15, f"max-flow = {max_flow:.0f}",
        ha="right", va="bottom", color=COL_VEC3, fontsize=11, fontweight="bold")

ax.set_xticks(x); ax.set_xticklabels(labels)
ax.set_xlabel("Kesim kümesi S"); ax.set_ylabel("Kesim kapasitesi")
ax.set_ylim(0, max(caps) + 2.5)
ax.set_title("Dualite görsel: HER kesim >= akış (14); minimum kesim akışa DEĞİYOR -> 14 optimal KANITLANDI",
             fontsize=10.5, fontweight="bold")
plt.show()

Şekil 25.5: Dualite görsel: HER kesim >= akış (14); minimum kesim akışa DEĞİYOR -> 14 optimal KANITLANDI

Şekil 25.5 dualitenin kanıt mantığını çubuklarla gösterir: dört s-t kesiminin kapasiteleri $\{s\}\to 14$, $\{s,a\}\to 15$, $\{s,b\}\to 16$, $\{s,a,b\}\to 15$; hiçbir kesim akışın (yatay turuncu çizgi, 14) altına inmez ve minimum kesim ($\{s\}$, navy çubuk) akışa tam değer — bu yüzden 14 hem maksimum akış hem minimum kesimdir, optimal kanıtlanmıştır.

Builder Notu — En Dar Boğaz Kanıttır

Max-flow min-cut, dualitenin en görsel örneği: “ne kadar gönderebilirim” (primal, maks) = “en dar boğaz” (dual, min). ML köprüsü: dualite optimizasyonun her yerinde — SVM’nin primal (margin) ve dual (destek vektörleri) formları, Lagrange dualitesi (Ders 18 KKT). 6.006 Ders 16’nın ağırlıklı en kısa yol problemi de bir LP dualitesi örneğidir (Phase 2 paralel ders köprüsü).

25.7 İki-Kişilik Sıfır-Toplamlı Oyunlar

Aynı dualite oyun teorisinde de var:

“…two-person games…” — Strang, 2:41

İki oyuncu $x$ ve $y$, bir payoff (ödeme) matrisi üzerinde. $x$ bir satır seçer, $y$ bir sütun. Ödeme $x$’ten $y$’ye akar — sıfır-toplamlı ($x$’in ödediği $y$’ye gider, üçüncü taraf yok). $x$ minimize eder (ödeyen), $y$ maksimize eder (alan) — tıpkı LP’nin primal/dual’i gibi. Basit örnek (payoff $[[1, 4], [2, 8]]$): $y$ büyük sayı ister → 2. sütun; $x$ küçük ister → 1. satır; sonuç 2’de kilitlenir. Bu bir saddle point: $y$’nin sütununda min, $x$’in satırında max.

Kod

fig, (axL, axR) = plt.subplots(1, 2, figsize=(9, 3.8))

# Sol: PAY_SADDLE [[1,4],[2,8]] -> saddle (satır2=indeks1, sütun1=indeks0) = 2
heatmap(axL, PAY_SADDLE, fmt="{:.0f}")
i, j = 1, 0
axL.add_patch(plt.Rectangle((j - 0.5, i - 0.5), 1, 1, fill=False, edgecolor=COL_VEC3, lw=3))
axL.text(j, i + 0.62, "satırında MIN,\nsütununda MAX", ha="center", va="top",
         color=COL_VEC3, fontsize=8.5, fontweight="bold")
axL.set_title("[[1,4],[2,8]]: saddle = 2", color=COL_TEXT, fontsize=11.5, fontweight="bold")

# Sağ: PAY_EGZ2 [[3,1],[5,4]] -> saddle (satır2=indeks1, sütun2=indeks1) = 4
heatmap(axR, PAY_EGZ2, fmt="{:.0f}")
i2, j2 = 1, 1
axR.add_patch(plt.Rectangle((j2 - 0.5, i2 - 0.5), 1, 1, fill=False, edgecolor=COL_VEC3, lw=3))
axR.set_title("Egz2 [[3,1],[5,4]]: saddle = 4", color=COL_TEXT, fontsize=11.5, fontweight="bold")

fig.suptitle("Saddle point: satırında min VE sütununda max — saf strateji kilitlenir (find_saddle taraması)",
             color=COL_TEXT, fontsize=10.5, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.94])
plt.show()

Şekil 25.6: Saddle point: satırında min VE sütununda max — saf strateji kilitlenir (find_saddle taraması). Sol [[1,4],[2,8]]: saddle = 2; sağ Egz2 [[3,1],[5,4]]: saddle = 4.

Şekil 25.6 saddle point’i iki payoff matrisinde gösterir: solda $[[1,4],[2,8]]$ için saddle hücresi 2 (turuncu çerçeve — satırında min, sütununda max), sağda Egzersiz 2’nin $[[3,1],[5,4]]$ matrisinde saddle 4; find_saddle taraması bu hücreleri otomatik bulur.

[motor notu]: Rol adlandırması transkriptte gevşek; Notion’un “$x$ küçük ister → 1. satır, sonuç 2” akışı kendi sayılarıyla birebir tutarlı değil ((1. satır, 2. sütun) = 4 olurdu). Sayılar (saddle 2, $q = 2/3$, değer $10/3$) klasik SATIR-ALIR (maximin) / SÜTUN-ÖDER (minimax) konvansiyonunda motor-tanıklıdır: saddle = (satır 2, sütun 1) = 2 satırında min ve sütununda max’tır (find_saddle), ve game_value_lp iki yönden $10/3 = 10/3$ verir.

Builder Notu — Oyunun Primal’i Dual’i

“$x$ minimize (satır), $y$ maksimize (sütun)” oyun yapısı LP primal-dual’in birebir karşılığı. ML köprüsü: GAN’lar (Ders 23) tam iki-kişilik oyun — üretici (generator) kayıbı minimize, ayırıcı (discriminator) maksimize; eğitim bu oyunun dengesini (Nash/saddle) arar. Adversarial robustness de min-maks bir oyun.

25.8 Karma Strateji ve Minimax

Her matriste saddle point yoktur. Payoff $[[1, 4], [8, 2]]$: $y$ 8’i sever (2. sütun), ama $x$ 2. satırı seçince $y$ 4’ü görüp 1. sütuna kayar — saf strateji kilitlenmez. Çözüm karma strateji (mixed strategy):

“Mixed strategy…” — Strang, 43:00

$y$ sütunları $p$ ve $1-p$ olasılıkla, $x$ satırları $q$ ve $1-q$ ile karıştırır. Optimal nokta, karışık seçeneklerin eşit olduğu yerdir (rakip avantaj bulamasın). Örnekte $9p = 6 \to p = 2/3$; oyunun değeri $10/3$. Bu, minimax teoremi (von Neumann): en iyi karma stratejiyle

\[\max_{y}\ \min_{x}\ (\text{payoff}) = \min_{x}\ \max_{y}\ (\text{payoff})\]

Maks-min = min-maks. Bu eşitlik tam olarak LP dualitesidir — iki-kişilik sıfır-toplamlı oyun bir LP’ye eşdeğerdir.

Kod

fig, ax = plt.subplots(figsize=(7.5, 4.6))

qs = np.linspace(0, 1, 200)
c1 = qs * 1 + (1 - qs) * 8     # sütun 1 beklentisi
c2 = qs * 4 + (1 - qs) * 2     # sütun 2 beklentisi

ax.plot(qs, c1, color=COL_PRIMARY, lw=2, label="sütun 1 beklentisi")
ax.plot(qs, c2, color=COL_VEC3, lw=2, label="sütun 2 beklentisi")

env = np.minimum(c1, c2)
ax.plot(qs, env, color=COL_TEAL, lw=3, alpha=0.55, label="satır oyuncusunun garantisi")

q_star, val_star = 2 / 3, 10 / 3
ax.scatter([q_star], [val_star], s=160, marker="*", color=COL_TEAL,
           edgecolors=COL_TEXT, linewidths=0.8, zorder=6)
ax.annotate("q = 2/3, değer = 10/3 (9q = 6)",
            xy=(q_star, val_star), xytext=(0.30, 5.4),
            color=COL_TEXT, fontsize=10, fontweight="bold",
            arrowprops=dict(arrowstyle="->", color=COL_TEXT, lw=1.2))

ax.text(0.02, 0.96, "LP iki yönden: maximin = minimax = 3.3333\n(von Neumann, game_value_lp)",
        transform=ax.transAxes, va="top", ha="left", fontsize=9.5,
        bbox=dict(boxstyle="round,pad=0.4", facecolor=COL_BG,
                  edgecolor=COL_ACCENT, linewidth=1.0))

apply_style(ax)
ax.set_xlabel("q (satır 1 olasılığı)")
ax.set_ylabel("beklenen ödeme")
ax.legend(loc="upper right")
ax.set_title("Karma strateji: iki sütun beklentisi q = 2/3 te eşitlenir -> oyun değeri 10/3 (LP birebir teyit)",
             color=COL_TEXT, fontsize=11, fontweight="bold")
plt.show()

Şekil 25.7: Karma strateji: iki sütun beklentisi q = 2/3 te eşitlenir -> oyun değeri 10/3 (LP birebir teyit)

Şekil 25.7 karma stratejiyi klasik oyun grafiğiyle gösterir: $[[1,4],[8,2]]$ için iki sütun beklentisi $q\cdot 1 + (1-q)\cdot 8$ (navy) ve $q\cdot 4 + (1-q)\cdot 2$ (turuncu) $q = 2/3$ noktasında eşitlenir; satır oyuncusunun garantisi (alt zarf, teal) tam orada maksimum olur ve oyun değeri $10/3$ (teal yıldız) — $9q = 6$ denkleminin çözümü. LP iki yönden maximin = minimax = 3.3333 verir (game_value_lp), von Neumann minimaxı birebir teyitlenir.

Builder Notu — von Neumann’ın Dengesi

von Neumann’ın minimax teoremi (maks-min = min-maks) oyun teorisinin kurucu sonucu ve LP dualitesinin ikizidir. ML köprüsü: bu, Ders 19’un eigenvalue maxmin’inin (Courant-Fischer) oyun-teorik kuzenidir; GAN eğitimi, robust optimizasyon ve adversarial örnekler hep bu min-maks dengesini çözmeye çalışır. Karma strateji = olasılıksal politika (stochastic policy), pekiştirmeli öğrenmenin temeli.

25.9 Bu Dersin Özeti

LP: $\min c^{T}x$, kısıt $Ax = b$, $x \geq 0$. Eşitsizlik kısıtı LP’yi özel yapar; feasible set $K$.
Köşe çözümü: doğrusal maliyet → optimum bir köşede (vertex). Örnek $\min x_{1}+2x_{2}+5x_{3}$, $x_{1}+x_{2}+x_{3}=3$ → $(3,0,0)$, maliyet 3.
Algoritmalar: simplex (Dantzig, köşeden köşeye) + iç-nokta (Karmarkar, içeriden). LP ∈ P (ellipsoid).
Max-flow min-cut: kaynak→hedef maksimum akış = minimum kesim kapasitesi; tamsayı optimum (gevşetilebilir).
Dualite: her akış ≤ her kesim; maks = min optimal. Min (kesim) = maks (akış).
İki-kişilik oyun: payoff matrisi; $x$ satır (min), $y$ sütun (max). Saddle yoksa karma strateji.
Minimax (von Neumann): $\max_{x} \min_{y} = \min_{y} \max_{x}$; iki-kişilik sıfır-toplamlı oyun = LP dualitesi.

Tek Bir Cümle

Lineer programlama doğrusal bir hedefi ($c^{T}x$) doğrusal kısıtlar ($Ax=b$, $x\geq 0$) altında bir köşede minimize eder; dualite (max-flow = min-cut, primal-dual) optimali kanıtlar ve iki-kişilik sıfır-toplamlı oyunların minimax dengesi (maxmin = minmax) bu LP dualitesinin ta kendisidir.

25.10 Kontrol Soruları

Soru 1 — Köşe çözümü ve özel kısıt

Soru: Lineer programlamada çözüm neden bir köşede bulunur, ve hangi kısıt LP’yi “doğrusal-olmayan” yapar?

Cevap: Maliyet $c^{T}x$ doğrusaldır; doğrusal bir fonksiyon bir konveks bölge (politop) üzerinde ekstremumunu daima bir köşede (vertex) alır — iç noktada değil. $x \geq 0$ eşitsizlik kısıtı LP’yi “özel/doğrusal-olmayan” yapar: çözümü kısıt bölgesinin köşesine iter (eşitlik kısıtları tek başına bir düzlem verir, eşitsizlik onu köşeli politopa böler).

Soru 2 — Simplex ve iç-nokta farkı

Soru: Simplex ve iç-nokta yöntemleri nasıl farklıdır?

Cevap: Simplex (Dantzig) uygunluk politopunun kenarları üzerinde yürür: bir köşeden başlar, maliyeti düşüren kenar boyunca sonraki köşeye gider (kenarda steepest descent). İç-nokta (Karmarkar) politopun içinden geçer: arama yönü seçer, sınıra çarpmadan durur, Newton/kalkülüsle ilerler. Simplex en-kötü üstel ama ortalama polinom; iç-nokta polinom garantili.

Soru 3 — Max-flow min-cut dualitesi

Soru: Max-flow min-cut dualitesi ne der ve neden optimali kanıtlar?

Cevap: Maksimum akış (kaynak→hedef) = minimum kesim kapasitesi. Her akış, ağı ikiye bölen herhangi bir kesimi geçmek zorundadır, dolayısıyla akış ≤ her kesim kapasitesi. Bir akış değeri 14’e ulaşıyorsa ve hiçbir kesim 14’ün altında değilse, 14 optimaldir — maks (akış) ile min (kesim) çakıştığında ikisi de kanıtlanmış olur. Bu dualitedir.

Soru 4 — Saddle yoksa minimax

Soru: İki-kişilik sıfır-toplamlı oyunda saddle point yoksa ne yapılır, minimax teoremi ne der?

Cevap: Saf strateji kilitlenmiyorsa karma strateji (mixed strategy): oyuncular satır/sütunları olasılıklarla ($p$, $q$) karıştırır; optimal nokta karışık seçeneklerin eşit olduğu yerdir. von Neumann’ın minimax teoremi: en iyi karma stratejiyle $\max_{y} \min_{x} (\text{payoff}) = \min_{x} \max_{y} (\text{payoff})$. Bu maks-min = min-maks eşitliği, iki-kişilik oyunun bir LP’ye eşdeğer olduğunu (LP dualitesi) gösterir.

25.11 Egzersizler

Köşe maliyeti. $\min 4x_{1} + x_{2} + 3x_{3}$, kısıt $x_{1} + x_{2} + x_{3} = 6$, $x \geq 0$. Üç köşeyi $(6,0,0)$, $(0,6,0)$, $(0,0,6)$ ve maliyetlerini yaz. Kazanan köşe ve minimum maliyet nedir? (Motor tanığı: maliyetler $24 / 6 / 18$; kazanan $(0,6,0)$, maliyet 6; linprog köşeyle birebir.)
Saddle point. Payoff matrisi $[[3, 1], [5, 4]]$. $y$ sütun (max), $x$ satır (min) seçer. Bir saddle point var mı? Varsa hangi (satır, sütun) ve oyunun değeri kaç? (Motor tanığı: saddle (satır 2, sütun 2) = 4 — satırında min, sütununda max; bkz. Şekil 25.6 sağ panel.)
Karma strateji. Payoff $[[1, 4], [8, 2]]$ için $y$’nin karma stratejisi $p$ (1. sütun), $1-p$ (2. sütun). $x$’in iki satır beklentisini eşitle: $p + 8(1-p) = 4p + 2(1-p)$. $p$’yi ve oyun değerini bul (Strang’ın $2/3$, $10/3$ sonucuyla karşılaştır). (Motor tanığı: $q = 2/3$, değer $10/3$; game_value_lp maximin = minimax = 3.333333 birebir.)
Dualite mantığı. Bir ağda bir akış değeri 12 buldun ve kapasitesi 12 olan bir kesim gördün. Bu, 12’nin maksimum akış olduğunu kanıtlar mı? Neden? (İpucu: akış ≤ her kesim — bir akış bir kesim kapasitesine değiyorsa, ikisi de optimaldir.)
(Ders 25 habercisi) Şimdiye kadar gradyanı tüm veriyle (full batch) hesapladık. Peki milyonlarca eğitim örneği varsa her adımda hepsini kullanmak çok pahalıysa? Rastgele küçük bir alt-küme (mini-batch) yeter mi? Bir tahmin yaz — Ders 25 “stochastic gradient descent” (konuk Prof. Sra) ile derin öğrenmenin asıl çalışan algoritmasını işliyor.

25.12 Sonraki Ders İçin Hazırlık

Ders 25: Stochastic Gradient Descent (konuk: Suvrit Sra). Derin öğrenmenin kritik algoritması: gradyanı tüm veriyle değil, rastgele bir mini-batch ile tahmin et. Hem hesaplama olarak ucuz hem de beklenen-değer (olasılıksal) problemleri çözebilir. Konuk Prof. Sra anlatır; quote’lar “— Sra, X:XX”.

Hazırlık

Ders 25 dersi konuk Prof. Suvrit Sra verir — quote’lar Strang’a değil Sra’ya atfedilecek (“— Sra, X:XX”). Bu dersteki Egzersiz 5’in sorduğu soruyu zihninde tut: milyonlarca örnekte tüm veriyle gradyan hesaplamak pahalıysa, rastgele bir mini-batch yeterli mi? Sra tam bu soruyu işleyecek; gradient descent’i (Ders 22-23) “stochastic” hale getirmek hem hesaplamayı ucuzlatır hem de beklenen-değer problemlerini çözer.

25.13 Anahtar Kavramlar (Cheat Sheet)

Kavram	Formül / Fikir	Strang (dk)
LP nedir	$\min c^{T}x$, $Ax = b$, $x \geq 0$	1m57
Köşe çözümü	doğrusal maliyet → optimum köşede (vertex)	8m15
Simplex (Dantzig)	köşeden köşeye, kenarda steepest descent	10m45
İç-nokta (Karmarkar)	feasible set içinden, Newton	13m46
Max-flow	kaynak→hedef max akış; akış ≤ kapasite	34m45
Dualite	max-flow = min-cut; akış ≤ her kesim	37m32
İki-kişilik oyun	payoff; $x$ satır (min), $y$ sütun (max)	2m41
Karma strateji / minimax	$\max_{x} \min_{y} = \min_{y} \max_{x}$ (von Neumann)	43m00

25.14 ML Bağlantıları Özeti

Dualite her yerde: SVM primal (margin) / dual (destek vektörleri); Lagrange dualitesi (Ders 18 KKT); max-flow min-cut.
Graph cut / segmentasyon: max-flow min-cut görüntü segmentasyonu ve enerji minimizasyonunda (binary labeling) standart araç.
Minimax = GAN: iki-kişilik sıfır-toplamlı oyun; üretici-ayırıcı (Ders 23), adversarial robustness, pekiştirmeli öğrenme (karma strateji = stokastik politika).
Köşe = seyreklik: doğrusal-maliyet köşe çözümü → LASSO’nun ℓ¹ seyrekliği (Ders 8/16); ℓ¹ topu köşeli.
LP ∈ P: ellipsoid (Khachiyan) polinom; iç-nokta yöntemleri büyük-ölçek LP/QP (SVM eğitimi) çözücülerinin temeli.
Paralel kurs: 6.006 Ders 16 ağırlıklı en kısa yol = bir LP dualitesi örneği (Phase 2 köprü).
Geriye köprü: Ders 18 (KKT, Lagrange), Ders 19 (maxmin/minimax — özdeğer versiyonu), Ders 21 (konvekslik, feasible set), Ders 22 (steepest descent — simplex kenarda).

Kapanış

“…that’s what duality is, that any flow has [to be ≤ the capacity of any cut].” — Strang, 37:32

Dualite optimizasyonun kalbi: her minimizasyonun bir maksimizasyon ikizi vardır; ikisi eşitse optimal kanıtlanır — max-flow = min-cut, LP primal-dual ve oyunların minimax dengesi hep aynı ilke.

--- title: "Lineer Programlama ve İki-Kişilik Oyunlar" subtitle: "Köşe çözümleri, max-flow min-cut dualitesi ve von Neumann minimax" --- ::: {.callout-note title="Bölüm bilgisi"} Bu ders optimizasyonun özel ama merkezî bir sınıfını işler: doğrusal hedef + doğrusal kısıtlar (lineer programlama). Anahtar kavram **dualite** — max-flow = min-cut ve iki-kişilik sıfır-toplamlı oyunların minimax dengesi hep aynı ilkedir. Strang'in [Ders 24 videosu](https://www.youtube.com/watch?v=feb9j65Iz4w) (≈53 dk) ve [OCW Lecture 24](https://ocw.mit.edu/courses/18-065-matrix-methods-in-data-analysis-signal-processing-and-machine-learning-spring-2018/resources/lecture-24-linear-programming-and-two-person-games/) temel alınmıştır. Okuma süresi ≈34 dk; önkoşul Ders 23 (gradient descent, momentum, kondisyon). ::: ```{python} #| echo: false """ _engine24.py — MIT 18.065 Ders 24 (LP, simplex/iç-nokta, max-flow min-cut, oyunlar/minimax) motor + viz. Setup hücresi = cat. Figür testi `from _engine24 import *`. matplotlib.use("Agg") burada YOK. """ import numpy as np import matplotlib.pyplot as plt from matplotlib.colors import LinearSegmentedColormap from itertools import combinations from scipy.optimize import linprog COL_PRIMARY = "#1f4e79"; COL_ACCENT = "#2e75b6"; COL_TEXT = "#13243a" COL_BG = "#eaf1f8"; COL_STEEL_300 = "#aac4dd"; COL_SKY_400 = "#6fa8dc" COL_WHITE = "#ffffff" COL_VEC1 = "#1f4e79"; COL_VEC2 = "#2e75b6"; COL_VEC3 = "#e67e22" COL_TEAL = "#17a2b8"; COL_PURPLE = "#6f42c1" NAVY_CMAP = LinearSegmentedColormap.from_list("strang_navy", ["#ffffff", "#cfe0f0", "#6fa8dc", "#2e75b6", "#1f4e79"]) DIVERGE = LinearSegmentedColormap.from_list("div", [COL_VEC3, "#ffffff", COL_PRIMARY]) def apply_style(ax): ax.set_facecolor(COL_WHITE); ax.grid(True, alpha=0.25, color=COL_STEEL_300, linewidth=0.8) for sp in ax.spines.values(): sp.set_color(COL_STEEL_300) ax.tick_params(colors=COL_TEXT); ax.title.set_color(COL_TEXT) ax.xaxis.label.set_color(COL_TEXT); ax.yaxis.label.set_color(COL_TEXT) return ax def heatmap(ax, M, title=None, cmap=None, annotate=True, fmt="{:.2g}", vmin=None, vmax=None, fontsize=11, text_thresh=None): M = np.asarray(M, dtype=float) if cmap is None: cmap = NAVY_CMAP if vmin is None: vmin = float(np.min(M)) if vmax is None: vmax = float(np.max(M)) if abs(vmax - vmin) < 1e-12: vmax = vmin + 1.0 ax.imshow(M, cmap=cmap, vmin=vmin, vmax=vmax, aspect="equal"); nr, nc = M.shape if text_thresh is None: text_thresh = vmin + 0.62*(vmax-vmin) if annotate and nr*nc <= 36: for i in range(nr): for j in range(nc): v = M[i, j] ax.text(j, i, fmt.format(v), ha="center", va="center", color=COL_WHITE if v >= text_thresh else COL_TEXT, fontsize=fontsize, fontweight="bold") ax.set_xticks(range(nc)); ax.set_yticks(range(nr)); ax.set_xticklabels([]); ax.set_yticklabels([]); ax.tick_params(length=0) for sp in ax.spines.values(): sp.set_color(COL_STEEL_300) if title: ax.set_title(title, color=COL_TEXT, fontsize=12, fontweight="bold") # ---- Ders 24 motoru: LP köşe, max-flow/min-cut, oyunlar ---- def lp_corner_demo(c, total): """min cᵀx, Σx = total, x ≥ 0 (Strang üçgeni). Köşeler = total·eᵢ; (köşe maliyetleri, kazanan, linprog teyidi).""" c = np.asarray(c, dtype=float); n = len(c) corners = [total * np.eye(n)[i] for i in range(n)] costs = np.array([c @ v for v in corners]) win = int(np.argmin(costs)) res = linprog(c, A_eq=np.ones((1, n)), b_eq=[total], bounds=[(0, None)] * n, method="highs") return costs, win, corners[win], res.x, float(res.fun) # -- Max-flow ağı (motor ağı; min-cut = 14, Strang'ın derste bulduğu değerle aynı sayı) -- # Düğümler: s=0, a=1, b=2, t=3. Kenarlar (u, v, kapasite): EDGES = [(0, 1, 8.0), (0, 2, 6.0), (1, 2, 2.0), (1, 3, 7.0), (2, 3, 8.0)] N_NODES = 4 def max_flow_lp(edges=None, n_nodes=N_NODES, s=0, t=3): """Max-flow'u LP olarak çöz (linprog): max Σ akış(s→·) s.t. korunum + 0 ≤ f ≤ cap. (optimal akışlar, max-flow değeri) döner.""" if edges is None: edges = EDGES ne = len(edges) # amaç: s'ten çıkan net akışı maksimize = min eksi c = np.zeros(ne) for k, (u, v, cap) in enumerate(edges): if u == s: c[k] -= 1.0 if v == s: c[k] += 1.0 # korunum: ara düğümlerde giren = çıkan A_eq = []; b_eq = [] for node in range(n_nodes): if node in (s, t): continue row = np.zeros(ne) for k, (u, v, cap) in enumerate(edges): if v == node: row[k] += 1.0 if u == node: row[k] -= 1.0 A_eq.append(row); b_eq.append(0.0) bounds = [(0.0, cap) for (_, _, cap) in edges] res = linprog(c, A_eq=np.array(A_eq), b_eq=np.array(b_eq), bounds=bounds, method="highs") return res.x, float(-res.fun) def all_cuts(edges=None, n_nodes=N_NODES, s=0, t=3): """Tüm s-t kesimleri brute-force: (kesim kümesi S, kapasite) listesi — min-cut tanığı.""" if edges is None: edges = EDGES others = [n for n in range(n_nodes) if n not in (s, t)] cuts = [] for r in range(len(others) + 1): for extra in combinations(others, r): S = {s} | set(extra) cap = sum(c for (u, v, c) in edges if u in S and v not in S) cuts.append((sorted(S), float(cap))) return cuts def min_cut(edges=None, n_nodes=N_NODES, s=0, t=3): """(min kesim kümesi, min kapasite).""" cuts = all_cuts(edges, n_nodes, s, t) k = int(np.argmin([c for _, c in cuts])) return cuts[k] # -- Oyunlar -- PAY_SADDLE = np.array([[1.0, 4.0], [2.0, 8.0]]) # ders örneği: saddle (satır2, sütun1) = 2 PAY_MIXED = np.array([[1.0, 4.0], [8.0, 2.0]]) # karma strateji örneği: değer 10/3 PAY_EGZ2 = np.array([[3.0, 1.0], [5.0, 4.0]]) # Egz2: saddle (satır2, sütun2) = 4 def find_saddle(P): """Saddle hücreleri: satırında min VE sütununda max olan (i, j, değer) listesi.""" P = np.asarray(P, dtype=float) out = [] for i in range(P.shape[0]): for j in range(P.shape[1]): if abs(P[i, j] - P[i, :].min()) < 1e-12 and abs(P[i, j] - P[:, j].max()) < 1e-12: out.append((i, j, float(P[i, j]))) return out def game_value_lp(P): """von Neumann tanığı — KLASİK KONVANSİYON: SATIR oyuncusu ALIR (maximin), SÜTUN oyuncusu ÖDER (minimax). [motor notu] Notion'un rol cümleleri gevşek; bu konvansiyon Notion'un ÜÇ sayısını (saddle 2, q=2/3, değer 10/3) birden tutarlı kılar. (maximin, minimax, satır-karması q, sütun-karması p) döner — von Neumann: maximin = minimax.""" P = np.asarray(P, dtype=float); nr, nc = P.shape # satır oyuncusu (alır, maximin): max w s.t. Pᵀq ≥ w·1, Σq = 1, q ≥ 0 res_r = linprog(c=np.r_[np.zeros(nr), -1.0], A_ub=np.hstack([-P.T, np.ones((nc, 1))]), b_ub=np.zeros(nc), A_eq=[np.r_[np.ones(nr), 0.0]], b_eq=[1.0], bounds=[(0, 1)] * nr + [(None, None)], method="highs") # sütun oyuncusu (öder, minimax): min v s.t. P·p ≤ v·1, Σp = 1, p ≥ 0 res_c = linprog(c=np.r_[np.zeros(nc), 1.0], A_ub=np.hstack([P, -np.ones((nr, 1))]), b_ub=np.zeros(nr), A_eq=[np.r_[np.ones(nc), 0.0]], b_eq=[1.0], bounds=[(0, 1)] * nc + [(None, None)], method="highs") return float(res_r.x[-1]), float(res_c.x[-1]), res_r.x[:nr], res_c.x[:nc] def mixed_2x2_row_mix(P): """2×2 karma strateji — SATIR karması q (sütun beklentilerini eşitler; Notion'un 'p + 8(1−p) = 4p + 2(1−p)' denklemi tam budur → q = 2/3, değer 10/3).""" P = np.asarray(P, dtype=float) # sütun1 beklentisi: q·P[0,0] + (1−q)·P[1,0]; sütun2: q·P[0,1] + (1−q)·P[1,1] num = P[1, 1] - P[1, 0] den = (P[0, 0] - P[1, 0]) - (P[0, 1] - P[1, 1]) q = num / den value = q * P[0, 0] + (1 - q) * P[1, 0] return float(q), float(value) ``` ## Bu Derste Ne Var? {#sec-bu-derste-d24} Bu derste beş sonuç var: 1. **LP:** $\min\ c^{T}x$, kısıt $Ax = b$ ve $x \geq 0$ (eşitsizlik kısıtı LP'yi "özel" yapar). Çözüm bir **köşe**dedir. 2. **Algoritmalar:** simplex (Dantzig, köşeden köşeye) ve iç-nokta (Karmarkar, feasible set içinden). 3. **Max-flow min-cut:** ağın maksimum akışı = minimum kesim kapasitesi — klasik dualite örneği. 4. **Dualite:** her akış ≤ her kesim; maksimum = minimum olduğunda optimal. 5. **İki-kişilik oyun:** payoff matrisi; $x$ satır seçer, $y$ sütun; saddle point yoksa **karma strateji** (mixed strategy) + minimax. > *"Linear programming is a very famous part of optimization." — Strang, 1:57* ```{mermaid} %%| label: fig-kavram-haritasi-l24 %%| fig-cap: "Ders 24 kavram haritasi — lineer programlama, max-flow min-cut dualitesi ve iki-kisilik oyunlar tek bir minimax cercevesinde bulusur." %%| echo: false flowchart TD M["LP + dualite + oyunlar"] M --> A["LP: min c^T x, Ax = b, x >= 0 (esitsizlik = ozel hal)"] M --> B["cozum bir KOSEDE (dogrusal maliyet)"] M --> C["simplex: koseden koseye ic-nokta: iceriden (Karmarkar)"] M --> D["max-flow = min-cut (dualite)"] M --> E["iki-kisilik oyun: payoff matrisi"] G["karma strateji + minimax (von Neumann)"] H["minimax = GAN / adversarial"] P["Ders 18 KKT + Ders 19 maxmin koprusu"] E --> G G --> H classDef merkez fill:#1f4e79,stroke:#13243a,stroke-width:2px,color:#ffffff; classDef dal fill:#2e75b6,stroke:#1f4e79,stroke-width:1.5px,color:#ffffff; classDef sky fill:#9dc3e6,stroke:#2e75b6,stroke-width:1.5px,color:#1f4e79; class M merkez; class A,B,C,D,E dal; class G,H,P sky; ``` @fig-kavram-haritasi-l24 dersin iskeletini gösterir: merkezdeki "LP + dualite + oyunlar" fikri, eşitsizlik kısıtının LP'yi özel kıldığı doğrusal hedeften, doğrusal maliyetin çözümü bir köşeye ittiği geometriden, simplex (köşeden köşeye) ile iç-nokta (Karmarkar) algoritma ikiliğinden, max-flow = min-cut dualitesinden ve payoff matrisli iki-kişilik oyundan dallanır; ayrı düğümlerde karma strateji + minimax (von Neumann), minimax = GAN/adversarial köprüsü ve Ders 18 (KKT) + Ders 19 (maxmin) bağı durur. ::: {.callout-tip title="Builder Notu — Her Min'in Bir Maks İkizi"} - **Dualite = optimizasyonun kalbi** — her minimizasyon probleminin bir maksimizasyon ikizi vardır; ikisi eşitse optimal kanıtlanmıştır (max-flow min-cut, primal-dual). - **LP ∈ P** — polinom zamanda çözülür (ellipsoid, Khachiyan); simplex ortalama-durumda hızlı (Spielman smoothed analysis). - **Minimax = GAN** — iki-kişilik sıfır-toplamlı oyun; üretici-ayırıcı (Ders 23) ve adversarial eğitim aynı minimax yapısı. - **Geriye köprü:** Ders 18 (KKT, Lagrange kısıtlı optimizasyon), Ders 19 (maxmin/minimax — özdeğer versiyonu), Ders 21 (konvekslik, feasible set). Paralel: 6.006 Ders 16 (ağırlıklı en kısa yol — LP dualitesi). ::: ## Lineer Programlama Nedir? {#sec-lp-nedir} Optimizasyonun en ünlü özel sınıfı: > *"Linear programming is a very famous part of optimization." — Strang, 1:57* Doğrusal bir maliyet fonksiyonunu, doğrusal kısıtlar altında minimize et: $$\min\ c^{T}x \quad \text{s.t.}\quad Ax = b, \quad x \geq 0$$ $x$ bilinmeyen ($n\times 1$), $c$ maliyet vektörü, $A$ ise $m\times n$ ($m < n$, kare-tersinir DEĞİL). Maliyet doğrusal, eşitlik kısıtları doğrusal — ama $x \geq 0$ (vektör eşitsizliği: her $x_{i} \geq 0$) işi doğrusal-olmayan, "özel" yapar. Bu iki kısıt birlikte **uygunluk kümesi** (feasible set) $K$'yi tanımlar. ::: {.callout-tip title="Builder Notu — Eşitsizlik Köşe Yaratır"} "$x \geq 0$ eşitsizliği LP'yi özel kılar" — eşitsizlik kısıtları çözümü kısıt bölgesinin sınırına/köşesine iter. ML köprüsü: negatif-olmama kısıtı her yerde (olasılıklar, ağırlıklar, kaynaklar ≥ 0); LP, kaynak tahsisi, üretim planlama ve (dual formda) SVM gibi problemlerin temelidir. ::: ## Geometri: Çözüm Bir Köşededir {#sec-geometri-d24} $n = 3$'te görselleştir. $x \geq 0$ → uzayın 1/8'i (oktant). Tek kısıt ($Ax = b$) bir düzlem; oktantla kesişimi bir **üçgen**. Örnek: $\min x_{1} + 2x_{2} + 5x_{3}$, kısıt $x_{1} + x_{2} + x_{3} = 3$, $x \geq 0$. Düzlem eksenleri $(3,0,0)$, $(0,3,0)$, $(0,0,3)$'te keser. Maliyet doğrusal olduğundan minimum bir **köşede**dir: > *"...one of these three corners is the winner." — Strang, 8:15* Üç köşenin maliyeti: $(3,0,0)\to 3$, $(0,3,0)\to 6$, $(0,0,3)\to 15$. Kazanan $x^{*} = (3,0,0)$, maliyet 3. Doğrusal fonksiyon uçlarda (köşelerde) ekstremumdadır — iç noktada değil. ```{python} #| label: fig-lp-kose #| fig-cap: "Feasible set = oktant ∩ duzlem (x₁ + x₂ + x₃ = 3) = üçgen. Doğrusal maliyet köşeye kaçar: köşe maliyetleri (3,0,0)→3, (0,3,0)→6, (0,0,3)→15; kazanan köşe (3,0,0), maliyet 3 (linprog çözümü birebir köşede)." #| fig-width: 7.5 #| fig-height: 5.5 #| code-fold: true from mpl_toolkits.mplot3d import Axes3D from mpl_toolkits.mplot3d.art3d import Poly3DCollection # Motor: köşeler ve maliyetler doğrulanmış costs, win, win_corner, x, fun = lp_corner_demo([1, 2, 5], 3) V = [(3, 0, 0), (0, 3, 0), (0, 0, 3)] fig = plt.figure(figsize=(7.5, 5.5)) ax = fig.add_subplot(projection="3d") # Üçgen yüzey (oktant ∩ düzlem x1+x2+x3=3) tri = Poly3DCollection([V], alpha=0.3, facecolor=COL_PRIMARY, edgecolor=COL_PRIMARY, linewidths=2) ax.add_collection3d(tri) # Köşe maliyet etiketleri labels = ["maliyet 3", "6", "15"] for (vx, vy, vz), lab, cst in zip(V, labels, costs): ax.scatter([vx], [vy], [vz], color=COL_PRIMARY, s=45, depthshade=False) ax.text(vx, vy, vz + 0.25, lab, color=COL_TEXT, fontsize=11, fontweight="bold", ha="center") # Kazanan köşe (3,0,0) turuncu büyük marker wx, wy, wz = win_corner ax.scatter([wx], [wy], [wz], color=COL_VEC3, s=180, depthshade=False, zorder=10, edgecolor=COL_TEXT, linewidth=1.2) # Maliyet azalma yönü -c oku (kazanan köşeye doğru kaçar) ax.quiver(1.3, 1.3, 0.4, -1.0, -0.5, -0.3, color=COL_VEC3, linewidth=2.5, arrow_length_ratio=0.18) ax.text(1.4, 1.4, 0.55, "-c yönü", color=COL_VEC3, fontsize=10, fontweight="bold") ax.set_xlabel("x₁"); ax.set_ylabel("x₂"); ax.set_zlabel("x₃") ax.set_xlim(0, 3.2); ax.set_ylim(0, 3.2); ax.set_zlim(0, 3.4) # Pane sadeleştir ax.xaxis.pane.set_alpha(0.0); ax.yaxis.pane.set_alpha(0.0); ax.zaxis.pane.set_alpha(0.0) ax.xaxis.pane.set_edgecolor(COL_STEEL_300); ax.yaxis.pane.set_edgecolor(COL_STEEL_300); ax.zaxis.pane.set_edgecolor(COL_STEEL_300) ax.tick_params(colors=COL_TEXT) ax.xaxis.label.set_color(COL_TEXT); ax.yaxis.label.set_color(COL_TEXT); ax.zaxis.label.set_color(COL_TEXT) ax.view_init(elev=22, azim=35) ax.set_title("Feasible set = oktant ∩ duzlem = ucgen; dogrusal maliyet koseye kacar: kazanan (3,0,0), maliyet 3", color=COL_TEXT, fontsize=10.5, fontweight="bold", pad=12) fig.tight_layout() plt.show() ``` @fig-lp-kose LP'nin temel teoremini görselleştirir: feasible set, oktant ($x \geq 0$) ile düzlemin ($x_{1}+x_{2}+x_{3}=3$) kesişimi olan bir üçgendir; üç köşenin maliyeti $3 / 6 / 15$ ve doğrusal maliyet köşeye kaçtığı için kazanan köşe $(3,0,0)$ (turuncu marker), minimum maliyet 3 — linprog çözümü bu köşeyle birebir aynı çıkar. ::: {.callout-tip title="Builder Notu — Doğrusal Maliyet Uçlara Kaçar"} "Doğrusal maliyet → köşede optimal" LP'nin temel teoremi: optimum daima bir köşede (vertex) bulunur. ML köprüsü: bu, LASSO'nun (ℓ¹ regülarizasyon, Ders 8/16) neden seyrek çözüm verdiğini açıklar — ℓ¹ topu köşelidir, optimum köşeye (çok sıfırlı) düşer. Köşe = seyreklik geometrisi. ::: ## Algoritmalar: Simplex ve İç-Nokta {#sec-algoritmalar} Köşeyi bulmak yeter — ama büyük $m, n$'de **üstel** sayıda köşe var, hepsini sayamayız. İki algoritma ailesi: **Simplex (Dantzig):** bir köşeden başla, maliyeti düşüren bir kenar boyunca yürü, sonraki köşeye var, tekrarla — kenarlar üzerinde steepest descent. > *"...the simplex method, which finds a corner." — Strang, 10:45* **İç-nokta (interior point, Karmarkar):** kenarlardan değil, uygunluk kümesinin **içinden** geç; bir arama yönü seç, sınıra çarpmadan dur, Newton/kalkülüsle minimize et. > *"...interior point method." — Strang, 13:46* Karmarkar'ın 1984'teki yöntemi (New York Times'a çıkacak kadar ses getirdi) iç-nokta fikrini popülerleştirdi. Karmaşıklık: simplex en-kötü durumda üstel ama **ortalama-durumda polinom** (Spielman smoothed analysis); ayrıca LP'nin **P** sınıfında olduğu kanıtlandı (ellipsoid yöntemi, Khachiyan — ünlü Rus sonucu). ```{python} #| label: fig-simplex-ic-nokta #| fig-cap: "İki strateji aynı köşeye varır. Şematik politopun kenarı boyunca simplex (turuncu oklar) köşeden köşeye sıçrar — Dantzig'in yöntemi. İç-nokta yolu (navy) ise politopun içinden kıvrılarak aynı optimum köşeye (teal yıldız) yaklaşır — Karmarkar'ın 1984 yaklaşımı. Aynı çözüm, iki ayrı geometri." #| fig-width: 7 #| fig-height: 4.6 #| code-fold: true fig, ax = plt.subplots(figsize=(7, 4.6)) # --- Şematik politop (kapalı çokgen) --- verts = [(0, 0), (4, 0), (5.5, 2), (4.5, 4.5), (2, 5), (0, 3)] poly = plt.Polygon(verts, closed=True, facecolor=COL_ACCENT, alpha=0.2, edgecolor=COL_PRIMARY, linewidth=1.8, zorder=2) ax.add_patch(poly) # --- Simplex yolu: kenarda köşeden köşeye (turuncu oklar) --- simplex_path = [(0, 0), (4, 0), (5.5, 2), (4.5, 4.5)] for (x0, y0), (x1, y1) in zip(simplex_path[:-1], simplex_path[1:]): ax.annotate("", xy=(x1, y1), xytext=(x0, y0), arrowprops=dict(arrowstyle="-|>", color=COL_VEC3, lw=2.4, shrinkA=4, shrinkB=4), zorder=5) for (x, y) in simplex_path: ax.plot(x, y, "o", color=COL_VEC3, markersize=7, zorder=6) ax.plot([], [], "-", color=COL_VEC3, lw=2.4, marker="o", label="simplex: kenarda köşeden köşeye") # --- İç-nokta yolu: içeriden kıvrılan çizgi (navy) --- interior_path = np.array([(1, 1), (2.5, 2), (3.6, 3.2), (4.3, 4.2)]) ax.plot(interior_path[:, 0], interior_path[:, 1], "-o", color=COL_PRIMARY, lw=2.2, markersize=6, zorder=4, label="iç-nokta: içeriden (Karmarkar)") # --- Optimal köşe (teal yıldız) --- ax.plot(4.5, 4.5, "*", color=COL_TEAL, markersize=22, markeredgecolor=COL_PRIMARY, markeredgewidth=1.2, zorder=7) apply_style(ax) ax.set_xlim(-0.6, 6.2); ax.set_ylim(-0.6, 5.6) ax.set_aspect("equal") ax.set_xticks([]); ax.set_yticks([]) for sp in ax.spines.values(): sp.set_visible(False) ax.grid(False) ax.legend(loc="lower right", fontsize=9, framealpha=0.92) ax.set_title("İki strateji aynı köşeye: simplex kenarda yürür (Dantzig),\niç-nokta içeriden geçer (1984, NYT)", color=COL_PRIMARY, fontsize=11.5, fontweight="bold") fig.tight_layout() plt.show() ``` @fig-simplex-ic-nokta iki algoritma stratejisini aynı politopta karşılaştırır: simplex (turuncu oklar) feasible kümenin kenarı boyunca köşeden köşeye sıçrar (Dantzig), iç-nokta yolu (navy) ise politopun içinden kıvrılarak aynı optimum köşeye (teal yıldız) yaklaşır (Karmarkar, 1984) — aynı çözüm, iki ayrı geometri. ::: {.callout-tip title="Builder Notu — Kenardan mı İçinden mi"} Simplex (kenar) vs iç-nokta (iç) ikiliği, optimizasyonun iki büyük stratejisini temsil eder. ML köprüsü: simplex'in "kenarda steepest descent"i, gradient descent'in (Ders 22) kısıtlı versiyonu; iç-nokta yöntemleri Newton'ı (Ders 21) kısıt bölgesi içinde kullanır. Modern büyük-ölçek LP/QP çözücüleri (SVM eğitimi dahil) iç-nokta tabanlıdır. ::: ## Max-Flow Problemi {#sec-max-flow} LP'nin en güzel örneği: bir ağda kaynaktan (source) hedefe (sink) **maksimum akış** gönder. Her kenarın bir **kapasitesi** var; o kenardaki akış kapasiteyi aşamaz: $$\max\ (\text{sink akisi}) \quad \text{s.t.}\quad 0 \leq (\text{kenar akisi}) \leq (\text{kapasite})$$ Bu bir tamsayı (integer) LP'dir ama dikkat çekici bir özelliği var: kesirli akışa izin versen bile **optimal akış tamsayı** çıkar — yani tamsayı kısıtını "güvenle gevşetebilirsin" (LP rahatlatması), simplex/iç-nokta uygulayabilirsin. Bu, max-flow'u verimli çözülebilir kılar. @fig-maxflow motor ağında max-flow = min-cut = 14 sonucunu çizer; aşağıda dualite bölümünde optimal akışların tamsayı çıktığını ve kesim kümelerinin akışı nasıl sınırladığını ayrıntılandıracağız. ::: {.callout-tip title="Builder Notu — Tamsayı Bedava Çıkar"} Max-flow'un "LP optimumu tamsayı çıkar" özelliği (tümleşik-modülerlik, total unimodularity) nadir ve değerlidir: genelde tamsayı programlama NP-zordur, ama max-flow polinomdur. ML köprüsü: graf-kesim (graph cut) görüntü segmentasyonu, ikili etiketleme (binary labeling) ve enerji minimizasyonu max-flow'a indirgenir — bilgisayarlı görüde standart araç. ::: ## Dualite: Max-Flow = Min-Cut {#sec-dualite} Bir akışın en fazla ne kadar olabileceğini nasıl sınırlarız? **Kesim** (cut) ile: ağı kaynak-tarafı ve hedef-tarafı düğümlere ayır; tüm akış bu kesimi geçmek zorunda. Kesimin kapasitesi = onu geçen kenarların toplamı. Her akış ≤ her kesim kapasitesi. > *"...that's what duality is, that any flow has [to be ≤ the capacity of any cut]." — Strang, 37:32* Maksimum akış ile minimum kesim **çakıştığında** optimal kanıtlanır: > *"The maximum flow turned out to be 14[, and the minimum cut turned out to be 14]." — Strang, 34:45* $$\max\ \text{flow} = \min\ \text{cut}$$ İşte dualite: bir minimizasyon (en küçük kesim) ile bir maksimizasyon (en büyük akış) aynı sayıya varır. Akış 14'ü geçebiliyorsam ve hiçbir kesim 14'ün altında değilse, 14 optimaldir. Büyük ağda min-cut görünmez ama hızlı bulunabilir. ```{python} #| label: fig-maxflow #| fig-cap: "[motor ağı] Max-flow = min-cut = 14: optimal akışlar TAMSAYI [8, 6, 1, 7, 7], kesim {s} en dar boğaz (Strang derste de 14 bulur). Her kenarda \"akış/kapasite\" etiketi; turuncu kesik eğri {s} kesimini ayırır." #| fig-width: 8.5 #| fig-height: 4.6 #| code-fold: true # --- Max-flow min-cut: motor ağı (s,a,b,t), LP çözümü flows=[8,6,1,7,7], değer=14 --- import networkx as nx flows, mf = max_flow_lp() mc = min_cut() fig, ax = plt.subplots(figsize=(8.5, 4.6)) G = nx.DiGraph() pos = {0: (0, 0.5), 1: (1, 1), 2: (1, 0), 3: (2, 0.5)} labels = {0: "s", 1: "a", 2: "b", 3: "t"} for (u, v, cap) in EDGES: G.add_edge(u, v) nx.draw_networkx_nodes(G, pos, node_color=COL_PRIMARY, node_size=1400, ax=ax) nx.draw_networkx_labels(G, pos, labels=labels, font_color=COL_WHITE, font_size=15, font_weight="bold", ax=ax) nx.draw_networkx_edges(G, pos, edge_color=COL_ACCENT, width=2.2, arrowsize=22, node_size=1400, ax=ax, connectionstyle="arc3,rad=0.0") edge_labels = {(u, v): "{:.0f}/{:.0f}".format(flows[k], cap) for k, (u, v, cap) in enumerate(EDGES)} nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_color=COL_TEXT, font_size=11, font_weight="bold", label_pos=0.5, bbox=dict(boxstyle="round,pad=0.15", fc=COL_BG, ec=COL_STEEL_300, alpha=0.95), ax=ax) # min-cut {s} ayırıcı kavisli kesik çizgi (x ~ 0.5) yy = np.linspace(-0.05, 1.05, 60) xx = 0.5 + 0.10 * np.sin((yy - 0.5) * np.pi) ax.plot(xx, yy, color=COL_VEC3, lw=2.5, ls="--", zorder=1) ax.text(0.5, 1.18, "min-cut = {:.0f}".format(mc[1]), color=COL_VEC3, fontsize=12, fontweight="bold", ha="center") ax.set_title( "[motor agi] Max-flow = min-cut = {:.0f}: optimal akislar TAMSAYI {}\n" "(Strang derste de 14 bulur)".format(mf, [int(round(x)) for x in flows]), color=COL_TEXT, fontsize=12, fontweight="bold", ) ax.set_xlim(-0.35, 2.35); ax.set_ylim(-0.2, 1.4) ax.axis("off") plt.show() ``` @fig-maxflow dualiteyi somut bir ağda gösterir: kaynak $s$'ten hedef $t$'ye giden LP-optimal akışlar tamsayı $[8, 6, 1, 7, 7]$ çıkar, her kenarda "akış/kapasite" etiketi durur, turuncu kesik eğri $\{s\}$ kesimini ayırır ve max-flow = min-cut = 14. Bu motor ağıdır — Strang'ın derste çizdiği ağ farklı olabilir, ama o da aynı 14 değerine varır; dualite mesajı birebir aynıdır. ```{python} #| label: fig-dualite-sinir #| fig-cap: "Dualite görsel: HER kesim >= akış (14); minimum kesim akışa DEĞİYOR -> 14 optimal KANITLANDI" #| fig-width: 7 #| fig-height: 4.2 #| code-fold: true cuts = all_cuts() labels = ["{s}", "{s,a}", "{s,b}", "{s,a,b}"] caps = [cap for _, cap in cuts] max_flow = max_flow_lp()[1] fig, ax = plt.subplots(figsize=(7, 4.2)) apply_style(ax) min_idx = int(np.argmin(caps)) colors = [COL_PRIMARY if i == min_idx else COL_VEC2 for i in range(len(caps))] x = np.arange(len(caps)) bars = ax.bar(x, caps, color=colors, edgecolor=COL_TEXT, linewidth=0.8, width=0.6, zorder=3) for i, (b, cap) in enumerate(zip(bars, caps)): ax.text(b.get_x() + b.get_width() / 2, cap + 0.25, f"{cap:.0f}", ha="center", va="bottom", color=COL_TEXT, fontsize=11, fontweight="bold") ax.text(bars[min_idx].get_x() + bars[min_idx].get_width() / 2, caps[min_idx] / 2, "min-cut", ha="center", va="center", color=COL_WHITE, fontsize=11, fontweight="bold", rotation=90) ax.axhline(max_flow, color=COL_VEC3, linewidth=2.2, linestyle="--", zorder=4) ax.text(len(caps) - 0.5, max_flow + 0.15, f"max-flow = {max_flow:.0f}", ha="right", va="bottom", color=COL_VEC3, fontsize=11, fontweight="bold") ax.set_xticks(x); ax.set_xticklabels(labels) ax.set_xlabel("Kesim kümesi S"); ax.set_ylabel("Kesim kapasitesi") ax.set_ylim(0, max(caps) + 2.5) ax.set_title("Dualite görsel: HER kesim >= akış (14); minimum kesim akışa DEĞİYOR -> 14 optimal KANITLANDI", fontsize=10.5, fontweight="bold") plt.show() ``` @fig-dualite-sinir dualitenin kanıt mantığını çubuklarla gösterir: dört s-t kesiminin kapasiteleri $\{s\}\to 14$, $\{s,a\}\to 15$, $\{s,b\}\to 16$, $\{s,a,b\}\to 15$; hiçbir kesim akışın (yatay turuncu çizgi, 14) altına inmez ve minimum kesim ($\{s\}$, navy çubuk) akışa tam değer — bu yüzden 14 hem maksimum akış hem minimum kesimdir, optimal kanıtlanmıştır. ::: {.callout-tip title="Builder Notu — En Dar Boğaz Kanıttır"} Max-flow min-cut, dualitenin en görsel örneği: "ne kadar gönderebilirim" (primal, maks) = "en dar boğaz" (dual, min). ML köprüsü: dualite optimizasyonun her yerinde — SVM'nin primal (margin) ve dual (destek vektörleri) formları, Lagrange dualitesi (Ders 18 KKT). 6.006 Ders 16'nın ağırlıklı en kısa yol problemi de bir LP dualitesi örneğidir (Phase 2 paralel ders köprüsü). ::: ## İki-Kişilik Sıfır-Toplamlı Oyunlar {#sec-oyunlar} Aynı dualite oyun teorisinde de var: > *"...two-person games..." — Strang, 2:41* İki oyuncu $x$ ve $y$, bir **payoff (ödeme) matrisi** üzerinde. $x$ bir **satır** seçer, $y$ bir **sütun**. Ödeme $x$'ten $y$'ye akar — sıfır-toplamlı ($x$'in ödediği $y$'ye gider, üçüncü taraf yok). $x$ **minimize** eder (ödeyen), $y$ **maksimize** eder (alan) — tıpkı LP'nin primal/dual'i gibi. Basit örnek (payoff $[[1, 4], [2, 8]]$): $y$ büyük sayı ister → 2. sütun; $x$ küçük ister → 1. satır; sonuç 2'de kilitlenir. Bu bir **saddle point**: $y$'nin sütununda min, $x$'in satırında max. ```{python} #| label: fig-saddle-oyun #| fig-cap: "Saddle point: satırında min VE sütununda max — saf strateji kilitlenir (find_saddle taraması). Sol [[1,4],[2,8]]: saddle = 2; sağ Egz2 [[3,1],[5,4]]: saddle = 4." #| fig-width: 9 #| fig-height: 3.8 #| code-fold: true fig, (axL, axR) = plt.subplots(1, 2, figsize=(9, 3.8)) # Sol: PAY_SADDLE [[1,4],[2,8]] -> saddle (satır2=indeks1, sütun1=indeks0) = 2 heatmap(axL, PAY_SADDLE, fmt="{:.0f}") i, j = 1, 0 axL.add_patch(plt.Rectangle((j - 0.5, i - 0.5), 1, 1, fill=False, edgecolor=COL_VEC3, lw=3)) axL.text(j, i + 0.62, "satırında MIN,\nsütununda MAX", ha="center", va="top", color=COL_VEC3, fontsize=8.5, fontweight="bold") axL.set_title("[[1,4],[2,8]]: saddle = 2", color=COL_TEXT, fontsize=11.5, fontweight="bold") # Sağ: PAY_EGZ2 [[3,1],[5,4]] -> saddle (satır2=indeks1, sütun2=indeks1) = 4 heatmap(axR, PAY_EGZ2, fmt="{:.0f}") i2, j2 = 1, 1 axR.add_patch(plt.Rectangle((j2 - 0.5, i2 - 0.5), 1, 1, fill=False, edgecolor=COL_VEC3, lw=3)) axR.set_title("Egz2 [[3,1],[5,4]]: saddle = 4", color=COL_TEXT, fontsize=11.5, fontweight="bold") fig.suptitle("Saddle point: satırında min VE sütununda max — saf strateji kilitlenir (find_saddle taraması)", color=COL_TEXT, fontsize=10.5, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.94]) plt.show() ``` @fig-saddle-oyun saddle point'i iki payoff matrisinde gösterir: solda $[[1,4],[2,8]]$ için saddle hücresi 2 (turuncu çerçeve — satırında min, sütununda max), sağda Egzersiz 2'nin $[[3,1],[5,4]]$ matrisinde saddle 4; `find_saddle` taraması bu hücreleri otomatik bulur. *[motor notu]: Rol adlandırması transkriptte gevşek; Notion'un "$x$ küçük ister → 1. satır, sonuç 2" akışı kendi sayılarıyla birebir tutarlı değil ((1. satır, 2. sütun) = 4 olurdu). Sayılar (saddle 2, $q = 2/3$, değer $10/3$) klasik SATIR-ALIR (maximin) / SÜTUN-ÖDER (minimax) konvansiyonunda motor-tanıklıdır: saddle = (satır 2, sütun 1) = 2 satırında min ve sütununda max'tır (`find_saddle`), ve `game_value_lp` iki yönden $10/3 = 10/3$ verir.* ::: {.callout-tip title="Builder Notu — Oyunun Primal'i Dual'i"} "$x$ minimize (satır), $y$ maksimize (sütun)" oyun yapısı LP primal-dual'in birebir karşılığı. ML köprüsü: GAN'lar (Ders 23) tam iki-kişilik oyun — üretici (generator) kayıbı minimize, ayırıcı (discriminator) maksimize; eğitim bu oyunun dengesini (Nash/saddle) arar. Adversarial robustness de min-maks bir oyun. ::: ## Karma Strateji ve Minimax {#sec-karma-strateji} Her matriste saddle point yoktur. Payoff $[[1, 4], [8, 2]]$: $y$ 8'i sever (2. sütun), ama $x$ 2. satırı seçince $y$ 4'ü görüp 1. sütuna kayar — saf strateji kilitlenmez. Çözüm **karma strateji** (mixed strategy): > *"Mixed strategy..." — Strang, 43:00* $y$ sütunları $p$ ve $1-p$ olasılıkla, $x$ satırları $q$ ve $1-q$ ile karıştırır. Optimal nokta, karışık seçeneklerin **eşit** olduğu yerdir (rakip avantaj bulamasın). Örnekte $9p = 6 \to p = 2/3$; oyunun değeri $10/3$. Bu, **minimax teoremi** (von Neumann): en iyi karma stratejiyle $$\max_{y}\ \min_{x}\ (\text{payoff}) = \min_{x}\ \max_{y}\ (\text{payoff})$$ Maks-min = min-maks. Bu eşitlik tam olarak LP dualitesidir — iki-kişilik sıfır-toplamlı oyun bir LP'ye eşdeğerdir. ```{python} #| label: fig-karma-strateji #| fig-cap: "Karma strateji: iki sütun beklentisi q = 2/3 te eşitlenir -> oyun değeri 10/3 (LP birebir teyit)" #| fig-width: 7.5 #| fig-height: 4.6 #| code-fold: true fig, ax = plt.subplots(figsize=(7.5, 4.6)) qs = np.linspace(0, 1, 200) c1 = qs * 1 + (1 - qs) * 8 # sütun 1 beklentisi c2 = qs * 4 + (1 - qs) * 2 # sütun 2 beklentisi ax.plot(qs, c1, color=COL_PRIMARY, lw=2, label="sütun 1 beklentisi") ax.plot(qs, c2, color=COL_VEC3, lw=2, label="sütun 2 beklentisi") env = np.minimum(c1, c2) ax.plot(qs, env, color=COL_TEAL, lw=3, alpha=0.55, label="satır oyuncusunun garantisi") q_star, val_star = 2 / 3, 10 / 3 ax.scatter([q_star], [val_star], s=160, marker="*", color=COL_TEAL, edgecolors=COL_TEXT, linewidths=0.8, zorder=6) ax.annotate("q = 2/3, değer = 10/3 (9q = 6)", xy=(q_star, val_star), xytext=(0.30, 5.4), color=COL_TEXT, fontsize=10, fontweight="bold", arrowprops=dict(arrowstyle="->", color=COL_TEXT, lw=1.2)) ax.text(0.02, 0.96, "LP iki yönden: maximin = minimax = 3.3333\n(von Neumann, game_value_lp)", transform=ax.transAxes, va="top", ha="left", fontsize=9.5, bbox=dict(boxstyle="round,pad=0.4", facecolor=COL_BG, edgecolor=COL_ACCENT, linewidth=1.0)) apply_style(ax) ax.set_xlabel("q (satır 1 olasılığı)") ax.set_ylabel("beklenen ödeme") ax.legend(loc="upper right") ax.set_title("Karma strateji: iki sütun beklentisi q = 2/3 te eşitlenir -> oyun değeri 10/3 (LP birebir teyit)", color=COL_TEXT, fontsize=11, fontweight="bold") plt.show() ``` @fig-karma-strateji karma stratejiyi klasik oyun grafiğiyle gösterir: $[[1,4],[8,2]]$ için iki sütun beklentisi $q\cdot 1 + (1-q)\cdot 8$ (navy) ve $q\cdot 4 + (1-q)\cdot 2$ (turuncu) $q = 2/3$ noktasında eşitlenir; satır oyuncusunun garantisi (alt zarf, teal) tam orada maksimum olur ve oyun değeri $10/3$ (teal yıldız) — $9q = 6$ denkleminin çözümü. LP iki yönden maximin = minimax = 3.3333 verir (`game_value_lp`), von Neumann minimaxı birebir teyitlenir. ::: {.callout-tip title="Builder Notu — von Neumann'ın Dengesi"} von Neumann'ın minimax teoremi (maks-min = min-maks) oyun teorisinin kurucu sonucu ve LP dualitesinin ikizidir. ML köprüsü: bu, Ders 19'un eigenvalue maxmin'inin (Courant-Fischer) oyun-teorik kuzenidir; GAN eğitimi, robust optimizasyon ve adversarial örnekler hep bu min-maks dengesini çözmeye çalışır. Karma strateji = olasılıksal politika (stochastic policy), pekiştirmeli öğrenmenin temeli. ::: ## Bu Dersin Özeti {#sec-ozet-d24} - **LP:** $\min c^{T}x$, kısıt $Ax = b$, $x \geq 0$. Eşitsizlik kısıtı LP'yi özel yapar; feasible set $K$. - **Köşe çözümü:** doğrusal maliyet → optimum bir köşede (vertex). Örnek $\min x_{1}+2x_{2}+5x_{3}$, $x_{1}+x_{2}+x_{3}=3$ → $(3,0,0)$, maliyet 3. - **Algoritmalar:** simplex (Dantzig, köşeden köşeye) + iç-nokta (Karmarkar, içeriden). LP ∈ P (ellipsoid). - **Max-flow min-cut:** kaynak→hedef maksimum akış = minimum kesim kapasitesi; tamsayı optimum (gevşetilebilir). - **Dualite:** her akış ≤ her kesim; maks = min optimal. Min (kesim) = maks (akış). - **İki-kişilik oyun:** payoff matrisi; $x$ satır (min), $y$ sütun (max). Saddle yoksa karma strateji. - **Minimax (von Neumann):** $\max_{x} \min_{y} = \min_{y} \max_{x}$; iki-kişilik sıfır-toplamlı oyun = LP dualitesi. ::: {.callout-important title="Tek Bir Cümle"} Lineer programlama doğrusal bir hedefi ($c^{T}x$) doğrusal kısıtlar ($Ax=b$, $x\geq 0$) altında bir köşede minimize eder; dualite (max-flow = min-cut, primal-dual) optimali kanıtlar ve iki-kişilik sıfır-toplamlı oyunların minimax dengesi (maxmin = minmax) bu LP dualitesinin ta kendisidir. ::: ## Kontrol Soruları {#sec-sorular-d24} ::: {.callout-note collapse="true" title="Soru 1 — Köşe çözümü ve özel kısıt"} **Soru:** Lineer programlamada çözüm neden bir köşede bulunur, ve hangi kısıt LP'yi "doğrusal-olmayan" yapar? **Cevap:** Maliyet $c^{T}x$ doğrusaldır; doğrusal bir fonksiyon bir konveks bölge (politop) üzerinde ekstremumunu daima bir **köşede** (vertex) alır — iç noktada değil. $x \geq 0$ eşitsizlik kısıtı LP'yi "özel/doğrusal-olmayan" yapar: çözümü kısıt bölgesinin köşesine iter (eşitlik kısıtları tek başına bir düzlem verir, eşitsizlik onu köşeli politopa böler). ::: ::: {.callout-note collapse="true" title="Soru 2 — Simplex ve iç-nokta farkı"} **Soru:** Simplex ve iç-nokta yöntemleri nasıl farklıdır? **Cevap:** **Simplex** (Dantzig) uygunluk politopunun **kenarları** üzerinde yürür: bir köşeden başlar, maliyeti düşüren kenar boyunca sonraki köşeye gider (kenarda steepest descent). **İç-nokta** (Karmarkar) politopun **içinden** geçer: arama yönü seçer, sınıra çarpmadan durur, Newton/kalkülüsle ilerler. Simplex en-kötü üstel ama ortalama polinom; iç-nokta polinom garantili. ::: ::: {.callout-note collapse="true" title="Soru 3 — Max-flow min-cut dualitesi"} **Soru:** Max-flow min-cut dualitesi ne der ve neden optimali kanıtlar? **Cevap:** Maksimum akış (kaynak→hedef) = minimum kesim kapasitesi. Her akış, ağı ikiye bölen herhangi bir kesimi geçmek zorundadır, dolayısıyla **akış ≤ her kesim kapasitesi**. Bir akış değeri 14'e ulaşıyorsa ve hiçbir kesim 14'ün altında değilse, 14 optimaldir — maks (akış) ile min (kesim) çakıştığında ikisi de kanıtlanmış olur. Bu dualitedir. ::: ::: {.callout-note collapse="true" title="Soru 4 — Saddle yoksa minimax"} **Soru:** İki-kişilik sıfır-toplamlı oyunda saddle point yoksa ne yapılır, minimax teoremi ne der? **Cevap:** Saf strateji kilitlenmiyorsa **karma strateji** (mixed strategy): oyuncular satır/sütunları olasılıklarla ($p$, $q$) karıştırır; optimal nokta karışık seçeneklerin eşit olduğu yerdir. von Neumann'ın **minimax teoremi**: en iyi karma stratejiyle $\max_{y} \min_{x} (\text{payoff}) = \min_{x} \max_{y} (\text{payoff})$. Bu maks-min = min-maks eşitliği, iki-kişilik oyunun bir LP'ye eşdeğer olduğunu (LP dualitesi) gösterir. ::: ## Egzersizler {#sec-egzersizler-d24} 1. **Köşe maliyeti.** $\min 4x_{1} + x_{2} + 3x_{3}$, kısıt $x_{1} + x_{2} + x_{3} = 6$, $x \geq 0$. Üç köşeyi $(6,0,0)$, $(0,6,0)$, $(0,0,6)$ ve maliyetlerini yaz. Kazanan köşe ve minimum maliyet nedir? (Motor tanığı: maliyetler $24 / 6 / 18$; kazanan $(0,6,0)$, maliyet 6; linprog köşeyle birebir.) 2. **Saddle point.** Payoff matrisi $[[3, 1], [5, 4]]$. $y$ sütun (max), $x$ satır (min) seçer. Bir saddle point var mı? Varsa hangi (satır, sütun) ve oyunun değeri kaç? (Motor tanığı: saddle (satır 2, sütun 2) = 4 — satırında min, sütununda max; bkz. @fig-saddle-oyun sağ panel.) 3. **Karma strateji.** Payoff $[[1, 4], [8, 2]]$ için $y$'nin karma stratejisi $p$ (1. sütun), $1-p$ (2. sütun). $x$'in iki satır beklentisini eşitle: $p + 8(1-p) = 4p + 2(1-p)$. $p$'yi ve oyun değerini bul (Strang'ın $2/3$, $10/3$ sonucuyla karşılaştır). (Motor tanığı: $q = 2/3$, değer $10/3$; `game_value_lp` maximin = minimax = 3.333333 birebir.) 4. **Dualite mantığı.** Bir ağda bir akış değeri 12 buldun ve kapasitesi 12 olan bir kesim gördün. Bu, 12'nin maksimum akış olduğunu kanıtlar mı? Neden? (İpucu: akış ≤ her kesim — bir akış bir kesim kapasitesine değiyorsa, ikisi de optimaldir.) 5. **(Ders 25 habercisi)** Şimdiye kadar gradyanı tüm veriyle (full batch) hesapladık. Peki milyonlarca eğitim örneği varsa her adımda hepsini kullanmak çok pahalıysa? Rastgele küçük bir alt-küme (mini-batch) yeter mi? Bir tahmin yaz — Ders 25 "stochastic gradient descent" (konuk Prof. Sra) ile derin öğrenmenin asıl çalışan algoritmasını işliyor. ## Sonraki Ders İçin Hazırlık {#sec-sonraki-d24} **Ders 25: Stochastic Gradient Descent (konuk: Suvrit Sra).** Derin öğrenmenin kritik algoritması: gradyanı tüm veriyle değil, rastgele bir **mini-batch** ile tahmin et. Hem hesaplama olarak ucuz hem de beklenen-değer (olasılıksal) problemleri çözebilir. Konuk Prof. Sra anlatır; quote'lar "— Sra, X:XX". ::: {.callout-warning title="Hazırlık"} Ders 25 dersi **konuk Prof. Suvrit Sra** verir — quote'lar Strang'a değil Sra'ya atfedilecek ("— Sra, X:XX"). Bu dersteki Egzersiz 5'in sorduğu soruyu zihninde tut: milyonlarca örnekte tüm veriyle gradyan hesaplamak pahalıysa, rastgele bir mini-batch yeterli mi? Sra tam bu soruyu işleyecek; gradient descent'i (Ders 22-23) "stochastic" hale getirmek hem hesaplamayı ucuzlatır hem de beklenen-değer problemlerini çözer. ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet-d24} | Kavram | Formül / Fikir | Strang (dk) | |--------|----------------|-------------| | **LP nedir** | $\min c^{T}x$, $Ax = b$, $x \geq 0$ | 1m57 | | **Köşe çözümü** | doğrusal maliyet → optimum köşede (vertex) | 8m15 | | **Simplex (Dantzig)** | köşeden köşeye, kenarda steepest descent | 10m45 | | **İç-nokta (Karmarkar)** | feasible set içinden, Newton | 13m46 | | **Max-flow** | kaynak→hedef max akış; akış ≤ kapasite | 34m45 | | **Dualite** | max-flow = min-cut; akış ≤ her kesim | 37m32 | | **İki-kişilik oyun** | payoff; $x$ satır (min), $y$ sütun (max) | 2m41 | | **Karma strateji / minimax** | $\max_{x} \min_{y} = \min_{y} \max_{x}$ (von Neumann) | 43m00 | ## ML Bağlantıları Özeti {#sec-ml-baglantilar-d24} - **Dualite her yerde:** SVM primal (margin) / dual (destek vektörleri); Lagrange dualitesi (Ders 18 KKT); max-flow min-cut. - **Graph cut / segmentasyon:** max-flow min-cut görüntü segmentasyonu ve enerji minimizasyonunda (binary labeling) standart araç. - **Minimax = GAN:** iki-kişilik sıfır-toplamlı oyun; üretici-ayırıcı (Ders 23), adversarial robustness, pekiştirmeli öğrenme (karma strateji = stokastik politika). - **Köşe = seyreklik:** doğrusal-maliyet köşe çözümü → LASSO'nun ℓ¹ seyrekliği (Ders 8/16); ℓ¹ topu köşeli. - **LP ∈ P:** ellipsoid (Khachiyan) polinom; iç-nokta yöntemleri büyük-ölçek LP/QP (SVM eğitimi) çözücülerinin temeli. - **Paralel kurs:** 6.006 Ders 16 ağırlıklı en kısa yol = bir LP dualitesi örneği (Phase 2 köprü). - **Geriye köprü:** Ders 18 (KKT, Lagrange), Ders 19 (maxmin/minimax — özdeğer versiyonu), Ders 21 (konvekslik, feasible set), Ders 22 (steepest descent — simplex kenarda). ::: {.callout-important title="Kapanış"} > *"...that's what duality is, that any flow has [to be ≤ the capacity of any cut]." — Strang, 37:32* Dualite optimizasyonun kalbi: her minimizasyonun bir maksimizasyon ikizi vardır; ikisi eşitse optimal kanıtlanır — max-flow = min-cut, LP primal-dual ve oyunların minimax dengesi hep aynı ilke. :::