Lagrange, KKT y el problema dual

💡En simple: lee esto primero

El problema dual es otra forma de plantear el mismo SVM, en la que cada punto tiene un «precio» que dice cuánto empuja la frontera.

Imagínalo así

Imagina la frontera como una tabla y cada punto como una persona que puede empujarla. La mayoría ni la toca (precio 0); solo los que están pegados a ella empujan (precio positivo). Esos son los vectores de soporte.

Lo que tienes que llevarte

• Un multiplicador de Lagrange (α) es el «precio» de una regla: cuánto mejorarías si la aflojaras un poquito.
• KKT dice: si una regla no te estorba, su precio es 0; si te estorba, estás justo en el borde.
• El dual solo usa productos punto entre puntos → eso abre la puerta al truco del kernel.

Palabras raras de esta página

restricción

una regla que la solución debe cumplir («no cruzar esta pared»).

Lagrangiano

el objetivo más «multas» por romper las reglas, todo en una sola fórmula.

primal / dual

dos versiones del mismo problema: una busca la frontera, la otra los precios de cada punto.

holgura complementaria

o la regla está «floja» (precio 0) o está «apretada» (en el borde); nunca ambas cosas a medias.

Más abajo viene la versión completa, con fórmulas. Si una palabra aparece subrayada con puntos, pasa el mouse (o tócala) para ver qué significa.

¿Cuánto te cuesta una regla?

Todos los problemas de esta sección tienen la forma $\min_x J(x)$ s.a. $g(x)\ge0$. Ejemplo: minimizar $J(x)=(x-3)^2$ con $x\le1$ ($g(x)=1-x\ge0$). Sin la regla, $x=3$ y $J=0$. La pared lo prohíbe, así que la respuesta se desliza sobre la pared: $x=1$, $J=4$. Dos cosas pasaron: el valor empeoró, y $J'(1) = -4\ne0$: «igualar la derivada a cero» ya no encuentra la respuesta.

Mejor pregunta: ¿cuánto vale esta regla? Si empujamos la pared un poco, ¿cuánto mejora el mejor valor? Esa tasa de cambio es el multiplicador.

• Con la pared en $c$: $J^\star(c) = (c-3)^2$ para $c<3$. Su pendiente en $c=1$ es $2(1-3) = -4$: mover la pared $\varepsilon$ mejora $J^\star$ en $\approx4\varepsilon$ ($c=1.1$ da 3.61, una ganancia de $0.39\approx4\times0.1$). Esa tasa es $\alpha=4$.
• Más espacio nunca empeora, así que la pendiente nunca es positiva: $\alpha\ge0$.

¿Cuánto cuesta una regla? El multiplicador α

Minimiza $J(x)=(x-3)^2$ sujeto a $g(x)=c-x\ge 0$ (una pared en x = c). Mueve la pared y mira tres lecturas del mismo número α: precio, tasa y fuerza.

posición de la pared c 1

Primal: el óptimo se pega a la pared

Mejor valor J*(c): su pendiente es −α

Dual: q(α) = minₓ L(x, α) = −α²/4 − α(c − 3). Su máximo coincide con el primal (brecha cero)

x*1.00

J* (primal)4.000

α* = 2(3 − c)₊4.00

q(α*) (dual)4.000

α*·g(x*)0.000

La pared aprieta (restricción activa, g = 0) y α = 4.00 > 0: empujar la pared ε hacia fuera mejora J* en ≈ 4.00ε. En x*, J′ = -4.00 ≠ 0, pero ∂L/∂x = J′ + α = 0: α es la fuerza que falta.

El Lagrangiano: una función que conoce el precio

$$L(x,\alpha) = J(x) - \alpha\,g(x) = (x-3)^2-\alpha(1-x) \qquad\Rightarrow\qquad \frac{\partial L}{\partial x} = 2(x-3)+\alpha = 0 \Rightarrow \alpha = 2(3-x)$$

Una ecuación, dos incógnitas; lo cierra que hay solo dos finales posibles:

• Pared holgada: no cuesta nada, $\alpha = 0$, $x=3$ (legal solo si $c\ge3$).
• Pared apretada: la respuesta está sobre ella, $x=c$, $\alpha = 2(3-c)$.

