DEPARTAMENTO UNIVERSIDAD TÉCNICA

DE MATEMÁTICA FEDERICO SANTA MARÍA

MAT279 - Optimización no Lineal (Semestre primavera 2017)

Profesor: Cristopher Hermosilla Ayudante: Piero Visconti

Certamen # 2

21 de diciembre de 2017 - Tiempo: 3 horas

P1. Aproximación de rango 1 de una matriz simétrica

p
Sea A ∈ Sn (R) una matriz simétrica dada de orden n y denotemos por kBk = tr(B 2 ) para cualquier
B ∈ Sn (R). Considere el problema
1
(P1 ) Minimizar f (x) := kA − xx> k2 sobre todos los x ∈ Rn .
2
Este problema consiste en encontrar la matriz de rango 1 más cercana a la matriz A.

a) Pruebe que f es coerciva y justifique que es al menos dos veces Fréchet diferenciable.
b) Muestre que el problema tiene solución, digamos x̄ ∈ Rn , y pruebe usando la CNPO que tal
solución debe satisfacer la ecuación
Ax = |x|2 x.
c) Muestre que A es semi-definida negativa si y sólo si x̄ = 0.
Indicación: Utilice la CNSO para demostrar una de las implicancias y demuestre también que

d> ∇2 f (x)d = −2d> Ad + 2|x|2 |d|2 + 4(d> x)2 , ∀x, d ∈ Rn .

d ) Supongamos que A no es semi-definida negativa y por lo tanto x̄ 6= 0. Demuestre que x̄ es un

vector propio de A, asociado al valor propio maximal de A.
e) Si λ1 ≥ λ2 ≥ . . . ≥ λn son lo valores propios de A, demuestre que
n n
1X 2 1X 2
val (P1 ) = λi si − A ∈ Sn+ (R) y val (P1 ) = λi si no.
2 2
i=1 i=2

Solución. a) Usando las propiedades de la traza vemos que

1 
(1) f (x) = kAk2 − 2x> Ax + |x|4 , ∀x ∈ Rn .
2
De aquı́ vemos que f es al menos dos veces Fréchet diferenciable, pues es suma de funciones
al menos dos veces Fréchet diferenciable (de hecho k-veces Fréchet diferenciable para cualquier
k ∈ N). Dado que A es simétrica, tenemos que todos sus valores propios son reales y además

x> Ax ≤ λmax (A)|x|2 , ∀x ∈ Rn ,

donde λmax (A) es el valor propio maximal de A. Con esto obtenemos que
1
kAk2 − 2λmax (A)|x|2 + |x|4 , ∀x ∈ Rn ,


f (x) ≥
2
lo que implica que f es coerciva, independiente del signo de λmax (A).

1
b) Dado que la función es Fréchet diferenciable, es en particular continua. Además, como sabemos
que es coerciva, por el Teorema de Weierstrass-Hilbert-Tonelli, tenemos que la función f alcanza
un mı́nimo y por lo tanto el problema (P1 ) tiene solución que denotaremos x̄. En particular,
esta solución debe satisfacer la CNPO, es decir, ∇f (x̄) = 0. Usando (1) vemos que

∇f (x) = −2Ax + 2|x|2 x, ∀x ∈ Rn .

Luego, la condición ∇f (x̄) = 0 es equivalente a Ax̄ = |x̄|2 x̄.

c) Dado que Ax̄ = |x̄|2 x̄, tenemos que |x̄|2 es un valor propio de A si x̄ 6= 0. Asumamos que A es
semi-definida negativa (es decir, todos sus valores propios son no positivos) y que x̄ 6= 0. Dado
que |x̄|2 es un valor propio de A tenemos que |x̄|2 ≤ 0. Esto implica que x̄ = 0, lo que nos lleva
a una contradicción. En consecuencia, si A es semi-definida negativa, necesariamente x̄ = 0.
Por otro lado, la CNSO dice que ∇2 f (x̄) debe ser semi-definida positiva. Notemos que

∇2 f (x) = −2A + 2|x|2 I + 4xx> , ∀x ∈ Rn .

En particular tenemos que

(2) d> ∇2 f (x)d = −2d> Ad + 2|x|2 |d|2 + 4(d> x)2 , ∀x, d ∈ Rn .

En consecuencia, si x̄ = 0 entonces no es difı́cil ver que A es semi-definida negativa.

d ) Supongamos que A no es semi-definida negativa, por la parte anterior sabemos que x̄ 6= 0. Por
la parte (b) tenemos que x̄ es un vector propio de A asociado al valor propio |x̄|2 . Para concluir
tenemos que probar que si λ es un valor propio de A entonces λ ≤ |x̄|2 . Dado que A es simétrica,
existe {v1 , . . . , vn } una base ortonormal de vectores propios de A. Sin perdida de generalidad
podemos asumir que v1 = |x̄| 1
x̄. Recordemos que |vi | = 1 y vi > x̄ = 0 para cada i = 2, . . . , n. En
consecuencia, evaluando (2) en x = x̄ y d = vi con i = 2, . . . , n, vemos que (usando la CNSO)

