∇Optimización — Teoría por niveles

Bachillerato — Optimización elemental

Objetivo: modelar situaciones reales, usar derivadas y/o métodos gráficos (programación lineal en 2 variables) para encontrar máximos y mínimos con sentido.

¿Qué es optimizar? Extremos con derivadas Programación lineal (método gráfico) Desigualdades útiles (AM-GM) Modelado paso a paso Ejercicios propuestos

¿Qué es optimizar?

Optimizar es elegir la mejor alternativa según un criterio (máximo beneficio, mínimo coste, mínima distancia…). Siempre hay tres piezas: (1) variables de decisión, (2) función objetivo y (3) restricciones. Con ellas formamos un problema de optimización.

Plantilla → Variables: x,y,…; Objetivo: maximizar/minimizar f(x,y,…); Restricciones: gᵢ(x,y,…) ≤/=/≥ bᵢ y dominios.

Extremos con derivadas (una variable)

En un intervalo cerrado [a,b], un extremo global ocurre en puntos críticos (f′=0 o no derivable) o en los extremos a,b. Clasifica con tabla de signos de f′ o con f″.

Ejemplos resueltos (10)

  1. Rectángulo de perímetro fijo P: ¿máximo área?Área A=x(P/2−x)=−x²+(P/2)x ⇒ A′=−2x+P/2=0 ⇒ x=P/4 ⇒ cuadrado. Conclusión: el cuadrado maximiza área con perímetro fijo.
  2. Minimiza S(x)=x+9/x para x>0.S′=1−9/x²=0 ⇒ x=3 ⇒ S(3)=6. Por AM-GM, S≥2√(9)=6 (se verifica).
  3. Caja sin tapa desde cuadrado 30×30 cm cortando esquinas de lado x.V(x)=x(30−2x)²; V′=0 ⇒ x≈5 cm da el máximo (comprobar con f″ o tabla).
  4. Distancia mínima de (2,0) a y=x².Minimiza D²=(x−2)²+(x²−0)² ⇒ (D²)′=2(x−2)+4x³=0 ⇒ 2x−4+4x³=0 ⇒ solución numérica x≈0,879 ⇒ D≈1,41.
  5. Optimiza el área de un corral pegado a un muro con 40 m de valla.Si el muro hace de un lado, perímetro 2x+y=40, área A=xy ⇒ y=40−2x ⇒ A=40x−2x² ⇒ máximo en x=10 ⇒ y=20.
  6. Máximo de f(x)=x√(12−x²) en [0,√12].f′=√(12−x²)+x(−x/√(12−x²))=0 ⇒ 12−x²=x² ⇒ x=√6 ⇒ f=6.
  7. Máximo beneficio B(q)=−2q²+40q−75.Parábola cóncava: vértice q=−b/2a=40/4=10 ⇒ B(10)=125.
  8. Tiempo mínimo en una playa: correr (v₁) y nadar (v₂).Principio de Snell 1D con derivadas: senθ₁/v₁ = senθ₂/v₂ → punto óptimo donde cambia de medio.
  9. Máximo producto con suma fija: x+y=12, x,y>0.Producto P=xy ⇒ y=12−x ⇒ P=12x−x² ⇒ máximo en x=6 ⇒ P=36 (y=6). También AM-GM: P≤(6)².
  10. Modelo de crecimiento con saturación: C(t)=At e^{−kt}.Máximo cuando C′=0 ⇒ A e^{−kt}(1−kt)=0 ⇒ t*=1/k.

Programación lineal en 2 variables (método gráfico)

Objetivo y restricciones lineales. Se grafica la región factible y el óptimo está en un vértice.

Ejemplos resueltos (5)

  1. Max z=3x+2y s.a. x+2y≤14, 3x+y≤18, x,y≥0.Vértices: (0,0),(0,7),(6,0),(4,5). Evalúa: z=0,14,18,3·4+2·5=22 ⇒ óptimo (4,5), z=22.
  2. Min c=5x+4y s.a. x+y≥8, x≥2, y≥3.Vértices relevantes: (2,6),(5,3),(2,3) no cumple x+y≥8. Evalúa: c(2,6)=32; c(5,3)=37 ⇒ mínimo (2,6).
  3. Max beneficio con horas de máquina y mano de obra.Plantea restricciones del tipo 2x+y≤40, x+3y≤45; solución en cruce → x=15, y=10; z=3·15+2·10=65.
  4. Max z=7x+5y s.a. x≤10, y≤8, 2x+3y≤30.Vértices: (0,0),(10,0),(0,8),(9,4) ⇒ mejor (9,4): z=7·9+5·4=83.
  5. Min c= x+y con x+2y≥10, 3x+y≥12, x,y≥0.Vértice de cruce: x=14/5, y=8/5 ⇒ c=22/5=4,4.