Con $x\le1$ la primera rama quiere $x=3$ (prohibido) ⇒ segunda: $\alpha = 4$, el mismo 4 de la pendiente. Con $x\le5$, $x=3$ ya es legal ⇒ $\alpha=0$.

¿Por qué «fuerza»? En $x=1$, $J'(1)=-4$: el objetivo todavía quiere ir a la derecha. Pero $\partial L/\partial x = -4+4 = 0$: el multiplicador aporta exactamente el empujón que falta. Precio, tasa y fuerza son tres lecturas del mismo número; una regla que no presiona vale 0 en las tres.

Dos variables: los gradientes se alinean

$\min u_1^2+u_2^2$ s.a. $u_1+u_2-2\ge0$. El óptimo es el punto de la recta más cercano al origen, $(1,1)$. Ahí $\nabla J = (2,2) = 2\nabla g$ ⇒ $\alpha=2$. Si $\nabla J$ no fuera paralelo a $\nabla g$, parte de $-\nabla J$ apuntaría a lo largo del borde: podrías deslizarte, seguir legal y bajar. Solo cuando $\nabla J$ apunta derecho hacia fuera del borde no queda a dónde ir.

El Lagrangiano es el problema con restricciones

Dale $\alpha$ a un oponente que elige cualquier $\alpha\ge0$ para hacer $L$ lo más grande posible, con $x$ congelado:

• $x$ cumple con holgura ($g>0$): $-\alpha g<0$, lo mejor es $\alpha=0$ ⇒ queda $J(x)$.
• $x$ viola ($g<0$): $-\alpha g = \alpha|g|$ crece sin límite ⇒ multa infinita.
• $x$ justo en la pared ($g=0$): el término se anula para todo $\alpha$. Un precio positivo solo es posible aquí.

$$\max_{\alpha\ge0}L(x,\alpha) = \begin{cases}J(x) & g(x)\ge0\\ +\infty & g(x)<0\end{cases}\qquad\Rightarrow\qquad \min_x\max_{\alpha\ge0}L = \min_{x:\,g(x)\ge0}J(x)$$

Primal y dual

Jugar primero nosotros es el primal ($\min_x\max_\alpha L$); dejar que el oponente se comprometa primero es el dual ($\max_\alpha\min_x L$). Comprometerse primero solo puede perjudicar: $\max\min\le\min\max$ (dualidad débil, vale para cualquier problema). Si además el objetivo es un bowl y las reglas son semiespacios (convexidad), la brecha es cero: dualidad fuerte, resolver uno resuelve el otro.

En el ejemplo: $\min_x L$ da $x = 3-\alpha/2$ y la función dual $q(\alpha) = 2\alpha - \alpha^2/4$. Maximizando: $q'(\alpha)=2-\alpha/2=0\Rightarrow\alpha^\star=4$, $q(4)=4$ = valor primal. Y $x = 3-4/2 = 1$: el dual devolvió la respuesta sin mirar la restricción directamente.

De vuelta al SVM: un precio por punto

$$L(\mathbf{w},b,\boldsymbol\alpha) = \tfrac12\|\mathbf{w}\|^2 - \sum_{i=1}^n \alpha_i\big[y_i(\mathbf{w}^\top\mathbf{x}_i+b)-1\big],\qquad \alpha_i\ge0$$

Los precios no interactúan (cada $\alpha_i$ está en un solo término), así que el oponente juega el juego de una regla en cada punto. $\alpha_i$ es cuánto presiona el punto $i$ sobre la frontera.

w y b desaparecen al sustituir las condiciones de estacionariedad: el dual solo toca los datos a través de productos internos xᵢᵀxⱼ. Ese es el enganche para los kernels.

Condiciones KKT

En el óptimo de un problema convexo como este valen a la vez:

1. Estacionariedad: $\nabla_\mathbf{w}L = 0$, $\partial L/\partial b=0$.
2. Factibilidad primal: $y_if(\mathbf{x}_i)\ge1$.
3. Factibilidad dual: $\alpha_i\ge0$ (una pared empuja, nunca jala).
4. Holgura complementaria: $\alpha_i\,[y_if(\mathbf{x}_i)-1] = 0$ para todo $i$.

La 4 es un producto de dos no negativos forzado a 0: o el precio es cero o la restricción está apretada. Nadie puede estar lejos y ser caro:

• Estrictamente fuera de la banda ($y_if>1$) ⇒ $\alpha_i=0$.
• Precio positivo ($\alpha_i>0$) ⇒ $y_if = 1$: el punto está exactamente en una recta de margen.

