Optimización Convexa

Mauricio Junca

Índice
1. Preliminares de cálculo 2

2. Criterios básicos de optimalidad 6

2.1. Mı́nimos globales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2. Funciones suaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3. Métodos numéricos para optimización suave 9

3.1. Métodos de búsqueda lineal - Caso general . . . . . . . . . . . . . . . . . . . 9
3.2. Método de región de confianza - Caso general suave . . . . . . . . . . . . . . 18

4. Conjuntos y funciones convexas 24

4.1. Conjuntos convexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2. Funciones convexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5. Optimización convexa suave 30

1
5.1. Método del descenso del gradiente - Caso C convexo . . . . . . . . . . . . . 30
5.1.1. Caso fuertemente convexo . . . . . . . . . . . . . . . . . . . . . . . . 32
5.2. Método acelerado de Nesterov . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.3. Método de (Quasi-)Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.3.1. Caso fuertemente convexo C 2 . . . . . . . . . . . . . . . . . . . . . . 35
5.3.2. Caso self-concordant . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

6. Conceptos básicos de análisis convexo 36

6.1. Subgradientes I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.2. Teoremas de separación I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6.3. Subgradientes II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.3.1. Cálculo con subgradientes . . . . . . . . . . . . . . . . . . . . . . . . 44
6.4. Teoremas de separación II . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.5. Funciones conjugadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

7. Optimización convexa no suave 49

7.1. Método del subgradiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
7.2. Método del (sub)gradiente estocástico . . . . . . . . . . . . . . . . . . . . . . 52
7.3. Método del gradiente proximal . . . . . . . . . . . . . . . . . . . . . . . . . . 54

1
8. Programación lineal 57
8.1. Conos y poliedros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
8.2. Dualidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

9. Problemas convexos generales 62

9.1. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
9.1.1. Programación cuadrática . . . . . . . . . . . . . . . . . . . . . . . . . 63
9.1.2. Programación cónica . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
9.1.3. Programación seminfinita - Problema de momentos . . . . . . . . . . 65
9.2. Puntos de silla y condiciones KKT . . . . . . . . . . . . . . . . . . . . . . . 66
9.3. Dualidad fuerte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
9.3.1. Prueba del teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

[Link]́n con restricciones 72

10.1. Minimización con restricciones de igualdad . . . . . . . . . . . . . . . . . . . 73
10.2. Método de barrera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
10.2.1. Cono semidefinido positivo . . . . . . . . . . . . . . . . . . . . . . . . 76
10.3. Método primal-dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
10.3.1. Programación lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
10.3.2. Programación cuadrática . . . . . . . . . . . . . . . . . . . . . . . . . 81
10.3.3. Programación semidefinida . . . . . . . . . . . . . . . . . . . . . . . . 82

1. Preliminares de cálculo
Sea U ⇢ Rn abierto y f : U 7! R. Dado x 2 U , si el siguiente lı́mite existe

f (x1 , . . . , xi + t, . . . , xn ) f (x)
lı́m ,
t!0 t
@f
lo denotamos como @x i
(x) y la llamamos derivada parcial de f con respecto a xi . Si todas
las derivadas parciales existen, llamamos al vector rf (x) cuyas entradas son las derivadas
parciales gradiente de f en x. La derivada direccional de f en x en la dirección d 2 Rn está
dada por
f (x + td) f (x)
f 0 (x; d) := lı́m ,
t#0 t
@f
siempre que exista. Notemos que f 0 (x; ei ) = @xi
(x), donde ei es el i-ésimo vector canónico.

Definición. Decimos que f es Gâteaux diferenciable en x 2 U si la derivada direccional

f 0 (x; d) existe para toda d 2 Rn y además es una función lineal en d.

Notemos que si f es Gâteaux diferenciable en x, entonces para d 2 Rn se tiene que

f 0 (x; d) = f 0 (x; d1 e1 + . . . + dn en ) = d1 f 0 (x; e1 ) + . . . + dn f 0 (x; en ) = hrf (x), di.

2
Definición. Decimos que f es Fréchet diferenciable en x 2 U si existe una función lineal
` : Rn 7! R, es decir, si existe ` 2 Rn tal que `(x) = h`, xi, tal que

f (x + h) f (x) h`, xi
lı́m = 0.
khk!0 khk

Otra forma equivalente de diferenciabilidad en el sentido de Fréchet es decir que

f (x + h) = f (x) + h`, xi + o(khk).

Veamos algunas propiedades y relaciones de las diferentes nociones de diferenciabilidad.

1. Si f es Fréchet diferenciable en x entonces f es continua en x.

