Optimización convexa y condiciones de optimalidad

Elegimos x, y en C y un peso θ entre cero y uno. El punto θx+(1−θ)y recorre su segmento. C es convexo si todos esos puntos permanecen dentro, para cualquier pareja.

En varias coordenadas, la misma combinación se hace en cada una.

Intervalos, semiespacios y bolas de una norma son convexos. Intersectar conjuntos convexos conserva la propiedad porque el segmento pertenece a cada uno. La unión no la conserva necesariamente. Una circunferencia sin su interior no es lo mismo que el disco que incluye ese interior.

Sobre un dominio convexo, f es convexa si f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y) para todos los puntos y pesos permitidos. Primero promediamos las entradas y evaluamos; después comparamos con promediar sus valores. La cuerda usa exactamente la misma proporción.

Una función afín da igualdad siempre y es convexa y cóncava. Cambiar f por −f intercambia ambas propiedades. La forma de una pequeña parte de la gráfica no demuestra una condición que se pide en todo el dominio.

Minimizar una función convexa sobre un conjunto convexo es un problema convexo. Una representación suficiente usa desigualdades gᵢ≤0 con gᵢ convexas e igualdades afines. No hace falta que todas las restricciones sean lineales: los subniveles de funciones convexas también son convexos.

El sentido importa. Un supernivel de una función convexa puede no ser convexo; una igualdad no lineal tampoco garantiza convexidad. Maximizar una función convexa es otra tarea. Diagnosticamos el problema completo, incluido el dominio, antes de aplicar certificados.

Supongamos que x* es mínimo local y que existe un y factible con f(y)<f(x*).

Para t>0 pequeño está tan cerca de x* como queramos, y convexidad da f(x_t)≤(1−t)f(x*)+tf(y)<f(x*), contradicción. La prueba incluye mínimos en fronteras y no necesita derivadas.

La hipótesis combina convexidad del objetivo y del conjunto. Sin ella, un pozo cercano puede ser peor que otro más lejano. Un punto estacionario de una función arbitraria tampoco se convierte en mínimo por haber anulado su derivada.

Se deriva aplicando convexidad al segmento x+t(y−x), dividiendo la diferencia por t>0 y tomando t→0. El gradiente contiene las derivadas parciales y su producto con el desplazamiento es el cambio lineal previsto.

Si ∇f(x*)=0, la cota demuestra mínimo global sin restricciones. Para minimizar sobre C convexo, la condición ∇f(x*)ᵀ(y−x*)≥0 para todo y∈C basta. Bajo diferenciabilidad apropiada también es necesaria en un mínimo sobre C: las derivadas iniciales de todos los segmentos factibles no pueden ser negativas.

Si f es C² en un abierto convexo, es convexa exactamente cuando H(x) es semidefinida positiva en cada punto: vᵀH(x)v≥0 para todo vector v. La restricción a una recta tiene segunda derivada de esa forma. Positividad definida en todo punto implica estricta convexidad, pero no es una condición necesaria para ella.

Comprobar H solo en un punto informa de curvatura local. No prueba convexidad en todo el dominio. En particular, una segunda derivada cero no descarta un extremo: hay que seguir analizando. Esta distinción evita convertir una prueba suficiente en una regla falsa de clasificación.

La estricta convexidad sobre C convexo impide dos mínimos distintos: su punto medio tendría valor menor. Eso prueba a lo sumo uno. Para existencia podemos usar continuidad sobre un C compacto no vacío. Otra vía, en dimensión finita, es continuidad y coercividad sobre un C cerrado no vacío: f crece hacia más infinito cuando ‖x‖→∞ dentro del conjunto.

En el segundo caso, tomamos un punto factible x₀ y el subnivel f≤f(x₀). Es no vacío, cerrado y acotado, por tanto compacto; el mínimo que alcanza allí es también global. Si faltan las condiciones, puede existir un ínfimo finito sin ningún punto que lo alcance.

En un problema sin restricciones con mínimo existente y f fuertemente convexa de parámetro m>0, f(y)≥f(x)+gᵀ(y−x)+(m/2)‖y−x‖².

Además ‖x−x*‖≤‖g‖/m, por la monotonía fuerte del gradiente. Sin un m válido no se deducen esas cifras de un gradiente pequeño.

Sobre C compacto convexo, la cota tangente da f(x)−f*≤G(x), donde G(x)=max_{y∈C}∇f(x)ᵀ(x−y), para x factible. G mide si queda una dirección factible que mejore. En una frontera puede ser cero con gradiente no nulo. Las dos cotas responden a modelos y condiciones distintos.