Desigualdades útiles: AM-GM y Cauchy

Para a,b>0, AM-GM: (a+b)/2 ≥ √(ab). Útil para acotar y hallar mínimos. Cauchy-Schwarz: (∑aᵢbᵢ)² ≤ (∑aᵢ²)(∑bᵢ²).

Ejemplos resueltos (3)

  1. Minimiza x+16/x, x>0.≥2√16=8; se logra en x=4.
  2. Maximiza xy con x+y fijo.xy ≤ ((x+y)/2)² (AM-GM) ⇒ máximo cuando x=y.
  3. Cota superior de 3x+4y si x²+y²≤1.Por Cauchy: (3x+4y)² ≤ (3²+4²)(x²+y²) ≤ 25 ⇒ 3x+4y ≤5.

Modelado paso a paso

  1. Define variables (qué controlas).
  2. Escribe el objetivo (qué mides).
  3. Construye restricciones realistas.
  4. Resuelve (derivadas o método gráfico).
  5. Interpreta y verifica unidades / sentido.

Ejercicios propuestos (con respuestas)

  1. Valla: 120 m para un rectángulo pegado a un río (un lado gratis). Máximo área.Sol: 2x+y=120 ⇒ A=xy ⇒ x=30, y=60, A=1800 m².
  2. Min de f(x)=x+25/x, x>0.x=5 ⇒ mínimo 10.
  3. PL: max z=2x+5y; x+2y≤10; 3x+y≤12; x,y≥0.Óptimo (x,y)=(2,4) ⇒ z=24.
  4. Distancia mínima de (3,1) a y=1/x (x>0).Minimiza D²=(x−3)²+(1/x−1)² ⇒ x≈1,618.
  5. Max de volumen de una lata de área lateral fija 200π: V=πr²h.h= A/(2πr)=100/r ⇒ V=πr²(100/r)=100πr ⇒ crece con r → falta restricción de tapas; si total fija, óptimo h=2r.
  6. Maximiza producto de tres positivos con suma 30.Por AM-GM, máximo en 10,10,10 ⇒ 1000.
  7. Min de costo C(q)=q²−14q+60 en [0,20].vértice q=7 ⇒ C=11 (dentro del intervalo).
  8. PL: min x+y con x≥4, y≥2, x+3y≥18.Vértice (12,2) ⇒ 14.
  9. Punto del círculo x²+y²=25 que maximiza 3x+4y.Dirección (3,4) ⇒ (x,y)=5(3,4)/5=(3,4) ⇒ valor 25.
  10. Encuentra k para que f(x)=x³−3kx tenga extremo relativo en x=2.f′=3x²−3k ⇒ f′(2)=0 ⇒ k=4.
  11. Minimiza tiempo T(x)= √(x²+9)/2 + √((12−x)²+16)/1 (dos medios).x≈5,7.
  12. Diseña una caja de volumen 1000 cm³ con mínimo material (caja con tapa).Resultado cercano a cubo: lado ≈ 10 cm.

Universidad — Optimización de varias variables

Gradiente, Hessiano, multiplicadores de Lagrange, programación lineal y métodos básicos (descenso, Newton).

Sin restricciones Con Lagrange Convexidad y condiciones de segundo orden LP y Simplex (visión) Métodos de gradiente / Newton Ejercicios propuestos

Óptimos sin restricciones

f∈C². Candidatos: ∇f=0. Clasifica con el Hessiano H. Si H≻0 ⇒ mínimo local; H≺0 ⇒ máximo; si H indefinido ⇒ silla.