Como $\mathbf{w}=\sum_i\alpha_iy_i\mathbf{x}_i$ (abajo), todo punto con $\alpha_i=0$ no aporta nada: la frontera se construye solo con vectores de soporte. Esta es la prueba prometida. (Ojo: un punto puede tocar el margen y tener $\alpha_i = 0$; lo prohibido es «lejos y con precio».)

Derivando el dual

Paso 1 — estacionariedad:

$$\nabla_\mathbf{w}L = \mathbf{w}-\sum_i\alpha_iy_i\mathbf{x}_i = 0\Rightarrow \boxed{\mathbf{w}=\sum_i\alpha_iy_i\mathbf{x}_i}\qquad \frac{\partial L}{\partial b} = -\sum_i\alpha_iy_i = 0\Rightarrow\boxed{\sum_i\alpha_iy_i = 0}$$

La primera es una receta para $\mathbf{w}$; la segunda, una restricción sobre los precios. $b$ desaparece (por eso se recupera aparte).

Paso 2 — sustituir: $L = \tfrac12\mathbf{w}^\top\mathbf{w}-\sum_i\alpha_iy_i\mathbf{w}^\top\mathbf{x}_i - b\underbrace{\sum_i\alpha_iy_i}_{=0}+\sum_i\alpha_i$. Con la receta, $\sum_i\alpha_iy_i\mathbf{w}^\top\mathbf{x}_i = \mathbf{w}^\top\mathbf{w}$, así que $L = \sum_i\alpha_i-\tfrac12\|\mathbf{w}\|^2$, y $\|\mathbf{w}\|^2 = \sum_{i,j}\alpha_i\alpha_jy_iy_j\mathbf{x}_i^\top\mathbf{x}_j$:

$$\boxed{\max_{\boldsymbol\alpha}\ W(\boldsymbol\alpha)=\sum_{i=1}^n\alpha_i-\frac12\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\,\mathbf{x}_i^\top\mathbf{x}_j\quad\text{s.a.}\quad \alpha_i\ge0,\ \ \sum_i\alpha_iy_i=0}$$

Otra vez un QP convexo, ahora en $n$ variables $\alpha_i$ (en vez de las $d+1$ de $(\mathbf{w},b)$). Por dualidad fuerte, $\max W = \min\tfrac12\|\mathbf{w}\|^2$. Y los datos entran solo como productos internos $\mathbf{x}_i^\top\mathbf{x}_j$: esa línea es toda la razón de existir de los kernels.

Vista primal: «¿dónde pongo la recta?». Vista dual: «¿cuánto empuja cada punto la recta?». Misma respuesta, otra pregunta.

$\sum_i\alpha_iy_i=0$ dice que la presión total de la clase + equilibra la de la clase −: la frontera está en equilibrio.

Recuperar el modelo

• $\mathbf{w} = \sum_i\alpha_iy_i\mathbf{x}_i$ (solo vectores de soporte).
• $b$: toma un vector de soporte $\mathbf{x}_k$ sobre su recta de margen: $y_kf(\mathbf{x}_k)=1$; multiplicando por $y_k$ ($y_k^2=1$): $b = y_k-\mathbf{w}^\top\mathbf{x}_k$. En la práctica se promedia sobre todos esos $k$ (estabilidad numérica).
• Predicción: $\hat y(\mathbf{x}) = \operatorname{sign}\big(\sum_i\alpha_iy_i\,\mathbf{x}_i^\top\mathbf{x}+b\big)$: ni siquiera hace falta formar $\mathbf{w}$.

Pregunta del banco

«Como $b$ desaparece del dual, queda indeterminado y se fija en 0 por convención» → Falso. Precisamente porque desaparece, se recupera aparte con $b=y_k-\mathbf{w}^\top\mathbf{x}_k$; fijarlo en 0 movería la frontera.

El dual más pequeño y el ejemplo de la clase

Dos puntos: un parábola en una variable

$\mathbf{x}_+=(1,1)$, $y=+1$; $\mathbf{x}_-=(-1,-1)$, $y=-1$. La restricción $\alpha_1-\alpha_2=0$ fuerza $\alpha_1=\alpha_2=\alpha$. Con $\mathbf{x}_+^\top\mathbf{x}_+=\mathbf{x}_-^\top\mathbf{x}_-=2$, $\mathbf{x}_+^\top\mathbf{x}_-=-2$:

$W(\alpha) = 2\alpha-\tfrac12(\alpha^2\cdot2+\alpha^2\cdot2+2\alpha^2\cdot2) = 2\alpha-4\alpha^2$. $W'=2-8\alpha=0\Rightarrow\alpha=\tfrac14$, $W=\tfrac14$.

$\mathbf{w} = \tfrac14(1,1)-\tfrac14(-1,-1)=(\tfrac12,\tfrac12)$, $b = 1-\mathbf{w}^\top\mathbf{x}_+ = 0$, $\tfrac12\|\mathbf{w}\|^2=\tfrac14 = W$ ✓ (dualidad fuerte).

Tres puntos: (2,0)+, (0,2)+, (0,0)− por el dual

Óptimo dual: $\alpha_1=\tfrac12$, $\alpha_2=\tfrac12$, $\alpha_3=1$.

• Balance: $\tfrac12+\tfrac12-1=0$ ✓
• $\mathbf{w}=\tfrac12(2,0)+\tfrac12(0,2)-1\cdot(0,0) = (1,1)$ ✓
• $b = 1-(1,1)^\top(2,0) = -1$ ✓
• $W = \sum\alpha_i-\tfrac12\|\mathbf{w}\|^2 = 2-1 = 1$ = primal ✓
• Identidad gratis en margen duro: $\sum_i\alpha_i = \|\mathbf{w}\|^2 = 2$ ✓

$\mathbf{x}_4=(3,3)$ con $y_4f=5>1$ ⇒ por holgura complementaria $\alpha_4=0$: bórralo y nada cambia.

Encuentra el óptimo del dual a mano

Puntos (2,0)⁺, (0,2)⁺ y (0,0)⁻. La restricción Σαᵢyᵢ = 0 obliga a α₃ = α₁ + α₂, así que el dual depende de dos números. Mueve α₁ y α₂ hasta maximizar W(α); el mapa muestra W (color más intenso = mayor).

α₁ 0.2α₂ 0.7

α = (α₁, α₂, α₃)(0.20, 0.70, 0.90)

W(α)0.7400

w = Σ αᵢyᵢxᵢ(0.40, 1.40)

½‖w‖² (primal)1.0600

$$W(\alpha) = \sum_i\alpha_i - \tfrac12\|\textstyle\sum_i\alpha_iy_i\mathbf{x}_i\|^2 = 2(\alpha_1+\alpha_2) - \tfrac12\big[(2\alpha_1)^2 + (2\alpha_2)^2\big] = 0.7400$$

Como W = 2α₁ − 2α₁² + 2α₂ − 2α₂², cada término es una parábola con máximo en ½. Fuera del óptimo, el valor dual W(α) queda por debajo del primal ½‖w*‖² = 1 (dualidad débil): todo α factible da una cota inferior.

El dual del ejemplo de tres puntos, sin atajos

1. Productos internos: $\mathbf{x}_1^\top\mathbf{x}_1 = 4$, $\mathbf{x}_2^\top\mathbf{x}_2 = 4$, $\mathbf{x}_1^\top\mathbf{x}_2 = 0$, y todo producto con $\mathbf{x}_3 = (0,0)$ vale 0.
2. Restricción de balance: $\alpha_1 + \alpha_2 - \alpha_3 = 0 \Rightarrow \alpha_3 = \alpha_1 + \alpha_2$.
3. Término cuadrático: solo sobreviven $\alpha_1^2\cdot4 + \alpha_2^2\cdot4$ (los cruzados valen 0). Entonces $W = (\alpha_1+\alpha_2+\alpha_3) - \tfrac12(4\alpha_1^2+4\alpha_2^2) = 2\alpha_1 + 2\alpha_2 - 2\alpha_1^2 - 2\alpha_2^2$.
4. Derivadas: $\partial W/\partial\alpha_1 = 2 - 4\alpha_1 = 0 \Rightarrow \alpha_1 = \tfrac12$; igual $\alpha_2 = \tfrac12$; luego $\alpha_3 = 1$. Todos $\ge 0$ ✓.
5. $\mathbf{w} = \tfrac12(2,0) + \tfrac12(0,2) - 1\cdot(0,0) = (1,1)$; con el vector de soporte $\mathbf{x}_1$: $b = y_1 - \mathbf{w}^\top\mathbf{x}_1 = 1 - 2 = -1$.
6. Valores: $W(\boldsymbol\alpha) = 1 + 1 - \tfrac12 - \tfrac12 = 1$ y $\tfrac12\Vert\mathbf{w}\Vert^2 = 1$: brecha cero (dualidad fuerte). Los tres $\alpha_i > 0$: los tres puntos son vectores de soporte.