|x̄|2 ≥ vi > Avi = λi |vi |2 = λi , ∀i = 2, . . . , n

donde cada λi es el vector propio asociado a vi . De aquı́ concluimos que |x̄|2 es el valor propio
maximal de la matriz A.
e) Si A es semi-definida negativa tenemos que val (P1 ) = 12 kAk2 pues x̄ = 0. Supongamos que
λ1 ≥ λ2 ≥ . . . ≥ λn son los valores propios de A asociado a la base ortonormal de vectores
propios {v1 , . . . , vn }. Usando la descomposición espectral de A
n
X
A= λi vi vi>
i=1

no es difı́cil ver que val (P1 ) coincide con la expresión del enunciado pues
n 2 n n
X X X
kAk =2
λi vi vi> = λi λj vi> vj tr(vi vj> ) = λ2i .
i=1 i,j=1 i=1

1
Por otro lado, si A no es semi-definida negativa, tenemos que v1 = |x̄| x̄, λ1 = |x̄|2 . Luego, usando
la descomposición espectral de A tenemos que
n
X n
X
A= λi vi vi> =⇒ A − x̄x̄ = >
λi vi vi> .
i=1 i=2

Finalmente, la conclusión se obtiene de notar que

n 2 n n
X X X
λi vi vi> = λ2i tr(vi vi> ) = λ2i .
i=2 i=2 i=2

2
P2. Condición de Mangasarian-Fromovitz
Sea (X, h·, ·i) un espacio de Hilbert de dimensión finita. Para funciones g1 , . . . , gp : X → R y
h1 , . . . , hq : X → R Gâteaux diferenciables considere el conjunto

S = {x ∈ X | gi (x) ≤ 0, i = 1, . . . , p, hj (x) = 0, j = 1, . . . , q} .

Sea x̄ ∈ S dado y supongamos que I(x̄) = {i ∈ {1, . . . , p} | gi (x̄) = 0} es no vacı́o.

a) Demostrar que la condición de calificación de Mangasarian-Fromovitz (MF) se satisface en x̄ si

y sólo si:

X q
X
(?) λi ∇gi (x̄) + µj ∇hj (x̄) = 0 con λi ≥ 0 =⇒ µj = λi = 0, ∀j = 1, .., q, i ∈ I(x̄).
i∈I(x̄) j=1

Indicación: Para probar que (?) implica (MF), considere los conjuntos
   
X q  X X 
A= µj ∇hj (x̄) µ1 , . . . , µq ∈ R y B= λi ∇gi (x̄) λi = 1, λi ≥ 0, i ∈ I(x̄)
   
j=1 i∈I(x̄) i∈I(x̄)

Muestre que (?) implica que A ∩ B = ∅. Luego, usando apropiadamente el Teorema de Hahn-
Banach Geométrico, demuestre la existencia de d ∈ X \ {0} que verifica la segunda condición
de (MF). No olvide verificar las hipótesis del Teorema de Hahn-Banach Geométrico.
b) Sea f : X → R una función Gâteaux diferenciable. Considere el problema de programación
matemática

(P2 ) Minimizar f (x) sobre los x ∈ X tales que x ∈ S,

Supongamos que el conjunto Λ(x̄) de multiplicadores de KKT asociados a x̄ es no vacı́o, donde

 
 q 
Λ(x̄) := (λ, µ) ∈ Rp+ × Rq ∇f (x̄) +
X X
λi ∇gi (x̄) + µj ∇hj (x̄) = 0, λi = 0 si i ∈
/ I(x̄) .
 
i∈I(x̄) j=1

Pruebe x̄ satisface (MF) si y sólo si el conjunto Λ(x̄) es acotado.

Indicación: Utilice la parte (a). Para probar que Λ(x̄) es acotado implica x̄ satisface (MF),
razone por contradicción.

Solución. a) Supongamos que (MF) se verifica y que para ciertos λ1 , . . . , λp ≥ 0 y µ1 , . . . , µq ∈ R

se tiene que

X q
X
(3) λi ∇gi (x̄) + µj ∇hj (x̄) = 0.
i∈I(x̄) j=1

Notemos que si λi = 0 para todo i ∈ I(x̄), entonces, dado que la condición (MF) implica que
{∇h1 (x̄), . . . , ∇hq (x̄)} es linealmente independiente, tenemos que (3) implica que µj = 0 para
cualquier j = 1, . . . , q, y por lo tanto, (?) también se verifica.
Si por el contrario, hubiese λi 6= 0 para algún i ∈ I(x̄), multiplicando (3) por el vector d¯ dado
por (MF), obtenemos una contradicción pues esto implicarı́a que

