Optimización no diferenciable

Para f propia convexa y finita en x, g es subgradiente si . El lado derecho es una recta o plano que toca en x y queda debajo globalmente. El conjunto de tales g se llama subdiferencial ∂f(x).

El conjunto ∂f(x) es cerrado y convexo; puede contener varios vectores o estar vacío en la frontera del dominio. Una función convexa finita en un entorno de x sí tiene subgradientes allí. No basta que una recta parezca quedar debajo en dos puntos de una tabla.

En cero no hay derivada ordinaria, pero sí un intervalo de soportes.

Cada g entre ambos extremos funciona en las dos regiones. Por eso ∂|·|(0)=[−1,1], sin elegir una pendiente única arbitraria.

Es la condición de Fermat convexa: certifica un mínimo global, incluidas esquinas y restricciones incorporadas al dominio.

Existencia y unicidad siguen siendo preguntas distintas. Subniveles compactos y semicontinuidad inferior, con función propia y valor ínfimo finito, dan existencia. Convexidad estricta da a lo sumo un minimizador, pero no garantiza que se alcance el ínfimo.

Si h es diferenciable, sumamos ∇h. Con dominios restringidos se requieren cualificaciones, como intersección de interiores relativos; no se presupone la igualdad en cualquier frontera.

Si f=maxᵢfᵢ con un número finito de funciones convexas diferenciables, su subdiferencial es la envolvente convexa de los gradientes activos, aquellos cuyo valor alcanza el máximo en ese punto. Un gradiente de una rama que queda por debajo no se añade automáticamente.

Para C convexo cerrado no vacío, su indicador vale cero en C e infinito fuera.

En x∈C, ∂(x)=(x)={n:⟨n,y−x⟩≤0 para todo y∈C}.

Son direcciones exteriores que la restricción puede equilibrar.

Bajo una regla de suma válida, minimizar f sobre C equivale a 0∈∂f(x)+(x). Si f es convexa diferenciable en un entorno de C, equivale a ⟨∇f(x),y−x⟩≥0 para todo y∈C. En una frontera el gradiente puede ser distinto de cero.

Así .

La parte cuadrática da estricta convexidad y coercividad; el mínimo existe y es único, incluidos los bordes a=±λ.

La iteración xₖ₊₁=xₖ−αₖgₖ, con gₖ∈∂f(xₖ) y αₖ>0, usa una pendiente de soporte. A diferencia del gradiente suave con paso adecuado, la dirección −gₖ no asegura que f baje para toda elección admisible.

Si se imponen restricciones convexas cerradas, proyectamos el nuevo punto sobre ellas. Para garantías hacen falta mínimo existente, un control de los subgradientes y una regla de pasos apropiada. Se controla el mejor valor visitado o ciertos promedios; no se promete una bajada monótona de cada valor.

Expandimos ||xₖ−αₖgₖ−x*||².

Si hay proyección sobre un convexo que contiene x*, su no expansión no empeora la cota de distancia.

Sumar y descartar la distancia final no negativa produce .

La garantía se refiere al mejor valor, no al descenso de cada iteración.

Para f propia convexa semicontinua inferior en ℝⁿ y λ>0, existe y es único. El término cuadrático y un minorante afín de f dan coercividad; la estricta convexidad da unicidad.

Con f=|·| da el umbral suave; con f= da proyección euclídea sobre el convexo cerrado no vacío C. El parámetro λ multiplica f si escribimos de forma equivalente λf(u)+||u−a||²/2.

Para F=h+f, con h convexa diferenciable y gradiente L-Lipschitz, f propia convexa semicontinua inferior y mínimo existente, el paso es . Una elección 0<α≤1/L, con L>0, da el marco usual de descenso y convergencia de valores; no se traslada sin revisar hipótesis.

En problemas no convexos se usan otras subdiferenciales, como Clarke, y distintas condiciones estacionarias. La presencia del cero ya no certifica por sí sola un mínimo global. El certificado global que hemos usado viene de convexidad y soporte, no de la palabra subgradiente.