Ejemplos resueltos (7)

  1. f(x,y)=x²+xy+y².∇f=(2x+y, x+2y)=0 ⇒ (0,0). H=[[2,1],[1,2]]≻0 ⇒ mínimo global en (0,0).
  2. f(x,y)=x²−y².∇f=(2x,−2y)=0 ⇒ (0,0). H diag(2,−2) indefinido ⇒ punto de silla.
  3. f(x,y)=x⁴+y⁴−4xy.∇f=(4x³−4y, 4y³−4x)=0 ⇒ soluciones simétricas x=y, etc. En x=y, 4x³−4x=0 ⇒ x∈{−1,0,1}. Clasificar con H.
  4. Distancia mínima de (a,b) a la parábola y=x².Minimiza g(x)= (x−a)²+(x²−b)². Resuelve g′(x)=0 numéricamente.
  5. Ajuste cuadrático: min f(m)=∑(yᵢ−mxᵢ)².f′(m)=−2∑xᵢ(yᵢ−mxᵢ)=0 ⇒ m= (∑xᵢyᵢ)/(∑xᵢ²).
  6. Newton en f(x)=x³−2.x_{k+1}=x_k − (x_k³−2)/(3x_k²). Con x₀=1.5 converge a ³√2.
  7. Descenso por gradiente en f(x)=1/2‖Ax−b‖².x_{k+1}=x_k−αAᵀ(Ax_k−b). Con 0<α<2/λ_max(AᵀA) converge linealmente.

Óptimos con restricciones: Lagrange

Para g(x)=0, resuelve ∇f=λ∇g con g=0. Para varias restricciones de igualdad, multiplica por λᵢ. Las desigualdades requieren KKT (ver abajo).

Ejemplos resueltos (6)

  1. Maximiza f(x,y)=xy s.a. x+y=10.∇f=(y,x)=λ(1,1) ⇒ y=x, x+y=10 ⇒ (5,5), f=25.
  2. Mínima distancia del punto (2,0) a la elipse x²/9+y²/4=1.L= (x−2)²+y² + λ(x²/9+y²/4−1). Sistema ⇒ solución ≈(1.62,1.17).
  3. Max 3x+4y con x²+y²=25.∇f=(3,4)=λ(2x,2y) ⇒ (x,y)= (3,4) ⇒ valor 25.
  4. Min f(x,y)=(x−1)²+(y−2)² con g=x+y−1=0.∇f=(2(x−1),2(y−2))=λ(1,1) y g=0 ⇒ (x,y)=(0.5,0.5).
  5. Isoperimétrico discreto: máximo área de rectángulo con perímetro P.L clásico → cuadrado.
  6. Cilindro de volumen fijo V: minimiza área total.A=2πr²+2πrh, V=πr²h ⇒ h=V/(πr²). A(r)=2πr²+2V/r ⇒ A′=4πr−2V/r²=0 ⇒ h=2r.

Convexidad y condiciones de óptimo

Si f es convexa y el dominio es convexo, todo mínimo local es global. Para f∈C², f convexa ⇔ H≽0. Restricciones convexas + f convexa ⇒ problema convexo.

Programación lineal (visión rápida del Simplex)

Los LP buscan max/min de cᵀx con Ax≤b, x≥0. El óptimo está en un vértice. Simplex avanza de vértice en vértice mejorando cᵀx.

Métodos numéricos básicos

Ejercicios propuestos (con respuestas)

  1. Clasifica los críticos de f(x,y)=x³−3xy².∇f=(3x²−3y², −6xy)=0 ⇒ puntos (0,0) y x=±y≠0. Clasificación estándar (silla en (0,0)).
  2. Min de f(x,y)=x²+y²−2x−4y s.a. x+y=1.L ⇒ (x,y)=(1/2,1/2).
  3. PL: max z=4x+3y s.a. x+2y≤8; 3x+y≤9; x,y≥0.Vértice óptimo (3,2) ⇒ z=18.
  4. Hessiano de f(x,y)=e^{x}+y⁴ y convexidad.H diag(e^{x}, 12y²) ≽ 0 ⇒ f convexa.
  5. Un paso de Newton para f(x)=x²−10 en x₀=3.x₁=3−(9−10)/6≈3.1667.
  6. Descenso con α=1/L en f(x)=1/2‖Ax−b‖².Con L=λ_max(AᵀA) da mejor cota lineal.

Máster — Optimización convexa y algoritmos de primer/segundo orden

Dualidad, KKT, métodos de primer orden (GD acelerado, proximal), interior-point y programación cuadrática.

Convexidad avanzada y dualidad KKT y Slater Métodos de primer orden Operadores proximales Métodos de punto interior Ejercicios propuestos

Convexidad avanzada y dualidad