X q
X X
0= λi h∇gi (x̄), di + µj h∇hj (x̄), di = λi h∇gi (x̄), di < 0.
i∈I(x̄) j=1 i∈I(x̄)

3
 Supongamos ahora que (?) se satisface. Notemos que esto implica que {∇h1 (x̄), . . . , ∇hq (x̄)}
es linealmente independiente (tomando λi = 0 en el lado derecho de (?)). Luego para concluir
basta demostrar la existencia de d ∈ X \ {0} tal que

h∇gi (x̄), di < 0, ∀i ∈ I(x̄) y h∇hj (x̄), di = 0, ∀j = 1, . . . , q.

Consideremos los conjuntos A y B dados por el enunciado. Notemos que ambos conjuntos son
convexos, cerrados y no vacı́os. Más aún, B es compacto pues es acotado. Además, tenemos que
A ∩ B = ∅. En efecto, si esto no fuese ası́, tendrı́amos que existe ξ ∈ X tal que
X q
X
λi ∇gi (x̄) = ξ = − µj ∇hj (x̄)
i∈I(x̄) j=1
P
para ciertos µ1 , . . . , µq ∈ R y λi ≥ 0 para i ∈ I(x̄) tales que i∈I(x̄) λi = 1. En particular,
tendrı́amos que
X q
X
λi ∇gi (x̄) + µj ∇hj (x̄) = 0.
i∈I(x̄) j=1
P
Luego, (?) implica que λi = 0 para todo i ∈ I(x̄), lo que no puede ser pues i∈I(x̄) λi = 1.
Por lo tanto, gracias al Teorema de de Hahn-Banach Geométrico, existe d ∈ X \ {0} y α ∈ R
tales que
X q
X
(4) λi h∇gi (x̄), di < α ≤ µj h∇hj (x̄), di
i∈I(x̄) j=1
P
para todo µ1 , . . . , µq ∈ R y λi ≥ 0 para i ∈ I(x̄) tales que i∈I(x̄) λi = 1. Dado que los µj
son arbitrarios, no es difı́cil ver que h∇hj (x̄), di = 0 y por lo tanto α ≤ 0. Por otro lado,
evaluando (4) en λi = 1 para cada i ∈ I(x̄) (dejando los otros multiplicadores en cero), vemos
que h∇gi (x̄), di < α ≤ 0 para cada i ∈ I(x̄). En consecuencia, (MF) se verifica con d ∈ X dado
por el Teorema de de Hahn-Banach Geométrico.
b) Supongamos primero que (MF) se satisface, y supongamos por contradicción que Λ(x̄) no es
acotado. Sea {(λk , µk )} una sucesión en Λ(x̄) tal que rk := máx{|λk |, |µk |} → +∞ cuando
k → +∞. Dado que r1k λk y r1k µk son acotados, pasando a una subsucesión si fuese necesario,
podemos asumir que r1k λk → λ y r1k µk → µ. Notemos que λ ∈ Rp+ .
Por otro lado, dado que (λk , µk ) ∈ Λ(x̄) tenemos que

X q
X
∇f (x̄) + λki ∇gi (x̄) + µkj ∇hj (x̄) = 0.
i∈I(x̄) j=1

Dividiendo por rk tenemos que

q
1 X λk
i
X µkj
∇f (x̄) + ∇gi (x̄) + ∇hj (x̄) = 0.
rk rk rk
i∈I(x̄) j=1

Haciendo k → +∞ llegamos a
X q
X
(5) λi ∇gi (x̄) + µj ∇hj (x̄) = 0.
i∈I(x̄) j=1

Dado que (MF) es equivalente a (?), tenemos que λ = 0 y µ = 0. Sin embargo, tenemos que
rk = |λk | o bien rk = |µk | para todo k ∈ N. Luego pasando a una subsucesión si fuese necesario,
podemos asumir que |λ| = 1 o bien |µ| = 1. En cualquiera de los dos casos, obtenemos una
contradicción y por lo tanto Λ(x̄) debe ser acotado.

4
 Finalmente, supongamos que Λ(x̄) es acotado y, por contradicción supongamos que x̄ no satisface
(MF). Por parte a) esto es equivalente a que existen (λ, µ) ∈ Rp+ × Rq \ {(0, 0)}, tales que (5) se
verifica. Como Λ(x̄) es no vacı́o, sea (λ̄, µ̄) ∈ Λ(x̄) y consideremos λk := λ̄+kλ y µk := µ̄+kµ. Es
fácil ver que, para todo k ∈ N, (λk , µk ) ∈ Λ(x̄) y, como (λ, µ) 6= (0, 0) la sucesión {(λk , µk )}k∈N
es no acotada, llegando a una contradicción.