2. Si f es Fréchet diferenciable en x, entonces f es Gâteaux diferenciable y además ` =

rf (x). Esto se sigue de tomar h = tei para cada i con t > 0. Ası́ que

f (x + h) = f (x) + hrf (x), hi + o(khk).

3. El converso no es cierto. (Ejercicio)

4. Sea f Gâteaux diferenciable en U y sean x, y 2 U tales que el segmento que une a x con
y, que lo notamos como [x, y], esté contenido en U . Sea g(t) = f (x + t(y x)) para t 2
[0, 1], entonces g es una función diferenciable y además g 0 (t) = hrf (x+t(y x), y x)i.
Por el teorema de valor medio existe t̄ tal que g(1) g(0) = g 0 (t̄), es decir, existe
z 2 [x, y] tal que f (y) f (x) = hrf (z), y xi. Esto no es más que el Teorema del
Valor Medio.
De lo anterior, si además asumimos que todas las derivadas parciales son continuas en
x, se tiene que para todo h 2 Rn tal que el segmento [x, x+h] ⇢ U existe xh 2 [x, x+h]
tal que

f (x + h) f (x) hrf (x), hi = hrf (xh ) rf (x), hi = o(khk),

dado que la continuidad de las derivadas implica que

|hrf (xh ) rf (x), hi|

lı́m  lı́m krf (xh ) rf (x)k = 0.
khk!0 khk khk!0

Es decir, f es Fréchet diferenciable en x. Lo anterior motiva la siguiente definición.

Definición. Si f : U 7! R es Gâteaux diferenciable en U y rf es continua en U , decimos

que f 2 C 1 (U ).

Las definiciones anteriores las podemos extender al caso vectorial, es decir, cuando F :
U 7! Rm . En este caso, si F es Gâteaux diferenciable, entonces para toda d 2 Rn la derivada
direccional en x satisface que
F 0 (x; d) = Ad,

3
donde A es una matriz de m ⇥ n cuyas entradas están dadas por Aij = @F@xi (x)
j
, la llamamos
la matriz Jacobiana de F en x y la denotamos como DF (x). Si F es Fréchet diferenciable
en x 2 U , entonces
kF (x + h) F (x) DF (x)hk
lı́m = 0.
khk!0 khk
Ahora, si f : U 7! R y rf es Gâteaux diferenciable en x, entonces llamamos la matriz
Hessiana de f en x a Hf (x) := D2 f (x) := D(rf )(x) con entradas

@ 2f
Hf (x)ij = (x).
@xi @xj

Si además las entradas de la matriz Hessiana son continuas en U , decimos que f 2 C 2 (U ).

En este caso sabemos que la matriz es simétrica.

Fórmula de Taylor

Si f 2 C 2 (U ) y x, y 2 U son tales que [x, y] ⇢ U , entonces existe z 2 [x, y] tal que

1
f (y) = f (x) + hrf (x), y xi + hHf (z)(y x), y xi.
2
Otra forma equivalente de escribir la fórmula de Taylor de segundo orden de f es la siguiente:
Para todo h 2 Rn tal que el segmento [x, x + h] ⇢ U se tiene que
1
f (x + h) = f (x) + hrf (x), hi + hHf (x)h, hi + o(khk2 ).
2

Ejemplo. Consideremos la función cuadrática

1
f (x) = hAx, xi + hb, xi + c,
2
con A matriz simétrica. En este caso es fácil ver que rf (x) = Ax + b y Hf (x) = A.

Para el siguiente ejemplo necesitamos algunos resultados sobre matrices simétricas semi-
definidas positivas. Recordemos que una matriz simétrica de n⇥ A es semidefinida positiva,
y lo notamos como A ⌫ 0, si para todo x 2 Rn se tiene que hAx, xi 0, y es definida
positiva (A 0) si la desigualdad es estricta para todo x 6= 0. Como A es simétrica, el
teorema espectral garantiza que existen matrices diagonal ⇤ y ortogonal Q que diagonalizan
a A = Q⇤QT . Luego
hAx, xi = h⇤QT x, QT xi.
Esto implica que A ⌫ 0 si y solo si ⇤ ⌫ 0 y lo último es equivalente si y solo si las
entradas de la diagonal ⇤ son no negativas. Ası́ que los valores propios de A son no negativos.
Análogamente A 0 si y solo si sus valores propios son positivos. Además, se tiene que
2 2
mı́n (A)kxk  hAx, xi  máx (A)kxk .

4
 Figura 1: Cálculo del gradiente y la segunda derivada de la función ln det(X).

Ejemplo. Consideremos ahora un ejemplo más elaborado. Recordemos que en el espacio

vectorial de las matrices cuadradas de n ⇥ n se puede definir naturalmente el producto
interno X
hX, Y i := xij yij = tr(X T Y ) = tr(Y T X).
i,j

Si solo consideramos el subespacio de matrices simétricas, es claro que hX, Y i = tr(XY ) =

5
tr(Y X). Del subespacio anterior vamos a considerar el subconjunto abierto U = {X : X
0}, es decir, el conjunto de matrices simétricas definidas positivas. Sea f : U 7! R definida
como
f (X) = ln det(X).
Esta es una función muy importante en el estudio de la programación semidefinida. Queremos
calcular rf y D2 f . Ver Figura 1.

2. Criterios básicos de optimalidad

En esta sección vamos a introducir los primeros conceptos, resultados y algoritmos de
optimización sin restricciones para funciones suaves. Vamos a denotar Br (x) = {y 2 Rn :
kx yk  r}.

Definición. Sea f : U 7! R con U ⇢ Rn abierto. Decimos que x 2 U es

un mı́nimo local de f si existe r > 0 tal que f (x)  f (y) para todo y 2 Br (x) y mı́nimo
local estricto si la desigualdad es estricta para todo y 6= x,

un mı́nimo global de f su f (x)  f (y) para todo y 2 U y mı́nimo global estricto si la

desigualdad es estricta para todo y 6= x,

un punto crı́tico de f si es Gâteaux diferenciable en x y rf (x) = 0.

2.1. Mı́nimos globales

El primer criterio para la existencia de mı́nimos globales es el teorema de Weierstrass.
Este dice que si f : K 7! R es continua y K es compacto, entonces existe x⇤ que es mı́nimo
global. Existen versiones más débiles de este teorema como la siguiente.

Teorema (Weierstrass). Sea f : U 7! R continua tal que existe un ↵ 2 R para el cual el

conjunto de nivel L↵ = {x 2 U : f (x)  ↵} es no vacı́o y compacto. Entonces existe x⇤ 2 U
mı́nimo global.

Prueba. Sean f ⇤ = ı́nf f (x) y {xk } ⇢ U sucesión minimizadora de f , es decir, f (xk ) ! f ⇤ .

x2U
Asumimos también que la sucesión está contenida en L↵ , y como es compacto, existe una
subsucesión convergente en L↵ , es decir, xkn ! x⇤ . Por la continuidad de f se tiene además
que f (xkn ) ! f (x⇤ ) = f ⇤ , luego x⇤ es un mı́nimo global.

Definición. Sea U no acotado, decimos que es coerciva si f (x) ! 1 cuando kxk ! 1.

Notemos que si f es continua entonces L↵ debe ser cerrado para todo ↵ 2 R. Además,
si f es coerciva todo conjunto de nivel debe ser acotado, ası́ que si f es continua y coerci-
va garantizamos las condiciones del teorema anterior. Ahora, la continuidad de la función
tampoco es necesaria para tener que los conjuntos de nivel sean cerrados, veamos.

6
 Definición. Una función f : Rn 7! R [ {+1} es semicontinua por debajo en x 2 Rn si

f (x)  lı́m inf f (xk ),

k!1

para toda sucesión tal que xk ! x. Es semicontinua por debajo en Rn si lo es para todo x.

Definición. Sea f : Rn 7! R [ {+1}. El epı́grafo de f se define como

epi(f ) = {(x, t) 2 Rn ⇥ R : f (x)  t}.

Teorema. Sea f : Rn 7! R [ {+1}. Las siguientes son equivalentes;

1. f es semicontinua por debajo en Rn .

2. epi(f ) es cerrado.

3. Los conjuntos de nivel L↵ son cerrados para todo ↵ 2 R.

Prueba.

1. =) 2. Sea {(xk , tk )} ⇢ epi(f ) una sucesión que converge a (x, t). Queremos ver que (x, t) 2
epi(f ), es decir, que f (x)  t. Puesto que xk ! x se tiene, por ser f semicontinua por
debajo, que
f (x)  lı́m inf f (xk )  lı́m inf tk = t.
k!1 k!1

2. =) 3. Sea ↵ 2 R y sea {xk } ⇢ L↵ que converge a x. Entonces {(xk , ↵)} ⇢ epi(f ), y como es
cerrado, entonces (x, ↵) 2 epi(f ), es decir, x 2 L↵ .

3. =) 1. Supongamos que existe una sucesión {xk } que converge a x tal que f (x) > lı́m inf f (xk )
k!1
y sea ↵ tal que f (x) > ↵ > lı́m inf f (xk ). Por lo tanto existe una subsucesión {xkn }
k!1
tal que f (xkn )  ↵ para toda n, es decir, que está contenida en L↵ . Como el conjunto
de nivel es cerrado y la subsucesión converge a x, entonces f (x)  ↵ y tenemos una
contradicción.

Con lo anterior tenemos entonces que si f es semicontinua por debajo en Rn y coerciva,

entonces tiene un mı́nimo global.

2.2. Funciones suaves

Pasemos ahora a resultados en donde vamos a asumir que f es suave. Los siguientes
resultados se basan en el teorema de Taylor. Siempre vamos a asumir que f : U 7! R con U
abierto.

Teorema (Condición necesaria de primer orden para mı́nimo local). Si f es Gâteaux dife-
renciable en U , entonces todo mı́nimo local es un punto crı́tico.

7
Prueba. Sea x mı́nimo local de f y sea d 2 Rn . Entonces
f (x + td) f (x)
f 0 (x; d) = lı́m 0
t#0 t
pues x es mı́nimo local. Ası́ que tomando d = rf (x) se tiene que 0  hrf (x), di =
krf (x)k lo que implica que rf (x) = 0.
Teorema (Condición de necesaria segundo orden para mı́nimo local). Sea f 2 C 2 (U ). Si x
es mı́nimo local entonces la matriz Hf (x) es semidefinida positiva.
Prueba. Sabemos que para todo x 2 U existen rf (x) y matriz simétrica Hf (x) tal que para
todo h 2 Rn se tiene que
t2
f (x + th) = f (x) + thrf (x), hi + hHf (x)h, hi + o(t2 ).
2
Por el teorema anterior se tiene además que rf (x) = 0, ası́ que
t2
0  f (x + th) f (x) = hHf (x)h, hi + o(t2 ),
2
y al dividir por t2 y haciendo t ! 0 se obtiene que hHf (x)h, hi 0.
Teorema (Condición suficiente de segundo orden para mı́nimo local estricto). Sea f 2
C 2 (U ). Si x es un punto crı́tico de f y Hf (x) es definida positiva, entonces x es un mı́nimo
local estricto.
Prueba. Sea > 0 el valor propio mı́nimo de la matriz Hessiana Hf (x), tenemos entonces
que hHf (x)d, di kdk2 para todo d 2 Rn . Usando el teorema de Taylor tenemos que para
d 2 Rn con kdk suficientemente pequeño se tiene que
1
f (x + d) = f (x) + hrf (x), di + hHf (x)d, di + o(kdk2 )
✓ 2 ◆
2
2 o(kdk )
f (x) + kdk +
2 kdk2
> f (x).

Por último tenemos una condición suficiente para un mı́nimo global, veremos que esto
está relacionado con el concepto de convexidad.
Teorema (Condición suficiente de segundo orden para mı́nimo global). Sea f 2 C 2 (U ) tal
que la matriz Hessiana Hf (z) ⌫ 0 para todo z 2 U . Si x 2 U es un punto crı́tico de f tal
que para todo y 2 U el segmento [x, y] ⇢ U , entonces es mı́nimo global.
Prueba. Sea y 2 U , a partir del teorema de Taylor tenemos que existe z 2 (x, y) tal que
1
f (y) = f (x) + hHf (z)(y x), y xi f (x).
2

En el resultado anterior, si la matriz Hessiana es definida positiva, entonces x es un

mı́nimo global estricto.

8
3. Métodos numéricos para optimización suave
Ahora vamos ver métodos numéricos para resolver el siguiente problema sin restricciones
mı́n f (x),
x2Rn

imponiendo diferentes condiciones para f , pero siempre vamos a asumir que existe un va-
lor mı́nimo denotado por f ⇤ . Existen dos grandes familias de métodos de minimización si
restricciones:
de búsqueda lineal
de región de confianza
Ahondaremos principalmente en la primera familia, considerando diferentes condiciones
para f . Primero veremos el caso cuando f es una función suave (C 1 y C 2 ).

3.1. Métodos de búsqueda lineal - Caso general

Inicialmente supongamos que f : Rn ! R con f 2 C 1 (Rn ). Adicionalmente, vamos a
pedir que rf (·) sea Lipschitz con constante L, es decir, para todo x, y 2 Rn se cumple que
krf (x) rf (y)k  Lkx yk.
En cada iteración de los métodos de búsqueda lineal se calcula una dirección pk y luego se
decide qué tanto se avanza en esa dirección, de esta forma, cada iteración está dada por
xk+1 = xk + ↵k pk , (1)
donde ↵k > 0 es el tamaño del paso. Ası́, el éxito del método depende de la escogencia de la
dirección y el tamaño del paso. Recordemos que la derivada direccional cumple que
f (x + ↵p) f (x)
f 0 (x; p) := lı́m = hrf (x), pi,
↵#0 ↵
es decir, es la tasa de crecimiento de la función en la dirección p, y como estamos minimizando,
en cada iteración debemos buscar direcciones tales que
hrf (xk ), pk i < 0.
A estas las llamamos direcciones de descenso.
Nota. En muchos casos tienen la forma pk = Bk 1 rf (xk ) donde Bk es una matriz definida
positiva, lo que garantiza que sı́ sea de descenso.
Comencemos por la escogencia más sencilla: pk = rf (xk ) (o Bk = I) y un tamaño de
paso constante, este es el caso más sencillo del método del descenso del gradiente. Por el
teorema fundamental del cálculo, para x, y 2 Rn , se tiene que
Z1
f (y) f (x) = hrf (x + ↵(y x)), y xid↵, (2)
0

9
y usando esto tenemos que
Z1
|f (y) f (x) hrf (x), y xi| = hrf (x + ↵(y x)) rf (x), y xid↵
0
Z1
 |hrf (x + ↵(y x)) rf (x), y xi|d↵
0
Z1
 krf (x + ↵(y x)) rf (x)kky xkd↵
0
Z1
L
 ↵Lky xk2 d↵ = ky xk2 . (3)
2
0

Examinemos ahora el resultado de un paso del método. Sea y = x ↵rf (x), por (3) tenemos
que
L
f (y)  f (x) + hrf (x), y xi + ky xk2
2
↵2
= f (x) ↵krf (x)k2 + Lkrf (x)k2
⇣ 2
↵ ⌘
= f (x) ↵ 1 L krf (x)k2 ,
2
luego, tomando ↵ = L1 se alcanza la mı́nima cota superior para el decrecimiento de la función
en el nuevo punto y, y esta es
1
f (y)  f (x) krf (x)k2 .
2L
1
Ası́ que el método del descenso del gradiente con tamaño de paso constante L
tiene la forma
1
xk+1 = xk rf (xk )
L
y se cumple que
1
f (xk ) f (xk+1 )krf (xk )k2 . (4)
2L
Sumando la desigualdad anterior sobre k = 0, . . . , N tenemos que
N
1 X
krf (xk )k2  f (x0 ) f (xN +1 )  f (x0 ) f ⇤, (5)
2L k=0
⇤
luego krf (xk )k ! 0 cuando k ! 1. Si definimos gN = mı́n krf (xk )k, de (5) obtenemos
0kN
que
1
⇤
gN p (2L(f (x0 ) f ⇤ ))1/2 .
N +1

10
 Figura 2: Condición de Armijo

Ası́ que si queremos obtener un punto cuyo gradiente sea menor a ✏, esto se garantiza cuando
N + 1 2L ✏2
(f (x0 ) f ⇤ ).
En muchos casos no es posible conocer la constante L de la función, ası́ que debemos
escoger el tamaño del paso de una forma distinta. La forma más usada en la práctica es
escoger el tamaño del paso de tal forma que satisfagan ciertas condiciones de decrecimiento
suficiente. Veamos estas condiciones para el caso general con dirección de descenso pk , es
decir, consideremos que cada iteración está dada por (1).

Condición de Armijo

Se busca un tamaño de paso ↵k tal que

f (xk ) f (xk+1 ) c1 ↵k hrf (xk ), pk i,

para alguna constante c1 2 (0, 1). Si definimos las funciones (↵) := f (xk + ↵pk ) y l(↵) :=
f (xk ) + c1 ↵hrf (xk ), pk i. Puesto que c1 2 (0, 1) entonces (↵)  l(↵) para valores de ↵
suficientemente pequeños, como se muestra en la figura 2. Un algoritmo muy usado para
encontrar un tamaño de paso que satisfaga la condición de Armijo es el llamado backtracking:

Escoger ↵ > 0, ⇢ 2 (0, 1). Se define ↵ ↵;

mientras f (xk + ↵pk ) > f (xk ) + c1 ↵hrf (xk ), pk i hacer
↵ ⇢↵;
fin
Escoger ↵k = ↵.
Algoritmo 1: Backtracking

Únicamente esta condición no es suficiente pues se pueden escoger tamaños de paso muy
pequeños y el método se harı́a muy lento. Adicionar alguna de las siguientes dos condiciones
buscan evitar esto.

11
Condición de Goldstein

Se busca un tamaño de paso ↵k tal que

f (xk ) f (xk+1 )  c2 ↵k hrf (xk ), pk i,

para alguna constante c2 2 (c1 , 1). La figura 3 ilustra los tamaño de paso que satisfacen las
condiciones de Armijo y Goldstein. Una desventaja de esta condición es que puede excluir
los mı́nimos de . Ahora, por (3) tenemos que
L 2
f (xk ) f (xk+1 ) ↵k hrf (xk ), pk i ↵ kpk k2 ,
2 k
y combinando con la condición de Goldstein tenemos que
2(c2 1) hrf (xk ), pk i
↵k . (6)
L kpk k2

Condición de Wolfe

Se busca un tamaño de paso ↵k tal que

hrf (xk+1 ), pk i c2 hrf (xk ), pk i,

para alguna constante c2 2 (c1 , 1). Notemos que el lado izquierdo de la desigualdad anterior
es precisamente 0 (↵k ) y el lado derecho c2 0 (0) < 0 (0). La figura 4 ilustra los tamaño de
paso que satisfacen la condición de Wolfe. Un desventaja de esta condición es que podemos
tener ↵k tal que 0 (↵k ) es positiva muy grande. Ahora, la condición implica que

hrf (xk+1 ) rf (xk ), pk i (c2 1)hrf (xk ), pk i.

Figura 3: Condición de Goldstein

12
 Figura 4: Condición de Wolfe

Por otro lado, la condición de Lipschitz del gradiente implica que

hrf (xk+1 ) rf (xk ), pk i  ↵k Lkpk k2 ,

y combinando estas dos desigualdades tenemos que

c2 1 hrf (xk ), pk i
↵k . (7)
L kpk k2

Nota. Notemos que la existencia de ↵k que satisfaga la condición de Goldstein o la de Wolfe

está garantizada pues f está acotada por debajo y es C 1 (Rn ).

Vamos a usar (6) y (7), junto con la condición de Armijo, para mostrar la convergencia.
Para esto definimos ✓k el ángulo entre pk y rf (xk ), es decir

hrf (xk ), pk i
cos ✓k = .
krf (xk )kkpk k
Ası́, obtenemos que

(hrf (xk ), pk i)2

f (xk ) f (xk+1 ) = cos2 ✓k krf (xk )k2 ,
kpk k2

donde = 2c1 (1L c2 ) para la condición de Goldstein y = c1 (1L c2 ) para la de Wolfe. Notemos
la similitud con (4), ası́ que si sumamos sobre k, tenemos, como en (5), que
N
X
cos2 ✓k krf (xk )k2  f (x0 ) f (xN +1 )  f (x0 ) f ⇤,
k=0

luego cos2 ✓k krf (xk )k ! 0 cuando k ! 1. Si se garantiza que cos ✓k > 0 para todo k,
como en el descenso del gradiente, tenemos que krf (xk )k ! 0.

13
Nota. Es importante notar que lo único que podemos garantizar es la convergencia de los
gradientes a 0.

Supongamos ahora que f 2 C 2 (Rn ) con matriz Hessiana Hf (·) Lipschitz con constante K.
Adicionalmente suponemos que existe un óptimo del problema x⇤ y que la matriz Hessiana
Hf (x⇤ ) es definida positiva con valores propios en el intervalo [m, M ]. Veamos diferentes
métodos (y sus pruebas de convergencia).

Nota. Recordemos que para matrices simétricas la norma espectral (la misma norma ope-
rador) está dada por p
kAk = T
máx (AA ) = máx | i |
i

y satisface para todo x 2 R que kAxk  kAkkxk. Dadas A, B matrices simétricas notamos
n

A B si B A es semidefinida positiva.

Método del descenso del gradiente

Consideremos el método del descenso del gradiente. Como x⇤ es mı́nimo, tenemos que
rf (x⇤ ) = 0, luego

Z1
⇤
rf (xk ) = rf (xk ) rf (x ) = Hf (x⇤ + ↵(xk x⇤ ))(xk x⇤ )d↵
0
⇤
=: Gk (xk x ),

luego
xk+1 x⇤ = xk x⇤ ↵k Gx (xk x⇤ ) = (I ↵k Gk )(xk x⇤ ).
Queremos ahora estimar la norma espectral de I ↵k Gk . Para esto vemos a usar los supuestos
sobre f . Dados x, y 2 Rn y r := ky xk, por la condición de Lipschitz tenemos que

kHf (y) Hf (x)k  Kky xk = Kr,

por lo tanto
Hf (x) rKI Hf (y) Hf (x) + rKI. (8)
Si tomamos y = x⇤ ↵(xk x⇤ ) y x = x⇤ y definimos rk = kxk x⇤ k, entonces

(m ↵Krk )I Hf (x⇤ ) ↵Krk I

Hf (x⇤ ↵(xk x⇤ ))
Hf (x⇤ ) + ↵Krk I
(M + ↵Krk )I.

De la definición de Gk e integrado ambos extremos de las desigualdades anteriores tenemos

que ⇣ rk ⌘ ⇣ rk ⌘
m K I Gk M +K I,
2 2

14
y por lo tanto
⇣ ⇣ rk ⌘⌘ ⇣ ⇣ rk ⌘⌘
1 ↵k M + K I I ↵ k Gk 1 ↵k m K I.
2 2
Ası́ que
n ⇣ rk ⌘ ⇣ rk ⌘ o
kI ↵k Gk k  máx 1 ↵k m K , ↵k M + K 1 =: h(↵k ).
2 2
2m
Notemos que si rk < r = K
, entonces h(↵k ) < 1 para ↵k suficientemente pequeño y, además,
h se minimiza cuando
⇣ rk ⌘ ⇣ rk ⌘
1 ↵k m K = ↵k M + K 1,
2 2
2 M m+Krk
es decir, cuando ↵k⇤ = m+M
, en este caso h(↵k⇤ ) = M +m
< 1. Por lo tanto

rk+1 = kxk+1 x⇤ k = k(I ↵k Gk )(xk x⇤ )k

✓ ◆
M m + Krk
 kI ↵k Gk krk  rk .
M +m
Finalmente, se puede mostrar con un poco de álgebra (ver pág. 31-32 de [N]) que si r0 < r,
es decir, si el método se inicia en un punto cercano a x⇤ , entonces el método del descenso
2
del gradiente converge con tamaño ↵k = m+M converge con una tasa lineal dada por
✓ ◆k
r0 r 2m
rk  1 .
r r0 M + 3m
Método de Newton

El método de Newton es un método muy usado para encontrar una solución a sistemas
de ecuaciones no lineales. Si F : Rn ! Rn es C 1 (Rn ) y hacemos la aproximación de F
alrededor de x y x⇤ ⇡ x + x donde F (x⇤ ) = 0, entonces tenemos el sistema lineal

F (x) + DF (x) x = 0,

donde DF (x) es el Jacobiano de F en x. Si este Jacobiano es no singular, tenemos entonces

que x = [DF (x)] 1 F (x), y esto genera el método iterativo dado por

xk+1 = xk [DF (xk )] 1 F (xk ).

Sabemos que todo óptimo de nuestro problema de minimización debe ser un punto esta-
cionario, es decir, debe satisfacer que rf (x⇤ ) = 0, luego, si aplicamos el método a rf (·)
obtenemos
xk+1 = xk [Hf (xk )] 1 rf (xk ). (9)
Notemos que no tenemos necesariamente que [Hf (xk )] 1 rf (xk ) sea una dirección de
descenso (la matriz Hessiana podrı́a ser singular incluso), aún ası́, bajo los supuestos ini-
ciales podemos garantizar la convergencia del método siempre que iniciemos lo suficiente-
mente cerca de x⇤ . Como antes notamos rk = kxk x⇤ k, entonces de (8) tenemos que

15
 m
Hf (xk ) ⌫ Hf (x⇤ ) rk KI ⌫ (m rk K)I, por lo tanto si rk < K
, entonces Hf (xk ) es
definida positiva y además
1
k[Hf (xk )] 1 k  . (10)
m rk K
Para mostrar la convergencia del método vamos a seguir la misma idea que usamos en el
método del descenso del gradiente. Tenemos que:

xk+1 x⇤ = xk x⇤ [Hf (xk )] 1 rf (xk )

= xk x⇤ [Hf (xk )] 1 (rf (xk ) rf (x⇤ ))
Z1
= xk x⇤ [Hf (xk )] 1 Hf (x⇤ + ↵(xk x⇤ ))(xk x⇤ )d↵
0
Z1
= [Hf (xk )] 1
(Hf (xk ) Hf (x⇤ + ↵(xk x⇤ ))) (xk x⇤ )d↵
0
ek (xk
=: [Hf (xk )] G 1
x⇤ ).

Ahora,
Z1
ek k 
kG kHf (xk ) Hf (x⇤ + ↵(xk x⇤ ))k d↵
0
Z1
rk
 K(1 ↵)kxk x⇤ kd↵ = K,
2
0

y usando (10)
rk K
rk+1  r k < rk ,
2(m rk K)
siempre que 2(mrk K
rk K)
< 1 o equivalentemente, siempre que rk < 2m
3K
< m
K
. Ası́ que, si r0 < 2m
3K
el método converge a una tasa cuadrática dada por

3Krk2
rk+1  .
2m
Finalmente, para evitar que el método diverja se puede iniciar la búsqueda incluyendo un
tamaño de paso en el método:

xk+1 = xk ↵k [Hf (xk )] 1 rf (xk ),

y en la etapa final tomar ↵k = 1.

Métodos Quasi-Newton

Lo que tenemos hasta ahora es un método que solo usa información de primer orden de

16
f con una tasa de convergencia lineal y un método que usa información de segundo or-
den (por lo tanto requiere más operaciones en cada iteración) con una tasa de convergencia
cuadrática. Veamos ahora una familia de métodos que están en la mitad de los dos anteriores.
Consideremos las siguientes aproximaciones cuadráticas de f alrededor de un punto x 2 Rn :
1
1 (x) = f (x) + hrf (x), x xi + kx xk2 , ↵ > 0
2↵
1
2 (x) = f (x) + hrf (x), x xi + hHf (x)(x x), x xi
2
1
Nota. Cuando ↵ = L
se tiene que 1 es la cota que se obtiene en (3).

Notemos que los únicos puntos crı́ticos de estas aproximaciones son respectivamente

x1 = x ↵rf (x)
x2 = x [Hf (x)] 1 rf (x),

que son precisamente los pasos iterativos de los métodos anteriores. Lo anterior sugiere que a
partir de diferentes aproximaciones cuadráticas podemos construir diferentes métodos. Dada
Bk matriz definida positiva, si consideremos la aproximación
1
k (x) = f (xk ) + hrf (xk ), x xk i + hBk (x xk ), x xk i, (11)
2
cuyo mı́nimo es xk +pk , con pk = Bk 1 rf (xk ), la cual es una dirección de descenso (recuerde
la nota al inicio de la sección). Tenemos entonces el proceso iterativo dado por

xk+1 = xk + ↵k pk

donde ↵k se puede escoger con las condiciones y criterios vistos antes. La idea ahora es escoger
Bk+1 con dos criterios: a) que únicamente use información de primer orden, b) que sea fácil
de calcular a partir de Bk . Consideremos la aproximación k+1 , queremos que el gradiente
de esta aproximación coincida con el gradiente de f en los puntos xk y xk+1 , entonces

r k+1 (x) = rf (xk+1 ) + Bk+1 (x xk+1 )

y ası́ r k+1 (xk+1 ) = rf (xk+1 ) y r k+1 (xk ) = rf (xk+1 ) + Bk+1 (xk xk+1 ) = rf (xk ).
1
Concluimos que Hk+1 := Bk+1 debe satisfacer la ecuación

Hk+1 yk = sk ,

donde yk = rf (xk+1 ) rf (xk ) y sk = xk+1 xk . Una condición necesaria para poder

satisfacer esta ecuación es que hyk , sk i > 0, la cual se tiene si f es estrictamente convexa
(recuerden el ejercicio 11 del cap. 5 de [G]), de lo contrario, escogiendo ↵k tal que satisfaga la
condición de Wolfe también se tiene (¿puede mostrarlo?). Una vez se garantice esta condición
necesaria, hay infinitas formas de escoger Hk+1 (o Bk+1 ), pero queremos algunas que estén

17
cerca de Hk (o Bk ). El método más popular desde el punto de vista computacional es el BFGS
(Broyden-Fletcher-Goldfarb-Shanno), y resulta de resolver el problema de optimización

mı́n kH Hk k⇤
sujeto a H = HT
Hyk = sk ,
P
donde kAk⇤ = kW 1/2 AW 1/2 kF , kCkF = Cij2 , llamada la norma de Frobenius, y W es
i,j
definida positiva tal que W sk = yk . En este caso se puede mostrar que la única solución del
problema de optimización es

Hk+1 = (I ⇢k sk ykT )Hk (I ⇢k yk sTk ) + ⇢k sk sTk

= Hk ⇢k Hk yk sTk ⇢k sk ykT Hk + ⇢2k sk ykT Hk yk sTk + ⇢k sk sTk
= Hk + ⇢2k (hyk , sk i + hHk yk , yk i) sk sTk ⇢k (Hk yk sTk + sk ykT Hk ), (12)
1
donde ⇢k = hyk ,sk i
. Además, usando que

(A + U V T ) 1
=A 1
A 1 U (I + V T AU ) 1 V T A 1 ,

se puede mostrar que

Bk sk sTk Bk
Bk+1 = Bk + ⇢k yk ykT . (13)
hBk sk , sk i
Otras formas de calcular Hk+1 las pueden ver en la la pág. 41 de [N]. Se puede mostrar
también que la convergencia de este método es mejor que la del descenso del gradiente pero
peor que la de Newton bajo las mismos supuestos iniciales de esta sección.

3.2. Método de región de confianza - Caso general suave

En este método se define una aproximación (cuadrática) de la función f , la cual llamamos
modelo, y una región (un bola en realidad) alrededor de la iteración actual xk sobre la cual
se tiene suficiente confianza de que el modelo es adecuado, y luego escogemos como xk+1 el
mı́nimo (o una aproximación de este) del modelo sobre la región. De acuerdo a qué tanto
cambia la función en el nuevo punto con respecto a cambio en el modelo, se decide expandir
o contraer la región de confianza alrededor del nuevo punto. Veamos los detalles de este
método, para esto asumimos que f 2 C 1 (Rn ) y que su gradiente es Lipschitz con constante
L. Recordemos la aproximación de f dada en (11)
1
mk (p) := k (xk + p) = f (xk ) + hrf (xk ), pi + hBk p, pi,
2
donde, en este caso, a Bk solo se pide que sea simétrica. Ası́, en cada iteración se busca
resolver el problema
1
pk :=mı́n mk (p) = f (xk ) + hrf (xk ), pi + hBk p, pi (14)
2
sujeto a kpk  k ,

18
con k > 0. Para resolver este problema debemos decidir dos cosas: a) Bk , el cual podrı́a
ser Hf (xk ) en caso de que exista, y en este caso serı́a el método de Newton con región de
confianza, o alguna de las matrices usadas en los métodos quasi-Newton. b) k , para esto
definimos
f (xk ) f (xk + pk )
⇢k = .
mk (0) mk (pk )
Notemos que el denominador siempre es positivo pues pk es el óptimo del problemas. Ahora,
si ⇢k < 0 la función en el nuevo punto es mayor que en xk y por tanto debemos rechazarlo, si
⇢k ⇡ 1 entonces el modelo es una buena aproximación de la función y por lo tanto podemos
expandir la región de confianza, y si 0 < ⇢k ⌧ 1 el modelo no es tan confiable y debemos
contraer la región. Ası́, tenemos el siguiente algoritmo:

Escoger ˆ > 0, 0 2 (0, ˆ ) y ⌘ 2 (0, 14 );

para k = 0, 1, 2, . . . hacer
Obtener pk (o una aproximación);
Calcular ⇢k ;
si ⇢k < 14 entonces
1
k+1 = 4 k ;
fin
en otro caso
si ⇢k > 34 y kpk k = k entonces
ˆ
k+1 = mı́n(2 k , );
fin
en otro caso
k+1 = k;
fin
fin
si ⇢k > ⌘ entonces
xk+1 = xk + pk ;
fin
en otro caso
xk+1 = xk ;
fin
fin
Algoritmo 2: Región de confianza

Ahora, resolver el problema (14) en cada iteración puede ser muy costoso, y tampoco es
necesario para mostrar la convergencia, como veremos más adelante. Una primera aproxima-
ción es el denominado punto de Cauchy, que denotamos con pC k . Primero vamos a considerar
una aproximación lineal de f en lugar de la cuadrática y resolvemos el problema

p̂k :=mı́n f (xk ) + hrf (xk ), pi

sujeto a kpk  k ,

19
cuya solución está dada por
k
p̂k = rf (xk ).
krf (xk )k
Notemos que esta dirección es la misma del descenso del gradiente. El siguiente paso es
escoger un tamaño de paso que minimice el modelo dentro de la región de confianza, esto es,
solucionar el problema
⌧k = arg mı́n{mk (⌧ p̂k ) : k⌧ p̂k k  k}
⌧ 0

= arg mı́n mk (⌧ p̂k )

0⌧ 1

⌧ 2 2k
= arg mı́n ⌧ k krf (xk )k + hBk rf (xk ), rf (xk )i
0⌧ 1 2krf (xk )k2
(
=
1 ⇣ ⌘ si hBk rf (xk ), rf (xk )i  0
krf (xk )k3
mı́n 1, k hBk rf (xk ),rf (xk )i de lo contrario.
Tenemos entonces que
⌧k k
pC
k = rf (xk ).
krf (xk )k
La pregunta ahora es ¿qué tan bueno es el punto de Cauchy? Tratemos de dar una respuesta
estimando mk (0) mk (pCk ). Por simplicidad vamos a omitir el ı́ndice k y a definir g = rf (x).
Supongamos que hBg, gi  0, entonces
✓ ◆
C
m(0) m(p ) = f (x) m g
kgk
2
= kgk hBg, gi
2kgk2
kgk.
kgk3
Consideremos ahora el caso hBg, gi > 0 y hBg,gi
 1, entonces
kgk4 kgk4
m(0) m(pC ) =
hBg, gi 2hBg, gi
kgk4
=
2hBg, gi
kgk4 1 kgk
2
= kgk .
2kgk kBk 2 kBk
kgk3
Y finalmente, si hBg, gi > 0 y hBg,gi
> 1, entonces
2
C
m(0) m(p ) = kgk hBg, gi
2kgk2
2
kgk3
kgk
2kgk2
1
= kgk.
2

20
Podemos concluir entonces que
✓ ◆
1 krf (xk )k
mk (0) mk (pC
k) krf (xk )k mı́n k, , (15)
2 kBk k
lo cual nos garantiza un decrecimiento mı́nimo del modelo en el punto de Cauchy. Veamos que
cualquier solución aproximada de (14) que satisfaga este decrecimiento mı́nimo es suficiente
para mostrar la convergencia del algoritmo 2.
Teorema. Supongamos que en al algoritmo 2, pk satisface (15) y que kBk k  para todo
k. Entonces lı́m krf (xk )k = 0.
k!1

Prueba. Sea {xk }k 0 la sucesión generada por el algoritmo 2 y tomemos m tal que 0 <
krf (xm )k =: 2✏ y R = L✏ . Entonces, si kx xm k  R se tiene que
krf (x)k krf (xm )k krf (x) rf (xm )k 2✏ LR = ✏.
Supongamos que {xk }k m ⇢ BR (xm ), por lo tanto krf (xk )k ✏. De (3) y (15) tenemos que
para todo k m
mk (pk ) f (xk + pk )
|⇢k 1| =
mk (0) mk (pk )
|f (xk ) f (xk + pk ) hrf (xk ), pk i| + 12 |hBk pk , pk i|
=
|mk (0) mk (pk )|
L kBk k
2
kpk k2 + kpk k2
 ⇣2 ⌘
1 krf (xk )k
2
krf (xk )k mı́n k , kBk k

kpk k2 (L + kBk k)
 ⇣ ⌘
✏
✏ mı́n ,
k kBk k
2 2
k (L+ kBk k) k (L + )
 ⇣ ⌘ ⇣ ⌘. (16)
✏ ✏
✏ mı́n k , kBk k ✏ mı́n k,

Ahora, si k  := 12 L+✏ < ✏ , entonces |⇢k 1|  12 y por lo tanto ⇢k > 14 y del algoritmo
1
obtenemos que k+1 k . Por otro lado, si k+1 = 4 k < k , del algoritmo tenemos que
1
⇢k < 4 y por lo tanto k > . Lo anterior implica que para todo k m se tiene
✓ ◆
k mı́n m, . (17)
4
1
Caso 1: Existe una subsucesión {kj }j 0 tal que ⇢kj 4
, entonces, de la descripción del
algoritmo y (15), tenemos que
f (xkj ) f (xkj +1 ) = f (xkj ) f (xkj + pkj )
= ⇢kj (mkj (0) mkj (pkj ))
✓ ◆
11 ✏
✏ mı́n kj , ,
42

21
lo que implica que kj ! 0, de lo contrario f no estarı́a acotada por debajo. Pero esto
contradice (17).
Caso 2: ⇢k < 14 para todo k suficientemente grande. Pero esto también implica que k ! 0
y de nuevo es una contradicción.
Todo lo anterior implica que existe l > m tal que xl+1 2 / BR (xm ) y además {xk }lk=m ⇢
BR (xm ), luego, usando (15),
l
X
f (xm ) f (xl+1 ) = f (xk ) f (xk+1 )
k=m
X
⌘(mk (0) mk (pk ))
xk 6=xk+1
✓ ◆
⌘ X ✏
✏ mı́n k, .
2 x 6=x
k k+1

✏
Si k  para todo k = m, . . . , l, entonces
⌘ X
f (xm ) f (xl+1 ) ✏ k
2 x 6=x
k k+1
⌘ X
✏ kxk xk+1 k
2 x 6=x
k k+1

⌘ ⌘✏2
✏R = ,
2 2L
✏ ⌘✏2
y por otro lado, si k > para algún k, entonces f (xm ) f (xl+1 ) 2
. En cualquier caso
⌘
f (xm ) f (xl+1 ) krf (xm )k > 0,
4 máx(L, )

y como esto se cumple para todo m tal que krf (xm )k > 0, tenemos que krf (xk )k ! 0.

Ahora, simplemente escoger el punto de Cauchy en cada iteración no es lo más eficiente,

ni interesante pues tendrı́amos el método del descenso del gradiente con un tamaño de paso
particular. Supongamos que Bk es definida positiva y notemos por p⇤k ( k ) el óptimo de (14)
en función del tamaño de la región de confianza. Es claro que pB
k = Bk 1 rf (xk ) es el óptimo
global del modelo y es también el óptimo del subproblema si kpB kk  k . Si, por el contrario,
⇤
k es muy pequeño, el término cuadrático de mk es despreciable y por lo tanto pk ( k ) es-
tarı́a muy cercano al punto de Cauchy con ⌧k = 1. Para tamaños de k intermedios, p⇤k ( k )
sigue una trayectoria similar a la se ve en la figure 5. El método dogleg busca aproximar esta
trayectoria por dos rectas. Como Bk es definida positiva, sabemos que el mı́nimo del modelo
en la dirección rf (xk ) está dado por

krf (xk )k2

pUk = rf (xk ),
hBk rf (xk ), rf (xk )i

22
 Figura 5: Método dogleg

luego la primera recta va del origen a pUk y la segunda de pUk a pB

k . Esta trayectoria la podemos
parametrizar como
(
⌧ pUk si 0  ⌧  1
p̃k (⌧ ) = (18)
pUk + (⌧ 1)(pB k pUk ) si 1  ⌧  2.

Queremos ahora minimizar el modelo a lo largo de esta trayectoria sujeto a estar dentro de
la región de confianza. Para esto veamos que kp̃k (⌧ )k es creciente y mk (p̃k (⌧ )) es decreciente.
Esto es claro cuando ⌧ 2 [0, 1], ası́ que solo vamos considerar ⌧ 2 [1, 2]. En este caso
1
h(⌧ ) := kp̃k (⌧ )k2
2
1 U 2 1
= kpk k + (⌧ 1)hpB
k pUk , pUk i + (⌧ 1)2 kpB
k pUk k2 ,
2 2
luego

h0 (⌧ ) = hpB
k pUk , pUk i + (⌧ 1)kpB
k pUk k2
hpB
k pUk , pUk i
krf (xk )k2 hBk 1 rf (xk ), rf (xk )i krf (xk )k6
=
hBk rf (xk ), rf (xk )i hBk rf (xk ), rf (xk )i2
krf (xk )k2
= hBk 1 rf (xk ), rf (xk )ihBk rf (xk ), rf (xk )i krf (xk )k4
hBk rf (xk ), rf (xk )i2
0,

donde la última desigualdad se sigue de

1/2 1/2
krf (xk )k4 = hBk rf (xk ), Bk rf (xk )i2
1/2 1/2
 kBk rf (xk )k2 kBk rf (xk )k2
= hBk 1 rf (xk ), rf (xk )ihBk rf (xk ), rf (xk )i.

23
 Ahora, si notamos ĥ(⌧ ) = mk (p̃k (⌧ )) y derivamos con respecto a ⌧ , tenemos

ĥ0 (⌧ ) = hrf (xk ), pB

k pUk i + hBk (pUk + (⌧ 1)(pB
k pUk )), pB
k pUk i
 hrf (xk ), pB
k pUk i + hBk pB B
k , pk pUk i
= hrf (xk ) + Bk pB B
k , pk pUk i = 0.

De lo anterior podemos concluir que la trayectoria p̃k (⌧ )) intersecta la frontera de la región

de confianza a lo sumo en un solo punto. En caso de que kpUk k < k pero kpB kk > k,
podemos hallar el valor ⌧ ⇤ 2 (1, 2) que minimiza el modelo dentro de la región de confianza
resolviendo la ecuación cuadrática

kpUk + (⌧ ⇤ 1)(pB
k pUk )k2 = 2
k.

4. Conjuntos y funciones convexas

4.1. Conjuntos convexos
Definición. Un subconjunto C ⇢ Rn es un conjunto convexo si para todo x, y 2 C el
segmento [x, y] ⇢ C, es decir, si para todo ↵ 2 [0, 1] se tiene que ↵x + (1 ↵)y 2 C.

Ejemplo. Algunos ejemplos son las rectas, subespacios vectoriales, semiespacios, el conjunto
de las matrices semidefinidas positivas y el cono de segundo orden, este es el epı́grafo de la
función kxk, bolas.

Veamos algunas de propiedades de los conjuntos convexos (intente probar algunas de

ellas):
T
1. Dada una familia de conjuntos convexos {Ci }i2I , entonces la intersección Ci es
i2I
también convexa.

Ejemplo. Un ejemplo importante de conjunto convexo son los poliedros {x : Ax  b}

pues son intersecciones de semiespacios. El conjunto de matrices semindefinidas es
también una intersección (no contable) de semiespacios del tipo {X : hX, zz T i 0}
con z 6= 0.
Q
2. Dada una familia de conjuntos convexos {Ci }i2I , entonces el producto cartesiano Ci
i2I
es también convexo.

3. La unión de conjuntos convexos no es necesariamente convexa. Ejemplo??

4. Si A 2 Rm⇥n y b 2 Rm , y C ⇢ Rn es convexo, entonces AC +b = {Ax+b : x 2 C} ⇢ Rm

es convexo. Esto es, imagen de un convexo a través de una función afı́n es convexa.
Esta propiedad permite mostrar que la suma de Mikowski de una colección finita de
conjuntos convexos es convexa. También muestra que proyecciones de un conjunto
convexo sobre algunas de sus coordenadas también es convexo.

24
 5. Si C es convexo entonces su clausura también lo es.
6. Si C es convexo entonces su interior es convexo. Para ver esto sean x, y 2 int(C),
entonces existe r > 0 tal que Br (x) ⇢ C y Br (y) ⇢ C. Sea ↵ 2 [0, 1] y kzk  r, ası́ que
x + z y y + z están en C. Entonces
↵x + (1 ↵)y + z = ↵(x + z) + (1 ↵)(y + x) 2 C,
luego ↵x + (1 ↵)y 2 int(C).
Definición. Un conjunto A ⇢ Rn es afı́n si dados x, y 2 A, la recta que pasa por estos
puntos está contenida en A, es decir, si para todo ↵ 2 R se tiene que ↵x + (1 ↵)y 2 A.
Definición. Dado B ⇢ Rn definimos la envoltura afı́n y la envoltura convexa de B, respec-
tivamente, como:
⇢k
P P
k
a↵(B) = ↵i xi : xi 2 B, ↵i = 1, k 2 N
i=1 i=1
⇢
P
k P
k
conv(B) = ↵i xi : xi 2 B, ↵i 0, ↵i = 1, k 2 N
i=1 i=1

Esto es, son las combinaciones afines y convexas, respectivamente, de elementos de B.

Es claro que B ⇢ conv(B) ⇢ a↵(B).
Proposición. Si B 6= ?, entonces conv(B) es convexo (a↵(B) es afı́n). Además, conv(B)
(a↵(B)) es el conjunto convexo (afı́n) más pequeño que contiene a B.
Prueba. Veamos la prueba para la envoltura convexa pues el caso de la envoltura afı́n es
P
n P
m
similar. Sea x = ↵ i xi y y = µj yj en conv(B), es decir, xi , yj 2 B y los ↵i , µj forman
i=1 j=1
una combinaciones convexas. Entonces, para 2 [0, 1] los escalares ↵i , (1 )µj forman
una combinación convexa con los vectores xi , yj con lo cual
n
X m
X
x + (1 )y = ↵ i xi + (1 )µj yj 2 conv(B).
i=1 j=1

Para la segunda parte, sea C convexo tal que B ⇢ C, queremos ver que conv(B) ⇢ C.
Sea x 2 conv(B). Vamos a hacer inducción en el número de términos en la suma de la
representación como combinación convexa x, esto es, si x 2 B, entonces x 2 C. Ahora, sea
x como arriba con n términos en la suma y supongamos que todo elemento de conv(B) con
n 1 términos está en C, entonces, tomando = 1 ↵n 2 [0, 1], se tiene que
n 1
!
X ↵i
x= xi + (1 )xn .
i=1
↵i
Como para i = 1, . . . , n 1 forman una combinación convexa y C es convexo, entonces
x 2 C.
Lo anterior muestra entonces que si C es convexo entonces conv(C) = C, es decir,
combinaciones convexas de elementos de C están en C, y análogamente para conjuntos
afines.

25
Definición. Sean {x1 , . . . , xk } ⇢ Rn . Decimos que son afı́nmente independientes si para
P
k P
k
escalares ↵1 , . . . , ↵k tales que ↵ i xi = 0 y ↵i = 0, entonces todos los escalares son 0.
i=1 i=1

Lema. Los vectores {x1 , . . . , xk } son afı́nmente independientes si y solo si los k 1 vectores
{x2 x1 , . . . , xk x1 } son linealmente independientes.
P
k P
k
Prueba. Notemos que las condiciones ↵ i xi = 0 y ↵i = 0, son equivalentes a que
i=1 i=1
P
k
↵k (xk x1 ) = 0, con lo que se tiene el resultado.
i=2
El anterior lema nos permite mostrar un siguiente teorema debido a Carathéodoty.
Teorema (Carathéodory). Sea B ⇢ Rn . Todo elemento de conv(B) se puede escribir como
combinación convexa de elementos de B afı́nmente independientes. Por lo tanto, todo ele-
mento de conv(B) se puede escribir como combinación convexa de a lo más n + 1 elementos
de B.
Pk
Prueba. Sea x = ↵i xi con ↵i > 0, si los vectores xi son afı́nmente independientes, entonces
i=1
k 1  n por el lema y por consiguiente k  n + 1. Ahora, supongamos que los vectores xi
P
k P
k
no son linealmente independientes, luego existen escalares µi tales que µi xi = 0, µi = 0
i=1 i=1
y no todos son 0. Entonces, para ✏ > 0 se tiene que
k
X
x= (↵i ✏µi )xi
i=1

P
k
y además (↵i ✏µi ) = 1. Si µi  0, entonces ↵i ✏µi 0, de lo contrario, si tomamos
i=1
✏ = mı́n{↵i /µi : µi > 0} > 0, se tiene que los escalares ↵i ✏µi forman una combinación
convexa y uno de ellos es 0, ası́ que x se puede escribir como combinación convexa de k 1
vectores. Continuando este proceso podemos obtener vectores afı́nmente independientes.
Notemos que si B es cerrado, conv(B) no lo es necesariamente, pero sı́ se tiene el siguiente
resultado.
Corolario. Si B es compacto, entonces conv(B) también lo es.
Prueba. Para mostrar que conv(B) es compacto es suficiente con mostrar que todoa suce-
sión tiene una subsucesión convergente. Sea {xk } ⇢ conv(B), entonces cada elemento de la
sucesión se puede escribir como
n+1
X
k
x = ↵ik xki .
i=1

Como el simplex n-dimesional n = {↵ 2 Rn+1 + : h↵, 1i = 1}, con 1 el vector de unos, es

n+1
compacto, entonces B ⇥ n es compacto, entonces {(xk1 , . . . , xkn+1 , ↵k )} tiene una sub-
sucesión convergente a (x1 , . . . , xn+1 , ↵). Luego {xk } tiene una subsucesión convergente a
P
n+1
↵i xi 2 conv(B).
i=1

26
 No es difı́cil ver todo conjunto afı́n A es la translación de un subespacio, luego podemos
definir dim(A) como la dimensión del subespacio asociado. De la misma forma podemos
definir dim(B) = dim(a↵(B)) para todo B ⇢ Rn . Ahora, dim(B) = m < n, entonces todo
elemento de conv(B) se puede escribir como combinación convexa de a lo más m+1 elementos
de B.

Definición. Un conjunto K ⇢ Rn es un cono si para todo x 2 K y > 0 se tiene que

x 2 K. Dado B ⇢ Rn la envolvente cónica de B se define como
( k )
X
cone(B) = i xi : xi 2 B, i > 0, k 2 N .
i=1

No todo cono es convexo, pero los convexos son los que nos interesan. Tenemos además
resultados análogos a los anteriores para los conos, estos son:

Si B 6= ?, entonces cone(B) es el cono convexo más pequeño que contiene a B.

(Carathéodory) Sea B ⇢ Rn . Todo elemento de cone(B) se puede escribir como com-

binación positiva de elementos de B linealmente independientes. Por lo tanto, todo
elemento de conv(B) se puede escribir como combinación positiva de a lo más n ele-
mentos de B.

Ejemplo. Los ejemplos de conos más importantes son Rn+ , las matrices semidefinidas positi-
vas y el cono de segundo orden. Otro usando es el cono de matrices copositivas que contiene
al cono de matrices semidefinidas positivas.

Ahora, si intersectamos alguno de los conos anteriores con espacios afines, tenemos con-
juntos convexos sobre los cuales nos va a interesar optimizar funciones lineales, como veremos
más adelante. Un ejemplo es el conjunto {x 2 Rn+ : Ax = b} para alguna matriz A 2 Rm⇥n
y algún vector b 2 Rm . De hecho este conjunto es un poliedro con dimensión tı́picamente
menor a n.

4.2. Funciones convexas

En esta parte vamos a considerar funciones que toman valores en R [ {1} y definimos
el dom(f ) como el conjunto de valores que toma valor finito.

Definición. f : Rn 7! R [ {1} es una función convexa si para todo x, y 2 Rn y ↵ 2 [0, 1]

se tiene que
f (↵x + (1 ↵)y)  ↵f (x) + (1 ↵)f (y),
y es estrictamente convexa si la desigualdad es estricta para todo x 6= y y ↵ 2 (0, 1).

Es claro que si f es convexa entonces dom(f ) es un conjunto convexo. Algunos ejemplos

de funciones convexas son las funciones afines y normas.
Algunas propiedades de las funciones convexas son las siguientes (intente probar algunas
de ellas):

27
 1. Combinación positiva de funciones convexas en convexa.
2. Conjuntos de nivel de funciones convexas son convexos. Note que el converso no es
cierto.
3. Si f es convexa, entonces f (Ax + b) es convexa.
4. f es convexa si y solo si epi(f ) es convexo.
5. Sea {fi }i2I colección de funciones convexas. Entonces f (x) := sup fi (x) es convexa.
i2I
Para ver esto notemos que \
epi(f ) = epi(fi ).
i2I
Ası́, el resultado se sigue de la propiedad anterior. Un ejemplo importante de esta
propiedad es la llamada función de soporte de un conjunto B ⇢ Rn definida como
B (x) = sup hy, xi,
y2B

la cual es siempre convexa y semicontinua por debajo por el mismo argumento de antes.
6. Si g : Rn+m 7! R [ {1} es convexa, entonces f (x) := ı́nfm g(x, y) es convexa. Para ver
y2R
esto tomemos x1 , x2 2 dom(f ), luego existen {y1k } y {y2k } tales que g(x1 , y1k ) # f (x1 ) y
g(x2 , y2k ) # f (x2 ). Luego, para ↵ 2 [0, 1]
f (↵x1 + (1 ↵x2 ))  g(↵x1 + (1 ↵x2 ), ↵y1k + (1 ↵y2k ))
 ↵g(x1 , y1k ) + (1 ↵)g(x2 , y2k ) # ↵f (x1 ) + (1 ↵)f (x2 ).

El siguiente resultado se conoce como la desigualdad de Jensen.

Proposición. Sea f convexa, entonces
k
! k
X X
f ↵ i xi  ↵i f (xi ),
i=1 i=1

donde los ↵i forman una combinación convexa.

Prueba. Puesto que (xi , f (xi )) 2 epi(f ), que es convexo, entonces
k k k
!
X X X
↵i (xi , f (xi )) = ↵ i xi , ↵i f (xi ) 2 epi(f ),
i=1 i=1 i=1

y esto muestra el resultado.

Un corolario del resultados anterior es el siguiente: Sea B = {x1 , . . . , xk } ⇢ dom(f ) y
M = máx f (xi ), entonces f (x)  M para todo x 2 conv(B). En particular esto muestra
i
que el máximo de una función convexa sobre un conjunto convexo cerrado siempre está en
la frontera del conjunto.
Veamos ahora algunas propiedades y caracterizaciones de funciones convexas suaves.
Primero, tenemos que las nociones de diferenciabilidad de Gâteaux y Fréchet son equivalentes
en funciones convexas.

28
Teorema. Sea C convexo con interior no vacı́o y f convexa en C. Si x 2 C es Gâteaux
diferenciable en x entonces f es Fréchet en x.

Prueba. Sea g : Rn 7! R definida por g(h) = f (x + h) f (x) hrf (x), hi. Notemos que g
es convexa y además g(0) = 0 y Gâteaux diferenciable en 0 con rg(0) = 0. Ahora, usando
la desigualdad de Jensen, para h 2 Rn se tiene que
n
! n
1X 1X
g(h) = g nhi ei  g(nhi ei )
n i=1 n i=1
X g(nhi ei )
= hi
hi 6=0
nhi
!1/2
X ✓ g(nhi ei ) ◆2
 khk
h 6=0
nhi
i
X g(nhi ei )
 khk ,
h 6=0
nh i
i

donde la penúltima desigualdad se sigue de la desigualdad de Cauchy-Schwarz y la última

de la desigualdad de normas k · k  k · k1 . Por otro lado la convexidad de g implica que
0 = 2g(0)  g( h) + g(h), por lo tanto
X g( nhi ei ) g( h) g(h) X g(nhi ei )
   .
h 6=0
nh i khk khk h 6=0
nh i
i i

Finalmente, como cada uno de los términos dentro de las sumas de los extremos converge a
@g
@xi
(0) = 0 cuando hi ! 0, entonces g(h) = o(khk) lo que es equivalente a que f es Fréchet
en x.
Seguimos con una caracterización de primer orden.

Teorema. Sea C ⇢ Rn convexo y f Gâteaux diferenciable en un abierto U que contiene a

C. Entonces f es convexa en C si y solo si para todo x, y 2 C se tiene que

f (y) f (x) + hrf (x), y xi.

Lo que dice el teorema es que una función es convexa si y solo si la función siempre está
por encima de su aproximación de primer orden en todo punto.
Prueba. Supongamos primero que f es convexa y sea x 6= y 2 C. Sea g : (0, 1] 7! R dada por

f (x + t(y x)) f (x)

g(t) = . (19)
t
Veamos que g es una función creciente. Sean 0 < t1 < t2 , entonces
✓ ◆
t1 t1
x + t1 (y x) = 1 x + (x + t2 (y x)) ,
t2 t2

29
luego ✓ ◆
t1 t1
f (x + t1 (y x))  1 f (x) + f (x + t2 (y x)),
t2 t2
que es equivalente a que g(t1 )  g(t2 ). Ası́ que
hrf (x), y xi = lı́m g(t)  g(1) = f (y) f (x).
t#0

Para el converso, sea z = ↵x + (1 ↵)y para ↵ 2 [0, 1], entonces

f (x) f (z) + hrf (z), x zi, f (y) f (z) + hrf (z), y zi,
y multiplicando por ↵ y 1 ↵ respectivamente cada desigualdad, y sumándolas, se tiene que
↵f (x) + (1 ↵)f (y) f (z) + hrf (z), ↵x + (1 ↵)y zi = f (z).

El resultado anterior también se cumple si consideramos funciones estrictamente convexas

y cambiamos la desigualdad por una desigualdad estricta. Un corolario muy importante del
resultado anterior es si x 2 C es un punto crı́tico, entonces x es mı́nimo global de f en C,
esto es, una condición suficiente para mı́nimo global es ser punto crı́tico.
Ahora, si f 2 C 2 podemos caracterizar las funciones convexas a partir de la matriz
Hessiana.
Teorema. Sea C ⇢ Rn convexo y f 2 C 2 (U ) con U abierto que contiene a C. Entonces, f
es convexa en C si y solo si Hf (x) ⌫ 0 para todo x 2 C.
Prueba. Sea f es convexa y sean d 2 Rn y x 2 C. Para t > 0 suficientemente pequeño, por
el teorema anterior se tiene que
t2
f (x) + thrf (x), di  f (x + td) = f (x) + thrf (x), di + hHf (x)d, di + o(t2 ),
2
2
luego hHf (x)d, di + o(tt2 ) 0, y tomando t ! 0 se tiene que hHf (x)d, di 0. Para el
converso, sean x 6= y 2 C, entonces existe z 2 (x, y) tal que
1
f (y) = f (x) + hrf (x), y xi + hHf (z)(y x), y xi f (x) + hrf (x), y xi,
2
luego f es convexa por el resultado anterior.
Igual que en el caso anterior la función es estrictamente convexa si y solo si la Hessiana
es definida positiva.

5. Optimización convexa suave

5.1. Método del descenso del gradiente - Caso C 1 convexo
Además de la convexidad, igual que en el caso general, vamos a asumir que su gradiente
es Lipschitz con contante L. Igual que antes, tenemos que el paso óptimo es ↵ = L1 y de (4)
tenemos que
1
f (xk+1 )  f (xk ) krf (xk )k2 . (20)
2L
Veamos ahora un lema necesario para mostrar la convergencia.

30
Lema. Para todo x, y 2 Rn se tiene

hrf (y) rf (x), y xi  Lky xk2 , (21)

1
hrf (x), y xi + krf (x) rf (y)k2  f (y) f (x), (22)
2L
y
1
krf (x) rf (y)k2  hrf (y) rf (x), y xi. (23)
L
Prueba. La desigualdad (21) se obtiene de sumar dos veces (3) intercambiando x y y. Ahora,
sea x 2 Rn arbitrario y (y) := f (y) hrf (x), yi. Es claro que es también una función
convexa con gradiente Lipschitz con contante L. Además, r (x) = 0, luego x es un mı́nimo
global de . Ası́ que, usando (3), para todo y 2 Rn
✓ ◆
1
f (x) hrf (x), xi = (x)  y r (y)
L
⌧
1 1
 (y) r (y), r (y) + kr (y)k2
L 2L
1
= (y) kr (y)k2
2L
1
= f (y) hrf (x), yi krf (x) rf (y)k2 .
2L
La tercera desigualdad sale de sumar dos veces la segunda intercambiando x y y.

Veamos ahora la convergencia del método, para esto definimos rk = kxk x⇤ k, y para
una tamaño de paso 0 < ↵k < L2 tenemos
2
rk+1 = kxk x⇤ ↵k rf (xk )k2
= rk2 2↵k hrf (xk ), xk x⇤ i + ↵k2 krf (xk )k2
= rk2 2↵k hrf (xk ) rf (x⇤ ), xk x⇤ i + ↵k2 krf (xk )k2
✓ ◆
2 2
 rk ↵ k ↵k krf (xk )k2 ,
L
donde la última desigualdad se sigue de (23). Tenemos entonces que rk  r0 . Ahora, por la
convexidad de f tenemos también que

k := f (xk ) f ⇤  hrf (xk ), xk x⇤ i  r0 krf (xk )k.

Tomemos ahora el paso óptimo ↵ = L1 , de (20) obtenemos

1 2
k+1  k k  k,
2Lr02
y dividiendo por k k+1 tenemos
1 1 1 k 1 1
+ + .
k+1 k 2Lr02 k+1 k 2Lr02

31
Finalmente, si sumamos esta desigualdad entre 0 a k, llegamos a
1 1 k+1
+ ,
k+1 0 2Lr02

y puesto que (usando (3)) f (x0 )  f ⇤ + L2 kx0 x⇤ k2 , obtenemos la cota

2L(f (x0 ) f ⇤ )kx0 x⇤ k2 2Lkx0 x⇤ k2

f (xk ) f⇤   .
2Lkx0 x⇤ k2 + k(f (x0 ) f ⇤ ) (k + 4)

Este es un resultado mucho mejor que el que se obtiene en el caso general, donde no podemos
garantizar la convergencia a un mı́nimo (local). En este caso siempre se converge a un óptimo
(aunque a una tasa sublineal).

5.1.1. Caso fuertemente convexo

Recordemos que cuando f 2 C 2 , más otras condiciones adicionales, sı́ pudimos garantizar
la convergencia al mı́nimo a una tasa lineal, siempre que iniciemos el método cerca de x⇤ .
Veamos que en el caso convexo no tenemos que pedirle tanta regularidad a f pero si un tipo
de convexidad más fuerte.

Definición. Una función f 2 C 1 es fuertemente convexa si existe µ > 0 tal que para todo
x, y 2 Rn
µ
f (y) f (x) + hrf (x), y xi + ky xk2 . (24)
2
Si sumamos dos veces (24), intercambiando x y y, tenemos que para todo x, y 2 Rn

hrf (y) rf (x), y xi µky xk2 , (25)

y si además usamos que el gradiente de f es L-Lipschitz, usando (21) tenemos que

µky xk2  hrf (y) rf (x), y xi  Lky xk2 .

L
Definimos Qf = µ
1. Definimos ahora la función
µ
(x) = f (x) kxk2 , (26)
2
queremos ver que es convexa y su gradiente es (L µ)-Lipschitz. Puesto que r (x) =
rf (x) µx, (25) implica que

hr (y) r (x), y xi = hrf (y) rf (x), y xi µky xk2 0, (27)

es decir, es convexa por ejercicio de la tarea. Ahora, usando (21) tenemos, para todo
x, y 2 Rn , que
hr (y) r (x), y xi  (L µ)ky xk2 . (28)

32
Si L = µ, esto implica que r es constante, luego es 0-Lipschitz, y además de (27) y (23)
tenemos que
µL 1 µ 1
kx yk2 + krf (y) rf (x)k2 = kx yk2 + krf (y) rf (x)k2
µ+L µ+L 2 2µ
 hrf (y) rf (x), y xi.
Si µ < L, (28) implica que
Z1
(y) (x) hr (x), y xi = hr (x + t(y x)) r (x), y xidt
0
Z1
L µ
 (L µ)tky xk2 dt = ky xk2 ,
2
0

es decir, satisface (3), que es condición suficiente para que también satisfaga (23) (ver
prueba del Lema), luego
1
kr (x) r (y)k2  hr (y) r (x), y xi  kr (x) r (y)kky xk,
L µ
lo que muestra que r es (L µ)-Lipschitz. Además de (27) se tiene que
1
hrf (y) rf (x), y xi µky xk2 krf (y) rf (x)k2
L µ
2µ µ2
hrf (y) rf (x), y xi + ky xk2 ,
L µ L µ
que es equivalente a que
µL 1
kx yk2 + krf (y) rf (x)k2  hrf (y) rf (x), y xi, (29)
µ+L µ+L
lo mismo que en el caso µ = L.
Esto nos va a permitir encontrar la tasa de convergencia del método en este caso. Para
2
una tamaño de paso 0 < ↵  L+µ tenemos de (29) que
2
rk+1 = kxk x⇤ ↵rf (xk )k2
= rk2 2↵hrf (xk ) f (x⇤ ), xk x⇤ i + ↵2 krf (xk )k2
✓ ◆ ✓ ◆
2 2↵µL 2
 rk 1 ↵ ↵ krf (xk )k2 ,
L+µ L+µ
2
con lo cual, si ↵ = L+µ
se tiene que
✓ ◆ ✓ ◆k
L µ Qf 1
rk  rk 1  r0 ,
L+µ Qf + 1
y usando (3)
✓ ◆2k
⇤L 2 Qf 1
f (xk ) f  rk  r02 ,
2 Qf + 1
es decir, tenemos una convergencia con tasa lineal con cualquier punto inicial.

33
5.2. Método acelerado de Nesterov
Vamos a asumir que f es convexa y que su gradiente es Lipschitz con contante L. Bajo
estos supuestos es posible construir un método del tipo búsqueda lineal que tiene una tasa
mejor que o(1/k), que fue la que obtuvimos antes. Se puede mostrar que el método que vamos
a analizar ahora es óptimo en términos de la tasa de convergencia o(1/k 2 ). La idea es hacer
una búsqueda lineal con el método del gradiente con paso constante, pero considerando un
paso anterior en la iteración.

p 2
k 1+ 1+4 1
Iniciar 0 = 0 y obtener las sucesiones: k+1 2
y k
k
k+1
;
Iniciar x1 = y1 arbitrario;
para k = 1, 2, . . . hacer
yk+1 xk L1 rf (xk );
xk+1 (1 k )yk+1 + k yk ;
fin
Algoritmo 3: Acelerado de Nesterov

Notemos que k  0 y que 2k = 2k+1 k+1 para todo k. Usando inducción podemos ver
p
k 1 1+ 5 1 (k 1)2
que k > 2 , en efecto, 2 = 2 > 2 y, 2k+1 k+1 > 4
, lo que implica que k+1 > k2
2 2
pues k4 k
2
< (k 41) y la función x 7! x2 x es estrictamente creciente después de 12 .
Analicemos ahora la convergencia del algoritmo 3. Primero, de (3) y la convexidad de f ,
para x, y 2 Rn se tiene que
✓ ◆ ✓ ◆
1 1
f x rf (x) f (y)  f x rf (x) f (x) hrf (x), y xi
L L
1
 hrf (x), x yi krf (x)k2 .
2L
Tomando x = xk y y = yk , y x = xk y y = x⇤ en la desigualdad de arriba tenemos que
1
f (yk+1 ) f (yk )  hrf (xk ), xk yk i krf (xk )k2
2L
L
= Lhyk+1 x k , xk yk i kyk+1 xk k2
2
y
L
f (yk+1 ) f (x⇤ )  Lhyk+1 x k , xk x⇤ i kyk+1 xk k2 .
2
Multiplicando la primera desigualdad por ( k 1), sumando a la segunda y denotando
k = f (yk ) f (x⇤ ), tenemos

L k
k k+1 ( k 1) k  Lhyk+1 xk , k xk ( k 1)yk x⇤ i kyk+1 xk k2 .
2

34
Multiplicando esta desigualdad por k y usando la relación entre k y k 1 tenemos
L
2
k k+1
2
k 1 k  k k (yk+1 xk )k2 + 2h k (yk+1 xk ), k xk ( k 1)yk x⇤ i
2
L
= k k yk+1 ( k 1)yk x⇤ k2 k k xk ( k 1)yk x⇤ k2
2
L
= k k xk ( k 1)yk x ⇤ k2 k k+1 xk+1 ( k+1 1)yk+1 x ⇤ k2 ,
2
donde la última igualdad viene de la definición de xk+1 y k en el algoritmo. Si definimos
rk = k k xk ( k 1)yk x⇤ k, tenemos que

2 2 L 2 2
k k+1 k 1 k  (r rk+1 ),
2 k
y sumando estas desigualdades de k = 1, . . . , N , obtenemos
L 2L
N +1  2
(r12 2
rN +1 )  r12 .
2 N (N 1)2

5.3. Método de (Quasi-)Newton

5.3.1. Caso fuertemente convexo C 2
Vamos a ahora a suponer que f 2 C 2 . Si detallamos con cuidado la forma como se
mostró la convergencia cuadrática del método de Newton en el caso general, las condiciones
importantes sobre f son: a) Hf es K-Lipschitz y b) Hf (x) ⌫ µI para todo x suficientemente
cerca a x⇤ y algún µ > 0. Bien, la condición b) se tiene para todo x 2 Rn si f es fuertemente
convexa. En efecto, recordemos que definida en (26) es convexa, luego

0 H (x) = Hf (x) µI.

Ası́ que el método de Newton en este caso sigue con la misma convergencia cuadrática
iniciando desde cualquier punto.
Ahora, la definición de convexidad fuerte implica que f es coerciva, luego los conjuntos
de nivel son convexos y acotados y por lo tanto, para x0 2 Rn arbitrario el conjunto L =
{x 2 Rn : f (x)  f (x0 )} es convexo y compacto. Además, como Hf es continua se tiene que
existe M > 0 tal que para todo x 2 L

µI Hf (x) M I.

Esto es suficiente para mostrar que el método BFGS converge a x⇤ a una tasa superlineal
(ver teoremas 6.5 y 6.6 en [NW]).

5.3.2. Caso self-concordant

Ver libro de Nesterov.

35
6. Conceptos básicos de análisis convexo
Vimos antes que puntos crı́ticos de funciones convexas son óptimos globales. Si f no es
diferenciable no es posible hablar de puntos crı́ticos, aún ası́ tenemos el siguiente resultado.

Teorema. Sea f : C 7! R con C convexo y f convexa. Entonces si x es un mı́nimo local de

f en C, entonces es mı́nimo global.

Prueba. Sea y 2 C y ↵ 2 (0, 1) suficientemente pequeño de tal forma que

f (x)  f (x + ↵(y x))  ↵f (y) + (1 ↵)f (x),

es decir, f (x)  f (y).

Veamos ahora algunas propiedades de regularidad de las funciones convexas generales.
Es claro que no tienen que ser C 1 .
Recordemos⇢que un corolario de la desigualdad de Jensen es que si f convexa está definida
Pn
en el conjunto x 2 Rn : |xi |  1 , esto es, la bola de radio 1 centrada en el origen con
i=1
la norma `1 , entonces f alcanza su máximo en la bola. Esto implica que si f es convexa
definida en la bola Br (x), para algún r > 0, entonces existe m 2 R tal que f (x)  m para
todo y 2 Br (x). Asumiendo x = 0 sin pérdida de generalidad, tenemos entonces que para
todo y 2 Br (0) se tiene que 0 = 12 y + 12 (y), luego