Dual de Lagrange: L(x,λ,ν)=f(x)+∑λᵢgᵢ(x)+∑νⱼhⱼ(x). Función dual q(λ,ν)=infₓ L. Brecha dual ≥0; con Slater puede cerrarse.

Condiciones KKT

Métodos de primer orden

Operadores proximales

prox_{τh}(v)=argminₓ { h(x)+ (1/2τ)‖x−v‖² }. Ej.: h(x)=λ‖x‖₁ ⇒ soft-thresholding: S_{λτ}(v)=sign(v)·max(|v|−λτ,0).

Punto interior (idea)

Para gᵢ(x)≤0, resuelve min f(x)−(1/t)∑log(−gᵢ(x)) con t creciente. Sigue la central path hasta converger.

Ejemplos resueltos (6)

  1. Dual de Lasso: min 1/2‖Ax−b‖²+λ‖x‖₁.Dual: max −1/2‖y‖²−bᵀy s.a. ‖Aᵀy‖_∞≤λ. KKT conecta signos con soporte.
  2. Deriva Nesterov para f convexa L-suave.Esquema: y_k=x_k+β_k(x_k−x_{k−1}); x_{k+1}=y_k−(1/L)∇f(y_k); β_k=(k−1)/(k+2).
  3. Prox de norma ℓ₂: h(x)=λ‖x‖₂.prox(v)= (1−λτ/‖v‖₂)_+ v.
  4. QP: min 1/2 xᵀQx + cᵀx s.a. Ax≤b, Q≻0.Único óptimo; resuelve con KKT o IPM.
  5. SGD con tasa α_k=α₀/√k en ERM.Convergencia en expectativa a óptimo para convexa.
  6. Barrera log para x>0 en min −∑log xᵢ.Newton con Hessiano diag(1/xᵢ²).

Ejercicios propuestos (con respuestas abreviadas)

  1. Demuestra que f(x)=e^{ax} es convexa para todo a.f″=a²e^{ax}≥0.
  2. Obtén KKT para min x²+y² s.a. x+y≥1, x≥0,y≥0.Activas en óptimo: x=y=1/2, λ₁>0, λ₂=λ₃=0.
  3. Prox de h(x)=λ‖x‖₁.Soft-thresholding componente a componente.
  4. Demuestra O(1/k) para GD en convexa L-suave.Usa desigualdad de cocoercividad de ∇f.
  5. Diseña un IPM para LP estándar.Introduce barrera −∑log s y condiciones centrales.
  6. Deriva el dual de SVM lineal duro.max ∑αᵢ − 1/2 ∑αᵢαⱼyᵢyⱼ xᵢᵀxⱼ s.a. αᵢ≥0, ∑αᵢyᵢ=0.

Doctorado — Tópicos avanzados y fronteras

No convexo, subgradientes, proximal avanzado, ADMM, tasas de convergencia, optimización estocástica moderna.

Subgradientes y no suavidad Proximal avanzado y splitting ADMM y penalizaciones No convexo y paisaje Complejidad y tasas Ejercicios/desafíos

Subgradientes

Para f convexa no diferenciable, g es subgradiente en x si f(y)≥f(x)+gᵀ(y−x). Método de subgradientes: x_{k+1}=x_k−α_k g_k; requiere reglas de paso decrecientes (p.ej. α_k=α₀/√k).

Splitting y proximal

ADMM

Para min f(x)+g(z) s.a. Ax+Bz=c. Itera: x^{k+1}=argmin f(x)+(ρ/2)‖Ax+Bz^k−c+u^k‖²; z^{k+1}=argmin g(z)+(ρ/2)‖Ax^{k+1}+Bz−c+u^k‖²; u^{k+1}=u^k+Ax^{k+1}+Bz^{k+1}−c.

No convexo

Tasas y complejidad

Desafíos / ejercicios cortos (con ideas)

  1. Demuestra convergencia de FISTA para g L-suave y h proper, l.s.c.Idea: potencial con secuencia {t_k} y desigualdad de tres puntos.
  2. Aplica ADMM a Lasso separando x=z.Deriva soft-thresholding en subproblema de z.
  3. Demuestra que GD con ruido isotrópico escapa de sillas estrictas.Idea: direcciones de curvatura negativa y perturbaciones.
  4. Ejemplo no convexo con mínimos locales: f(x)=x⁴−3x²+2x.Analiza críticos y valores globales.
  5. Diseña regla adaptativa de ρ en ADMM para acelerar.Usa residual primal/dual balanceados.