P3. Proyección en un hiperplano

Sean m < N dos enteros positivos, A una matriz real de m × N tal que ker A> = {0}, b ∈ Rm y
z ∈ RN . Considere el problema
1
(P3 ) Minimizar f (x) := |x − z|2 sobre los x ∈ RN tales que Ax = b.
2
a) Demuestre que (P3 ) tiene un único mı́nimo global x̄ y que satisface (MF).
b) Pruebe que
x̄ = z − A> (AA> )−1 (Az − b),
justificando por qué AA> es invertible. Si es necesario, verifique que x̄ satisface la CSSO.

Ahora sea c > 0 y considere el problema penalizado

1 c
(Pc3 ) Minimizar fc (x) := |x − z|2 + |Ax − b|2 sobre los x ∈ RN .
2 2
c) Demuestre que (Pc3 ) tiene un único mı́nimo global x̄c que satisface
 −1
> 1
x̄c = z − A I + AA> (Az − b).
c

Justifique por qué 1c I + AA> es invertible y, si es necesario, verifique que x̄c satisface CSSO.
d ) Demuestre que x̄c → x̄ y fc (x̄c ) → f (x̄) cuando c → ∞.
Indicación: Utilice alguna propiedad topológica adecuada de la función X 7→ X −1 definida
sobre el conjunto de matrices Mm×m (R) invertibles. Para el último lı́mite pruebe que x̄c satisface
√ 1
c(Ax̄c − b) = √ (AA> )−1 A(z − x̄c ).
c

Solución. a) La función x 7→ |x − z|2 /2 es fuertemente convexa y, por lo tanto, coerciva. Además

el conjunto S := {x ∈ RN | Ax = b} es convexo, cerrado y no vacı́o, por lo que la función
x 7→ |x − z|2 /2 + δS (x) es fuertemente convexa, s.c.i., propia y coerciva. El teorema de WHT
asegura la existencia de una solución que es única pues la función objetivo es estrictamente
convexa. Como el problema tiene sólo restricciones de igualdad y m < N , para probar que
(MF) se satisface, basta verificar que los gradientes de las funciones hj (x) := a>
j x − bj son l.i.,
N
donde, para todo j ∈ {1, . . . , m}, aj ∈ R es la j-ésima fila de la matriz A y bj es la j-ésima
componente del vector b. Para todo j ∈ {1, . . . , m} y x ∈ RN se tiene ∇hj (x) = aj y, para
α = (α1 , . . . , αm ) ∈ Rm se tiene que
m
X m
X
0= αj ∇hj (x) = αj aj = A> α,
j=1 j=1

implica α = 0 pues ker A> = {0}, lo que prueba la independencia lineal de ∇h1 (x), . . . , ∇hm (x)
para todo x ∈ RN .

5
b) Las condiciones necesarias de optimalidad de primer orden implican que existe λ ∈ Rm tal que

∇x L(x̄, λ) = x̄ − z − A> λ = 0, Ax̄ = b,

de donde b = Ax̄ = Az + AA> λ y luego λ = (AA> )−1 (b − Az). La matriz AA> es invertible ya
que, para todo y ∈ Rm , y > AA> y = |A> y|2 que sólo es nulo si y = 0 pues ker A> = {0}. De ese
modo, deducimos que
x̄ = z + A> λ = z + A> (AA> )−1 (b − Az).
No es necesario verificar condiciones suficientes, dado que el problema es convexo. Sin embargo,
la CSSO se verifica pues ∇2xx L(x̄, λ) es la matriz identidad.
c) En este caso la función x 7→ 12 |x − z|2 + 2c |Ax − b|2 es continua, fuertemente convexa (coerciva),
por lo que tiene único mı́nimo, caracterizado por la regla de Fermat:

(6) x̄c − z + cA> (Ax̄c − b) = 0,

de donde, premultiplicando por A se deduce ( 1c I + AA> )(Ax̄c − b) = 1c (Az − b) y, luego,

 −1
1 1
Ax̄c − b = I + AA> (Az − b).
c c

Por lo tanto, reemplazando en (6) se obtiene

 −1
> > 1
x̄c = z − cA (Ax̄c − b) = z − A I + AA> (Az − b).
c

d ) El primer lı́mite es consecuencia de que la aplicación X 7→ X −1 es continua en Sm

++ (R). Para
el segundo lı́mite, la indicación se deduce de (6) premultiplicando por A e invirtiendo AA> .
Usando la indicación y x̄c → x̄ se deduce
1 c 1 1√ 1
fc (x̄c ) = |x̄c − z|2 + |Ax̄c − b|2 = |x̄c − z|2 + | c(Ax̄c − b)|2 → |x̄ − z|2 = f (x̄)
2 2 2 2 2
cuando c → +∞.