← AnteriorSiguiente paso →Ver todoReiniciar

¿Para qué molestarse con el dual?

• Kernels: los datos solo aparecen como $\mathbf{x}_i^\top\mathbf{x}_j$ → cámbialo por $K(\mathbf{x}_i,\mathbf{x}_j)$ y la frontera se curva gratis.
• Esparcidad explícita: la mayoría de $\alpha_i$ son exactamente 0 ⇒ modelo chico y predicción rápida.
• Intercambio de dimensión: $n$ variables sin importar $d$: gana cuando hay muchísimas features (texto, genómica).
• Interpretabilidad: $\alpha_i$ ordena qué tan influyente fue cada punto.
• Contra: necesita la matriz $n\times n$ de productos internos; con millones de puntos conviene el primal o SGD.

Autoevaluación

0/5 correctas · 0 respondidas Reiniciar

1. La holgura complementaria dice que…

a) todos los $\alpha_i$ son positivosb) $\alpha_i[y_if(\mathbf{x}_i)-1]=0$: o el precio es 0 o la restricción está activac) $\sum\alpha_i = 0$d) $b = 0$

2. El dual del SVM es un QP convexo.

a) Verdaderob) Falso

3. ¿Cuál es FALSA sobre reconstruir $\mathbf{w}$ y $b$?

a) $b$ queda indeterminado y se fija en 0 por convenciónb) $\sum_i\alpha_iy_i=0$ viene del término $b$c) $b = y_k - \mathbf{w}^\top\mathbf{x}_k$ con un vector de soported) $\hat y = \operatorname{sign}(\sum_i\alpha_iy_i\mathbf{x}_i^\top\mathbf{x}+b)$

4. La dualidad débil ($\max\min \le \min\max$)…

a) requiere convexidadb) vale para cualquier problemac) solo vale para el SVMd) implica brecha cero

5. En el dual, los datos aparecen solo como…

a) coordenadas crudasb) productos internos $\mathbf{x}_i^\top\mathbf{x}_j$c) distancias al origend) etiquetas

En código: mirar dentro del SVM entrenado

from sklearn.svm import SVC
import numpy as np

X = np.array([[2, 0], [0, 2], [0, 0], [3, 3]]); y = np.array([1, 1, -1, 1])
svm = SVC(kernel='linear', C=1e6).fit(X, y)   # C enorme ≈ margen duro

svm.support_            # índices de los vectores de soporte → [2, 0, 1] (no el (3,3))
svm.dual_coef_          # αᵢ·yᵢ de cada vector de soporte ≈ [[-1, 0.5, 0.5]]
svm.coef_, svm.intercept_   # ≈ w = (1, 1), b = −1 (tolerancia del solver)
w = svm.dual_coef_ @ svm.support_vectors_   # reconstruye w = Σ αᵢ yᵢ xᵢ

↔ Conexiones con otros temas

El truco del kernelCambiar xᵢᵀxⱼ por K(xᵢ, xⱼ) en este mismo dual.Margen suaveEl único cambio en el dual: 0 ≤ αᵢ ≤ C.Presupuesto vs penalizaciónPenalizar λΩ(w) equivale a restringir Ω(w) ≤ t: otra vez un multiplicador.Vectores de soporteAquí se prueba lo que allá era intuición: solo los postes sostienen la carpa.

Para profundizar

libroBoyd & Vandenberghe · Convex OptimizationCap. 5: dualidad y KKT (la base del SVM dual). Gratis en la web.apuntesStanford CS229 · Lecture notesNotas de Andrew Ng: GLMs, modelos generativos, SVM y kernels con derivaciones.videoStatQuest · lista SVMLas tres partes: ideas, kernel polinómico y kernel RBF.

Fuente ·ML_Course_SVM.pdf (slides 31–49) · ML_Course/session-06b-dual-and-kernel-trick.ipynb