Konveks Optimizasyon: Makine Öğrenmesinin "Mutlu Vadisi"

Yerel vs küresel minimum

Bir dağcı bir vadide ki en alçak noktaya inmek istiyor. Dağlık bir bölge düşünün — birçok vadi, birçok zirve. Dağcı yerel olarak aşağı yürürse, kendini bir çukurta bulabilir, ama gerçek derin vadi'ye ulaşamayabilir.

Sorun: yerel minimum ≠ küresel minimum. Modern optimizasyonun temel zorluğu.

Bir özel durum var ki bu sorun kaybolur: konveks fonksiyonlar. Onlarda yerel minimum = küresel minimum. Bir tek vadi.

Konveks küme ve fonksiyon

Konveks küme $C$: $x, y \in C \Rightarrow \lambda x + (1-\lambda) y \in C$ ($\lambda \in [0,1]$). İki nokta arasındaki doğru parçası kümede kalır.

Örnekler: top, küp, simpleks, lineer alt uzay, lineer eşitsizliklerin çözüm kümesi.

Konveks fonksiyon $f: C \to \mathbb{R}$: $f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y)$. Bir doğru parçasının altında kalır.

Örnekler: $x^2$, $|x|$, $e^x$, $-\log x$ ($x > 0$).

Konveks optimizasyon problemi

$\min_{x \in C} f(x)$

$f$ konveks, $C$ konveks. Kısıtlar genelde:

$\min f(x), \quad \text{s.t. } g_i(x) \leq 0, \quad h_j(x) = 0$

$g_i$ konveks, $h_j$ affine (lineer + sabit).

Niçin güzel?

1. Yerel minimum = küresel minimum

Konveks fonksiyonda her yerel minimum aynı zamanda küresel minimumdur. Optimizasyon algoritmaları takılı kalmaz.

2. Polinom zaman

Konveks optimizasyon polinom zamanda çözülür (iç nokta yöntemleri). NP-zor değil.

3. Dualite

Lagrange dualitesi çok zarif:

$L(x, \lambda, \nu) = f(x) + \sum_i \lambda_i g_i(x) + \sum_j \nu_j h_j(x)$

Dual fonksiyon: $g(\lambda, \nu) = \inf_x L$. Zayıf dualite: $g \leq p^*$ (her zaman). Güçlü dualite: $g^* = p^*$ (konveks + Slater koşulu altında).

4. KKT koşulları

Karush-Kuhn-Tucker koşulları: optimum noktanın gerekli ve yeterli koşulları (konveks problemde).

Klasik problemler

Lineer programlama (LP)

$\min c^T x$, $Ax = b$, $x \geq 0$. Dantzig'in simpleks (1947) ve Karmarkar iç nokta (1984) yöntemleri.

Kuadratik programlama (QP)

$\min x^T Q x + c^T x$, lineer kısıtlar. Pasif kuadratik form ⟺ konveks.

Konik programlama

Kısıtların konik olduğu genelleştirme: SDP (yarı-pozitif definitif), SOCP (ikinci dereceden konik).

Geometrik programlama

$\sum c_i \prod x_j^{a_{ij}}$ ile çalışan log-dönüşüm sonrası konveks olan problemler.

Çözüm yöntemleri

1. Gradyan iniş

$x_{k+1} = x_k - \alpha \nabla f(x_k)$. Sade. Konveks $f$'de yerel minimuma yakınsar (yerel = küresel).

2. Newton yöntemi

$x_{k+1} = x_k - H^{-1} \nabla f$ ($H$ = Hessian). Daha hızlı (kuadratik yakınsama).

3. İç nokta yöntemleri

Karmarkar (1984): LP için polinom zaman algoritma. Modern QP, SDP standardı.

4. ADMM (Alternating Direction Method of Multipliers)

Büyük ölçekli dağıtık optimizasyon. Modern makine öğrenmesi.

5. Proksimal yöntemler

$L^1$ düzenleştirme (LASSO) gibi non-pürüzsüz konveks problemler.

Modern uygulamalar

1. Makine öğrenmesi

SVM, lojistik regresyon, ridge regresyon, LASSO — hepsi konveks. Modern eğitimin "mutlu vadisi".

Dezavantaj: derin sinir ağları konveks değil — bu nedenle "non-konveks optimizasyon" modern araştırma alanı.

2. Sinyal işleme

Sıkıştırılmış algılama (compressed sensing), görüntü onarımı, lineer-kuadratik kontrol — hepsi konveks formülasyonlar.

3. Finans

Markowitz portföy optimizasyonu: ortalama-varyans kuadratik problem.

4. Mühendislik

Devre tasarımı, antenler, robotik — konveks gevşemeler (relaxations) kullanılır.

5. Operasyon araştırması

Tedarik zinciri, lojistik, üretim planlama — LP/QP problemleri.

6. İletişim

Beamforming (anten array yönlendirme), güç tahsisi — konveks problemler.

Konveks gevşeme

NP-zor bir problemi konveks bir versiyona "gevşet":

• Tamsayı programlama → LP gevşemesi.
• Maks kesim problemi → SDP gevşemesi (Goemans-Williamson, 0.878 yaklaşım).
• Sparse regresyon → LASSO.

Modern algoritma teorisinin paradigması: "Konveks gevşeme + yuvarlama = güçlü yaklaşım algoritması".

Tarihsel köken

• Dantzig (1947): simpleks algoritması, lineer programlama.
• Karush, Kuhn-Tucker (1939-1951): KKT koşulları.
• Rockafellar (1970): Convex Analysis — modern teorinin standart referansı.
• Karmarkar (1984): LP iç nokta yöntemi.
• Nesterov, Nemirovski (1990'lar): modern iç nokta + ivmeli gradyan.
• Boyd, Vandenberghe (2004): Convex Optimization — popüler ders kitabı.

Sonuç

Konveks optimizasyon:

• "Yerel = küresel" özelliği ile çözüm garantili.
• Polinom zamanda hesaplanabilir (Karmarkar 1984).
• Modern makine öğrenmesi, sinyal işleme, finans, mühendislik'in matematik temeli.
• Non-konveks problemler için konveks gevşeme: yaklaşım algoritması paradigması.

Bir geometrik özellik: konvekslik. Ama bu özelliğin sağladığı algoritmik refah modern hesaplamanın bir bölümünü mümkün kılar.

"Konveks problem, çözülebilir problem." Modern optimizasyon biliminin paradigma cümlesi. Dağcıya: eğer vadi konveksse, aşağı yürümeye devam et — derin noktaya varacaksın.