Bir optimization problem'inin anatomisi
Mühendislikte kurulan sistemlerin çoğunda birinin olabildiğince büyütmek ya da küçültmek istediği bir sayı vardır. Hoca ilk derste dört alan gösteriyor:
| Alan | Ne yapılıyor | Problem |
|---|---|---|
| Machine Learning & AI | Model eğitmek = milyonlarca parametre üzerinde bir loss'u minimize etmek | $\min\ \text{loss(weights)}$ |
| Networks & Systems | Trafiği latency ve congestion en az olacak şekilde yönlendirmek | $\min\ \text{delay(flows)}$ |
| VLSI & Hardware | Cell yerleştirmek, gate boyutlamak: chip area, wirelength, power | $\min\ \text{area}\cdot\text{power}$ |
| Scheduling & Resources | Task'ları processor'lara atayıp throughput'u artırmak | $\max\ \text{throughput}$ |
Hepsinde üç şey var: seçebildiğin bir şey, ölçebildiğin bir sayı ve uyman gereken kurallar.
$x \in \mathbb{R}^n$ optimization variable'dır.
| Parça | Anlamı |
|---|---|
| Decision variable $x$ | the unknowns you get to choose: senin seçtiğin bilinmeyenler |
| Objective $f_0(x)$ | the single number you minimize: minimize ettiğin tek bir sayı |
| Constraints $f_i,\ h_j$ | the limits a solution must respect: çözümün uyması gereken sınırlar |
| Feasible set | all $x$ satisfying every constraint: bütün constraint'leri birlikte sağlayan $x$'ler |
| Optimal point $x^*$ / optimal value $p^*$ | en iyi feasible $x$ ve onun objective değeri: $p^* = f_0(x^*)$ |
Maximizing $f$ is the same as minimizing $-f$, bu yüzden "minimize" yazmak hiçbir şey kaybettirmez.
- $\max f(x)$ → $\min\, -f(x)$. Sonunda asıl değer $= -p^*$.
- $g(x) \le b$ → $g(x) - b \le 0$.
- $g(x) \ge b$ → $b - g(x) \le 0$ (iki tarafı da $-1$ ile çarpınca yön döner).
- $x_1 \ge 0$ gibi sign restriction'lar da constraint'tir: $-x_1 \le 0$.
- $g(x) = b$ → $h(x) = g(x) - b = 0$.
Boyd'un kitabı aynı şeyi $f_i(x) \le b_i$ diye yazar: $b_i$'yi sola atınca slayttaki $f_i(x) \le 0$ biçimi çıkar.
Lab 01 (ve slayt 8) şu problemi kullanıyor: $\max\ 3x_1 + 4x_2$, $x_1 + x_2 \le 4$, $x_1 + 3x_2 \le 6$, $x_1, x_2 \ge 0$. Standard form'da:
$$\begin{aligned}\text{minimize}\quad & -3x_1 - 4x_2\\ \text{subject to}\quad & x_1 + x_2 - 4 \le 0\\ & x_1 + 3x_2 - 6 \le 0\\ & -x_1 \le 0,\quad -x_2 \le 0\end{aligned}$$Burada $n = 2$, $m = 4$, $p = 0$. 5. bölümde optimum'un $x^* = (3, 1)$ olduğunu göreceğiz. Min biçiminde $p^* = -3\cdot 3 - 4\cdot 1 = -13$; asıl (max) problemin değeri $13$.
- Max'ı min'e çevirdiysen $p^*$'nin işareti de döner. "$p^* = 13$" yazıp min biçimini kullanmak tutarsızdır.
- $\ge$ constraint'ini $\le 0$ biçimine çevirirken sadece sağ tarafı sola atmak yetmez: $x_1 + 2x_2 \ge 3$, $x_1 + 2x_2 - 3 \le 0$ değildir.
- $x^*$ bir nokta (vektör), $p^*$ bir sayıdır. "$p^* = (3,1)$" yanlış.
$x_1 + 2x_2 \ge 3$ constraint'inin $f(x) \le 0$ biçimi hangisi?
Lab 01 LP'sini ($\max\ 3x_1 + 4x_2$) yukarıdaki min biçimine çevirdin. Bu min probleminin $p^*$'si nedir?
Decision variable ve objective
- Serbestçe seçtiğin bilinmeyenlerdir. Solver'ın döndürdüğü cevap budur.
- Bir vektörde toplanır: $x = (x_1, \dots, x_n)$. $n$ çok küçük (2) ya da çok büyük (deep learning'de $10^9$) olabilir.
- Key idea: If you cannot change it, it is a parameter (data). Not a decision variable.
| Domain | Variables | Type |
|---|---|---|
| Neural net | weights & biases | continuous |
| Network routing | flow on each link | continuous |
| Path selection | use link? (0 / 1) | binary |
| VLSI placement | cell coordinates | continuous |
| Scheduling | task → slot | integer |
Winston bir ek şart koyar: decision variable'lar verilecek kararların tamamını anlatmalı. Giapetto örneğinde karar "haftada kaç soldier, kaç train üretilecek" olduğu için iki variable yeter.
Lab 01'in ilk bölümü bunu NumPy ile gösteriyor: x = np.array([3.0, 1.0]) aday bir decision vector; c, A, b ise problemin verisi (parameter). c @ x objective'i (13), A @ x constraint'lerin sol tarafını ($(4, 6)$) verir.
- Her karara tek bir reel sayı atayan bir fonksiyondur: kararın maliyeti ya da kalitesi.
- Bir cost'u (energy, error, delay) minimize ya da bir utility'yi (throughput, accuracy) maximize ederiz.
- Ölçülebilir olmalı: "make it good" bir objective değildir; "minimize mean-squared error" bir objective'tir.
- Sign convention: $\max f(x) \equiv \min\, -f(x)$, bu yüzden minimization'da standartlaşırız.
Gerçek sistemlerin çoğunun aynı anda birkaç hedefi vardır. Winston'ın örneğinde bir okul yönetimi öğrencileri iki liseye dağıtırken (1) iki okuldaki öğrenci sayısını eşitlemek, (2) ortalama yolu kısaltmak, (3) iki okulda da çeşitli bir öğrenci profili sağlamak istiyor. Tek bir objective'e inmenin iki yolu var (slayt 6):
- Ağırlıklarla birleştir: $\min\ E(v) + \lambda\cdot \text{delay}(v)$. $\lambda$'yı sen seçersin; farklı $\lambda$ farklı cevap verir.
- Birini objective olarak tut, diğerlerini constraint yap: $\min\ E(v)$ s.t. $\text{delay}(v) \le T$.
10. bölümdeki devre enerjisi modeli tam olarak ikinci yolu kullanıyor. Boyd'un data fitting örneği ise birinci yolu: objective = prediction error + $\rho \cdot$ (model complexity cezası), yani $\sum_i (a_i^T x - b_i)^2 + \rho \sum_j x_j^2$. Konunun tamamı dönemin ilerisinde.
- Kararlardan hesaplanan bir büyüklük (toplam energy, toplam delay) ayrı bir decision variable değildir; $x$'in fonksiyonudur.
- Problemde değeri verilen her şey (capacity, deadline, fiyat) parameter'dır, harfle yazılmış olsa bile ($C_j$, $T$).
- Objective'e sabit eklemek ya da objective'i pozitif bir sayıyla çarpmak $x^*$'ı değiştirmez, $p^*$'yi değiştirir. Winston bu yüzden Giapetto'da fixed cost'ları (kira, sigorta) objective'e katmaz.
Slayt 19'daki scheduler'da ($N$ task, $M$ processor, processor $j$'nin capacity'si $C_j$, task $i$'nin yükü $w_i$) hangisi decision variable?
Bir modelde objective $3x_1 + 2x_2$ iken haftalık 100 TL kira da düşmek istiyorsun: $3x_1 + 2x_2 - 100$. Ne değişir?
Constraint'ler ve feasible region
- Constraint'ler çözümün uyması gereken kurallardır. Feasible region'ı $\mathbb{R}^n$'in içinden oyarlar.
- Inequality $f_i(x) \le 0$: bir bölge / half-space (örnek: power ≤ budget).
- Equality $h_j(x) = 0$: bir yüzey (örnek: flow in = flow out).
- Feasible region: bütün constraint'leri aynı anda sağlayan noktaların kümesi.
- Bir constraint optimum'da eşitlikle sağlanıyorsa active (binding)'dir. "Önemli olan" constraint'ler bunlardır.
| Durum | Anlamı | Modelde ne var? |
|---|---|---|
| Feasible | En az bir nokta bütün constraint'leri sağlıyor | Normal durum |
| Infeasible | Hiçbir nokta sağlamıyor | Model over-constrained |
| Unbounded | Objective sonsuza kadar iyileşiyor | Bir constraint eksik |
$x = (3, 1)$ için $Ax = (3+1,\ 3+3) = (4, 6)$ ve $b = (4, 6)$. A @ x <= b iki satırda da True, $x \ge 0$ da sağlanıyor ⇒ feasible. Üstelik iki satır da eşitlikle sağlanıyor: bu noktada iki constraint de active.
$x = (2, 2)$ için $Ax = (4, 8)$: ikinci satırda $8 > 6$ ⇒ bu nokta infeasible.
"Farmer Jones must determine how many acres of corn and wheat to plant this year. An acre of wheat yields 25 bushels of wheat and requires 10 hours of labor per week. An acre of corn yields 10 bushels of corn and requires 4 hours of labor per week. All wheat can be sold at $\$4$ a bushel, and all corn can be sold at $\$3$ a bushel. Seven acres of land and 40 hours per week of labor are available. Government regulations require that at least 30 bushels of corn be produced during the current year. Let $x_1$ = number of acres of corn planted, and $x_2$ = number of acres of wheat planted. Using these decision variables, formulate an LP whose solution will tell Farmer Jones how to maximize the total revenue from wheat and corn."
"Answer these questions about Problem 1. a Is $(x_1 = 2, x_2 = 3)$ in the feasible region? b Is $(x_1 = 4, x_2 = 3)$ in the feasible region? c Is $(x_1 = 2, x_2 = 1)$ in the feasible region? d Is $(x_1 = 3, x_2 = 2)$ in the feasible region?"
İpucu 1
Variable'lar acre, fiyatlar bushel başına. Bir acre corn kaç dolar getirir? (10 bushel × 3 dolar.) Birimleri eşitle.
İpucu 2
Üç kaynak var: land (acre), labor (saat/hafta), corn alt sınırı (bushel). "At least 30 bushels" bir $\ge$ constraint'i: $10x_1 \ge 30$.
Çözümü göster
Bir acre corn $10 \cdot 3 = 30$ dolar, bir acre wheat $25 \cdot 4 = 100$ dolar getirir.
| Nokta | land ≤ 7 | labor ≤ 40 | corn ≥ 30 | Sonuç |
|---|---|---|---|---|
| a $(2, 3)$ | 5 ✓ | 38 ✓ | 20 ✗ | infeasible |
| b $(4, 3)$ | 7 ✓ | 46 ✗ | 40 ✓ | infeasible |
| c $(2, 1)$ | 3 ✓ | 18 ✓ | 20 ✗ | infeasible |
| d $(3, 2)$ | 5 ✓ | 32 ✓ | 30 ✓ | feasible |
Bir noktanın infeasible olması için tek bir constraint'i bozması yeter. (Bu modeli 4. bölümdeki sandbox'ta "Farmer Jones" preset'i olarak çizebilirsin: optimum $(3,\ 2.8)$, $z^* = 370$.)
- Bir noktanın infeasible olması ile problemin infeasible olması farklıdır. $(2, 2)$ infeasible bir nokta, ama Lab 01 problemi feasible.
- Feasible region'ın sınırsız olması problemi unbounded yapmaz. $\min\ x_1 + x_2$, $x \ge 0$: region sonsuza gidiyor ama $p^* = 0$.
- Bir constraint'in bütün terimleri aynı birimde olmalı (Winston: "otherwise one is adding apples and oranges").
- Strict inequality ($<$) kullanılmaz. $\max\ x$ s.t. $x < 1$'de $x$ 1'e istediğin kadar yaklaşır ama 1 olamaz; optimum yok. Winston Problem 5 tam bunu soruyor.
Solver "infeasible" diyor. Modelde büyük olasılıkla ne var?
Winston Group B Problem 5: "Why don't we allow an LP to have < or > constraints?" En iyi cevap hangisi?
2-D resim: polygon, contour ve vertex
- İki decision variable ($x_1, x_2$) varsa problemin tamamını çizebiliriz.
- Taralı polygon = feasible region (bütün constraint'lerin kesişimi).
- Kesikli çizgiler = objective contour'ları (level set'ler: objective'in aynı değeri aldığı noktalar).
- Contour'u iyileşme yönünde (gradient yönünde) kaydır, feasible set'ten çıkmak üzereyken dur.
- Optimum bir vertex'e düşer. Simplex'in neden çalıştığının ön izlemesi bu (Week 3).
Linear objective $c^T x$'in gradient'i her yerde $c$'dir. Lab 01 LP'sinde $c = (3, 4)$: contour'lar $3x_1 + 4x_2 = z$ doğruları, $c$'ye diktir ve $c$ yönünde kaydıkça $z$ artar.
Aşağıdaki sandbox, girdiğin constraint'lerden feasible region'ı gerçekten hesaplıyor (her half-plane ile büyük bir kareyi kırparak), vertex'leri buluyor ve objective'i her vertex'te değerlendiriyor. Slider contour'u ($c^T x = z$) kaydırır.
Önce tahmin et: Lab 01 LP'sinde objective'i $3x_1 + 4x_2$'den $x_1 + x_2$'ye değiştirirsen optimum hâlâ tek bir vertex mi olur?
Feasible region en az bir vertex içeriyorsa ve LP'nin sonlu bir optimum'u varsa, en az bir optimum bir vertex'tedir. $x \ge 0$ sign restriction'ları varsa region'ın vertex'i hep olur (boş değilse). Region bounded ise (Lab 01'deki gibi kapalı bir polygon) bütün vertex'leri bulup objective'i her birinde hesaplamak yeter. Region bir yönde sonsuza gidiyorsa önce objective'in o yönde sınırsız büyümediğini kontrol et; vertex tablosu tek başına unbounded durumu göstermez. Lab 01'in kodu bounded durumu çözüyor:
objective = lambda v: 3*v[0] + 4*v[1]
best = max(verts, key=objective) # verts = [(0,0), (4,0), (3,1), (0,2)]| Vertex | $3x_1 + 4x_2$ | Active constraint'ler |
|---|---|---|
| $(0, 0)$ | 0 | $x_1 \ge 0$, $x_2 \ge 0$ |
| $(4, 0)$ | 12 | $x_1 + x_2 \le 4$, $x_2 \ge 0$ |
| $(3, 1)$ | 13 | $x_1 + x_2 \le 4$, $x_1 + 3x_2 \le 6$ |
| $(0, 2)$ | 8 | $x_1 + 3x_2 \le 6$, $x_1 \ge 0$ |
"Re-solve the LP. Change the objective to maximize $x_1 + 2x_2$ over the same feasible region. Evaluate it at each vertex (reuse verts) to find the new optimum. Which constraint(s) are active at the solution?"
İpucu 1
Feasible region değişmedi, sadece objective değişti. Vertex'ler aynı: $(0,0)$, $(4,0)$, $(3,1)$, $(0,2)$.
İpucu 2
En iyi vertex'i bulduktan sonra her constraint'in sol tarafını o noktada hesapla; sağ tarafa eşit olanlar active.
Çözümü göster
| Vertex | $x_1 + 2x_2$ |
|---|---|
| $(0, 0)$ | 0 |
| $(4, 0)$ | 4 |
| $(3, 1)$ | 5 |
| $(0, 2)$ | 4 |
Optimum $x^* = (3, 1)$, $z^* = 5$. Active constraint'ler: $x_1 + x_2 \le 4$ ($3 + 1 = 4$) ve $x_1 + 3x_2 \le 6$ ($3 + 3 = 6$). $x_1 \ge 0$ ve $x_2 \ge 0$ active değil (ikisi de pozitif).
objective = lambda v: v[0] + 2*v[1]
best = max(verts, key=objective) # (3, 1) -> 5Neden optimum yer değiştirmedi? Yeni contour'ların eğimi ($-\tfrac12$) iki active constraint'in eğimleri ($-1$ ve $-\tfrac13$) arasında kalıyor; contour hâlâ en son $(3,1)$'e değiyor. Sandbox'ta "Lab01 Exercise 1" preset'iyle kontrol et.
- Vertex kontrolü LP'ye özgü. Nonlinear bir objective'in optimum'u region'ın içinde ya da bir kenarın ortasında olabilir.
- Contour bir kenara paralelse o kenarın tamamı optimal'dir (alternative optima). Vertex'lerden biri yine optimum ama tek değil. Week 3'teki bandwidth LP'si de böyle: $f_1 = 7$, $f_2 + f_3 = 9$ ve $f_3 \in [1, 3]$ olan her nokta optimal; slayttaki $(7, 8, 1)$ bunlardan sadece biri.
- Min probleminde contour'u $c$ yönünde değil, $-c$ yönünde kaydırırsın.
Aynı region'da $\max\ x_1 + x_2$. Optimum nedir?
$\min\ c^T x$ probleminde contour'u hangi yöne kaydırırsın?
Local ve global minimum
- Global minimum: $f(x^*) \le f(x)$ for ALL feasible $x$.
- Local minimum: $f(x^*) \le f(x)$ only for feasible $x$ NEAR $x^*$.
Most algorithms only guarantee a local optimum. Convexity is what makes local = global.
Lab 01'in 3. bölümü engebeli bir 1-D fonksiyon kullanıyor:
$$g(x) = \sin x + 0.5\sin 2.5x + 0.08x^2, \qquad x \in [-8, 8]$$Lab'daki kod 1000 noktalık bir grid'de "iki komşusundan küçük" noktaları sayıyor: 6 local minimum var, global olan $x \approx -0.81$'de, $g \approx -1.121$. Aşağıda bir başlangıç noktası seç; top yokuş aşağı yuvarlanıyor: her adımda $x \leftarrow x - 0.1\, g'(x)$. (Bu güncellemenin adı gradient descent; Week 5'te ayrıntısıyla gelecek.)
Önce tahmin et: Topu $x_0 = 3$'ten bırakırsan hangi çukurda durur: $x \approx 1.89$'daki mi, $x \approx 4.30$'daki mi?
Local optimization hızlıdır, büyük problemlerde çalışır, sadece türev ister. Ama bir başlangıç noktası ister (sonucu bu nokta belirler), bulduğu noktanın global optimum'dan ne kadar uzak olduğunu söylemez ve parametre ayarı ister. Global optimization gerçek çözümü bulur, ama worst-case karmaşıklığı problem boyutuyla exponential büyür.
- $g'(x) = 0$ olması global minimum demek değildir. Local minimum, local maximum ya da (çok boyutta) saddle olabilir.
- Her global minimum aynı zamanda local minimum'dur; tersi genelde yanlıştır.
- Constrained bir problemde local minimum sınırda olabilir; orada gradient sıfır olmak zorunda değil (polygon'daki $(3,1)$ gibi).
Yukarıdaki iterasyon $x_0 = 3$'ten başlayınca nerede durur?
Hangisi her zaman doğru?
Problem haritası I: continuous / discrete, linear / nonlinear
Slayt 10: her problem birkaç eksen üzerinde bir noktada durur, ve nerede durduğu hem ne kadar zor olduğunu hem de hangi algoritmanın uygulanacağını belirler. Dört eksen: (1) Continuous / Discrete, (2) Linear / Nonlinear, (3) Convex / Non-convex, (4) Unconstrained / Constrained.
| Continuous | Discrete / Integer |
|---|---|
| Variable'lar $\mathbb{R}$'de | Variable'lar $\mathbb{Z}$'de ya da $\{0, 1\}$'de |
| Calculus çalışır: gradient ve Hessian var | Türev yok; arama uzayı combinatorial |
| Örnek: voltage, weight, flow, position | Örnek: assignment, routing, scheduling |
| Workhorse: gradient-based yöntemler | Workhorse: branch-and-bound, search, DP |
| Genelde "daha kolay" dünya | Çoğu zaman NP-hard; exact çözüm pahalı olabilir |
Mixed-integer problemlerde ikisi birden var. Integer'ları reel sayılara gevşetmek (relaxation) bir bound verir: Week 12'nin anahtar hilesi (11. bölümde küçük bir örneğini göreceksin).
| Linear | Nonlinear |
|---|---|
| Objective ve constraint'ler linear: $c^T x$, $Ax \le b$ | Objective ya da constraint'lerden biri eğri |
| Linear Programs (LP) | Gradient ve Hessian kullanır |
| Çok büyük ölçekte çözülür: milyonlarca variable | Örnek: least squares, neural net, power ∝ $V^2$ |
| Optimum, feasible polytope'un bir vertex'inde | Daha zengin modelleme, ama genelde daha zor |
| Yöntemler: Simplex, interior-point | Yöntemler: gradient, Newton, SQP |
Linearity ≠ easy and nonlinearity ≠ hard. The deeper question is the next axis: convexity.
Bir model, decision variable'lar objective'te ve constraint'lerde her zaman sabitlerle çarpılıp toplanıyorsa linear'dır: $f(x) = c_1x_1 + \dots + c_nx_n$. $x_1^2x_2$ ya da $T\cdot P$ gibi terimler modeli nonlinear yapar. Bir LP'nin gerçeği iyi temsil etmesi için dört varsayım:
- Proportionality: 4 soldier'ın katkısı tam 4 × (1 soldier'ın katkısı).
- Additivity: bir variable'ın katkısı diğerlerinin değerinden bağımsız; toplam = katkıların toplamı.
- Divisibility: variable'lar kesirli değer alabilir (1.5 soldier). Alamıyorsa integer programming gerekir.
- Certainty: bütün parameter'lar kesin biliniyor.
Winston iki eksen daha sayar: static / dynamic (tek seferlik karar mı, dönemler boyunca bir karar dizisi mi) ve deterministic / stochastic (parameter'lar kesin mi, rastgele mi).
- $|x_1|$, $\max(x_1, x_2)$, $x_1x_2$, $x_1^2$ nonlinear'dır. (Bazıları LP'ye çevrilebilir; Boyd'un Chebyshev örneği $\min \max_i |a_i^Tx - b_i|$ yeni bir variable $t$ ile LP olur. Ama yazıldığı haliyle linear değildir.)
- $\dfrac{x_1}{x_1 + x_2} \le 0.4$ yazıldığı haliyle nonlinear, ama payda pozitifse $x_1 \le 0.4(x_1 + x_2)$ olarak linear yazılır.
- Optimal LP cevabını yuvarlamak her zaman güvenli değil. 150,000.4 araba → 150,000 yeterli; 0.4 füze üssü → 0 mı 1 mi büyük fark eder (Winston).
Hangi constraint linear?
Bir LP "0.4 füze üssü kur" diyor. Hangi LP varsayımı bozuluyor?
Problem haritası II: convex / non-convex, unconstrained / constrained
- Convex set: iki noktası arasındaki doğru parçası tamamen kümenin içinde kalır.
- Convex function: her chord grafiğin üstünde ya da üzerindedir. Boyd'un yazımıyla, her $\theta \in [0,1]$ için $$f(\theta x + (1-\theta) y) \le \theta f(x) + (1-\theta) f(y).$$
- Convex ⇒ her local minimum global'dir, ve optimality'yi sertifikalayabiliriz (duality).
- Non-convex (deep net'ler, combinatorial problemler): çok sayıda local minimum; global olarak NP-hard.
Linear bir fonksiyon bu eşitsizliği eşitlikle sağlar. Yani her LP convex'tir; Boyd convex optimization'ı linear programming'in bir genellemesi olarak görür.
"The great watershed in optimization is not between linearity and nonlinearity, but convexity and non-convexity." (R. T. Rockafellar)
Slayttaki iki resim, gerçek fonksiyonlardan çizildi. Chord'un grafiğin altına düştüğü bir nokta varsa fonksiyon convex değildir; kod bunu chord boyunca 200 noktada kontrol ediyor:
$x = -1$, $y = 3$, $\theta = \tfrac12$: sol taraf $f(1) = 1$, sağ taraf $\tfrac12\cdot 1 + \tfrac12\cdot 9 = 5$. $1 \le 5$ ✓. Bu tek bir kontrol; convexity her $x, y, \theta$ için sağlanmalı. Tam ispat yöntemleri (Hessian testi) sonraki dersin konusu.
| Unconstrained | Constrained |
|---|---|
| $f(x)$'i $\mathbb{R}^n$'in tamamında minimize et | Constraint'lere uy; feasible set'te kal |
| Optimum bir stationary point: $\nabla f(x^*) = 0$ | Optimum çoğu zaman sınırın ÜZERİNDE (polygon'u hatırla) |
| Yöntemler: gradient descent, Newton | Araçlar: Lagrange multipliers & KKT conditions |
| Model fitting / training'in doğal ortamı | Gerçek mühendislik: power, timing, area budget'ları hep bağlar |
Sık kullanılan strateji: constrained problemi penalty ya da barrier terimleriyle unconstrained'e çevirmek (Week 7).
$m$ lamba $n$ yüzeyi aydınlatıyor. Decision variable lamba güçleri $p_j$; yüzey $k$'nın aydınlığı $I_k = \sum_j a_{kj}p_j$ ($a_{kj}$ geometriden gelen parameter'lar). Problem: $0 \le p_j \le p_{\max}$ iken her $I_k$'yı istenen $I_{\text{des}}$'e yaklaştırmak. Boyd uygun bir objective ile bunu convex bir problem olarak yazar. Sonra iki ek constraint sorar:
- "no more than half of total power is in any 10 lamps"
- "no more than half of the lamps are on ($p_j > 0$)"
Cevap: (1) eklenince problem hâlâ kolay; (2) eklenince son derece zor. (2) "kaç lamba açık" diye sayıyor: hangi lambaların açık olacağı bir combinatorial seçim. Ders: iki problem birbirine çok benzeyip zorluk bakımından çok farklı olabilir.
- Convex problem için hepsi gerekir: objective convex (min problemi), her $f_i$ convex, her equality constraint affine ($Ax = b$). $x_1^2 + x_2^2 = 1$ gibi nonlinear bir equality bir çember tarif eder; çember convex set değildir.
- Convex bir fonksiyonu maximize etmek convex bir problem değildir.
- Boyd'un uyarısı: "linear kolay, nonlinear zor" klasik görüşü yanlış. Doğrusu: convex kolay, non-convex zor.
Aydınlatma problemine hangi ek constraint problemi zor hale getirir?
$\min\ x_1 + x_2$ s.t. $x_1^2 + x_2^2 = 1$. Bu problem convex mi?
Unconstrained, türevlenebilir bir problemin optimum'unda hangisi sağlanır?
Sınıf algoritmayı seçer: 6 adımlık tarif
İlk adım her zaman problemi sınıflandırmaktır. Sınıf hangi aracı kullanacağını ve exact bir cevabın mümkün olup olmadığını söyler.
| Problem class | Typical method(s) | Course week |
|---|---|---|
| Linear program | Simplex · interior-point | 3–4 |
| Unconstrained smooth | Gradient descent · Newton / quasi-Newton | 5–6 |
| Constrained nonlinear | Lagrange / KKT · SQP | 7 |
| Convex | Interior-point · CVXPY modeling | 8–9 |
| Large-scale / ML | SGD · momentum · Adam · proximal | 10–11 |
| Integer / combinatorial | Branch-and-bound · dynamic programming | 12–13 |
| Intractable / very large | Heuristics · metaheuristics | 14 |
- Identify the decision variables. Tam olarak neyi seçmekte serbestsin?
- Define the objective. "En iyi" ne demek: neyi minimize ya da maximize ediyorsun?
- List the constraints. Fiziksel sınırlar, budget'lar, capacity'ler, mantıksal kurallar.
- Pin down types & data. Continuous mu, integer mı? Hangi sayılar sabit parameter?
- Classify the problem. Eksenlere yerleştir: LP, convex, integer, …
- Choose a solver / algorithm. Sınıf doğru aracı gösterir.
Winston daha geniş bir 7 adımlık süreç anlatır (problemi tanımla, sistemi gözle ve veri topla, modeli kur, modeli doğrula, alternatif seç, sonuçları sun, uygula ve izle). Slayttaki 6 adım bunun "modeli kur ve çöz" kısmı.
Aşağıda bir hikâye seç. Her ifadeyi etiketle, dört ekseni işaretle, sonra kontrol et. Hepsi doğruysa widget modeli ve slayt 15'teki satırı gösterir.
Önce tahmin et: Giapetto hikâyesinde "bir soldier 2 saat finishing ister" ifadesi bir constraint mi, yoksa bir parameter mı?
"A small electronics workshop assembles two products: router cases and switch cases. Each router case brings a profit of 50 TL and each switch case 35 TL. A router case needs 2 hours of assembly and 1 hour of testing; a switch case needs 1 hour of assembly and 2 hours of testing. Each week at most 100 assembly hours and 80 testing hours are available, and at most 30 router cases can be sold.
(a) Identify the decision variables, the objective and the constraints, and write the model.
(b) Write the model in the standard form of Week 1 (minimize, $f_i(x) \le 0$).
(c) Classify the problem on the four axes and name a suitable method.
(d) Find the optimum by evaluating the objective at the vertices. Which constraints are active?"
İpucu 1
Variable'lar haftalık üretim miktarları: $x_1$ router case, $x_2$ switch case. Her kaynak (assembly, testing, demand) bir constraint.
İpucu 2
(d) için aday köşeler: eksenlerle kesişimler ve constraint çiftlerinin kesişimleri. $2x_1 + x_2 = 100$ ile $x_1 + 2x_2 = 80$'in kesişimini bulduğunda $x_1 \le 30$'u bozup bozmadığına bak.
Çözümü göster
(a) $x_1$ = haftada üretilen router case sayısı, $x_2$ = switch case sayısı.
$$\begin{aligned}\max\quad & z = 50x_1 + 35x_2\\ \text{s.t.}\quad & 2x_1 + x_2 \le 100 \quad\text{(assembly)}\\ & x_1 + 2x_2 \le 80 \quad\text{(testing)}\\ & x_1 \le 30 \quad\text{(demand)}\\ & x_1, x_2 \ge 0\end{aligned}$$(b)
$$\begin{aligned}\text{minimize}\quad & -50x_1 - 35x_2\\ \text{subject to}\quad & 2x_1 + x_2 - 100 \le 0\\ & x_1 + 2x_2 - 80 \le 0\\ & x_1 - 30 \le 0\\ & -x_1 \le 0, \quad -x_2 \le 0\end{aligned}$$(c) Continuous (adetler aslında tam sayı, ama LP modeli divisibility varsayar; burada optimum zaten tam sayı çıkıyor), linear, convex (her LP convex'tir), constrained ⇒ linear program ⇒ Simplex ya da interior-point (Week 3–4).
(d)
| Vertex | $z = 50x_1 + 35x_2$ |
|---|---|
| $(0, 0)$ | 0 |
| $(30, 0)$ | 1500 |
| $(30, 25)$ | 2375 |
| $(0, 40)$ | 1400 |
Assembly ile testing doğrularının kesişimi $(40, 20)$, ama $x_1 \le 30$'u bozuyor; vertex değil. Optimum $x^* = (30, 25)$, $z^* = 2375$ TL (min biçiminde $p^* = -2375$). Active: testing ($30 + 50 = 80$) ve demand ($x_1 = 30$). Assembly'de $100 - 85 = 15$ saat boş kalıyor.
$\min_x\ \sum_{k=1}^{K} (a_k^T x - b_k)^2$, constraint yok, $x \in \mathbb{R}^n$. Slayt 15'e göre hangi satır?
Variable'lar $\{0,1\}$'de, objective ve constraint'ler linear. Hangi yöntem ailesi?
Modeling clinic 1: bir devrenin enerjisini minimize etmek
"The problem, in words:
- A digital block has gates with supply voltages $v_1, \dots, v_n$.
- Dynamic energy per gate grows like $C_i v_i^2$ (the $CV^2$ law).
- Lower voltage saves energy but makes gates slower.
- The block must still meet a timing deadline $T$.
- Each voltage has physical lower/upper limits."
Modeli yaz ve problemi dört eksende sınıflandır.
İpucu 1
Neyi seçebiliyorsun? $C_i$ ve $T$'yi değiştirebilir misin?
İpucu 2
İki hedef çatışıyor: energy ve hız. Slayt 6'daki ikinci yolu kullan: birini objective yap, diğerini constraint.
Çözümü göster
Decision variable: $v = (v_1, \dots, v_n)$. Parameter'lar: $C_i$, $T$, $v_{\min}$, $v_{\max}$ ve delay modelinin katsayıları.
Standard form'da: $f_0(v) = \sum C_iv_i^2$; $f_1(v) = \text{delay}(v) - T \le 0$; her $i$ için $v_{\min} - v_i \le 0$ ve $v_i - v_{\max} \le 0$. Toplam $m = 2n + 1$ inequality, $p = 0$.
Problem class (slayttaki gibi): continuous · nonlinear · convex (if delay is modeled convexly) · constrained → convex / NLP methods; relates to geometric programming.
"Model & solve a CE problem. From lecture, the circuit-energy model is $\min \sum_i C_i v_i^2$ s.t. a delay budget and bounds $v_{\min}\le v_i\le v_{\max}$. Pick small numbers (e.g. 3 gates) and minimize it with scipy.optimize.minimize using the bounds= and constraints= arguments."
İpucu 1
Önce bir delay modeli seçmen gerekiyor. Voltage arttıkça delay azalmalı ve convex olmalı. Basit bir seçim: gate $i$'nin delay'i $a_i / v_i$, toplam delay $\sum_i a_i / v_i$ ($v > 0$ için convex).
İpucu 2
scipy'de {"type": "ineq", "fun": g} constraint'i $g(v) \ge 0$ demektir. Yani $\text{delay}(v) \le T$'yi T - delay(v) olarak yazarsın.
Çözümü göster
Seçilen sayılar (bunlar bizim seçimimiz; lab "pick small numbers" diyor): $C = (1, 2, 4)$, $a = (1, 1, 1)$, $T = 3.6$, $0.6 \le v_i \le 1.2$.
import numpy as np
from scipy.optimize import minimize
C = np.array([1.0, 2.0, 4.0]) # capacitances (normalized)
a = np.array([1.0, 1.0, 1.0]) # delay of gate i = a_i / v_i
T = 3.6 # timing deadline
energy = lambda v: np.sum(C * v**2)
cons = [{"type": "ineq", "fun": lambda v: T - np.sum(a / v)}] # scipy: fun(v) >= 0
res = minimize(energy, x0=[1.0, 1.0, 1.0], bounds=[(0.6, 1.2)] * 3,
constraints=cons, method="SLSQP")
print(np.round(res.x, 4), round(res.fun, 4)) # [1.0687 0.8482 0.6732] 4.3941| Çözüm | $v_1$ | $v_2$ | $v_3$ | Delay | Energy |
|---|---|---|---|---|---|
| Optimum | 1.0687 | 0.8482 | 0.6732 | 3.6000 | 4.3941 |
| Hepsi eşit ($v = 3/3.6$) | 0.8333 | 0.8333 | 0.8333 | 3.6000 | 4.8611 |
- Delay constraint'i active: delay tam $T = 3.6$. Sebep: bir voltage'ı biraz düşürmek energy'yi hep azaltır; bunu deadline izin verdiği sürece yaparsın.
- Bound'lar active değil: üç voltage da $[0.6, 1.2]$'nin içinde.
- Capacitance'ı büyük olan gate daha düşük voltage alıyor. Oranlar $v_i \propto (a_i/C_i)^{1/3}$ kuralına uyuyor: $v_1 / v_2 = 1.0687/0.8482 \approx 1.26 = 2^{1/3}$. Bu kuralın nereden geldiğini KKT dersinde (Week 7) türeteceğiz.
- Bütün gate'lere aynı voltage'ı vermek aynı deadline'ı tutturup yaklaşık %10.6 daha fazla energy harcıyor.
Sınıf: continuous, nonlinear, convex ($C_iv_i^2$ ve $a_i/v_i$ ($v_i > 0$) convex, bound'lar linear), constrained ⇒ convex / constrained nonlinear.
- scipy'nin
"ineq"'i $\ge 0$ anlamına gelir; standard form ise $f_i \le 0$. Constraint'i ters yazarsan solver "delay en az $T$ olsun" diye çözer. - Bound'ları unutursan voltage'lar fiziksel aralığın dışına çıkabilir. Bound'lar da constraint'tir.
- "Convex" etiketi delay modeline bağlı. Delay convex değilse problem non-convex olur ve local / global ayrımı geri gelir.
Optimumda hangi constraint active?
Deadline gevşetilirse ($T$ büyürse) optimal energy $E^*$ ne olur?
Modeling clinic 2: bir scheduler'ın throughput'unu maximize etmek
"The problem, in words:
- $N$ tasks must run on $M$ processors.
- Goal: complete as many tasks as possible.
- Each task is assigned to at most one processor.
- No processor may exceed its capacity $C_j$.
- Decision per pair: run task $i$ on processor $j$, yes or no."
Modeli yaz ve sınıflandır.
İpucu 1
Son madde decision variable'ı veriyor: her $(i, j)$ çifti için bir evet/hayır, yani $x_{ij} \in \{0, 1\}$.
İpucu 2
Capacity'yi yazmak için her task'ın processor'da ne kadar yer tuttuğunu bilmen gerekir: $w_i$ (task $i$'nin yükü, bir parameter).
Çözümü göster
Problem class (slayttaki gibi): discrete (binary) · linear · constrained → an integer program (ILP); generally NP-hard, solved by branch-and-bound or heuristics.
Modeli küçük bir örnekte dene. Varsayılan örnekte 5 task ($w = 4, 4, 2, 4, 4$) ve iki processor ($C = 7, 7$) var. Task'ları elle ata; sonra brute force bütün atamaları denesin.
Önce tahmin et: Toplam capacity 14, en hafif dört task'ın toplamı $2 + 4 + 4 + 4 = 14$. En fazla kaç task tamamlanır?
- Her task ya çalışmaz ya da $M$ processor'dan birine gider: $(M+1)^N$ atama. $x_{ij}$ vektörü olarak bakarsan $2^{NM}$ olasılık. $N = 30$, $M = 5$ için $2^{150} \approx 1.4 \times 10^{45}$: brute force imkânsız.
- Relaxation: $x_{ij} \in \{0,1\}$ yerine $0 \le x_{ij} \le 1$ yazarsan bir LP olur. Bu LP'nin değeri integer optimum için bir upper bound'dur (max problemi): daha geniş bir küme üzerinde maximize ediyorsun.
- Varsayılan örnekte LP relaxation 4 diyor (bir task'ı iki processor'a bölebiliyor), integer optimum 3. Branch-and-bound (Week 12) bu bound'ları kullanarak aramayı budar.
- "At most one processor" constraint'ini unutursan aynı task iki processor'da sayılır ve throughput şişer.
- $\sum_j x_{ij} = 1$ yazmak "her task mutlaka çalışsın" demektir. Capacity yetmiyorsa model infeasible olur.
- LP relaxation'ın kesirli cevabını yuvarlamak feasible ya da optimal bir atama vermeyebilir.
Varsayılan örnekte ($w = 4,4,2,4,4$; $C = 7,7$) $\sum_j x_{ij} \le 1$ yerine $\sum_j x_{ij} = 1$ yazılırsa?
Bir max ILP'nin LP relaxation'ı 4.0 veriyor. Integer optimum hakkında ne biliyoruz?
Kendi problemini kur: HW 0 ve proje
Slayt 21'in özeti: her problem = variables + objective + constraints; local ≠ global, convexity ikisi arasındaki köprü; önce sınıflandır, sınıf algoritmayı seçer; modelleme mühendisliğin ana becerisi.
"HW 0: formulate two CE problems in standard form"
İpucu 1
Her problem için 6 adımlık tarifi uygula, sonra 1. bölümdeki dönüşümlerle $f_i(x) \le 0$, $h_j(x) = 0$ biçimine getir. $m$ ve $p$'yi yaz.
İpucu 2
Biri continuous, biri discrete olsun: dört eksenin farkını göstermenin en kolay yolu bu.
Örnek çözüm göster
Problem A · sensor calibration. Bir sensörün okumaları $s_k$, gerçek değerler $y_k$ ($k = 1, \dots, K$). Model $y \approx \theta_1 + \theta_2 s$. Decision variable $\theta = (\theta_1, \theta_2)$; parameter'lar $(s_k, y_k)$.
$$\text{minimize}\quad f_0(\theta) = \sum_{k=1}^{K} (\theta_1 + \theta_2 s_k - y_k)^2$$$m = 0$, $p = 0$. Sınıf: continuous · nonlinear (quadratic) · convex · unconstrained ⇒ gradient descent / Newton (Week 5–6) ya da doğrudan normal equation'lar. Gain'in pozitif olması istenirse $-\theta_2 \le 0$ eklenir ve $m = 1$ olur.
Problem B · VM placement. $n$ sanal makine (boyutları $s_i$), en fazla $K$ server (capacity'leri $\text{Cap}$). Decision variable'lar: $z_{ik} = 1$ ise VM $i$ server $k$'da; $y_k = 1$ ise server $k$ açık.
$$\begin{aligned}\text{minimize}\quad & \sum_{k} y_k\\ \text{subject to}\quad & \sum_i s_i z_{ik} - \text{Cap}\cdot y_k \le 0, \quad k = 1,\dots,K\\ & \sum_k z_{ik} - 1 = 0, \quad i = 1,\dots,n\\ & z_{ik},\ y_k \in \{0, 1\}\end{aligned}$$$m = K$, $p = n$. Sınıf: discrete (binary) · linear · constrained ⇒ ILP ⇒ branch-and-bound (Week 12). $\{0,1\}$ şartı $f_i \le 0$ biçimine doğal olarak girmez; zorla yazarsan $z(1-z) = 0$ olur, bu da affine olmayan bir equality, yani non-convex. Zorluğun kaynağı bu.
Küçük bir örnek: boyutlar $(3, 2, 2, 1)$, $\text{Cap} = 4$. Toplam 8, yani en az 2 server gerekir; $\{3, 1\}$ ve $\{2, 2\}$ ile 2 server yeter ⇒ optimum 2.
Not: HW 0'ın kendisi repoda yok; slaytta yalnızca bu tek satır var. Yukarıdaki iki problem hocanın değil, örnek bir cevap.
"1. Model a real problem (decision variables, objective, constraints)" ve "A strong project picks a problem with both a convex formulation (provable optimum) and a heuristic approach, then quantifies the gap between them."
İpucu 1
Önce "neyi seçebiliyorum?" sorusunu cevapla, sonra "neyi ölçebiliyorum?" Ölçemediğin bir şey objective olamaz.
İpucu 2
Seçeneklerin bir listeden mi geliyor (model adı), yoksa bir aralıkta mı (bir oran)? Bu, axis 1'i belirler.
Örnek iskelet göster
Örnek konu: yerel çalışan bir LLM için model, context size ve GPU offload seçmek.
- Decision variables: model seçimi $y_k \in \{0,1\}$ ($\sum_k y_k = 1$), context size $c$ (bir listeden), GPU'ya offload edilen layer sayısı $g$ (integer).
- Objective: ölçülen kalite $Q(k, c, g)$'yi maximize et (bir benchmark skoru: ölçülebilir olmalı).
- Constraints: bellek kullanımı $\le$ bellek limiti, cevap latency'si $\le$ latency limiti, $0 \le g \le$ modelin layer sayısı.
- Sınıf: discrete (integer) · nonlinear (kalite ve latency ölçümle bulunuyor, formülü yok) · büyük olasılıkla non-convex · constrained ⇒ seçenek sayısı küçükse enumeration; büyükse heuristic / metaheuristic (Week 14).
Kendi sayıların ve ölçümlerinle doldur. Ölçülen her büyüklük bir parameter mı, yoksa kararlarından hesaplanan bir fonksiyon mu, ayır.
Problem B'de $\sum_k z_{ik} - 1 = 0$ satırı standard form'un hangi parçası?
Son kontrol
Kâğıt kalemle çöz, sonra cevaba bak.
$\max\ 2x_1 - x_2$ s.t. $x_1 + x_2 \ge 1$, $x_1 \le 5$. Standard form'da objective ve ilk constraint hangisi?
$\max\ x_1 + x_2$ s.t. $x_1 - x_2 \le 1$, $x_1, x_2 \ge 0$. Durum nedir?
Farmer Jones'un optimum'u $(3,\ 2.8)$, $z^* = 370$. Hangi constraint'ler active?
Convex bir problemde bir solver local minimum buldu. Ne söyleyebilirsin?
"Task'ları processor'lara ata, bitirilen task sayısını maximize et, capacity'leri aşma" problemi dört eksende nerede?