1 1 1 1
f (0)  f (y) + f ( y)  f (y) + m,
2 2 2 2
esto es, f (y) 2f (0) m y por lo tanto |f (y)|  2|f (0)| + |m|. Con lo anterior tenemos el
siguiente resultado.

Lema. Sea f convexa definida en la bola Br (x). Entonces existe M > 0 tal que |f (y)|  M
para todo y 2 Br (x).

El anterior lema nos permite mostrar lo siguiente:

Teorema. Sea f convexa definida en la bola Br (x). Entonces f es Lipschitz sobre la bola
Be ✏ (x) para todo 0 < ✏ < r.

Prueba. Sin pérdida de generalidad podemos asumir x = 0. Sean x, y 2 Br ✏ (0), definimos

✏
z=y+ (y x) 2 Br (0).
kx yk

Notemos que
✏ kx yk
y= x+ z,
✏ + kx yk ✏ + kx yk
luego
✏ kx yk
f (y)  f (x) + f (z),
✏ + kx yk ✏ + kx yk

36
que es equivalente a
✏(f (y) f (x))  kx yk(f (z) f (y)).
Finalmente, por el lema anterior e intercambiando los x y y, tenemos que
2M
|f (x) f (y)|  kx yk.
✏

Corolario. Si f es convexa, entonces f es continua en el interior de su dominio.

La conclusión del teorema anterior es que toda función convexa es localmente Lipschitz
continua, con lo cual se tiene que la función es diferenciable en casi todo punto por el teorema
de Rademacher. De hecho se puede mostrar que las derivadas direccionales existen en todo
punto. En efecto, dado d 2 Rn y x en el interior del dominio de f consideremos la función
t 7! f (x+td)t f (x) (ver (19)). Por un lado, si s > 0, entonces
s t
f (x)  f (x + td) + f (x sd),
t+s s+t
que es equivalente a que
f (x) f (x sd) f (x + td) f (x)
 ,
s t
esto es, la función es acotada por debajo para todo t > 0. Por otro lado sabemos que la
función es creciente, luego la derivada direccional existe y está dada por
f (x + td) f (x)
f 0 (x; d) = ı́nf .
t>0 t
Ahora, esto no implica que la f es Gâteaux diferenciable pues no sabemos si la derivada
direccional es lineal, aunque sı́ es positivamente homogénea y convexa (ejercicio). Finalmente,
sea y en el dominio de la función y ↵ 2 (0, 1), entonces
f (x + ↵(y x))  ↵f (y) + (1 ↵)f (x),
que es equivalente a
✓ ◆
f (x + ↵(y x) f (x))
f (y) f (x + ↵(y x)) + (1 ↵) ,
↵
y tomando ↵ # 0, la continuidad de f implica que
f (y) f (x) + f 0 (x, y x). (30)
Esto nos recuerda la caracterización de funciones convexas que son Gâteaux diferenciables y
motiva la siguiente definición central en el estudio de funciones convexas.
Definición. Sea f convexa. Decimos que g 2 Rn es un subgradiente de f en x 2 dom(f ) si
para todo x 2 dom(f ) se tiene que
f (y) f (x) + hg, y xi.
El conjunto de todos los subgradientes de f en x lo llamamos subdiferncial y lo notamos
como @f (x).
En lo que resta de esta sección alternaremos resultados sobre subgradientes y teoremas
de separación.

37
6.1. Subgradientes I
Notemos que

@f (x) = {g : hg, y xi  f (y) f (x) 8y 2 dom(f )}

\
= {g : hg, y xi  f (y) f (x)},
y2dom(f )

esto es, es la intersección de conjuntos convexos y cerrados, luego @f (x) es convexo y cerrado.

Proposición. Sean f convexa y x 2 int(dom(f )). Entonces @f (x) es compacto.

Prueba. Ya sabemos que es cerrado, falta ver que es acotado. Como toda función convexa es
localmente Lipschitz, existen ✏ > 0 y M > 0 tales que

|f (y) f (x)|  M ky xk
g
para todo y 2 B✏ (x). Sea g 2 @f (x) distinto de 0, entonces tomando y = x + ✏ kgk 2 B✏ (x),
se tiene que
✏kgk = hg, y xi  f (y) f (x)  M ky xk = ✏M,
esto es kgk  M .

Ejemplo. Si f es Gâteaux en x, es claro que rf (x) 2 @f (x).

p
Sea f (x) = x para x 0. Se tiene que @f (0) es vacı́o.

Dado C convexo definimos la función C (x) = 0 si x 2 C y de lo contrario se asigna

el valor 1. Es claro que esta es una función convexa. Si x 2
/ C es claro que @ C (x) es
vacı́o. Ahora, para x 2 C si g 2 @ C (x) entonces para todo y

C (y) C (x) + hg, y xi,

es decir, hg, y xi  0 para todo y 2 C. A este conjunto se le llama el cono normal a

C en x.

Dada una norma k · k en Rn , podemos definir su norma dual como

kyk⇤ = máx hx, yi.

kxk1

Además, la norma dual de la dual es la norma original, es decir,

kxk = máx hx, yi.

kyk⇤ 1

Se tiene que la norma dual de la norma euclidiana es la misma norma euclidiana y la

norma dual de la norma `1 es la norma `1 . Se tiene además que para todo x, y 2 Rn
se cumple la desigualdad
hx, yi  kxkkyk⇤ .

38
 Vamos ahora a calcular el subdiferencial de la función k · k. Sea x 2 Rn y g 2 @kxk,
entonces para todo d con kdk  1 se tiene que

hg, di + kxk  kx + dk  kxk + kdk  kxk + 1,

por lo tanto hg, di  1, y como esto vale para todo d en la esfera unitaria, entonces
kgk⇤  1. Ahora, tomando y = 0 en la desigualdad del subgradiente se tiene que
hg, xi + kxk  0, lo que implica que

kxk  hg, xi  kgk⇤ kxk  kxk.

Conversamente, sea g tal que kgk⇤  1 y además hg, xi = kxk. Entonces, para todo y
se tiene que
hg, y xi + kxk = hg, yi  kgk⇤ kyk  kyk,
luego g 2 @kxk.

Sabemos que en el caso suave ser punto crı́tico es equivalente a ser mı́nimo global. En el
caso general se tiene un resultado análogo.

Teorema. x es mı́nimo global de Rn para f convexa si y solo si 0 2 @f (x).

Prueba. Si 0 2 @f (x), entonces para todo y 2 Rn se tiene f (y) f (x) + h0, y xi = f (x).
Ahora, si x es mı́nimo global de f entonces para todo y 2 Rn f (y) f (x) = f (x)+h0, y xi.

Si queremos optimizar sobre un conjunto convexo tenemos el siguiente resultado.

Proposición. Si g 2 @f (x) es tal que hg, y xi 0 para todo y 2 C, entonces x es mı́nimo

global de f en C.

Prueba. Para todo y 2 C se tiene que f (y) f (x) + hg, y xi f (x).

Veamos algunas aplicaciones del resultado anterior:

Consideremos minimizar f convexa y suave sobre el conjunto C = {x : Ax = b}, con

A matriz de m ⇥ n y b 2 Rm . C es entonces un conjunto afı́n. Buscamos x⇤ 2 C tal
que hrf (x⇤ ), y x⇤ i 0 para todo y 2 C. Como x⇤ , y 2 C, entonces A(x⇤ y) = 0,
luego necesitamos que hrf (x⇤ ), zi 0 para todo z en el espacio nulo de A, pero como
esto es un subespacio de Rn , esto quiere decir que hrf (x⇤ ), zi = 0 para todo z en el
espacio nulo de A. Ahora, como el ortogonal del espacio nulo de A es el rango de AT ,
entonces una condición necesaria para que x⇤ sea mı́nimo es que exista 2 Rm tal que

rf (x⇤ ) T
A = 0.

Consideremos ahora minimizar f (x) = ha, xi con a 6= 0 sobre C = Br (0). Este problema
surgió anteriormente en el método de regiones de confianza. En este caso la condición
para la optimalidad de x⇤ es que ha, y x⇤ i 0 para todo y 2 Br (0). Usando la
r
desigualdad de Cauchy-Schwartz es fácil ver que x⇤ = kak a satisface la desigualdad.

39
6.2. Teoremas de separación I
En algunos ejemplos vimos casos donde el subdiferencial puede ser vacı́o. Los siguientes
resultados serán una herramienta importante para ver cuándo no sucede esto.
Sean z 2 Rn y C ⇢ Rn cerrado y convexo, consideremos el problema de minimzar
f (x) = 12 kx zk2 sobre C. Como f es coerciva y continua entonces los subconjuntos de
nivel son compactos y por lo tanto su intersección con C también lo son. Esto implica que
existe un mı́nimo global de f sobre C. Además f es estrictamente convexa pues Hf ⌘ I,
esto implica que el mı́nimo global es único x⇤ . Podemos entonces dar la siguiente definición:
Definición. Dado C ⇢ Rn cerrado y convexo, y z 2 Rn , definimos la proyección de z sobre
C como
⇡C (z) = arg mı́n kx zk.
x2C

Es claro que si z 2 C su proyección es el mismo z. También es fácil de ver que si C es un

subespacio, la proyección coincide con la proyección ortogonal usual.
Ahora, como rf (x) = x z, una condición suficiente para encontrar ⇡C (z) es que

h⇡C (z) z, x ⇡C (z)i 0

para todo x 2 C. Esta desigualdad en realidad caracteriza la proyección.

Proposición. Dado C ⇢ Rn cerrado y convexo, y z 2 Rn . Entonces

h⇡C (z) z, x ⇡C (z)i 0

Prueba. Sea x 2 C y ↵ 2 (0, 1], entonces ↵x + (1 ↵)⇡C (z) 2 C, luego

k⇡C (z) zk2  k↵x + (1 ↵)⇡C (z) zk2

= k⇡C (z) z + ↵(x ⇡C (z))k2
= k⇡C (z) zk2 + ↵2 kx ⇡C (z)k2 + 2↵h⇡C (z) z, x ⇡C (z)i,

esto es
↵
kx ⇡C (z)k2  h⇡C (z) z, x ⇡C (z)i,
2
y tomando ↵ # 0 se tiene el resultado.
Esta caracterización permite mostrar que la función proyección sobre C es Lipschitz
continua.
Corolario. La función ⇡C : Rn 7! C es Lipschitz continua con constante 1.
Prueba. Sean x1 , x2 2 Rn , entonces la desigualdad variacional anterior dice que

hx1 ⇡C (x1 ), ⇡C (x2 ) ⇡C (x1 )i  0

hx2 ⇡C (x2 ), ⇡C (x1 ) ⇡C (x2 )i  0,

y sumándolas se tiene que

hx1 x2 + ⇡C (x2 ) ⇡C (x2 ), ⇡C (x2 ) ⇡C (x1 )i  0,

40
luego

k⇡C (x2 ) ⇡C (x1 )k2  hx2 x1 , ⇡C (x2 ) ⇡C (x1 )i  kx2 x1 kk⇡C (x2 ) ⇡C (x1 )k.

La proyección sobre conjuntos convexos cerrados nos permite llegar a los llamados teo-
remas de separación.

Teorema (Separación estricta de puntos). Sea C conjunto no vacı́o, convexo y cerrado y

z2/ C. Entonces existe un hiperplano que separa estrictamente C de z, esto es, existe a 6= 0
tal que
ha, zi > supha, xi(= C (a)).
x2C

Prueba. Sea a = z ⇡C (z) 6= 0 pues z 2

/ C, ası́ que la desigualdad variacional implica que
para todo x 2 C vale

0 ha, x ⇡C (z)i = ha, x z + ai = ha, x zi + kak2 ,

luego
ha, zi ha, xi + kak2 .

Teorema (Hiperplanos de soporte). Sea C conjunto no vacı́o, cerrado y convexo y z 2

C \ int(C) = @(C). Entonces existe un hiperplano de soporte C en z, esto es, existe a 6= 0
tal que para todo x 2 C
ha, z xi 0.

Prueba. Sea {xk } ⇢ C C que converge a z, es decir una sucesión que converge a z desde afuera
de C, por lo tanto ⇡C (xk ) 6= xk . Sea

xk ⇡C (xk )
ak = ,
kxk ⇡C (xk )k

entonces la desigualdad variacional implica que para todo x 2 C

hak , ⇡c (xk ) xi 0.

Como la sucesión {ak } está en un compacto, tiene un subsucesión convergente a a 6= 0 pues

tiene norma 1. Puesto que ⇡C (xk ) ! ⇡C (z) = z, al tomar el lı́mite de la subsucesión a infinito
se tiene que
0  ha, z xi,
lo que muestra el resultado.

41
6.3. Subgradientes II
Podemos ahora seguir con la discusión sobre los subdiferenciales. Recordemos que estos
son siempre convexos y compactos.
Teorema. Sean f convexa y semicontinua por debajo, y x 2 int(dom(f )). Entonces @f (x)
es no vacı́o.
Prueba. Sabemos que (x, f (x) 2 @(epi(f )), la frontera de epi(f ) que es un conjunto convexo
y cerrado. Entonces existe un hiperplano de soporte del epigrafo en (x, f (x), es decir, existen
un vector a y un escalar con kak2 + 2 = 1 tales que
ha, x yi (t f (x)),
para todo (y, t) 2 epi(f ). Si t > f (x) entonces (x, t) 2 epi(f ), luego  0. Si < 0, tomando
g = a , y (y, f (y)) 2 epi(f ) y dividiendo por en la desigualdad de arriba se tiene que
f (y) f (x) + hg, y xi,
luego g 2 @f (x). Veamos entonces que no puede ser 0. Como toda función convexa es
localmente Lipschitz, existen ✏ > 0 y M > 0 tales que
|f (y) f (x)|  M ky xk
para todo y 2 B✏ (x), y puesto que  0, se tiene que
ha, x yi (f (y) f (x)) M kx yk.
Tomando y = x + ✏a 2 B✏ (x), tenemos que  kak M
, lo que implica que < 0.
En realidad no es necesario que la función sea semicontinua para tener ele resultado. Vea-
mos ahora la relación entre derivadas direccionales funciones de soporte de subdiferenciales.
Teorema. Sean f convexa, x 2 int(dom(f )) y d 2 Rn . Entonces
f 0 (x; d) = máx hg, di = @f (x) (d).
g2@f (x)

Prueba. Sea g 2 @f (x), entonces para todo t > 0 se tiene f (x + td) f (x) + thg, di, luego
f (x + td) f (x)
hg, di  ,
t
y tomando t # 0 se tiene que f 0 (x; d) hg, di, ası́ que f 0 (x; d) máx hg, di. Para mostrar
g2@f (x)
la otra desigualdad vamos usar dos resultados auxiliares. Recordemos que la función f 0 (x; ·)
es convexa sobre todo Rn .
@f (x) = @f 0 (x; 0). En efecto, puesto que f 0 (x; 0) = 0, y por el mismo argumento de
arriba f 0 (x; h) hg, hi para todo g 2 @f (x) y todo h 2 Rn , entonces
f 0 (x; h) hg, hi = f 0 (x; 0) + hg, hi,
luego @f (x) ⇢ @f 0 (x; 0). Para la otra contenencia, sea g 2 @f 0 (x; 0) y sea y 2 dom(f ),
entonces f 0 (x; y x) hg, y xi, luego, por (30)
f (y) f (x) + f 0 (x; y x) f (x) + hg, y xi,
esto es, g 2 @f (x).

42
 @f 0 (x; h) ⇢ @f 0 (x; 0) para todo h 2 Rn . Sea g 2 @f 0 (x; h), entonces, para todo b 2 Rn
se tiene que
f 0 (x; b) f 0 (x; h) + hg, b hi
y para todo ⌧ > 0, por la homogeneidad positiva,se tiene que

⌧ f 0 (x; b) = f 0 (x; ⌧ b) f 0 (x; h) + hg, ⌧ b hi,

esto es,
f 0 (x; h) hg, hi
f 0 (x; b) + hg, bi (31)
⌧
y tomando ⌧ ! 1 se tiene que f 0 (x; b) hg, bi, luego g 2 @f 0 (x; 0).

Volviendo a la desigualdad que queremos, para esto debemos encontrar un gd 2 @f (x) tal
que f 0 (x; d)  hgd , di. Sea gd 2 @f 0 (x; d) ⇢ @f (x) (y los subdiferenciales son no vacı́os),
entonces (31) se convierte en

f 0 (x; d) hgd , di
f 0 (x; b) + hgd , bi
⌧
y tomando ⌧ # 0 obtenemos que f 0 (x; d)  hgd , di.
Este teorema tiene como corolarios varios resultados importantes.

Corolario. f es Gâteaux diferenciable en x 2 int(dom(f )) si y solo si |@f (x)| = 1. En este

caso @f (x) = {rf (x)}.

Prueba. Supongamos que f es Gâteaux diferenciable en x y g 2 @f (x), entonces para todo

d 2 Rn se tiene que hrf (x), di = f 0 (x; d) hg, di. Tomando d en la desigualdad anterior
tenemos entonces que hrf (x), di =< g, di para todo d, lo que implica que g = rf (x) y
@f (x) = {rf (x)}. Conversamente, si @f (x) = {g}, entonces f 0 (x; d) = hg, di para todo d,
luego la derivada direccional es lineal y por lo tanto f es Gâteaux diferenciable en x con
g = rf (x).

Definición. Sea f : Rn 7! R [ {1} y C ⇢ dom(f ). Definimos la norma de Lipschitz de f

con respecto a C como
|f (x) f (y)|
kf kLip,C = sup .
x,y2int(C) kx yk

Proposición. Sea f función convexa y Lipschitz en C ⇢ dom(f ) con C convexo. Entonces

kf kLip,C = sup kgk⇤ .

x2int(C),g2@f (x)

Demostración. Sea x 2 int(C) y d 2 Rn con kdk  1, para t > 0 suficientemente pequeño se

tiene que
f (x + td) f (x)  tkf kLip,C kdk,
luego
f (x + td) f (x)
 f kLip,C ,
t
43
es decir, f 0 (x; d)  kf kLip,C . Ahora, del teorema tenemos que

máx hg, di  kf kLip,C .

g2@f (x)

Tomando el máximo sobre x 2 int(C) y kdk  1 tenemos la primera desigualdad por la

definición de norma dual. Ahora, para la desigualdad contraria, sean x, y 2 C con gx 2 @(x)
y gy 2 @(y), entonces
f (y) f (x) + hgx , y xi,
luego
!
f (x) f (y)  hgx , x yi  kgx k⇤ kx yk  sup kgk⇤ kx yk.
x2int(C),g2@f (x)

Análogamente,
!
f (y) f (x)  hgy , y xi  kgy k⇤ ky xk  sup kgk⇤ ky xk.
x2int(C),g2@f (x)

Combinando las dos desigualdades tenemos que

!
|f (x) f (y)|  sup kgk⇤ kx yk.
x2int(C),g2@f (x)

Dado que x, y son arbitrarios se tiene finalmente que

kf kLip,C  sup kgk⇤ .

x2int(C),g2@f (x)

6.3.1. Cálculo con subgradientes

La siguiente es la herramienta principal para hacer cálculo con subgradientes.
Proposición. Sean C1 , C2 conjuntos no vacı́os cerrados y convexos.

1. Si C1  C2 , entonces C1 ⇢ C2 .

2. Si C1 = C2 , entonces C1 = C2 .

Prueba.

1. Supongamos que x 2 C1 \ C2 , entonces existe un hiperplano que separa estrictamente

x de C2 , esto es, existen a 6= 0 y tales que

ha, xi > ha, yi 8y 2 C2 .

Esto implica que C2 (a) < ha, xi  C1 (a) que es una contradicción. Luego C1 ⇢ C2 ,

44
 2. Se sigue del anterior.

Proposición. Sean f convexa con dominio en Rm , A 2 Rm⇥n , b 2 Rm . Definimos la función

convexa '(x) = f (Ax + b). Entonces para x 2 int(dom(')) se tiene que

@'(x) = AT @f (Ax + b).

Prueba. Es claro que ' es convexa. Sea y = Ax + b, entonces para d 2 Rn se tiene que

@'(x) (d) = '0 (x; d) = f 0 (y; Ad)

= máx hg, Adi = máx hAT g, di
g2@f (y) g2@f (y)

= máx hh, di = AT @(y) (d).

h2AT @f (y)

Proposición. Sean f1 , f2 funciones convexas y ↵1 , ↵2 reales no negativos. Si ' = ↵1 f1 +↵2 f2

y x 2 int(dom(')), entonces

@'(x) = ↵1 @f1 (x) + ↵2 @f2 (x).

Prueba. De nuevo, sabemos que ' es convexa. Además, x 2 int(dom(f1 )) \ int(dom(f2 )).
Entonces, para d 2 Rn se tiene que

@'(x) (d) = '0 (x; d) = ↵1 f10 (x; d) + ↵2 f20 (x, d)

= f10 (x; ↵1 d) + f20 (x, ↵2 d)
= máx hg, ↵1 di + máx hg, ↵2 di
g2@f1 (x) g2@f2 (x)

= máx h↵1 g1 + ↵2 g2 , di
g1 2@f1 (x),g2 2@f2 (x)

= máx hh, di = ↵1 @f1 (x)+↵2 @f2 (x) (d).

h2↵1 @f1 (x)+↵2 @f2 (x)

Se puede mostrar que el resultado también es cierto para todo x 2 dom(') siempre que
int(dom(f1 )) \ int(dom(f2 )) 6= ?.
Recordemos que al minimizar una función convexa sobre un conjunto convexo, una con-
dición suficiente para un mı́nimo local es la existencia de g 2 @f (x) es tal que hg, y xi 0
para todo y 2 C, veamos que también es una condición necesaria.
Corolario. Sean f convexa y C ⇢ dom(f ) convexo con interior no vacı́o, entonces x 2 C
es mı́nimo global de f sobre C si y solo si existe g 2 @f (x) tal que hg, y xi 0 para todo
y 2 C.
Prueba. Consideremos ' = f + C . Entonces para x 2 C se tiene que @'(x) = @f (x)+@ C (x).
Ahora, x es un mı́nimo global de f sobre C si y solo si es un mı́nimo de ', que es equivalente
a que 0 2 @'(x) = @f (x) + NC (x), que es equivalente a que exista g 2 @f (x) tal que

45
 g 2 NC (x), que es equivalente a que exista g 2 @f (x) tal que hg, y xi 0 para todo
y 2 C.
Si f es Gâteaux diferenciable, el resultado anterior nos dice que x es mı́nimo de f sobre
C si y solo si hrf (x), y xi 0 para todo y 2 C.
Proposición. Sean {fi }i2I funciones convexas y '(x) = sup fi (x). Si x 2 dom('), entonces
i2I

conv{@fi (x) : i 2 I(x)} ⇢ @'(x),

donde I(x) = {i 2 I : '(x) = fi (x)}.

Prueba. Sea i 2 I(x) y g 2 @fi (x), entonces para y 2 dom(fi ) se tiene que,

'(y) fi (y) fi (x) + hg, y xi = '(x) + hg, y xi,

luego g 2 '(x). Puesto que '(x) es convexo, se tiene el resultado.

Ahora, cuando se toma el máximo de finitas funciones este resultado se puede mejorar.
Proposición. Sea '(x) = máx fi (x) con fi convexa, y sea x 2 int(dom(')). Entonces
1im

conv{@fi (x) : i 2 I(x)} = @'(x),

con I(x) igual que antes.

Prueba. Supongamos, sin pérdida de generalidad, que I(x) = {1, . . . , k}. Sea d 2 Rn , entonces
se tiene que (ejercicio)
'0 (x; d) = máx fi0 (x; d).
1ik

Luego, como x 2 int(dom(fi )) para todo i,

@'(x) (d) = máx máx hgi , di

1ik gi 2@fi (x)
k
X
= máx i máx hgi , di
2 k gi 2@fi (x)
i=1
( k
)
X
= máx h i gi , di : gi 2 @fi (x), 2 k
i=1
( k
)
X
= máx hg, di : g = i g i , gi 2 @fi (x), 2 k
i=1
= máx {hg, di : g 2 conv{@fi (x) : i 2 I(x)}} .

La siguiente es una consecuencia muy útil del resultado anterior.

46
Corolario (Condiciones de KKT). Sean f, f1 , . . . , fm funciones convexas y Gâteaux diferen-
ciables en Rn . Supongamos que existe x̄ tal que fi (x̄) < 0 para i = 1, . . . , m (conocida como
la condición de Slater). Entonces x⇤ es óptimo del problema de optimización

f ⇤ = mı́n f (x)
sujeto a fi (x)  0, i = 1, . . . , m
x 2 Rn ,

si y solo si fi (x⇤ )  0 para todo i y además existen i 0 para i 2 I = {i : fi (x⇤ ) = 0} tales

que X
rf (x⇤ ) + rfi (x⇤ ) = 0.
i2I

Prueba. Sea '(x) = máx{f (x) f , f1 (x), . . . , fm (x)}, entonces ' 0 y además x⇤ es óptimo
⇤

del problema de optimización si y solo si x⇤ es mı́nimo global de ' con '(x⇤ ) = 0, si y solo
si 0 2 @'(x⇤ ), si y solo si 0 2 conv{rf (x⇤ ), rfi (x⇤ ), i 2 I}.

6.4. Teoremas de separación II

Veamos en esta parte algunas aplicaciones de los teoremas de separación principales que
vimos antes, estos son el teorema de separación estricta de un punto fuera de un convexo
cerrado y el teorema del hiperplano de soporte.
Teorema (Separación fuerte de conjuntos convexos). Sean A, B conjuntos convexos, cerra-
dos y disjuntos. Si uno de ellos es acotado entonces existen a 6= 0 y ↵ 2 R tales que

ı́nf ha, xi > ↵ > sup ha, yi.

x2A y2B

Prueba. Asumamos que B es compacto, en ese caso podemos cambiar el sup por máx. Sea
C = A B, entonces C es convexo y además no contiene al 0 pues A y B son disjuntos.
Veamos que C es cerrado. Sea zk = xk yk ! z sucesión convergente de elementos en C.
Como B es compacto tenemos una subsucesión de los yk convergente a y 2 B. Pasando
a la subsucesión tenemos entonces que xk ! y + z =: x, y como A es cerrado, entonces
y + z 2 A, luego z = x y 2 C. Ası́ que 0 2 / C convexo y cerrado, luego existe a 6= 0 tal
que ha, zi kak2 > 0 para todo z 2 C, es decir, ha, x yi kak2 para todo x 2 A y y 2 B.
2
Tomando ↵ = kak 2
+ máx ha, yi se tiene el resultado.
y2B

Teorema. Sea C convexo y cerrado. Entonces C es la intersección de todos los semiespacios

cerrados que lo contienen.
T
Prueba. Dados a 6= 0 2 Rn y ↵ 2 R, sea Ha,↵ = {y : ha, yi ↵}. Definimos D := Ha,↵ ,
C⇢Ha,↵
es decir, la intersección de todos los semiespacios que contienen a C. Es claro que D es cerrado
y convexo y además que C ⇢ D. Supongamos que x 2 D \ C, entonces existen a 6= 0 y ↵
tales que ha, xi < ↵ < ha, yi para todo y 2 C, luego x 2 / Ha,↵ y C ⇢ Ha,↵ y por lo tanto
D ⇢ Ha,↵ , lo que contradice que x 2 D.

47
Corolario. Sea C ⇢ Rn+1 convexo y cerrado tal que no contiene rectas verticales, es decir,
rectas con dirección (0, ), 6= 0. Entonces existe un semiespacio no vertical que lo contiene,
es decir, existen a, 6= 0 y ↵ tales que

ha, xi + xn+1 ↵

para todo (x, xn+1 ) 2 C.

Prueba. Supongamos que todo semiespacio que contiene a C es vertical, es decir, todos los
semiespacios que contienen a C tiene vector director de la forma (a, 0) y por lo tanto si
(x, xn+1 ) 2 C, luego está en todos los semiespacios verticales, entonces la recta {(x, t +
xn+1 ) : t 2 R}, con 6= 0 está en todos los semiespacios que contienen a C, luego está en C
y tenemos una contradicción.
Definición. Sea C ⇢ Rn no vacı́o. El cono dual de C, denotado como C ⇤ se define como

C ⇤ = {y 2 Rn : hx, yi 0 8x 2 C}.

Notemos que \
C⇤ = {y : hx, yi 0},
x2C

luego es intersección de semiespacios cerrados y por lo tanto es un cono convexo y cerrado.

Ahora, para todo x 2 C se tiene que hx, yi 0 para todo y 2 C ⇤ , luego x 2 C ⇤⇤ , esto es,
C ⇢ C ⇤⇤ .
Teorema. Sea C un cono convexo y cerrado, entonces C ⇤⇤ = C.
Prueba. Ya tenemos una dirección. Supongamos que x 2 C ⇤⇤ \ C, entonces, como x 2 / C
existe una hiperplano que separa estrictamente x de C, esto es, a 6= 0 tal que para todo
z 2 C se tiene que
ha, xi < ha, zi.
Como C es un cono la desigualdad anterior vale para tz con t > 0 y z 2 C, luego ha, zi 0
para todo z, esto es a 2 C ⇤ , y como x 2 C ⇤⇤ , se debe cumplir que ha, xi 0, lo que contradice
la desigualdad anterior tomando z = 0 2 C.

6.5. Funciones conjugadas

Dada f : Rn ! R [ {1}, definimos la conjugada convexa de f como:

f ⇤ (y) = sup hx, yi f (x).

x2Rn

Puesto que f ⇤ es el supremo de funciones convexas y cerradas, entonces f ⇤ es convexa y

cerrada. Ahora, de la definición de f ⇤ tenemos que para todo x, y 2 Rn se tiene que

f ⇤ (y) hx, yi f (x) () f (x) hx, yi f ⇤ (y),

y tomando el supremos sobre y se tiene que f (x) f ⇤⇤ (x). Ahora, si f es convexa y ce-
rrada podemos mostrar la desigualdad contraria. En efecto, supongamos que existe x tal

48
que f ⇤⇤ (x) < f (x), como epi(f ) es convexo, cerrado y no contiene rectas verticales, por el
corolario de antes, existe un hiperplano no vertical que separa estrictamente (x, f ⇤⇤ (x)) de
epi(f ), esto es, existen a, 6= 0 y ↵ tales que
ha, zi + t < ↵ < ha, xi + f ⇤⇤ (x),
para todo (z, t) 2 epi(f ). Puesto que t puede ser arbitrariamente grande se tiene que < 0,
luego podemos tomarlo como 1 con lo que obtenemos que
ha, zi f (z) < ↵ < ha, xi f ⇤⇤ (x),
y tomando el supremo sobre z tenemos que f ⇤ (a) < ha, xi f ⇤⇤ (x) lo que contradice la
definición de f ⇤⇤ (x). Veamos un teorema importante que relaciona las funciones conjugadas
con los subgradientes.
Teorema (Igualdad de Fenchel-Young). Sea f : Rn ! R[{1} cerrada y convexa. Entonces
los siguientes son equivalentes:
(i) hx, yi = f (x) + f ⇤ (y),
(ii) y 2 @f (x),
(iii) x 2 @f ⇤ (y).
Prueba. De la definición de f ⇤ es claro que hx, yi  f (x) + f ⇤ (y), luego el contenido de este
resultado es la desigualdad contraria. Supongamos que hx, yi f (x) + f ⇤ (y), entonces para
todo z se tiene que
hx, yi f (x) + hz, yi f (z) () f (z) f (x) + hy, z xi,
es decir, y 2 @f (x). Supongamos ahora que y 2 @f (x), es decir, para todo z se tiene que
hx, yi f (x) + hz, yi f (z) y tomando supremos sobre z se tiene que hx, yi f (x) + f ⇤ (y).
Mostramos entonces la equivalencia de las dos primeras afirmaciones. Ahora, como f es
cerrada y convexa, la primera afirmación se puede escribir como hy, xi = f ⇤ (y) + f ⇤⇤ (x),
luego aplicando la equivalencia anterior a la función f ⇤ se tiene la equivalencia de (i) y (iii).

7. Optimización convexa no suave

7.1. Método del subgradiente
En este caso vamos a considerar f convexa, pero no suave y resolver el problema
mı́n f (x).
x2Rn

Asumimos que para cada x 2 dom(f ) podemos encontrar g(x) 2 @f (x), recordemos que
este conjunto es no vacı́o y acotado. Siguiendo la misma idea del método del descenso del
gradiente, en el método del subgradiente generamos una sucesión dada por
xk+1 = xk ↵k g(xk ),

49
donde, como antes, ↵k es el tamaño del paso. Una diferencia importante con el método
del descenso del gradiente es que un subgradiente no es necesariamente una dirección de
descenso, pero escogiendo un tamaño de paso adecuado se puede lograr la convergencia del
método, como veremos más adelante. Sea x⇤ óptimo global de f , y notando rk = kxk x⇤ k,
entonces
2
rk+1 = kxk x⇤ ↵k g(xk )k2
= rk2 + ↵k2 kg(xk )k2 2↵k hg(xk ), xk x⇤ i
 rk2 + ↵k2 kg(xk )k2 2↵k (f (xk ) f (x⇤ )).

Si iniciamos con x1 2 BR (x⇤ ) y sumamos la desigualdad obtenemos que

k
X k
R2 1 X 2
⇤
↵i (f (xi ) f (x ))  + ↵ kg(xi )k2 .
i=1
2 2 i=1 i

Vamos a asumir ahora que f es L-Lipschitz, luego para todo x se tiene que

kg(x)k  L,

y por lo tanto
k
X k
⇤ R 2 L2 X 2
↵i (f (xi ) f (x ))  + ↵ .
i=1
2 2 i=1 i
Ahora, como no tenemos un descenso garantizado podemos guardar el registro de los mejores
puntos y para esto definimos
fk⇤ = mı́n f (xi ),
0ik

y con esto llegamos a

P
k
R 2 + L2 ↵i2
i=1
fk⇤ f (x⇤ )  .
P
k
2 ↵i
i=1
P
Tomando entonces una sucesión {↵k }k 1 tal que ↵k ! 0 y además su serie diverja, ↵k =
k
1, tenemos que fk⇤ ! f (x⇤ ). El problema con esta forma de escoger el tamaño de los pasos
es que la convergencia es muy lenta. Otra forma de escoger el tamaño del paso es fijando un
número de iteraciones N y tomando ↵k = LpRN obtenemos la cota

LR
fN⇤ f⇤  p .
N
Puesto que L puede ser difı́cil de estimar, tomar ↵k = kg(x R)kpN da la misma cota. En
k
este caso no podemos garantizar la convergencia pero sı́ garantizar una mejor cota para la
diferencia. Ahora, de la desigualdad
2
rk+1  rk2 + ↵k2 kg(xk )k2 2↵k (f (xk ) f (x⇤ )),

50
podemos ver que la mejor forma de escoger el tamaño de paso, si conoces f (x⇤ ) (o lo podemos
estimar), es
f (xk ) f (x⇤ )
↵k = ,
kg(xk )k2
conocido como el tamaño de paso de Polyak, con lo que obtenemos que

2 (f (xk ) f (x⇤ ))2

rk+1  rk2 ,
kg(xk )k2

y sumando, finalmente llegamos a que

k
X
(f (xi ) f (x⇤ ))2  R2 L2 .
i=1

Esta desigualdad garantiza que para todo k

LR
fk⇤ f (x⇤ )  p ,
k
por lo tanto se tiene convergencia a la mejor tasa posible.
Consideremos ahora el problema con restricciones de la forma

f ⇤ = mı́n f (x),
x2C

con C convexo y cerrado y sea x⇤ 2 C mı́nimo. En este caso tenemos el método del subgra-
diente proyectado en el cual
xk+1 = ⇡C (xk ↵k g(xk )).
El éxito del método radica en la eficiencia computacional de la proyección, y esto depende del
conjunto C. Algunos casos de conjuntos cuya proyección es sencilla son las bolas respecto a la
norma euclidea o respecto a la norma `1 , o de forma más general, el producto de intervalos
cerrados.
Veamos ahora la convergencia del método. Puesto que
2
rk+1 = k⇡C (xk ↵k g(xk )) x⇤ k2 = k⇡C (xk ↵k g(xk )) ⇡C (x⇤ )k2  kxk ↵k g(xk ) x ⇤ k2 ,

pues la función proyección es 1-Lipschitz, entonces podemos hacer el mismo análisis que en el
método del subgradiente. Ahora, si que C es compacto, esto es, existe R tal que kx x⇤ k  R
para todo x 2 C, podemos hacer un análisis distinto. Bajo este supuesto además existe L > 0
tal que f es L-Lipschitz sobre C. Además vamos a asumir que la sucesión {↵k } es no creciente.
Igual que antes tenemos que
2
rk+1  rk2 + ↵k2 kg(xk )k2 2↵k (f (xk ) f (x⇤ )),

luego
1 2 ↵k
f (xk ) f⇤  (r 2
rk+1 )+ kg(xk )k2 ,
2↵k k 2

51
y sumando
k
X Xk k
⇤ 1 2 2 1X
(f (xi ) f (x ))  (r ri+1 ) + ↵i kg(xi )k2 .
i=1 i=1
2↵i i 2 i=1
Podemos organizar el primer sumando del lado derecho de tal forma que

Xk Xk ✓ ◆
1 2 2 1 1 1 2 1 2
(r ri+1 ) = ri2 + r r
i=1
2↵i i i=2
2↵i 2↵i 1 2↵1 1 2↵k k+1
Xk ✓ ◆
1 1 1 2
 R2 + R
i=2
2↵i 2↵i 1 2↵1
R2
=
2↵k
donde la desigualdad se tiene pues ↵i  ↵i 1 . Finalmente tenemos la desigualdad
k
R2 L2 X
fk⇤ ⇤
f  + ↵i .
2k↵k 2k i=1

P
k p
Tomando ↵k = p↵ con ↵ > 0 y usando que 1
p  2 k, tenemos que
k i
i=1

R2 L2 ↵
fk⇤ f⇤  p + p .
2↵ k k
R 3RL
Tomando ↵ = L
se logra la cota p .
2 k

7.2. Método del (sub)gradiente estocástico

El método del subgradiente, aunque con una convergencia lenta, es muy útil en problemas
de gran escala por ser muy sencillos de implementar y esto lo hace muy robusto a posible
ruido en cada una de las iteraciones. Esto se hace evidente en el método del subgradiente
estocástico que veremos a continuación.
Definición. Dada f : Rn 7! R [ {1} convexa un subgradiente estocástico de f en x es una
tupla (⌦, F, P, g) tal que (⌦, F, P) es un espacio de probabilidad, g : Rn ⇥ ⌦ 7! Rn y para
cada x 2 dom(f ) se tiene que
Z
EP [g(x)] = g(x, !)dP(!) 2 @f (x).
⌦

De acuerdo con la definición anterior tenemos que g(x, ·) es un vector aleatoria cuyo
valor esperado bajo la distribución P es un subgradiente de f en x. Usualmente escribiremos
simplemente g(x) para referirnos a este vector aleatorio.

52
 1
P
N
Ejemplo. Sea f (x) = N
fi (x) donde fi es una función convexa y diferenciable para cada
i=1
i. Podemos tomar ⌦ = {1, . . . , N }, P la distribución uniforme sobre ⌦ y g(x, i) = rfi (x).
Ası́,
N
1 X
EP [g(x)] = rfi (x) = rf (x),
N i=1
luego esto define una gradiente estocástico. Esto es, si escogemos un ı́ndice i aleatoriamente
y calculamos rfi (x) entonces tenemos un gradiente estocástico de f en x. Si las funciones
no son diferenciables podemos escoger un subgradiente fijo en @fi (x).
El método del subgradiente estocástico consiste entonces en escoger en cada iteración
g(xk ) y definir
xk+1 = ⇡C (xk ↵k g(xk )).
De esta forma tenemos un proceso estocástico {xk }. Para analizar la convergencia del método
vamos a asumir, igual que antes, que C está contenido en una bola de radio R centrada en
el origen y que para todo x se tiene que EP [kg(x)k2 ]  M 2 . Para facilitar el análisis vamos
a notar f 0 (x) = EP [g(x)] 2 @f (x). Igual que en el método del subgradiente proyectado se
tiene que
2
rk+1 = kxk+1 x⇤ k2  rk2 2↵k hg(xk ), xk x⇤ i + ↵k2 kg(xk )k2 ,
donde esta desigualdad se tiene con probailidad 1. Puesto que g(xk ) no es un verdadero
subgradiente vamos a sumar y restar el término 2↵k hf 0 (xk ), xk x⇤ i. Notemos que f 0 (xk ) es
un vector aleatorio pues xk también lo es. Entonces, si denotamos ⇠k = g(xk ) f 0 (xk ), se
tiene que
2
rk+1  rk2 2↵k hf 0 (xk ), xk x⇤ i + ↵k2 kg(xk )k2 2↵k h⇠k , xk x⇤ i
 rk2 2↵k (f (xk ) f ⇤ ) + ↵k2 kg(xk )k2 2↵k h⇠k , xk x⇤ i.

Reorganizando y sumando igual que antes, se obtiene con probabilidad 1 que

k
X k k
⇤ R2 1X X
(f (xi ) f ) + ↵i kg(xi )k2 h⇠i , xi x⇤ i.
i=1
2↵k 2 i=1 i=1

Ahora, como

EP [h⇠i , xi x⇤ i] = EP [EP [hg(xi ) f 0 (xi ), xi x⇤ i|xi ]]

== EP [hEP [g(xi )|xi ] f 0 (xi ), xi x⇤ i] = 0

entonces
k
R2 M2 X
EP [fk⇤ ⇤
f ] + ↵i ,
2k↵k 2k i=1
R
y tomando ↵k = p
M k
se tiene
3RM
EP [fk⇤ f ⇤]  p .
2 k

53
La desigualdad anterior muestra también, usando la desigualdad de Markov, que fk⇤ ! f ⇤
en probabilidad. Usando la desigualdad de Azuma y asumiendo que todos los gradientes
estocásticos están acotados, entonces se puede mostrar que fk⇤ f ⇤ se puede acotar con alta
probabilidad.

7.3. Método del gradiente proximal

Sea h : Rn ! R una función convexa y semicontinua por debajo, entonces para todo x
la función z 7! h(z) + 12 kz xk2 es coerciva y estrictamente convexa, luego tiene un único
mı́nimo, ası́ que podemos definir el operador proximal como
1
proxh (x) = arg mı́nn h(z) + kx zk2 .
z2R 2
Ahora, si ↵ > 0, entonces prox↵h (x) satisface que 0 2 ↵@h(prox↵h (x)) (x prox↵h (x)),
luego
x prox↵h (x)
2 @h(prox↵h (x)). (32)
↵
Ahora, encontrar este mı́nimo no siempre es fácil, depende de la función h, veamos algunos
ejemplos.
h(x) = 0. En este caso proxh (x) = x.
h(x) = IC (x), la función indicadora de un conjunto C convexo y cerrado. En este caso
proxh (x) = arg mı́n kx zk = ⇧C (x), la proyección de x sobre C.
z2C

x z⇤
h(x) = ↵kxk1 , con ↵ > 0. Sea proxh (x) = z ⇤ , de (32) tenemos que 2 @(kz ⇤ k1 ).
↵
Ası́ que
xi zi⇤
• si zi⇤ < 0, entonces = 1, luego zi⇤ = xi + ↵,
↵
xi zi⇤
• si zi⇤ > 0, entonces = 1, luego zi⇤ = xi ↵,
↵
xi
• si zi⇤ = 0, entonces 2 [ 1, 1], luego |xi |  ↵.
↵
Finalmente, tenemos que 8
>
<xi ↵ si xi > ↵
⇤
zi = 0 si |xi |  ↵
>
:
xi + ↵ si xi < ↵.

Consideremos ahora el problema

g ⇤ = mı́nn g(x) := f (x) + h(x)
x2R

donde f 2 C 1 , las dos funciones son convexas y h es cerrada. Funciones de esta forma son
ahora muy populares, especialmente cuando f es una función de error y h como en el tercer
ejemplo de arriba.

54
 Veamos cómo usamos el operador proximal para construir el método del gradiente proxi-
mal. Recordemos que una forma de interpretar el método del descenso gradiente es minimizar
una aproximación cuadrática de la función de la forma
1
(z) = f (xk ) + hrf (xk ), z xk i + kz x k k2 .
2↵k
Ası́ que si hacemos la misma aproximación en la parte diferenciable de g podemos encontrar
el siguiente paso del método como
xk+1 = arg mı́nn (z) + h(z)
z2R
1
= arg mı́nn f (xk ) + hrf (xk ), z xk i + kz xk k2 + h(z)
z2R 2↵k
1
= arg mı́nn hrf (xk ), z xk i + kz xk k2 + h(z)
z2R 2↵k
1
= arg mı́nn h(z) + kz (xk ↵k rf (xk ))k2
z2R 2↵k
= prox↵k h (xk ↵k rf (xk )).
Notemos que si h = 0 recuperamos el método del descenso del gradiente. Si h = IC , con C
conjunto convexo y cerrado, obtenemos el método del gradiente proyectado
xk+1 = ⇧C (xk ↵k rf (xk ))
para resolver el problema mı́n f (x). Veamos otro ejemplo, el problema de matrix completion.
x2C
Sea A una matriz de m ⇥ n de la cual sólo se conocen algunas de sus entradas dadas por
el conjunto ⌦, se quiere completar la matriz de tal forma que tengo el menor rango posible.
Ası́ que, idealmente, se quiere resolver el problema
mı́n ⇢(X)
sujeto a Xij = Aij 8(i, j) 2 ⌦.
La función rango ⇢ es una función que no es convexa y bastante difı́cil de optimizar, ası́ que
se suele aproximar por la norma nuclear k · k⇤ : Dada una matriz X de m ⇥ n con ⇢(X) = r,
siempre la podemos factorizar de la forma X = U ⌃V T , donde ⌃ es una matriz diagonal de
r ⇥ r con los valores singulares de X, i (X), (es decir, la raı́z cuadrada de los valores propios
positivos de X T X) y U,P V son matrices con columnas ortonormales con las dimensiones
apropiadas, ası́ kXk⇤ = i (X). Tenemos entonces que el problema anterior se reemplaza
i
por
1 X 1
mı́n (Xij Aij )2 + kXk⇤ = k⇧⌦ (X) ⇧⌦ (A)k2F + kXk⇤ ,
X 2 2
(i,j)2⌦

donde ⇧⌦ es la proyección sobre el subespacio definido por ⌦, kXk2F = tr(X T X) y > 0

es un parámetro de regularización. Ahora, se puede mostrar que si X tiene la factorización
descrita arriba, entonces
1 ˆ T,
prox k·k⇤ (X) = arg mı́n kZk⇤ + kZ Xk2F = U ⌃V
Z 2

55
 ˆ ii = máx{⌃ii
donde ⌃ , 0}. Aplicando el método del gradiente proximal a esta función
vemos que las iteraciones toman la forma (con tamaño de paso 1)

Xk+1 = prox k·k⇤ (X ⇧⌦ (X) ⇧⌦ (A)) = prox k·k⇤ (⇧⌦C (X) ⇧⌦ (A)).

x prox↵h (x ↵rf (x))

Si definimos G↵ (x) = , entonces podemos escribir el método
↵
como
xk+1 = xk ↵k G↵k (xk ).
De (32) tenemos entonces que para ↵ > 0

x ↵rf (x)
(x ↵G↵ (x))
G↵ (x) rf (x) =
↵
x ↵rf (x) prox↵h (x ↵rf (x))
=
↵
2 @h(x ↵G↵ (x)), (33)

ası́ que G↵ (x) 2 @h(x ↵G↵ (x)) + rf (x), y si x⇤ satisface que G↵ (x⇤ ) = 0 entonces 0 2
@h(x⇤ ) + rf (x⇤ ), luego x⇤ minimiza g. Ahora G↵ (x⇤ ) = 0 es equivalente a que prox↵h (x⇤
↵rf (x⇤ )) = x⇤ y por lo tanto un criterio de parada del método puede ser kG↵k (xk )k  ↵✏k .
Veamos ahora la convergencia del método. Asumamos ahora que f tiene gradiente L-
Lipschitz, usando (3), y tomando ↵  L1 , tenemos que

↵2 L
f (x ↵G↵ (x))  f (x) ↵hrf (x), G↵ (x)i + kG↵ (x)k2
2
↵
 f (x) ↵hrf (x), G↵ (x)i + kG↵ (x)k2 . (34)
2
Nota. La desigualdad anterior se puede usar para escoger el tamaño del paso usando back-
tracking. Notemos que cada vez que se evalúa un nuevo ↵ hay que calcular un nuevo punto
con el operador proximal.
Ahora, usando (34), la convexidad de f y h y (33), tenemos que para todo x, z 2 Rn se
cumple
↵
g(x ↵G↵ (x))  f (x) kG↵ (x)k2 + h(x ↵G↵ (x))
↵hrf (x), G↵ (x)i +
2
↵
 f (z) hrf (x), z xi ↵hrf (x), G↵ (x)i + kG↵ (x)k2 + h(x ↵G↵ (x))
2
↵
 f (z) hrf (x), z x ↵G↵ (x)i + kG↵ (x)k2 + h(z)
2
hG↵ (x) rf (x), z x + ↵G↵ (x)i
↵
= g(z) hG↵ (x), z xi kG↵ (x)k2 .
2
Si tomamos x = z = xk , entonces
↵k
g(xk+1 )  g(xk ) kG↵k (xk )k,
2

56
luego el método es un método de descenso (compare con (4)), y si tomamos x = xk y z = x⇤ ,
entonces
↵k
g(xk+1 ) g ⇤  hG↵ (xk ), xk x⇤ i kG↵k (xk )k2
2
1
= kxk x ⇤ k2 kxk x⇤ ↵k G↵k (xk )k2
2↵k
1
= kxk x ⇤ k2 kxk+1 x ⇤ k2 .
2↵k
1
Sumando estas desigualdades tomando el tamaño de paso constante L
, y usando que que g
va decreciendo en las iteraciones, obtenemos que
k
1X
⇤
g(xk ) g  (g(xi ) g⇤)
k i=1
k
L X
 kxi 1 x⇤ k2 kxi x⇤ k2
2k i=1
L
 kx0 x ⇤ k2 ,
2k
que es la misma velocidad de convergencia del método del descenso del gradiente. También
se puede definir el método proximal acelerado el cual tiene una tasa igual que la del método
del gradiente acelerado.

8. Programación lineal
Tal vez la clase de problemas de optimización convexa más estudiada y usada en la
práctica es la programación lineal, es decir, minimizar/maximizar una función lineal sobre
un poliedro. Ası́ que entender la geometrı́a de los poliedros es fundamental para analizar los
algoritmos usados para resolver estos problemas

8.1. Conos y poliedros

Definición. Sean {ai , i = 1, . . . , k} vectores en Rn .

Un cono K ⇢ Rn es un cono poliedral si tiene la forma

k
\
K= {x : hai , xi 0}.
i=1

Un cono K ⇢ Rn es finitamente generado si tiene la forma

( k )
X
K= ti ai : ti 0 = cone({ai , i = 1, . . . , k}) [ {0}.
i=1

57
 Es claro que un cono poliedral es cerrado pues es intersección de semiespacios cerrados.
Veamos que pasa lo mismo con los conos finitamente generados.
Lema. Un cono K finitamente generado es cerrado.
Prueba. Por el teorema de Carathéodry para conos sabemos que cada elemento de K se puede
escribir como combinación positiva de vectores linealmente independientes en {a1 , . . . , ak },
como hay una cantidad finita de estos subconjuntos de vectores linealmente independientes,
tenemos que K la unión finita de conos finitamente generados por vectores linealmente
independientes. Ası́ que es suficiente mostrar que cada uno de estos conos es cerrado. Sea
S = {a1 , . . . , ak } vectores linealmente independientes, luego el cono generado por S está
dado por {Ay : y 2 Rk+ }, con A la matriz con columnas dadas por los elementos de S, vamos
a ver que este conjunto es cerrado. Sea {xk } sucesión que converge a x, queremos ver que
existe y 2 Rk+ tal que x = Ay. Sean {yk } ⇢ Rk+ tales que xk = Ayk , entonces

yk = (AT A) 1 AT xk ,

y tomando el lı́mite cuando k ! 1 tenemos que yk ! y = (AT A) 1 AT x 2 Rk+ , y por lo

tanto x = Ay como querı́amos.
Veamos ahora la relación entre conos poliedrales y conos finitamente generados.
T
k
Teorema. Sea K = cone({ai , i = 1, . . . , k}) [ {0} y L = {x : hai , xi 0}, entonces
i=1
K ⇤ = L y L⇤ = K.
⌧
P
k
Prueba. Veamos la primera igualdad. Sea x 2 L, entonces t i ai , x 0 para todo ti 0,
i=1
luego x 2 K ⇤ . Si x 2 K ⇤ , entonces tomando ti = 1 y los demás 0 se tiene que hai , xi 0,
luego x 2 L. Ahora, tomando duales tenemos que K = (K ⇤ )⇤ = L⇤ , pues K es un cono
convexo y cerrado.
Otra forma de escribir el resultado anterior es dada A matriz de n ⇥ k, los conos K =
{Ay : y 0} y L = {x : xT A 0}, donde la desigualdad es componente por componente,
son duales uno del otro. El siguiente resultado, conocido como Lema de Farkas es otra forma
de enunciar el resultado anterior.
Teorema (Lema de Farkas). Sea A una matriz de n ⇥ k y b 2 Rn . Entonces exactamente
una de las siguientes dos alternativas se satisface:

1. Existe y 0 tal que Ay = b, es decir, b 2 K.

2. Existe x tal que xT A / L⇤ .

0 y hx, bi < 0, es decir, b 2

El siguiente es el resultado más importante sobre los conos que estamos estudiando.
Teorema. Todo cono K finitamente generado es poliedral y viceversa
Prueba. Sea K ⇢ Rn un cono finitamente generado, vamos a probar que es poliedral por
inducción en la cantidad de vectores que lo generan. Si k = 1 entonces K = {ta : t 0} y
consideremos dos casos. Si a = 0 entonces K = {0} el cual es un cono poliedral dado por
los vectores {±ei }ni=1 donde los vectores ei son los canónicos en Rn . Si a 6= 0 entonces K es

58
media recta y en este caso podemos escoger una base de Rn {ui }ni=1 tal que u1 = a y {ui }ni=2
son ortogonales a a, de tal forma que

K = {x : hx, u1 i 0, hx, ±ui i 0, i = 2, . . . .n}.

Supongamos ahora que el resultado es cierto para k 1. Sean K el cono generado por
{a, a1 , . . . , ak 1 } y K1 el cono generado por {a1 , . . . , ak 1 }, ası́ que dado x 2 K existen
y 2 K1 y t 0 tal que x = y + ta. Esto implica que

K = {x : 9t 0, x ta 2 K1 }.

Sabemos también que

K1 = {x : hx, bj i 0, j = 1, . . . , m}.
Ası́ que

K = {x : 9t 0, hx ta, bj i 0, j = 1, . . . , m}
= {x : 9t 0, hx, bj i tha, bj i, j = 1, . . . , m}
⇢
hx, bi i hx, bj i
= x : 9t 0, t , hx, bl i 0, i 2 I + , j 2 I , l 2 I 0 ,
ha, bi i ha, bj i

donde I + = {i : ha, bi i > 0}, I = {j : ha, bi i < 0} y I 0 = {l : ha, bl i = 0}. Ahora, existe
hx, bi i hx, bj i
t 0 que satisfaga lo de arriba si para todo i 2 I + , j 2 I y además si
ha, bi i ha, bj i
hx, bi i
mı́n 0, es decir, si hx, bi i 0 para todo i 2 I + . Finalmente tenemos que
i2I + ha, bi i

⇢
hx, bi i hx, bj i
K= x: , hx, bl i 0, i 2 I + , j 2 I , l 2 I + [ I 0 ,
ha, bi i ha, bj i

luego K es un cono poliedral. Para el converso, si K es un cono poliedral. entonces K ⇤ es

finitamente generado y por lo anterior se tiene que K ⇤ es también poliedral, luego (K ⇤ )⇤ = K
es finitamente generado.
Con este resultado podemos ahora probar el teorema fundamental de polidros convexos
conocido como el teorema de Minkowsi-Weyl.
Teorema. Un conjunto P ⇢ Rn es un poliedro si y solo si existen vectores {vi }m k
i=1 y {rj }j=1
tales que

P = conv({vi }m k
i=1 ) + (cone({rj }j=1 ) [ {0})
( m k m
)
X X X
= i vi + µj r j : i = 1, i 0, µj 0 .
i=1 j=1 i=1

Prueba. Sea P un poliedro, es decir, se puede escribir como

P = {x : hx, ai i bi , i = 1, . . . , l}.

59
Definimos el cono poliedral

K = {(x, t) 2 Rn ⇥ R : hx, ai i tbi 0, t 0, i = 1, . . . , l},

luego K es un cono finitamente generado por vectores de la forma {(vi , 1)}m k

i=1 y {(rj , 0)}j=1 .
Puesto que P = {x : (x, 1) 2 K}, entonces P se puede escribir como en el enunciado del
teorema. Ahora, si P tiene la forma como en el enunciado entonces definimos K como el
cono finitamente generado por los vectores {(vi , 1)}m k
i=1 y {(rj , 0)}j=1 . Puesto que K es un
cono poliedral con la forma como la de arriba, con un argumento similar al anterior se tiene
que P es un poliedro.

8.2. Dualidad
Veamos ahora cómo usamos estos resultados en problemas de optimización lineal. Con-
sideremos el problema

mı́n hc, xi
sujeto a Ax b, (P-LP)

es decir, minimizar una función lineal sobre el poliedro P = {x : hx, ai i bi , i = 1, . . . , l}.

Sabemos entonces que P lo podemos escribir como P = conv({vi }m k
i=1 )+(cone({rj }j=1 )[{0})
y por lo tanto podemos reescribir el problema de optimización lineal como
( m k m
)
X X X
mı́n i hc, vi i + µj hc, rj i : i = 1, i 0, µj 0 .
i=1 j=1 i=1

Supongamos que el problema es acotado, es decir, que existe M tal que hc, xi M para
todo x 2 P . Entonces para todo vi , rj y t 0 se tiene que hc, vi i + thc, rj i M , lo cual
implica que hc, rj i 0 para todo j. Ahora, si se tiene que hc, rj i 0 para todo j, entonces
el problema de optimización resulta en
( m m
)
X X
mı́n i hc, vi i : i = 1, i 0 = mı́n hc, vi i,
1im
i=1 i=1

luego el problema es acotado y el óptimo se alcanza en el conjunto {vi }m i=1 . Ahora, en la

práctica los problemas de optimización lineal se escribe P a partir de desigualdades y en-
contrar los vectores v’s y r’s no es una tarea fácil.
A cada problema lineal de la forma de (P-LP) se le puede asociar otro problema lineal al
que llamaremos problema dual. Veamos cómo encontrarlo: Lo primero es reescribir (P-LP)
de la siguiente forma:
mı́n máx hc, xi + hy, b Axi.
x y 0

En efecto, si x 2
/ P , entonces existe una coordenada i tal que bi hx, ai i > 0, luego escogiendo
y 0 con yi muy grande tenemos que hy, b Axi puede ser tan grande como queramos,

60
luego máx hc, xi + hy, b Axi es +1 si x 2
/ P y es hc, xi de lo contrario. Definimos ahora la
y 0
siguiente función conocida como Lagrangeano:

L(x, y) = hc, xi + hy, b Axi.

Es claro que para todo x, y 0 se tiene que máx L(x, y) L(x, y), luego mı́n máx L(x, y)
y 0 x y 0
mı́n L(x, y) para todo y 0 y finalmente tenemos la siguiente desigualdad conocida como
x
dualidad débil:
mı́n máx L(x, y) máx mı́n L(x, y).
x y 0 y 0 x

El problema dual lo definimos entonces como máx mı́n L(x, y) y veamos que también es un
y 0 x
problema lineal. Notemos que L(x, y) = hy, bi + hc AT y, xi y al minimizar sobre x debemos
tener que c AT y = 0 de lo contrario se obtiene 1. Ası́ que obtenemos el problema lineal

máx hy, bi
sujeto a AT y = c, (D-LP)
y 0.

El conjunto factible del problema dual Q = {y : AT y = c, y 0} es también un poliedro

y se puede llevar fácilmente a su forma estándar. Tenemos entonces que la dualidad débil
se puede escribir como: Dados x 2 P , factible para (P-LP), y y 2 Q, factible para (D-LP),
entonces hc, xi hy, bi. Vamos ahora a mostrar que existen soluciones factibles que alcanzan
la igualdad y por lo tanto son óptimas.
Teorema (Dualidad fuerte). Sea x⇤ 2 P solución óptima de (P-LP). Entonces existe y ⇤ 2 Q
tal que hc, x⇤ i = hy ⇤ , bi y por lo tanto solución óptima de (D-LP).
Prueba. Sea I = {i : hai , x⇤ i = bi } y supongamos que para z se tiene que hai , zi 0 para
todo i 2 I. Sea ✏ > 0 y consideremos el vector x⇤ + ✏z. Entonces hai , x⇤ + ✏zi hai , x⇤ i = bi
para todo i 2 I, y para i 2 / I, puesto que hai , x⇤ i > bi se puede escoger ✏ suficientemente
pequeño tal que x⇤ + ✏z 2 P . Puesto que x⇤ es óptimo, esto implica que hc, ziP ⇤0. Ahora,
el Lema de Farkas implica que existen escalares yi⇤ 0 para i 2 I tales que yi ai = c, y
i2I
definiendo yi⇤ = 0 para i 2 / I tenemos que existe y ⇤ 0 tal que AT y ⇤ = c, luego y ⇤ 2 Q.
Además * +
X X X
hy ⇤ , bi = yi⇤ bi = yi⇤ hai , x⇤ i = yi⇤ ai , x⇤ = hc, x⇤ i.
i2I i2I i2I

Dada (x, y), pareja de soluciones factible de los problemas lineales, llamamos brecha de
dualidad a
0  hc, xi hy, bi = hAT y, xi hy, bi = hy, Ax bi.
Por el resultado anterior tenemos que la pareja es óptima si y solo si la brecha de dualidad
es 0, y puesto que y 0 y Ax b 0, este se tiene si y solo si yi (hai , xi bi ) = 0 para todo
i, es decir, si y solo si, yi = 0 o hai , xi = bi para todo i. A esta condición la llamamos holgura
complementaria.

61
9. Problemas convexos generales
Vamos a considerar problemas de optimización de la siguiente forma
mı́n f (x)
sujeto a gi (x)  0, i = 1, . . . , r (P)
hj (x) = 0, j = 1, . . . , m
x2C⇢R . n

Decimos que x 2 Rn es factible para (P) si x 2 C y además satisface las restricciones del
problema. Igual que en el caso de optimización lineal, a cada problema (P), llamado primal,
se le asocia una función, llamada Lagrangiano, que se define como:
r
X m
X
L(x, y, z) = f (x) + yi gi (x) + zj hj (x), (L)
i=1 j=1

con dominio C ⇥ Rr+ ⇥ Rm . Notemos que para x 2 C

(
0 si gi (x)  0
sup yi gi (x) =
yi 0 +1 de lo contrario
y (
0 si hj (x) = 0
sup zj hj (x) =
zi 2R +1 de lo contrario.
Por lo tanto, para cada x 2 C, se tiene que
(
f (x) si x es factible para (P)
sup L(x, y, z) =
y 0,z +1 de lo contrario,

luego el problema (P) se puede reescribir como

ı́nf sup L(x, y, z). (P)
x2C y 0,z

Ahora, definimos el problema dual asociado al problema (P) como:

sup ı́nf L(x, y, z). (D)
y 0,z x2C

Notemos ahora que la función

q(y, z) := ı́nf L(x, y, z)
x2C

es el ı́nfimo de funciones lineales en y µ, y por lo tanto es una función cóncava, luego

el problema dual consiste en maximizar una función cóncava con restricciones lineales y lo
podemos escribir como
máx q(y, z)
sujeto a y 0 (D)

62
Decimos que un problema de optimización es convexo si consiste en minimizar una función
convexa sobre un conjunto convexo. Ası́ que el problema (P) es convexo si las funciones f y
gi , i = 1, . . . , r son convexas, las funciones hj , j = 1, . . . , m son afines y C es un conjunto
convexo.
Nota. Todo problema dual es convexo sin importar si el primal lo es.

9.1. Ejemplos
Ya vimos el primer ejemplo con el problema de optimización lineal. Veamos otros ejem-
plos.

9.1.1. Programación cuadrática

Sean 0 Q 2 S n , una matriz simétrica de n ⇥ n definida positiva, A una matriz de
m ⇥ n, c 2 Rn y b 2 Rm . Un programa cuadrático convexo tiene la forma
1
mı́n hQx, xi + hc, xi
2
sujeto a Ax = b (P-QP)
x 0.
Definimos entonces la función Lagrangiana, con dominio Rn ⇥ Rn+ ⇥ Rm , está dada por
1
L(x, y, z) = hQx, xi + hc, xi hy, xi + hz, b Axi
2
1
= hb, µi + hQx, xi hAT z + y c, xi,
2
y por lo tanto
⇢
1
q(y, z) = hb, zi + mı́n hQx, xi hAT z + y c, xi
x 2
=: hb, zi + mı́n h(x)
x

Notemos que h es una función cuadrática y estrictamente convexa con

rh(x) = Qx (AT z + y c),
luego Q 1 (AT z + y c) es el único minimizador de h. Ası́ que
1
q(y, z) = hb, zi + hAT z + y c, Q 1 (AT z + y c)i hAT z + y c, Q 1 (AT z + y c)i
2
1 T
= hb, zi hA z + y c, Q 1 (AT z + y c)i.
2
Finalmente, tenemos que el problema dual está dado por
1 T
máx hb, zi hA z + y c, Q 1 (AT z + y c)i
2
sujeto a y 0. (D-QP)

63
9.1.2. Programación cónica
Programación cónica es una generalización de la programación lineal. Sea V un espacio
vectorial de dimensión finita con producto interno h·, ·iV . Sea K ⇢ V un cono convexo cerrado
con interior no vacı́o que no contiene lı́neas. Consideremos ahora una transformación lineal
A : V ! W , donde W es un espacio vectorial con producto interno h·, ·iW , c 2 V y b 2 W .
Un problema cónico es, entonces, minimizar (o maximizar) un funcional lineal sobre un
conjunto convexo que se obtiene de intersectar un cono con un espacio afı́n, es decir, tiene
la forma

mı́n hc, xiV

sujeto a Ax = b (P-CP)
x 2 K.

Notamos por A⇤ : W ! V la transformación adjunta de A y recordemos el cono dual definido

como
K ⇤ = {y 2 V : hx, yiV 0 para todo x 2 K}.
Sabemos que K ⇤ es también un cono convexo cerrado, además como K no contiene lı́neas
y tiene interior no vacı́o, K ⇤ tampoco (trate de convencerse de eso). Encontremos ahora el
problema dual asociado. Definimos la función Lagrangiana con dominio K ⇥ W como:

L(x, y) = hc, xiV + hb Ax, yiW = hb, yiW + hc A⇤ y, xiV .

Igual que antes, tenemos que (P-CP) se puede escribir como

ı́nf sup L(x, y).

x2K y2W

El problema dual es entonces

⇢
sup ı́nf L(x, y) = sup hb, yiW + ı́nf hc A⇤ y, xiV
y2W x2K y2W x2K

= sup {hb, yiW : c A⇤ y 2 K ⇤ } .

y2W

Para ver la última igualdad, note que si c A⇤ y 2

/ K ⇤ , entonces existe x 2 K tal que
⇤
hc A y, xiV < 0, y tomando múltiplos arbitrariamente grandes de x tenemos que ı́nf hc
x2K
A⇤ y, xiV = 1. De lo contrario el ı́nfimo es 0. Ası́ que podemos escribir el problema dual
como

máx hb, yiW

sujeto a A⇤ y + s = c (D-CP)
s 2 K ⇤.

Algunos ejemplos importante de programación cónica son los siguientes:

Si V = Rn , K = Rn+ , W = Rm , entonces K ⇤ = K y obtenemos un programa lineal.

64
 Programación semidefinida: Sea V = S n , el espacio vectorial de las matrices simétricas
de n⇥n. y K = S+n el conjunto de matrices semidefinidas positivas. Tomemos W = Rm
y la transformación A tal que para X 2 V

(AX)i := hX, Ai i = tr(XAi ), i = 1, . . . , m,

donde Ai 2 S n . Calculemos la transformación adjunta A⇤ : Rm ! S n . Si y 2 Rm ,

entonces * +
Xm Xm
hAX, yi = yi hX, Ai i = X, yi Ai =: hX, A⇤ yi,
i=1 i=1
P
m
luego A⇤ y = yi Ai 2 S n . Finalmente, como K ⇤ = K, tenemos que el par primal-dual
i=1
en programación semidefinida es de la forma

mı́n hC, Xi máx hb, yi

m
X
sujeto a AX = b (P-SDP) sujeto a yi Ai + S = C (D-SDP)
i=1
X⌫0 S⌫0

Ejemplo. Ejemplo del problema del MAX-CUT

9.1.3. Programación seminfinita - Problema de momentos

Este es un ejemplo distinto a los anteriores pues en este caso el conjunto convexo sobre
el que vamos a optimizar está en un espacio vectorial de dimensión infinita. Sea M ⇢ Rn
compacto M(M )+ , el conjunto de medidas no-negativas soportadas en M . Sean fi , i =
0, 1, . . . , m en C(M ), el conjunto de funciones continuas sobre M , y b 2 Rm . Definimos el
problema de momentos como
Z
mı́n f0 (x)d'(x)
Z M

sujeto a fi (x)d'(x)  bi , i = 1, . . . , m (PM)

M
' 2 M(M )+ .
R
Nota. Si imponemos la restricción M d'(x) = 1, podemos optimizar sobre el conjunto de
medidas de probabilidad soportadas en M .
Definimos el Lagrangiano, con dominio M(M )+ ⇥ Rm
+ , está dada por

Z m
X ✓Z ◆
L(', y) = f0 (x)d'(x) + yi fi (x)d'(x) bi
M i=1 M
Z m
!
X
= hb, yi + f0 (x) + yi fi (x) d'(x),
M i=1

65
ası́ que
Z m
!
X
q(y) = hb, yi + ı́nf f0 (x) + yi fi (x) d'(x)
'2M(M )+ M i=1
8
<hb, yi si f (x) + P y f (x) 0 para todo x 2 M
m
0 i i
= i=1
:
1 de lo contrario.
R
Si usamos la notación hf, 'i := M f d', entonces el par primal-dual tiene la forma

mı́n hf0 , 'i máx hb, yi

m
X
sujeto a hfi , 'i  bi , i = 1, . . . , m (PM) sujeto a f0 + yi f i 0 (PS)
i=1
' 2 M(M )+ y 0.

El problema (PS) se llama programa seminfinito pues tiene infinitas restricciones, una por
cada x 2 M , y se optimiza sobre un espacio de dimensión finita.

9.2. Puntos de silla y condiciones KKT

Vamos ahora es ver algunas propiedades de la función Lagrangiana (L) y concluir las
llamadas condiciones Karush-Kuhn-Tucker que deben satisfacer los óptimos de (P). Por
ahora consideremos una función L : A ⇥ B ! R arbitraria, donde A, B son conjuntos
arbitrarios. A esta función le podemos asociar un par de problemas primal-dual:

ı́nf sup L(x, y) (P-L)

x2A y2B

sup ı́nf L(x, y) (D-L)

y2B x2A

En adelante vamos a notar como val(·) al valor óptimo del problema (·).
Teorema (Dualidad débil).
val(D-L)  val(P-L).
Prueba. Es claro que para todo z 2 A y y 2 B se tiene que

ı́nf L(x, y)  L(z, y),

x2A

luego, para todo z 2 A se tiene que

val(D-L) = sup ı́nf L(x, y)  sup L(z, y),

y2B x2A y2B

y tomando ı́nf sobre z 2 A

val(D-L) = sup ı́nf L(x, y)  ı́nf sup L(z, y) = val(P-L).

y2B x2A z2A y2B

66
Corolario. Si el problema (P-L) es no acotado, entonces para todo y 2 B se tiene que
ı́nf L(x, y) = 1. Similarmente, si el problema (D-L) es no acotado, entonces para todo
x2A
x 2 A se tiene que sup L(x, y) = 1.
y2B

Prueba. Notemos que (P-L) es no acotado si y solo si val(P-L) = 1, luego val(D-L) = 1

y se tiene el primer resultado. El segundo es similar.
Definición. Un punto (x⇤ , y ⇤ ) 2 A ⇥ B es un punto de silla de L si para todo (x, y) 2 A ⇥ B
se tiene que
L(x⇤ , y)  L(x⇤ , y ⇤ )  L(x, y ⇤ ).
Teorema (Teorema del punto de silla). Los siguientes son equivalentes:

1. (x⇤ , y ⇤ ) 2 A ⇥ B es un punto de silla de L.

2. x⇤ es un punto óptimo de (P-L), y ⇤ es un punto óptimo de (D-L), y val(P-L) =

val(D-L).

Además, si ambos enunciados son ciertos, entonces val(P-L) = val(D-L) = L(x⇤ , y ⇤ ).

Prueba. Suponga que 1. es cierto. Entonces

sup L(x⇤ , y) = máx L(x⇤ , y) = L(x⇤ , y ⇤ ) = mı́n L(x, y ⇤ ) = ı́nf L(x, y ⇤ ).

y2B y2B x2A x2A

Entonces,

val(P-L)  sup L(x⇤ , y) = L(x⇤ , y ⇤ )

y2B

= ı́nf L(x, y ⇤ )  val(D-L)

x2A
 val(P-L),

donde la última desigualdad se sigue de dualidad débil, y tenemos que se cumple 2. Supon-
gamos ahora que 2. vale, entonces

L(x⇤ , y ⇤ )  sup L(x⇤ , y) = val(P-L) = val(D-L) = ı́nf L(x, y ⇤ )  L(x⇤ , y ⇤ ),

y2B x2A

y esto implica que (x⇤ , y ⇤ ) es un punto de silla, y además que val(P-L) = val(D-L) =
L(x⇤ , y ⇤ ).
Nota. Se sigue del teorema anterior que el conjunto de puntos de silla tiene la forma A0 ⇥B0 ,
donde A0 ⇢ A y B0 ⇢ B.
Consideremos de ahora en adelante L definida en (L) con A = C y B = Rr+ ⇥Rm . Veamos
qué dice el teorema del punto de silla en este caso: El punto (x⇤ , y ⇤ , z ⇤ ) es un punto de silla
si y solo si satisface

1. x⇤ es óptimo para (P),

2. (y ⇤ , z ⇤ ) es óptimo para (D),

67
 3. val(P) = val(D),
y además, si (x⇤ , y ⇤ , z ⇤ ) es un punto de silla, se tiene que
val(P) = val(D) = L(x⇤ , y ⇤ , z ⇤ ),
lo que implica que
r
X m
X r
X
⇤ ⇤ ⇤ ⇤ ⇤
f (x ) = L(x , y , z ) = f (x ) + yi⇤ gi (x⇤ ) + zj⇤ hj (x⇤ ) = f (x ) +⇤
yi⇤ gi (x⇤ ),
i=1 j=1 i=1

pues x⇤ es factible para (P) y por lo tanto hj (x⇤ ) = 0, j = 1, . . . , m. Ası́ que si (x⇤ , y ⇤ , z ⇤ ) es
un punto de silla, o equivalentemente, si (x⇤ , y ⇤ , z ⇤ ) son óptimos para (P) y (D) y además se
tiene dualidad fuerte, es decir, val(P) = val(D), entonces
r
X
yi⇤ gi (x⇤ ) = 0,
i=1

y como yi⇤ 0 y gi (x )  0, se tiene que yi⇤ gi (x⇤ ) = 0 para todo i = 1, . . . , m. A esto lo

⇤

llamamos la condición de complementaridad. Adicionalmente, supongamos que las funciones

f , gi y hj , para i = 1, . . . , r, j = 1, . . . , m, son Gâteaux diferenciables, y que C = Rn . En
este caso, si (x⇤ , y ⇤ , z ⇤ ) es un punto de silla, entonces x⇤ minimiza la función x 7! L(x, y ⇤ , z ⇤ )
sobre Rn y por lo tanto
r
X m
X
⇤ ⇤ ⇤ ⇤
0 = rx L(x , y , z ) = rf (x ) + yi⇤ rgi (x⇤ ) + zj⇤ rhj (x⇤ ).
i=1 j=1

Supongamos ahora que los conjuntos A y B son convexos y que la función L es convexa-
cóncava, es decir, es convexa en x y cóncava en y. Usando la nota anterior, tenemos el
siguiente resultado.
Teorema. El conjunto de puntos de silla A0 ⇥ B0 satisface que A0 y B0 son convexos.
Además, si son no vacı́os y L es estrı́ctamente convexa (cóncava), entonces A0 (B0 ) solo tiene
un elemento.
Prueba. Sea y ⇤ 2 B0 . Sean x1 , x2 2 A0 y ↵ 2 (0, 1). Definimos x↵ = ↵x1 +(1 ↵)x2 , queremos
ver que (x↵ , y ⇤ ) es un punto de silla. Como (x1 , y ⇤ ) y (x2 , y ⇤ ) son puntos de silla, y por lo
tanto L(x1 , y ⇤ ) = L(x2 , y ⇤ ), y usando la convexidad de L tenemos, para todo y 2 B, que
L(x↵ , y)  ↵L(x1 , y) + (1 ↵)L(x2 , y)
 ↵L(x1 , y ⇤ ) + (1 ↵)L(x2 , y ⇤ ) = L(x1 , y ⇤ )
 L(x↵ , y ⇤ ).
Para ver la otra desigualdad, de nuevo usando la convexidad de L y que (x1 , y ⇤ ) y (x2 , y ⇤ )
son puntos de silla, tenemos, para todo x 2 A, que
L(x↵ , y ⇤ )  ↵L(x1 , y ⇤ ) + (1 ↵)L(x2 , y ⇤ )
 ↵L(x, y ⇤ ) + (1 ↵)L(x, y ⇤ )
= L(x, y ⇤ ).

68
Entonces (x↵ , y ⇤ ) es un punto de silla y por lo tanto A0 es convexo. Supongamos ahora que
L es estrictamente convexa y que x1 6= x2 . Entonces
✓ ◆
x1 + x2 ⇤ L(x1 , y ⇤ ) L(x2 , y ⇤ )
L ,y < + = L(x1 , y ⇤ ),
2 2 2

y esto es una contradicción pues (x1 , y ⇤ ) es un punto de silla. La prueba para B0 es análoga.

9.3. Dualidad fuerte

Vamos ahora a presentar el resultado más importante sobre problemas de optimización
convexa. Consideremos de nuevo el problema (P) dado por

mı́n f (x)
sujeto a gi (x)  0, i = 1, . . . , r (P)
hj (x) = 0, j = 1, . . . , m
x2C⇢R , n

donde las funciones f y gi , i = 1, . . . , r son convexas, las funciones hj , j = 1, . . . , m son afines

y C es un conjunto convexo. Además, vamos a asumir que para i = 1, . . . , r, dom(gi ) ◆ C,
y que dom(f ) ◆ C. Finalmente, vamos a suponer que f ⇤ := val(P) es finito. Recordemos
también la función Lagrangiana asociada
r
X m
X
L(x, y, z) = f (x) + yi gi (x) + zj hj (x), (L)
i=1 j=1

con dominio C ⇥ Rr+ ⇥ Rm y el problema dual

máx q(y, z)
sujeto a y 0 (D)
z 2 Rm ,

donde
q(y, z) := ı́nf L(x, y, z).
x2C

Nuestro objetivo es mostrar que, bajo la condición de Slater que veremos más adelante, existe
(y ⇤ , z ⇤ ) óptimo para (D) y además val(P) = val(D), es decir, se satisface dualidad fuerte.
Nota. No se está asumiendo la existencia de un óptimo para (P), solamente que f ⇤ sea
finito.
Igual que en el caso de programación lineal, la dualidad fuerte es consecuencia de un teore-
ma de alternativas, como el Lema de Farkas, pero en este caso con sistemas de desigualdades
dadas por funciones convexas. Necesitamos la siguiente definición.

69
Definición. Sea C ⇢ Rn , el interior relativo de C está dado por

ri(C) = {x 2 C : 9✏ > 0, B✏ (x) \ a↵(C) ⇢ C},

con a↵(C) la envolvente afı́n de C.

Consideremos ahora el siguiente teorema:
Teorema (de Transposición Convexa). Sean gi , i = 1, . . . , r funciones convexas, hj , j =
1, . . . , m afines y C un conjunto convexo tales que para i = 1, . . . , r, dom(gi ) ◆ C. Supon-
gamos además que existe
(⇧) x 2 ri(C) tal que hj (x) = 0, para todo j = 1, . . . , m.
Entonces, exactamente uno de los siguientes sistemas se satisface:
1. 9 x 2 C: gi (x) < 0, hj (x) = 0, 8 i = 1, . . . , r, j = 1, . . . , m,
P
r P
m
2. 9 y 0, z: yi gi (x) + zj hj (x) 0, 8 x 2 C.
i=1 j=1

La demostración de este teorema requiere varios resultados preliminares y la vamos a

hacer luego, por ahora veamos cómo se usa para mostrar el resultado principal. Para esto
vamos a enunciar la condición de Slater:
9 x 2 ri(C) tal que gi (x) < 0, hj (x) = 0, 8 i = 1, . . . , r, j = 1, . . . , m.
Consideremos el sistema

f (x) f ⇤ < 0,
gi (x) < 0, i = 1, . . . , r
hj (x) = 0, j = 1, . . . , m
x 2 C.

Como f ⇤ es el ı́nfimo, por el teorema anterior, el sistema anterior es inconsistente, luego

existen (y0⇤ , y ⇤ ) 0 y z ⇤ tales que para todo x 2 C
r
X m
X
y0⇤ (f (x) f ⇤) + yi⇤ gi (x) + zj⇤ hj (x) 0.
i=1 j=1

Supongamos que y0⇤ = 0, entonces y ⇤ 0 y para todo x 2 C

r
X m
X
⇤
i gi (x) + µ⇤j hj (x) 0,
i=1 j=1

y el teorema anterior implica que el sistema

gi (x) < 0, i = 1, . . . , r
hj (x) = 0, j = 1, . . . , m
x 2 C,

70
es inconsistente, pero esto contradice la condición de Slater. Ası́ que y0⇤ > 0 y podemos
tomarlo como 1. Por lo tanto, para todo x 2 C se tiene que
r
X m
X
⇤
f  f (x) + yi⇤ gi (x) + zj⇤ hj (x) = L(x, y ⇤ , z ⇤ ),
i=1 j=1

luego
f ⇤  ı́nf L(x, y ⇤ , z ⇤ ) = q(y ⇤ , z ⇤ )  val(D)  val(P) = f ⇤ ,
x2C

y esto es lo que se querı́a mostrar. Si además existe x⇤ óptimo para (P), entonces (x⇤ , y ⇤ , z ⇤ )
es un punto de silla para L.
Un corolario importante de lo anterior es que el problema dual siempre alcanza un óptimo
a diferencia del problema primal.

9.3.1. Prueba del teorema

Vamos ahora a la prueba del teorema. Primero necesitamos un lema sencillo.
Lema. Sea l una función afı́n no-negativa sobre un conjunto convexo C ⇢ Rn . Si existe
x 2 ri(C) tal que l(x) = 0, entonces l se anula en todo el C.
Prueba. Sea x0 2 C tal que l(x0 ) > 0. Como x 2 ri(C), existe x1 2 C tal que x 2 (x0 , x1 ), el
segmento abierto que une x0 con x1 , es decir, existe ↵ 2 (0, 1) tal que x = (1 ↵)x0 + ↵x1 .
Luego
0 = l(x) = (1 ↵)l(x0 ) + ↵l(x1 ) (1 ↵)l(x0 ) > 0,
y tenemos una contradicción.
x, yb, zb) factibles para
Supongamos primero que los sistemas 1. y 2. son consistentes, sean (b
ambos sistemas. Entonces se tiene la contradicción
r
X m
X r
X
0 ybi gi (b
x) + zbj hj (b
x) = ybi gi (b
x) < 0,
i=1 j=1 i=1

pues yb 0. Supongamos ahora que 1. es inconsistente, vamos a ver que 2. es consistente.

Definimos los conjuntos

D = {( , µ) 2 Rr ⇥ Rm : 9x 2 C, gi (x) < i , hj (x) = µj , 8i, j}

y N = Rr ⇥ {0} ⇢ Rr ⇥ Rm . Como C ✓ dom(gi ) para todo i = 1, . . . , r, D es un conjunto

convexo no vacı́o, al igual que N . Como 1. es inconsistente, D y N son disjuntos. Sabemos,
entonces, que existe un hiperplano que separa estos dos conjuntos, pero vamos a necesitar
que este hiplerplano cumpla una propiedad importante:
(?) D no puede estar contenido en el hiperplano.
Supongamos entonces que el hiperplano Hy,z,↵ separa D de N y que satisface (?), luego para
todo ( , µ) 2 D y todo (u, 0) 2 N , es decir u  0, se tiene que

h , yi + hµ, zi ↵ hu, yi,

71
o equivalentemente, para todo x 2 C, 0 < s 2 Rr y u  0, se tiene que
r
X m
X
yi (gi (x) + si ) + zj hj (x) ↵ hu, yi,
i=1 j=1

b 2 C y sb > 0 tales que la primera desigualdad es

y además, por la propiedad (?), existe x
estricta. Ahora, tomando u = 0 tenemos que ↵ 0. Ahora, si yi < 0 para algún i, tomando
u = tei y haciendo t ! 1, se tendrı́a una contradicción con la segunda desigualdad, luego
y 0. Finalmente, tomando si ! 0, tenemos que para todo x 2 C se cumple que
r
X m
X
l(x) := yi gi (x) + zj hj (x) 0.
i=1 j=1

Falta mostrar que y 6= 0. Supongamos que lo es, entonces l se convierte en una función afı́n
nonegativa sobre C, y como x satisface (⇧), l(x) = 0. Además, l(bx) > 0 esto contradice el
lema anterior, luego 0.
Para terminar la prueba nos resta ver la existencia de un hiperplano que satisface (?). Si
a↵(D) = Rr ⇥ Rm , entonces todo hiperplano que separa D de N satisface la condición.
Nota. ¿Qué condiciones sobre el problema de optimización garantizan que a↵(D) = Rr ⇥Rm ?
Si este no es el caso, mostrar la existencia de tal hiperplano no es evidente. Considere el
siguiente ejemplo en R2 : A = (0, 1) ⇥ {0} y B = {0} ⇥ ( 1, 1). Claramente son disjuntos,
pero no existe ningún hiperplano que los separe que no contenga a B.
Nota. El conjunto N es un poliedro.
El teorema de separación de Rockafellar garantiza su existencia.
Teorema. Sean C y P dos conjuntos convexos donde P es un poliedro. Entonces existe un
hiperplano que los separe y que no contenga C si y solo si ri(C) \ P = ?.

10. Minimización con restricciones

Consideremos ahora un problema de optimización de la forma

mı́n f (x)
sujeto a g(x)  0. (35)

donde f : Rn ! R y g : Rn ! Rm son funciones continuas y convexas. En lı́neas generales

los métodos que se usan para resolver este tipo de problemas se clasifican en dos grupos:
Métodos primales y métodos primales-duales. En el primer grupo solo se usa la información
del problema primal, es decir de (35), y se genera un esquema a partir de una sucesión de
problemas de optimización sin restricciones. En el segundo grupo se usan las condiciones
de KKT, usando la información del problema dual, y se genera un esquema a partir de una
sucesión de sistemas (no lineales) de ecuaciones. En ambos casos se usa el método de Newton
tanto para minimizar, como para resolver sistemas de ecuaciones, y por lo tanto asumimos
que f, g 2 C 2 (Rn ).

72
Nota. Usar el método de Newton permite dar cotas teóricas sobre la complejidad de los
métodos y por lo tanto mostrar que son algoritmos con tiempo polinomial.

10.1. Minimización con restricciones de igualdad

Consideremos un problema de optimización de la forma
mı́n f (x)
sujeto a Ax = b. (36)
Vamos a asumir que la matriz A 2 M m⇥n tiene rango m < n. Recordemos que en el
método de Newton para problemas sin restricciones reemplazamos f por una aproximación
cuadrática, ası́ si x 2 Rn (no necesariamente factible) y queremos encontrar un nuevo punto
de la forma x+ = x + x, podemos reemplazar el problema (36) por el problema
1
mı́n f (x) + hrf (x), xi + hHf (x) x, xi
2
sujeto a A(x + x) = b () A x = b Ax. (37)
Ahora, las condiciones de optimalidad de este problema son
rf (x) + Hf (x) x + AT z + = 0, A x=b Ax,
para algún z + 2 Rm , y estas condiciones se pueden reescribir como
  
Hf (x) AT x rf (x)
+ = . (38)
A 0 z Ax b
Notemos que si Hf (x) es definida positiva, por el supuesto sobre A, este sistema lineal es
siempre consistente. Además, incluso si x no es factible, x+ sı́ lo es. Este método pertenece
a la familia de métodos primales y se puede enmarcar en el paradigma aproximar y luego
optimizar.
Ahora, si optimizamos y luego aproximamos, tenemos que escribir las condiciones KKT
del problema original (36), estas son
rf (x) + AT z = 0, Ax b = 0,
el cual es ahora un sistema de ecuaciones no lineal  y podemos usar el método de Newton
rf (x) + AT z
para resolver este sistema. Si definimos G(x, z) = , entonces el método hace
Ax b
la actualización de la forma (x+ , z + ) = (x, z) + ( x, z) = (x, z) rG(x, z) 1 G(x, z), es
decir, en cada actualización debemos resolver el sistema
   
x Hf (x) AT x rf (x) + AT z
rG(x, z) = = ,
z A 0 z Ax b
que es similar a (38) (cambia el lado derecho). De nuevo, notemos que x+ es factible siempre.
Igual que en el método de Newton, hacer la actualización con el método puro podrı́a sacarnos
de la región de convergencia, ası́ que podemos actualizar de la forma
(xk+1 , zk+1 ) = (xk + ↵k xk , z + ↵k zk ).
De este modo, tenemos dos casos para escoger el tamaño del paso y dar un criterio de parada:

73
 Supongamos Axk = b, luego A xk = 0 y por lo tanto Axk+1 = b sin importar la
escogencia de ↵k . Además,

hrf (xk ), xk i = hHf (xk ) xk , xk i,

luego xk es una dirección de descenso y se puede hacer backtracking usando la con-

dición de Armijo para escoger ↵k . Finalmente, se puede usar hHf (xk ) xk , xk i < ✏
como criterio de parada.

Supongamos que xk no es factible. En este caso xk+1 no tiene que ser factible tampoco
(si ↵k 6= 1) y además xk no es necesariamente una dirección de descenso. Lo que
sı́ se puede mostrar (inténtelo!) es que para ↵k suficientemente pequeño se tiene que
kG(xk+1 , zk+1 )k < kG(xk , zk )k, luego se puede hacer backtracking buscando satisfacer
la condición
kG(xk+1 , zk+1 )k  (1 c↵k )kG(xk , zk )k.
Finalmente, se puede usar la condición kG(xk , zk )k < ✏ como criterio de parada.

Igual que en el caso sin restricciones, se puede empezar con el método amortiguado (↵k 6= 1)
y terminar con el método puro.

10.2. Método de barrera

Definición. Sea Q ⇢ Rn un conjunto cerrado con interior no vacı́o. Una función : Rn !
R+ continua es una función de barrera para el conjunto Q si (xk ) ! 1 siempre que
dist(xk , @Q) ! 0 y xk 2 Q.
P
Es fácil ver que si i es función de barrera de Qi , i = 1, . . . , n, entonces i es función
T i
de barrera de Qi siempre que este conjunto tenga interior no vacı́o. Ahora, si el problema
i
(35) satisface la condición de Slater, las siguientes son funciones de barrera para el conjunto
factible Q = {x : gi (x)  0, i = 1, . . . , m}:
P
m
1
Barrera potencia: (x) = ( gi (x))p
, con p 1.
i=1

P
m
Barrera exponencial: (x) = exp ( gi (x)).
i=1

P
m
Barrera logarı́tmica: (x) = log( gi (x)).
i=1

Supongamos ahora que f ⇤ = mı́n f (x), y sean x0 2 int(Q) y {tk }k una sucesión de reales
x2Q
positiva y creciente tal que tk ! 1. El esquema general de los métodos de barrera es
1
xk+1 2 arg mı́n f (x) + (x) = arg mı́n tk f (x) + (x),
x2Q tk x2Q

74
usando xk como punto inicial (siempre que exista) para minimizar la función k (x) :=
f (x) + t1k (x). Si x 2 Q y definimos ⇤k = k (xk+1 ), es decir el valor mı́nimo de k , entonces

⇤ 1
lı́m sup k  lı́m f (x) + (x) = f (x),
k!1 k!1 tk
⇤
luego lı́m sup k  f ⇤ . Por otro lado, si ⇤
es el valor mı́nimo de la función barrera, tenemos
k!1
que
⇤ 1 1
k mı́n f (x) + (x) f⇤ + ⇤
,
x2Q tk tk
⇤
luego lı́m inf k f ⇤.
k!1
El resultado anterior muestra la convergencia hacia el valor óptimo, pero también es
importante entender el comportamiento de los puntos óptimos. Sea Q convexo y cerrado con
interior no vacı́o, una función de barrera para Q y f convexa tal que para todo t 0 la
función tf (x) + (x) tenga en un único mı́nimo sobre Q, ası́, sea

x⇤ (t) = arg mı́n tf (x) + (x).

x2Q

Al camino t 7! x⇤ (t) se le llama el camino central y a x⇤ (0) el centro analı́tico. Tenemos

entonces que el esquema más básico de seguimiento del camino central está dado por
Iniciar con x0 el centro analı́tico y t0 = 0,
tk+1 = tk + k,

xk+1 = x⇤ (tk+1 ) donde se usa xk para inicial el método de minimización.

Para poder implementar este método debemos definir varias cosas. La primera y más
importante es ¿qué tipo de función barrera es mejor? Puesto que la idea es usar el método
de Newton para resolver el problema de minimización, debemos buscar funciones con un
buen comportamiento (al menos teórico) para este método, y la respuesta son funciones self-
concordant. Para esto no solo es importante el tipo de función de de barrera sino también
las funciones gi .
1
Nota. Ni la función ex , ni xp
, p > 0 son funciones self-concordant.
Otra caracterı́stica importante que debe cumplir es que la complejidad del problema de
minimización no debe incrementarse mucho cuando t es muy grande. Esta idea se desarrolla
en el libro de Nesterov en las secciones 4.2.2 y 4.2.3 y se muestra que la barrera logarı́tmica
con funciones gi lineales o cuadráticas convexas satisface esta propiedad.
Otro punto importante del método es que seguir exactamente el camino central es muy
costoso pues encontrar x⇤ (t) exactamente requiere muchas iteraciones. Notemos que la con-
dición de primer orden para xk+1 es

tk+1 rf (x) + r (x) = 0,

luego una condición aproximada que puede usarse para definir xk+1 está dada por

ktk+1 rf (x) + r (x)k⇤x := hH (x)(tk+1 rf (x) + r (x)), tk+1 rf (x) + r (x)i1/2  ,

75
para un parámetro suficientemente pequeño. En ocasiones, esta condición se alcanza en
un solo paso del método de Newton y en este caso se puede definir el esquema como
1
xk+1 = xk (tk+1 Hf (xk ) + H (xk )) (tk+1 rf (xk ) + r (xk )),
o usando el paso amortiguado de Newton.
Lo siguiente que se debe definir es el incremento en tk , k . Una posibilidad es un in-
cremento de la forma k = µtk , con µ > 0 (e iniciando con t0 > 0). Otra forma es tomar
k = krf (xk )k⇤ , con 2 (0, 1).
xk
Finalmente, para dar un criterio de parada, asumiendo la barrera logarı́tmica y Q el
conjunto factible de (35), tenemos para t > 0, que x⇤ (t) satisface gi (x⇤ (t)) < 0 y además
m
X
⇤ rgi (x⇤ (t))
trf (x (t)) = 0,
i=1
gi (x⇤ (t))

luego, si x⇤ es óptimo del problema, tenemos que

m
X
⇤ ⇤ ⇤ hrgi (x⇤ (t)), x⇤ (t) x⇤ i
0 = thrf (x (t)), x (t) xi
i=1
gi (x⇤ (t))
m
X
⇤ ⇤ gi (x⇤ ) gi (x⇤ (t))
t(f (x (t)) f )+
i=1
gi (x⇤ (t))
Xm
gi (x⇤ )
= t(f (x⇤ (t)) f ⇤) m+ t(f (x⇤ (t)) f ⇤) m,
g (x⇤ (t))
i=1 i
m m
es decir, f (x⇤ (t)) f⇤  t
. Ası́ que se puede usar como criterio de parada tk
 ✏.

10.2.1. Cono semidefinido positivo

Recordemos que en un problema de optimización de programación semidefinida el conjun-
to factible es un subconjunto de las matrices semidefinidas positivas, ası́ que si queremos usar
el método de la barrera para este problema debemos encontrar una función de barrera para
este conjunto. Se puede mostrar (ver la sección 4.3.3 de Nesterov) que una función que cumple
con todas las propiedades que buscamos está dada por (X) = log det X = log det X 1 .
Sabemos además que r (X) = X 1 y además se tiene que
1 1
hH (X)Y, Y iF = hX YX , Y iF ,
donde hA, BiF := tr(AB), para A, B matrices simétricas.

10.3. Método primal-dual

Consideremos el problema
mı́n f (x)
sujeto a g(x)  0
Ax = b, (39)

76
con f, g y A como en las secciones anteriores. Tenemos entonces que las condiciones de
optimalidad KKT de (39) son
m
X
rf (x) + yi rgi (x) + AT z = 0
i=1
hy, g(x)i = 0 () Y g(x) = 01
Ax = b
g(x)  0
y 0,
donde Y = diag(y) es una matriz diagonal con los valores de y en la diagonal, y 1 es el vector
con todas sus entradas 1. Veremos más adelante la utilidad de escribir la segunda condición
de esta forma (incluido el signo menos).
Una forma de motivar el método primal-dual es a partir del método de la barrera con
barrera logarı́tmica (adicionando las restricciones de igualdad). Recordemos que para t > 0
debemos resolver el problema
m
1X
mı́n f (x) log( gi (x))
t i=1
sujeto a Ax = b, (40)
y las condiciones de optimalidad KKT de (40) son
m
X rgi (x)
rf (x) + AT z = 0
i=1
tgi (x)
Ax = b
g(x)  0,
que son equivalentes a
m
X
rf (x) + yi rgi (x) + AT z = 0
i=1
1 1
yi gi (x) = 8i () Y g(x) = 1
t t
Ax = b
g(x)  0
y 0.
Igual que en el método de la barrera, la idea es hacer t ! 1 y ası́ aproximarnos al sis-
tema de condiciones KKT del problema original. Análogamente, podemos definir el mapa
t 7! (x⇤ (t), y ⇤ (t), z ⇤ (t)), llamado el camino primal-dual, donde (x⇤ (t), y ⇤ (t), z ⇤ (t)) son las
soluciones del sistema anterior. Recordemos la función Lagrangeana asociada al problema
(39):
m
X
L(x, y, z) = f (x) + yi gi (x) + hAx b, zi,
i=1

77
y el problema dual
máx q( , µ), q(y, z) = mı́n L(x, y, z).
0 x

Notemos entonces que

q(y ⇤ (t), z ⇤ (t)) = L(x⇤ (t), y ⇤ (t), z ⇤ (t))

m
= f (x⇤ (t)) ,
t
luego la brecha de dualidad asociado a (x⇤ (t), y ⇤ (t), z ⇤ (t)) es mt .
Ahora, si nos olvidamos por un momento de las desigualdades, podemos intentar resolver
este sistema no lineal usando el método de Newton. Igual que en el caso de los problemas
con restricciones de igualdad, si (x, y, z) es tal que g(x) < 0 y z > 0, podemos encontrar el
nuevo punto (x+ , y + , z + ) = (x, y, z) + ( x, y, z) resolviendo el sistema

2 3 2 3
P
m
T
2 3 P
m
T
6Hf (x) + i=1 Hgy(x) rg(x) A 7 x 6rf (x) + i=1 yi rgi (x) + A z 7
6 7 4 y5 = 6 7.
4 Y rg(x) diag(g(x)) 0 5 4 Y g(x) + 1t 1 5
z
A 0 0 Ax b

El lado derecho de este sistema lo denotamos como rt (x, y, z) = (rtd , rtc , rtp ). La primer
idea serı́a entonces hacer las iteraciones generadas por el método de Newton hasta obte-
ner rt (x, y, z) = 0, aumentar t y volver a solucionar el sistema. Esto, de nuevo, puede ser
muy costoso y en realidad no es necesario estar siempre sobre el camino primal-dual. Veamos
el método básico primal-dual:

Escoger parámetros ✏f > 0, ✏ > 0, 2 (0, 1), ✓ 2 (0, 1) y >1;

Escoger (x, y, z) tales que g(x) < 0 y y > 0 ;
repetir
m
t hy, g(x)i
;
Calcular ( x, y, ⇢ z);
yi
Definir ↵ = mı́n 1, mı́n yi
;
yi <0
↵ 0,99↵;
mientras g(x+ ) < 0 y krt (x+ , y + , z + )k  (1 ✓↵)krt (x, y, z)k, donde
(x+ , y + , z + ) = (x, y, z) + ↵( x, y, z) hacer
↵ ↵
fin
hasta que krtd k + krtp k < ✏f y hy, g(x)i < ✏;
Algoritmo 4: Método primal-dual
Finalmente, podemos preguntarnos ¿por qué no resolver el sistema de ecuaciones que
resulta del problema (39) directamente? Generalmente, esto resulta en que los tamaños de
los pasos que evitan la infactibilidad de x y/o y son muy pequeños y por lo tanto harı́an el
método más lento.

78
10.3.1. Programación lineal
Veamos ahora cómo se ve el algoritmo anterior en el caso de optimización lineal. En este
caso el problema tiene la forma
mı́n hc, xi
sujeto a Ax = b
x 0, (41)
y las condiciones de optimalidad son
AT z + y c = 0
hy, xi = 0 () Y x = 0
Ax = b
x 0
y 0,
con Y = diag(y). Sabemos que para todo x factible para el primal, es decir, tal que Ax = b y
x 0, y todo (y, z) factible para el dual, es decir, tal que c y AT z = 0 y y 0, entonces la
brecha de dualidad está dada por hy, xi. Esto nos permite encontrar ( x, y, z) resolviendo
el sistema 2 32 3 2 T 3
0 I AT x A z+y c
4Y X 0 5 4 y 5 = 4 Y x hy,xi 1 5 ,
n
A 0 0 z Ax b
donde X = diag(x) y > 1.
Hay varias modificaciones que se le pueden hacer al algoritmo básico en el caso de opti-
mización lineal, una de ellas es el algoritmo predictor-corrector de Mehrotra. En este método
primero se calcula un paso predictor resolviendo el sistema
2 3 2 pr 3 2 T 3
0 I AT x A z+y c
4Y X 0 5 4 y pr 5 = 4 Yx 5,
pr
A 0 0 z Ax b
que es el sistema que resulta de tratar de solucionar las condiciones de optimalidad del
problema original. Si se avanzara dando el paso completo, es decir, si (x+ , y + , z + ) = (x, y, z)+
( xpr , y pr , z pr ), se tendrı́a que
X + y + = Xy + X y pr + Y xpr + Y pr xpr = Y pr xpr ,
que no es necesariamente cero, y se puede usar esta información para dar un paso corrector,
como veremos más adelante, incorporando el término de centrado hy,xi n
1. El paso predictor
también se puede usar para estimar el factor , para esto primero se debe calcular el tamaño
de paso más grande que se puede dar sin perder la factibilidad, esto es
⇢
pr xi
↵p : = mı́n 1, mı́n ,
pr
xi <0 xpri
⇢
pr yi
↵d : = mı́n 1, mı́n .
yipr <0 yipr

79
La idea es que si estos tamaños de paso son grandes, quiere decir que no es necesario “centrar“
y por lo tanto puede ser grande, de lo contrario es necesario pegarse más al camino primal-
dual y por lo tanto no puede ser muy grande, ası́ se define (de forma heurı́stica)
✓ ◆3
hy, xi
= ,
hx + ↵ppr xpr , y + ↵dpr y pr i

y con esto se resuelve el sistema

2 32 3 2 3
0 I AT x AT z + y c
4⇤ X 0 5 4 y 5 = 4Y x + Y pr xpr hy,xi 5
1 .
n
A 0 0 z Ax b

Con este nuevo paso, podemos definir tamaños de paso distinto para cada variable, tal como
hicimos en el caso del paso predictor, esto es
⇢
xi
↵p : = mı́n 1, ⌘ mı́n ,
xi <0 xi
⇢
yi
↵d : = mı́n 1, ⌘ mı́n ,
yi <0 yi

donde ⌘ es un parámetro que puede ir acercándose a 1 a medida que avanza el método.

Finalmente, los valores actualizados de las variables se definen como

(x+ , y + , z + ) = (x, y, z) + (↵p x, ↵d y, ↵d z).

Notemos que en cada paso del algoritmo se debe resolver dos veces un sistema de la forma
2 32 3 2 d3
0 I AT x r
4⇤ X 0 5 4 y 5 = 4rc 5 ,
A 0 0 z rp

es decir, solo cambia el lado derecho del sistema. Como en cada iteración tanto x como
tiene entradas estrı́ctamente positivas, entonces las matrices X y Y son invertibles, luego
podemos simplificar el sistema eliminando la variable y = X 1 rc X 1 Y x para obtener
   d
D 2 AT x r X 1 rc
= ,
A 0 z rp

donde D = Y 1/2 X 1/2 . Se puede seguir simplificando, ahora eliminando x = D 2 AT z +

D2 rd Y 1 rc y como A x = rp , entonces

AD2 AT z = rp AXY 1 d
r + AY 1 c
r.

Este último sistema es más pequeño que el original y la matriz AD2 AT es definida positiva
bajo las hipótesis sobre A. Además. se puede factorizar (Cholesky, por ejemplo) y usar esta
factorización para resolver los dos sistemas que se deben resolver en cada iteración.

80
10.3.2. Programación cuadrática
Consideremos el siguiente problema de optimización cuadrática:
1
mı́n hGx, xi + hc, xi
2
sujeto a Ax b, (42)
donde G es definida positiva. Las condiciones de optimalidad son
Gx + AT y + c = 0
Yz =0
Ax + z b = 0
z 0
y 0,

y en este caso la brecha de dualidad está dada por hy,zi

m
. Ası́ que el paso de Newton se
encuentra resolviendo el sistema
2 32 3 2 3
G AT 0 x Gx + AT z + c
4 0 Z Y 5 4 y 5 = 4 Y z hy,zi 1 5 ,
m
A 0 I z Ax + z b
con > 1. Igual que en el caso de programación lineal podemos usar un algoritmo predictor-
corrector. Primero debemos encontrar el paso predictor resolviendo el sistema
2 3 2 pr 3 2 3
G AT 0 x Gx + AT y + c
4 0 Z Y 5 4 y pr 5 = 4 Yz 5,
A 0 I z pr Ax + z b
con (x, y, z) tal que y > 0 y z > 0. Para encontrar el tamaño del paso predictor, que en este
caso se usa el mismo tanto para el paso primal como para el dual, se calcula
⇢
pr xi zi
↵ := mı́n 1, mı́n pr , mı́n ,
xpr
i <0 xi zipr <0 zipr
y con esto se estima el valor de como
✓ ◆3
hy, zi
= .
hy + ↵pr y pr , z + ↵pr z pr i
Con este valor de se resuelve el sistema
2 32 3 2 3
G AT 0 x Gx + AT y + c
4 0 Z Y 5 4 y5 = 4Y z + Y pr z pr hy,zi 15 ,
n
A 0 I z Ax + z b
para calcular el paso corrector. Definimos el tamaño de paso como
⇢
yi zi
↵ := mı́n 1, ⌘ mı́n , ⌘ mı́n ,
yi <0 yi zi <0 zi

81
donde ⌘ es un parámetro que puede ir acercándose a 1 a medida que avanza el método.
Finalmente, los valores actualizados de las variables se definen como
(x+ , y + , z + ) = (x, y, z) + ↵( x, y, z).
Igual que en el caso de programación lineal, podemos reducir el tamaño de los sistemas que
debemos resolver en cada iteración. Primero eliminamos la variable z = Y 1 rc Y 1 Z y
para obtener   
G AT x rd
= ,
A Y 1Z y rp + Y 1 rc
1
y eliminando la variable y= Z Y rp Z 1 c
r Z 1
Y A x, obtenemos
(G AT Z 1
Y A) x = r d + AT Z 1 c
r + AT Z 1
Y rp .
Lo anterior puede ser eficiente si AT Z 1
Y A es dispersa.

10.3.3. Programación semidefinida

Por último, consideremos el siguiente problema de programación semidefinida

mı́n hC, XiF

sujeto a hAi , XiF = bi , i = 1, . . . , m (43)
X ⌫ 0,
y su problema dual
máx hb, zi
Xm
sujeto a zi Ai + Y = C (44)
i=1
Y ⌫ 0.
En este caso las condiciones de optimalidad son (campare con las de programación lineal)
m
X
zi Ai + Y C=0
i=1
XY =0
hAi , XiF = bi , i = 1, . . . , m
X ⌫0
Y ⌫ 0.
Una forma de obtener las condiciones anteriores es a partir del método de barrera para
matrices semidefinidas, ası́ que podemos aproximar el problema (43) por el problema
1
mı́n hC, XiF log det X
t
sujeto a hAi , XiF = bi , i = 1, . . . , m, (45)

82
cuyas condiciones de optimalidad KKT son
m
X 1 1
zi Ai + X C=0
i=1
t
hAi , XiF = bi , i = 1, . . . , m,
X ⌫ 0,

que son a su vez equivalentes a

m
X
zi Ai + Y C=0
i=1
1 1 1
Y = X () XY = I
t t
hAi , XiF = bi , i = 1, . . . , m,
X⌫0
Y ⌫ 0.

Ası́ que el paso de Newton se encuentra resolviendo el sistema

m
X m
X
z i Ai + Y = zi Ai Y +C
i=1 i=1
1
X Y + XY = XY + I
t
hAi , XiF = hAi , XiF + bi , i = 1, . . . , m.

Queremos que X y Y sean simétricas para que todas las iteraciones del método lo sean,
pero, al resolver el sistema, esto no lo podemos garantizar pues XY no lo es necesariamente
(solo podemos garantizar que Y es simétrica con la primera ecuación). Una opción es
1 1
reemplazar la ecuación XY t
I = 0 por Y t
X 1 = 0, que al linealizar obtenemos la
ecuación lineal
1 1
Y + X 1 XX 1 = Y + X 1 ,
t t
1 1
o podemos también usar la ecuación X t Y = 0, que al linealizar obtenemos

1 1 1 1 1
X+ Y YY = X+ Y .
t t
Una forma de usar la información de ambas posibilidades es con la ecuación
1 1
X +W YW = Y X,
t
donde
W = X 1/2 (X 1/2 Y X 1/2 ) 1/2
X 1/2 .
A esto se le conoce como el método de Nesterov-Todd.

83