Optimizacion Estatica (1)

Vista previa del material en texto

Economía Matemática
Optimización estática - BORRADOR clases
Prof. Constanza Fosco
Magister en Economía
Instituto de Economía - PUC
20 y 25 de abril 2016
Fosco (PUC) Math 20 y 25 de abril 2016 1 / 69
Elementos previos (recordatorio de clases anteriores y
referencias)
1. Suma de subconjuntos de espacios lineales (vectoriales) (Carter,
p. 75). S1,S2 � X , X espacio vectorial.
S1 + S2 = fx 2 X : x = x1 + x2, x1 2 S1, x2 2 S2g
2. Derivadas parciales, tasas marginales de sustitución, gradientes.
(Carter, p. 429 y siguientes). Realice ejercicio 4.17 (p. 437).
3. Hiperplanos en Rn. (Carter, p. 284). Hiperplano con normal p,
nivel α, donde p 2 Rn,p 6= 0n�1, kpk2 < ∞ y α 2 R (kxk2 es norma
euclidiana, recuerde).
H (p, α) = fx 2 Rn : p � x = αg
Fosco (PUC) Math 20 y 25 de abril 2016 2 / 69
Elementos previos (recordatorio de clases anteriores y
referencias)
4. Separación de conjuntos. (Carter, p. 358-369).
5. Teorema de Weierstrass (existencia de máx. y mín. globales) y
variantes. Lo sintetizamos en la siguiente formulación:
Sea X un subconjunto no vacío y compacto de Rn y sea f : X ! R
una función.
(i) Si f es semicontinua superior, entonces f alcanza un máximo en
X . (Carter, ejercicio 2.89, p. 217)
(ii) Si f es semicontinua inferior, entonces f alcanza un mínimo en
X . (Realice ej. 2.86, p. 216 y aplique resultado anterior).
(iii) Si f es continua, entonces f alcanza un máximo y un mínimo en
X . (Carter, Teorema 2.2, p. 215)
Fosco (PUC) Math 20 y 25 de abril 2016 3 / 69
Elementos previos (recordatorio de clases anteriores y
referencias)
6. Teorema Básico de Separación de un punto y un conjunto
cerrado en Rn (la siguiente formulación no se encuentra
exactamente así en Carter).
Sea S � Rn, no vacío y cerrado con respecto a la métrica euclidiana
y un punto x0 2 Rn, x0 /2 S. Entonces:
(i) 9~x 2 S : 0 < d (x0,~x) � d (x0, x), 8x 2 S
(ii) Si, adicionalmente, S es convexo, ~x es único y existe un
hiperplano con normal p 2 Rn,p 6= 0n�1, kpk2 < ∞ tal que
p � x > p � x0, 8x 2 S.
(La demostración de este teorema se dio en clase).
Fosco (PUC) Math 20 y 25 de abril 2016 4 / 69
Elementos previos (recordatorio de clases anteriores y
referencias)
7. Conos y conos convexos. Utilizamos notación diferente y
de�niciones equivalentes, pero se encuentra en Carter, p. 104 y
siguientes. De�niciones dadas en clase:
(i) Cono: Sean x1, x2, ..., xm 2 Rn (m puede ser in�nito). El cono
con vértice en el origen 0n�1 2 Rn que es generado por los vectores
x1, x2, ..., xm es el conjunto
K (x1, x2, ..., xm) = fx 2 Rn : x = µxj , µ � 0, j = 1, 2, ...,mg
(ii) Cono convexo: Sea K un cono en Rn, el conjunto
CK = fx 2 Rn : x = y+ z, 8y, z 2 Kg
(Razone por qué la de�nición dada en Carter es equivalente a la
anterior). Al mínimo CK generado por un K se le denomina envoltura
convexa (convex hull).
Fosco (PUC) Math 20 y 25 de abril 2016 5 / 69
Lema de Farkas (Alternativa de Farkas)
Lemma
Dados los vectores a1, a2, ..., am ,b 2 Rn, b 6= 0n�1, una y solo una de las
siguientes alternativas es verdadera:
(i) Existen λ1,λ2, ...,λm 2 R, no negativos y no todos nulos, tal que
b = λ1a1 + λ2a2 + ...+ λmam
(ii) Existe x 2 Rn, tal que
a1 � x � 0, a2 � x � 0, ..., am � x � 0 y b � x < 0
Fosco (PUC) Math 20 y 25 de abril 2016 6 / 69
Lema de Farkas (Alternativa de Farkas)
Demostración: (i) es Falso si y solo si (ii) es Verdadero.
(A) =) Supongamos que no existen los escalares λ1,λ2, ...,λm 2 R, no
negativos y no todos nulos, tal que b = ∑mj=1 λjaj . Esto implica que
fbg \ CK (a1, a2, ..., am) = ? (son disjuntos). Asimismo, fbg y
CK (a1, a2, ..., am) son conjuntos no vacíos, cerrados y convexos. Por el
Teorema de separación de conjunto y punto (que probamos en clase),
existe un hiperplano con normal x 2 Rn, tal que x 6= 0n�1, kxk2 < ∞,
x � b < 0 y x � z > 0 para todo z 2 CK (a1, a2, ..., am), incluyendo
a1, a2, ..., am 2 CK (a1, a2, ..., am).
(B) (= Supongamos que existe un x 2 Rn, tal que
a1 � x � 0, a2 � x � 0, ..., am � x � 0 y b � x < 0. Entonces, para que se
satisfaga x�
�
∑mj=1 λjaj
�
= x � b < 0 necesariamente algún λj < 0.
Fosco (PUC) Math 20 y 25 de abril 2016 7 / 69
Lema de Farkas (Alternativa de Farkas)
Carter (Prop. 3.19, p. 389) presenta la alternativa de Farkas de otra forma
equivalente. Muestre que la proposición 3.19 es equivalente al Lema
propuesto en clase.
La prop. 3.18 de Carter (p. 383) es una versión (aplicada) de la
alternativa de Farkas.
Fosco (PUC) Math 20 y 25 de abril 2016 8 / 69
Problema de optimización con restricciones (P)
Problema (P)
max
x1,x2,...,xn
f (x1, x2, ..., xn)
sujeto a
g1 (x1, x2, ..., xn) � 0
g2 (x1, x2, ..., xn) � 0
...
gm (x1, x2, ..., xn) � 0
Fosco (PUC) Math 20 y 25 de abril 2016 9 / 69
Problema de optimización con restricciones (P)
f es la función �objetivo�; gj es una restricción.
forma compacta de P, f : X ! R,X � Rn; g : X ! Rm , n y m
�nitos.
max
x2X
f (x) s.a. g (x) � 0
G = fx 2 X � Rn : g (x) � 0g ó
G = fx 2 X � Rn : g1 (x) � 0, ..., gm (x) � 0g conjunto factible.
Fosco (PUC) Math 20 y 25 de abril 2016 10 / 69
Solución de P
x es factible si x 2 G .
solución óptima de P: x� factible tal que
f (x�) � f (x) para todo x 2 G
Fosco (PUC) Math 20 y 25 de abril 2016 11 / 69
Solución óptima global, solución óptima local
1 x� 2 G es solución óptima global de P si y solo si f (x�) � f (x)
8x 2 G ; global estricta si y solo si f (x�) > f (x) 8x 2 G (si existe,
es única). �SOLUCION PROPIAMENTE DICHA de P
2 x� 2 G es solución óptima local de P si y solo si existe una vecindad
S no vacía de x� tal que f (x�) � f (x) 8x 2 S \G ; local estricta si y
solo si existe una vecindad S no vacía de x� tal que f (x�) > f (x)
8x 2 S \ G (si existe, es única en S). �NO todas son soluciones de
P.
Fosco (PUC) Math 20 y 25 de abril 2016 12 / 69
Restricciones activas/saturadas o inactivas/no saturadas
Suponga que x� es una solución local para P.
La restricción j está activa o está saturada en (binding at) x� si
gj (x�) = 0.
La restricción j está inactiva o no está saturada (slack at) en x� si
gj (x�) < 0.
Conjunto de restricciones activas en x�: B(x�) = fj : gj (x�) = 0g.
Conjunto de restricciones inactivas en x�: S(x�) = fj : gj (x�) < 0g.
Fosco (PUC) Math 20 y 25 de abril 2016 13 / 69
Teorema Karush-Kuhn-Tucker: Condiciones necesarias de
primer orden
Theorem
Considere el problema P donde las funciones f , g1, g2, ..., gm son
continuamente diferenciables con respecto a x y el conjunto factible G es
no vacío. Sea x� una solución óptima local de P y las restricciones activas
son regulares en x�. Entonces, existen escalares únicos λ�1,λ
�
2, ...,λ
�
m � 0,
no todos nulos, tal que
rf (x�) =
m
∑
j=1
λ�j rgj (x�) y λ�j gj (x�) = 0, j = 1, 2, ...,m
λ�j gj (x�) = 0 condición de holgura complementaria (la restricción es
activa, o el multiplicador es cero, o ambos)
∑mj=1 λ
�
j rgj (x�) = ∑j2B (x�) λ�j rgj (x�) +∑j2S (x�) λ�j rgj (x�).
Carter, Teorema 5.3, p. 552.
Fosco (PUC) Math 20 y 25 de abril 2016 14 / 69
Teorema Karush-Kuhn-Tucker: Condiciones necesarias de
primer orden
El teorema podría escribirse directamente indicando que λ�j � 0 para
todo j 2 B (x�) y λ�j = 0 para todo j 2 S (x�).
Si no hay restricciones activas B(x�) = ?, entonces rf (x�) = 0n�1.
�las restricciones activas son regulares en x��= cuali�cación de
restricciones. Después de la demostración, aclararemos qué signi�ca
esto.
Fosco (PUC) Math 20 y 25 de abril 2016 15 / 69
Derivadas de Fréchet y gradiente, notación Carter
Df [x] (notación Carter) es la derivada de Fréchet (una generalización
del gradiente a espacios de Banach).
Df [x0] (x) =
n
∑
i=1
xi ∂f∂xi (x0) = rf (x0) � x
Df [x�] (x� x�) =
n
∑
i=1
∂f
∂xi
(x�) (xi � x�i ) = rf (x�) � (x� x�)
Fosco (PUC) Math 20 y 25 de abril 2016 16 / 69
Kuhn-Tucker o Karush-Kuhn-Tucker? o Fritz John? Un
poco de historia
El principal teorema (condiciones necesarias p/problema P), se
conoce hoy como el Teorema de Kuhn-Tucker. Fue derivado por dos
matemáticos de Princeton, Harold W Kuhn y Albert W Tucker;
presentado en 1950y publicado en 1951 (�Nonlinear Programming�).
K&T se hicieron famosos por este teorema, pero...
En 1991, Kuhn descubrió que su teorema no era nuevo en 1951:
William Karush y Fritz John habían ya probado el teorema en 1939 y
en 1948, respectivamente, pero pasaron inadvertidos.
Robson & Stedall (2009), Oxford Handbook of the History of
Mathematics: ninguno de los dos tuvo como objetivo principal derivar
esas condiciones, sino que las utilizaron como herramientas para
resolver (o tener alguna intuición sobre) problemas más complejos
(cálculo de variaciones en el caso de Karush y resultados sobre
conjuntos convexos, en el de John).
Economía: antes solo KT, ahora, KKT. John sigue inadvertido...
Fosco (PUC) Math 20 y 25 de abril 2016 17 / 69
Explicación: x* es solución óptima local de P
Fosco (PUC) Math 20 y 25 de abril 2016 18 / 69
Explicación: x* no es solución óptima local de P
Fosco (PUC) Math 20 y 25 de abril 2016 19 / 69
Demostración
Sea x� (un punto regular) la solución óptima local de P en la que (sin
pérdida de generalidad) B (x�) = f1, 2, ..., kg y
S (x�) = fk + 1, k + 2, ...,mg. Es decir, para 4x pequeño
f (x�) � f (x� +4x) , 84 x : gj (x� +4x) � gj (x�) = 0, 8j 2 B (x�) .
Dado lo anterior, tenemos que demostrar que se cumple
rf (x�) =
m
∑
j=1
λ�j rgj (x�) y λ�j gj (x�) = 0, j = 1, 2, ...,m
Por contrapositivo. Suponga que rf (x�) = ∑mj=1 λ�j rgj (x�) es falso.
Podemos aplicar el Lema de Farkas (alternativa de Farkas). Decir que
rf (x�) = ∑mj=1 λ�j rgj (x�) es falso, es equivalente a suponer que la
alternativa (i) del Lema es falsa y que por lo tanto la alternativa (ii) es
verdadera.
Fosco (PUC) Math 20 y 25 de abril 2016 20 / 69
Demostración
Entonces, 94 x tal que:
�rg1 (x�) � 4x � 0, ...,�rgk (x�) � 4x � 0 y �rf (x�) � 4x < 0
es decir
rg1 (x�) � 4x � 0, ...,rgk (x�) � 4x � 0 y rf (x�) � 4x > 0
Dado que f , g1, g2, ..., gm son continuamente diferenciables con respecto a
x, para 4x pequeño:
f (x� +4x) = f (x�) +rf (x�) � 4x
gj (x� +4x) = gj (x�) +rgj (x�) � 4x, 8j 2 B (x�)
de donde llegamos a que f (x� +4x) > f (x�),
gj (x� +4x) � gj (x�) = 0, 8j 2 B (x�).
Fosco (PUC) Math 20 y 25 de abril 2016 21 / 69
Demostración
Es decir, x� no es una solución óptima local, puesto que x� +4x satisface
las mismas restricciones y la función alcanza un mayor valor.
Fijemos λ�j = 0 para j = k + 1, ...,m (es decir, 8j 2 S (x�)) y hemos
demostrado por contrapositivo la primera parte (la cond. necesaria).
Finalmente, dado el vector particular elegido, λ�j gj (x�) = 0 j = 1, 2, ...,m.
Si j 2 B (x�), gj (x�) = 0, si j 2 S (x�), gj (x�) < 0, pero λ�j = 0.�
Ahora indagaremos sobre la cuali�cación de restricciones.
Fosco (PUC) Math 20 y 25 de abril 2016 22 / 69
Cuali�cación de restricciones (CR=CQ)
Una cuali�cación es una restricción, por lo que una hipótesis de
cuali�cación de restricciones (CR) es una restricción sobre las propiedades
de las funciones gj de P. No tiene nada que ver con f . Cualquier CR (hay
varias) se plantea con el propósito de asegurar que cualquier solución
óptima local de P no ocurra en un punto factible de G donde la condición
KKT no existe.
Un punto donde la condición KKT no existe es un punto irregular. En
general, un punto factible es regular si y solo si la condición KKT existe en
dicho punto.
Es decir, la condición necesaria KKT puede no ser verdadera en una
solución óptima local que es un punto irregular de G . Ver el siguiente
ejemplo grá�co.
Fosco (PUC) Math 20 y 25 de abril 2016 23 / 69
Cuali�cación de restricciones: Punto irregular (ejemplo 1)
Fosco (PUC) Math 20 y 25 de abril 2016 24 / 69
Cuali�cación de restricciones: Punto irregular (ejemplo 2)
Considere P: maxx2R f (x) = x s.a. g(x) = x2 � 0.
G = f0g y x� = 0 es necesaria y su�cientemente la solución óptima
(global y local).
Sin embargo, los gradientes de f y g evaluados en x� = 0 son,
respectivamente, f 0(0) = 1 y g 0(0) = 0, luego la condición KKT falla. En
este caso, la intuición es porque no hay una vecindad de x� factible (la
vecindad es vacía).
Fosco (PUC) Math 20 y 25 de abril 2016 25 / 69
Cuali�cación de restricciones (dos de ellas)
1. Cuali�cación de restricciones de Slater: El conjunto factible G es
compacto con respecto a la métrica euclideana, es convexo y tiene un
interior no vacío (intG 6= ?).
2. Cuali�cación de restricciones de regularidad: Si el número de
restricciones que son activas en x̂ es k � 1, entonces el rango de la
matriz jacobiana de los gradientes de las restricciones activas
evaluadas en x̂ es k.
Teorema 5.4, Carter p. 577, enumera varias CR alternativas. En
particular, la segunda mencionada aquí corresponde a la llamada
�Regularidad�y la de Slater implica la �Quasiconvex QC�(ver
ejemplo 5.4, p. 579).
Fosco (PUC) Math 20 y 25 de abril 2016 26 / 69
Cuali�cación de restricciones
Ejemplo CRR: suponga R5 y que m = 5, pero solo k = 3 de las
restricciones son activas en x̂, luego, analizamos el rango de la matriz
rg (̂x) =
0B@
∂g1(x)
∂x1
∂g1(x)
∂x2
∂g1(x)
∂x3
∂g1(x)
∂x4
∂g1(x)
∂x5
∂g2(x)
∂x1
∂g2(x)
∂x2
∂g2(x)
∂x3
∂g2(x)
∂x4
∂g2(x)
∂x5
∂g3(x)
∂x1
∂g3(x)
∂x2
∂g3(x)
∂x3
∂g3(x)
∂x4
∂g3(x)
∂x5
1CA
�������
x=x̂
Si el rango(rg (̂x)) = 3, entonces, x̂ es regular; de lo contrario
rango(rg (̂x)) < 3, x̂ es irregular.
(Recuerde que el rango de una matriz es el número de vectores �la (o
columna) que son linealmente independientes. Dado que rg (̂x)3�5,
rango(rg (̂x)) � 3. Los vectores v1, v2, ..., vm 2 Rn son LI si y solo si
m
∑
i=1
aivi = 0n�1 se satisface solo para ai = 0 8i).
Fosco (PUC) Math 20 y 25 de abril 2016 27 / 69
Cuali�cación de restricciones
En la práctica, se detectan puntos irregulares y se analizan como si
fueran candidatos para el óptimo y se usa KKT para los demás
puntos. Por lo que, en de�nitiva, el teorema KKT se aplicará a P que
satisfagan alguna CR.
Es decir, cuando analizamos la CR de rango, en la práctica, vamos
trabajando con todos conjuntos posibles B(x), y buscamos puntos
irregulares. Es decir, aquellos valores de x para los que rango del
jacobiano sea inferior al número k (aún sin saber si son óptimos, pues
no sabemos de antemano cuál es x̂).
Finalmente, note que cualquier CR es una condición su�ciente pero
no necesaria para la condición necesaria de primer orden del teorema
KKT.
Fosco (PUC) Math 20 y 25 de abril 2016 28 / 69
Función de Lagrange o Lagrangiano
El Lagrangiano o función de Lagrange para el problema P es la función
L : X � Rn �Rm+ ! R de�nida
L (x1, ..., xn,λ1, ...,λm) = f (x1, ..., xn)�
m
∑
j=1
λjgj (x1, ..., xn)
L (x,λ) = f (x)�
m
∑
j=1
λjgj (x)
Fosco (PUC) Math 20 y 25 de abril 2016 29 / 69
Condiciones necesarias Karush-Kuhn-Tucker
Corollary
Suponga que x� es una solución óptima local de P y las restricciones
activas son regulares en x�. Entonces, existen multiplicadores únicos
λ�1,λ
�
2, ...,λ
�
m � 0, no todos nulos, tales que el Lagrangiano
L (x,λ) = f (x)�
m
∑
j=1
λjgj (x)
es estacionario en (x�,λ�), es decir (utilizando notación de gradiente)
rf (x�)�
m
∑
j=1
λ�j rgj (x�) = 0n�1 y λ�j gj (x�) = 0, j = 1, 2, ...,m
(Corolario 5.3.1, Carter, p. 554)
Fosco (PUC) Math 20 y 25 de abril 2016 30 / 69
Condiciones necesarias Karush-Kuhn-Tucker - Variables no
negativas
Corollary
Suponga que x� es un óptimo local de
max
x�0
f (x) , s.a. g (x) � 0
y las restricciones activas son regulares en x�. Entonces, existen
multiplicadores únicos λ�1,λ
�
2, ...,λ
�
m tales que
∂L(x�,λ�)
∂xi
� 0 x�i � 0 x�i
∂L(x�,λ�)
∂xi
= 0, i = 1, 2, ..., n
gj (x�) � 0 λ�j � 0 λ�j gj (x�) = 0, j = 1, 2, ...,m
(Corolario 5.3.2, Carter, p. 562)
Fosco (PUC) Math 20 y 25 de abril 2016 31 / 69
Multiplicadores, forma de L, interpretación
Por favor, leer Remark 5.3, Carter p. 534.
Fosco (PUC) Math 20 y 25 de abril 2016 32 / 69
Condiciones de segundo orden
A continuación, estudiaremos las condiciones de segundo orden, es decir,
las condiciones que se basan en el Hessiano y que, por lo tanto, requieren
que f , g1, ..., gm 2 C 2.
Hay condiciones necesarias de segundo orden y condicionessu�cientes de
segundo orden.
Fosco (PUC) Math 20 y 25 de abril 2016 33 / 69
Elemento previos: Formas cuadráticas
Forma cuadrática: tipo especial de polinomio de orden 2. Sea An�n,
A = AT (simétrica)y xn�1. Una forma cuadrática pura es xTAx.
Las formas cuadráticas pueden ser de�nidas, semide�nidas o inde�nidas.
1 xTAx es de�nida positiva () xTAx > 0 8x 2 Rn, x 6= 0.
2 xTAx es semide�nida positiva () xTAx � 0 8x 2 Rn.
3 xTAx es de�nida negativa () xTAx < 0 8x 2 Rn, x 6= 0.
4 xTAx es semide�nida negativa () xTAx � 0 8x 2 Rn.
5 xTAx es inde�nida () xTAx no es ni SDP ni SDN.
(La forma cuadrática de una matriz asimétrica es la forma cuadrática de
otra matriz simétrica. Muestre que si A 6= AT , existe B tal que B = BT y
xTAx = xTBx. Hágalo con A2�2).
Fosco (PUC) Math 20 y 25 de abril 2016 34 / 69
Elementos previos: Hessianos asociados al Lagrangiano
Hessiano o matriz hessiana: matriz de segundas derivadas.
Sea la función lagrangiana
L (x,λ) = f (x)�∑mj=1 λjgj (x) .
Supongamos que f , g1, ..., gm 2 C 2..
El Hessiano de L con respecto a x, HL (x;λ) es la matriz de segundas
derivadas de L con respecto a x. Es decir
HL (x;λ) =
0BBBBB@
∂2L
∂x 21
∂2L
∂x1∂x2
� � � ∂2L∂x1∂xn
∂2L
∂x2∂x1
∂2L
∂x 22
� � � ∂2L∂x2∂xn
...
...
...
∂2L
∂xn∂x1
∂2L
∂xn∂x2
� � � ∂2L
∂x 2n
1CCCCCA .
Fosco (PUC) Math 20 y 25 de abril 2016 35 / 69
Elementos previos: Hessianos asociados al Lagrangiano
El Hessiano Orlado, por su parte, H̃L (x,λ) es la matriz de segundas
derivadas de L con respecto a x y λ, convenientemente acomodadas. Es
decir,
H̃L (x,λ) =
0BBBBBBBBBBBBBBB@
0 0 � � � 0 ∂g1∂x1
∂g1
∂x2
� � � ∂g1∂xn
0 0 � � � 0 ∂g2∂x1
∂g2
∂x2
� � � ∂g2∂xn
...
...
...
...
0 0 � � � 0 ∂gm∂x1
∂gm
∂x2
� � � ∂gm∂xn
∂g1
∂x1
∂g2
∂x1
� � � ∂gm∂x1
∂2L
∂x 21
∂2L
∂x1∂x2
� � � ∂2L∂x1∂xn
∂g1
∂x2
∂g2
∂x2
� � � ∂gm∂x2
∂2L
∂x2∂x1
∂2L
∂x 22
� � � ∂2L∂x2∂xn
...
...
...
...
...
...
∂g1
∂xn
∂g2
∂xn
� � � ∂gm∂xn
∂2L
∂xn∂x1
∂2L
∂xn∂x2
� � � ∂2L
∂x 2n
1CCCCCCCCCCCCCCCA
Fosco (PUC) Math 20 y 25 de abril 2016 36 / 69
Elementos previos: Hessianos asociados al Lagrangiano
En este curso, vamos a trabajar con HL (x;λ). Por lo tanto, resulta útil
notar:
Sean Hf (x) el hessiano de f con respecto a x y Hgj (x) el hessiano de
gj con respecto a x, entonces
HL (x;λ) = Hf (x)�∑mj=1 λjHgj (x)
El hessiano orlado puede particionarse de la siguiente manera
H̃L (x,λ) =
�
0m�m rg (x)m�n
rg (x)Tn�m HL (x;λ)n�n
�
(a partir de esta última relación, ustedes podrán relacionar lo que
veremos en el curso y lo que saben del uso del h. orlado)
Fosco (PUC) Math 20 y 25 de abril 2016 37 / 69
Elementos previos: Restricciones activas degeneradas y
Jacobianos
Considere las condiciones necesarias de primer orden. De acuerdo con
estas condiciones, los multiplicadores asociados a las restricciones gj tal
que j 2 B (x�) son λ�j � 0.
Una restricción activa es degenerada si λ�j = 0. De lo contrario, es una
restricción activa no degenerada.
Llamaremos rg (x)jj2B (x�) al jacobiano del conjunto de restricciones
activas.
Llamaremos rg (x)jj2B (x�),λ�j >0 al jacobiano del conjunto de restricciones
activas no degeneradas.
Note que, en este contexto, HL (x;λ�) = Hf (x)�∑kj=1 λ�j Hgj (x) es el
hessiano de L con respecto a x que incluye solo las primeras k restricciones
(que son las activas o las activas no degeneradas según el caso).
(Estos nombres son para este curso, en caso de usarlos fuera del curso,
será necesario que los de�nan previamente).
Fosco (PUC) Math 20 y 25 de abril 2016 38 / 69
Condiciones necesarias de segundo orden para solución
óptima local de P
Suponga que j = 1, ..., k restricciones son activas (degeneradas o no) y
j = k + 1, ...,m son inactivas en x�.
Theorem
Suponga que x� es la solución óptima local de P y las restricciones activas
son regulares en x�. Entonces existen λ�1,λ
�
2, ...,λ
�
m � 0 tal que
(a) (x�,λ�) es un punto estacionario del Lagrangiano, es decir
rf (x�)�∑mj=1 λ�j rgj (x�) = 0 y λ�j gj (x�) = 0, j = 1, 2, ...,m; y
(b) HL (x�;λ�) es semide�nido negativo en el hiperplano tangente al
conjunto de restricciones activas, es decir xTHL (x�;λ�) x � 0 para todo
x 2 T =
n
x 2 X :
�
rg (x�)jj2B (x�)
�
x = 0
o
.
Fosco (PUC) Math 20 y 25 de abril 2016 39 / 69
Condiciones su�cientes de segundo orden para solución
óptima local de P
Suponga que j = 1, ..., k restricciones son activas no degeneradas y
j = k + 1, ...,m son inactivas o activas degeneradas en x�.
Theorem
Suponga que existe x� 2 X � Rn y λ 2 Rm tal que
(a) (x�,λ�) es un punto estacionario del Lagrangiano, es decir
rf (x�)�∑mj=1 λ�j rgj (x�) = 0 y λ�j gj (x�) = 0, j = 1, 2, ...,m; y
(b) HL (x�;λ�) es de�nido negativo en el hiperplano tangente al conjunto
de restricciones activas no degeneradas, es decir xTHL (x�;λ�) x < 0
para todo x 6= 0n�1 2 T =
n
x 2 X :
�
rg (x�)jj2B (x�),λ�j >0
�
x = 0
o
.
Entonces x� es una solución óptima local estricta de P.
Fosco (PUC) Math 20 y 25 de abril 2016 40 / 69
Aclaraciones
Los teoremas anteriores no se encuentran en Carter.
En la práctica, las condiciones de segundo orden necesarias casi no se
utilizan y los problemas de optimización se resuelven encontrando los
candidatos (puntos críticos) con las condiciones de primer orden necesarias
y determinando si se satisfacen o no las condiciones de segundo orden
su�cientes.
Cabe aclarar, sin embargo, que a menos que se satisfagan algunas
condiciones adicionales (que también veremos), las soluciones encontradas
son siempre locales, por lo que no estaremos seguros de haber encontrado
�la� solución de P.
Las condiciones de segundo orden (necesarias o su�cientes) también se
pueden comprobar utilizando el hessiano orlado. Es el enfoque que ustedes
deben haber visto antes y es equivalente, por lo que no lo usaremos aquí.
Fosco (PUC) Math 20 y 25 de abril 2016 41 / 69
Deducción intuitiva de las condiciones de segundo orden
su�cientes
Partimos con la siguiente idea: si para todos los puntos en algún
vecindario de ~x, contenido en G , exceptuando a ~x, la función alcanza un
valor estrictamente menor que en ~x, entonces ~x es un maximizador local
estricto de f en G . Es decir,
�Si para algún ε > 0,
(i) f (~x+ ∆x) < f (~x), (8∆x 6= 0 tal que ~x+ ∆x 2 Bε (~x)), y
(ii) gj (~x+ ∆x) � 0, j = 1, ...,m
entonces ~x es un maximizador local estricto de f en G .�
Sin pérdida de generalidad, supongamos que j = 1, .., k son restricciones
activas no degeneradas y j = k + 1, ...,m son restricciones inactivas o
activas degeneradas.
Fosco (PUC) Math 20 y 25 de abril 2016 42 / 69
Deducción intuitiva
Como f , g1, ..., gk 2 C 2, podemos realizar aproximaciones (lineales) de
segundo orden de Taylor para ∆x pequeño,
f (~x+ ∆x) = f (~x) +rf (~x) � ∆x+1
2
(∆x)T Hf (~x)∆x+ η (∆x) k∆xk2
gj (~x+ ∆x) = gj (~x)| {z }
=0
+rgj (~x) � ∆x+
1
2
(∆x)T Hgj (~x)∆x+ η (∆x) k∆xk
2 , j = 1, ..., k
donde η (∆x)! 0, y reescribimos (i) y (ii):
(i) rf (~x) � ∆x+ 12 (∆x)
T Hf (~x)∆x < 0, (8∆x 6= 0 tal que
~x+ ∆x 2 Bε (~x))
(ii) rgj (~x) � ∆x+ 12 (∆x)
T Hgj (~x)∆x � 0, j = 1, ..., k
Fosco (PUC) Math 20 y 25 de abril 2016 43 / 69
Deducción intuitiva
Supongamos que ~x es un punto regular en G , entonces, ~x no podrá ser un
maximizador local a menos que satisfaga las condiciones necesarias de
primer orden, de tal manera que cualquier conjunto de condiciones que
juntas sean su�cientes para que ~x sea un maximizador local deberán
incluir que existen λ1,λ2, ...,λm � 0, no todos nulos, tal que
rf (~x) =
m
∑
j=1
λjrgj (~x) y λjgj (~x) = 0, j = 1, ...,m
Fosco (PUC) Math 20 y 25 de abril 2016 44 / 69
Deducción intuitiva
Sabemos que λj = 0 si la restricción es inactiva o si es activa degenerada.
Por lo tanto, podemos cambiar nuestra �proposición�de condiciones
su�cientes de la siguiente manera:
�Si existen λ1,λ2, ...,λm � 0, no todos nulos, tal que
rf (~x) =
m
∑
j=1
λjrgj (~x) y λjgj (~x) = 0, j = 1, ...,m
y si, para algún ε > 0,
(i)
k
∑
j=1
λjrgj (~x) � ∆x+ 12 (∆x)
T Hf (~x)∆x < 0, (8∆x 6= 0 tal que
~x+ ∆x 2 Bε (~x))
(ii) rgj (~x) � ∆x+ 12 (∆x)
T Hgj (~x)∆x � 0, j = 1, ...,k
entonces ~x es un maximizador local estricto de f en G .�
Fosco (PUC) Math 20 y 25 de abril 2016 45 / 69
Deducción intuitiva
Ahora, exigimos que las restricciones que son activas no degeneradas en ~x
sean también activas en los puntos ~x+ ∆x
gj (~x+ ∆x) = 0, j = 1, ..., k
luego, (ii) implica
rgj (~x) � ∆x = �
1
2
(∆x)T Hgj (~x)∆x, j = 1, ..., k
y reemplazando en (i)
k
∑
j=1
λj
�
�1
2
(∆x)T Hgj (~x)∆x
�
+
1
2
(∆x)T Hf (~x)∆x
=
1
2
(∆x)T
h
Hf (~x)�∑kj=1 λjHgj (x)
i
∆x
=
1
2
(∆x)T HL (x;λ1, ...,λk )∆x
(para simpli�car la notación, llamamos λk = (λ1, ...,λk ), luego
HL (x;λ1, ...,λk ) es HL (x;λk )
Fosco (PUC) Math 20 y 25 de abril 2016 46 / 69
Deducción intuitiva
Luego, nuestra proposición de condiciones su�cientes quedaría así:
�Si existen λ1,λ2, ...,λm � 0, no todos nulos, tal que
rf (~x) =
m
∑
j=1
λjrgj (~x) y λjgj (~x) = 0, j = 1, ...,m
y si, para algún ε > 0, (∆x)T HL (x;λk )∆x < 0, (8∆x 6= 0 tal que
~x+ ∆x 2 Bε (~x) y gj (~x+ ∆x) = 0, j = 1, ..., k), entonces ~x es un
maximizador local estricto de f en G .�
Fosco (PUC) Math 20 y 25 de abril 2016 47 / 69
Deducción intuitiva
8∆x 6= 0 tal que ~x+ ∆x 2 Bε (~x) y gj (~x+ ∆x) = 0, j = 1, ..., k: nos
dice que consideramos puntos x = ~x+ ∆x tal que están en un
entorno de ~x y que satisfacen las mismas restricciones activas no
degeneradas que ~x. Estos puntos son los que pertenecen al plano
tangente al conjunto de restricciones activas no degeneradas
x 6= 0n�1 2 T =
n
x 2 X :
�
rg (x�)jj2B (x�),λ�j >0
�
x = 0
o
. Para
entender esto, piense en una restricción activa no degenerada, g . Las
perturbaciones ∆x tienen que ser tales que la restricción se siga
satisfaciendo con igualdad, es decir, que permanezcamos sobre el
contorno de valor 0. Tal como vimos, estas perturbaciones son
ortogonales al gradiente de la restricción.
La �idea�detrás de xTHL (x�;λ�) x < 0 es que cuando nos
acercamos al punto x�, de cualquiera de los puntos x (en el entorno
de x� y moviéndonos sobre las mismas restricciones activas no
degeneradas en x�), la función crece a tasa estrictamente decreciente.
Fosco (PUC) Math 20 y 25 de abril 2016 48 / 69
Deducción intuitiva
Cabe aclarar que la deducción intuitiva es una aproximación. Esta
aproximación resulta idéntica a la condición establecida en el teorema
cuando las relaciones entre los distintos ∆xi , i = 1, .., n que
satisfacen gj (~x+ ∆x) = 0, j = 1, ..., k son todas lineales.
Fosco (PUC) Math 20 y 25 de abril 2016 49 / 69
Concavidad y Optimización - Introducción
�Condiciones de concavidad� (o de concavidad o programación
cóncava o convexa)...involucran condiciones sobre conjuntos de
oportunidades + condiciones sobre la función objetivo.
Cuando un problema de optimización satisface estas condiciones, los
óptimos locales son globales.
Cuando el problema satisface condiciones de convexidad estricta, el
óptimo global es único.
Si, adicionalmente, las funciones involucradas (función objetivo y
restricciones) son diferenciables, entonces las condiciones de primer
orden para óptimos locales son su�cientes para óptimos globales.
Fosco (PUC) Math 20 y 25 de abril 2016 50 / 69
De�niciones
Una función f : X � Rn ! R, X convexo, es cóncava (convexa) en X
() (8x1, x2 2 X ) (8α 2 [0, 1]):
f [αx1 + (1� α)x2] � αf (x1) + (1� α)f (x2)
(f [αx1 + (1� α)x2] � αf (x1) + (1� α)f (x2))
Hay funciones que no son cóncavas ni convexas y hay funciones que
son cóncavas y convexas. Por ejemplo, f (x) = x3 no es cóncava ni
convexa, f (x) = a+ bx es cóncava y convexa.
Fosco (PUC) Math 20 y 25 de abril 2016 51 / 69
De�niciones
Una función f : X � Rn ! R, X convexo, es estrictamente cóncava
(convexa) en X si (8x1, x2 2 X ) (x1 6= x2) (8α 2 (0, 1)):
f [αx1 + (1� α)x2] > αf (x1) + (1� α)f (x2)
(f [αx1 + (1� α)x2] < αf (x1) + (1� α)f (x2))
Una función f es cóncava en X () �f es convexa en X . Es
estrictamente cóncava en X () �f es estrictamente convexa en
X .
Fosco (PUC) Math 20 y 25 de abril 2016 52 / 69
Concavidad y Optimización - De�niciones
Caracterización grá�ca funciones convexas y funciones cóncavas: una
función es cóncava (convexa) si y solo si el subgrafo (epigrafo) es un
conjunto convexo.
Toda función cóncava o convexa de�nida en un conjunto abierto S de
un espacio vectorial normado de dimensión �nita (por ejemplo, Rn)
debe necesariamente ser continua en el interior de su dominio. Podrá
ser discontinua en los bordes.
La concavidad o convexidad de una función que es diferenciable en
todo su dominio, puede ser caracterizada completamente a través de
sus derivadas y la concavidad o convexidad de una función de clase
C 2 puede ser completamente caracterizada en términos de sus
derivadas segundas.
Fosco (PUC) Math 20 y 25 de abril 2016 53 / 69
Caracterización a través de derivadas
Sea X un conjunto abierto y convexo en Rn y sea f : X ! R una función
diferenciable en X . Luego, f es cóncava (convexa) en X ()
rf (x) � (x1 � x2) � f (x1)� f (x2) 8x1, x2 2 X
(rf (x) � (x1 � x2) � f (x1)� f (x2) 8x1, x2 2 X )
Fosco (PUC) Math 20 y 25 de abril 2016 54 / 69
Caracterización a través de derivadas
Sea X un conjunto abierto y convexo en Rn y sea f : X ! R una función
C 2 en X . Luego,
(i) f es cóncava en X () Hf (x) es SDN 8x 2 X .
(ii) f es convexa en X () Hf (x) es SDP 8x 2 X .
(iii) Si Hf (x) es DN 8x 2 X , entonces f es estrictamente cóncava en X .
(iv) Si Hf (x) es DP 8x 2 X , entonces f es estrictamente convexa en X .
Fosco (PUC) Math 20 y 25 de abril 2016 55 / 69
Concavidad y Optimización
Theorem (óptimos locales y globales)
En el problema P, suponga que f es cóncava y G convexo. Entonces:
(i) Todo máximo local de f es un máximo global de f (Ejercicio 5.2 Carter)
(ii) El conjunto de maximizadores de f en G es vacío o convexo.
Parte (i): si existe un óptimo local, entonces es global.
Parte (ii): el conjunto de puntos que optimiza la función puede ser
vacío (puede no existir un óptimo), pero si no es vacío, es convexo (si
hay un único punto que optimiza, es convexo por de�nición; si hay
más de un punto, la combinación convexa de cualquier par de ellos es
también un punto optimizador).
Fosco (PUC) Math 20 y 25 de abril 2016 56 / 69
Concavidad y Optimización
Theorem (un resultado de unicidad)
En el problema P, suponga que f es estrictamente cóncava y G es
convexo, entonces: el conjunto de maximizadores de f es vacío o tiene un
único elemento (singleton).
Este teorema re�na el resultado del teorema anterior y establece que
si f es estrictamente cóncava para máximo, el óptimo global es único
o no existe.
Fosco (PUC) Math 20 y 25 de abril 2016 57 / 69
Concavidad y Optimización
Atención: no se requiere en ninguno de estos dos teoremas que la
función objetivo sea diferenciable. Las condiciones son sobre G que
debe ser convexo y sobre f que debe ser cóncava.
Pero f puede satisfacer estas condiciones y no ser diferenciable.
Si f es diferenciable, y se cumplen algunas condiciones adicionales, las
condiciones necesarias de primer orden se convierten en condiciones
necesarias y su�cientes para óptimos que, si existen, son globales.
Fosco (PUC) Math 20 y 25 de abril 2016 58 / 69
Concavidad y optimización con restricciones - funciones
diferenciables
(Teorema 5.6 Carter)
Theorem (óptimos restringidos - caso general)
Suponga que f es cóncava y gj son convexas 8j y existe algún ex2X tal
que g (ex) < 0. Luego, x� es una solución global para P si y solo si
9λ� � 0 2Rm tal que el Lagrangiano es maximizado en x� y
λ�j gj (x�) = 0 para todo j. Si f y gj son diferenciables, es necesario y
su�ciente que (x�,λ�) sea un punto estacionario del Lagrangiano, es decir,
que satisfaga las condiciones KKT.
Fosco (PUC) Math 20 y 25 de abril 2016 59 / 69
Concavidad y optimización con restricciones - funciones
diferenciables
Como el problema se ha planteado como maximización, f debe ser
cóncava y C 1 (continua, diferenciable).
Como las restricciones de desigualdad se plantean g (x) � 0, entonces
el conjunto G será convexo si y solo si las funciones gj son convexas.
Pero igualmente podríamosprobar que G es convexo de otra manera
y es lo mismo.
Fosco (PUC) Math 20 y 25 de abril 2016 60 / 69
Concavidad y optimización con restricciones - funciones
diferenciables
Cuali�cación de restricciones de Slater: existe algún ex2X tal que
g (ex) < 0 + condiciones de convexidad de gj (i.e. G convexo).
En de�nitiva: si el problema es convexo, es decir, planteando el
problema como maximización con las restricciones de desigualdad
como acordamos, las condiciones necesarias de primer orden son
también su�cientes cuando f es cóncava y X es convexo.
Fosco (PUC) Math 20 y 25 de abril 2016 61 / 69
Cuasi-concavidad y Optimización - De�niciones
Una función f : X � Rn ! R, X convexo, es cuasi-cóncava en X ()
(8x1, x2 2 X ) (8α 2 (0, 1))
f [αx1 + (1� α)x2] � minff (x1), f (x2)g.
La función f es cuasi-convexa en X () (8x1, x2 2 X ) (8α 2 (0, 1))
f [αx1 + (1� α)x2] � maxff (x1), f (x2)g.
Fosco (PUC) Math 20 y 25 de abril 2016 62 / 69
Cuasi-concavidady Optimización - De�niciones
Una función f : X � Rn ! R, X convexo, es cuasi-cóncava estricta en
X () (8x1, x2 2 X ) (x1 6= x2) (8α 2 (0, 1))
f [αx1 + (1� α)x2] > minff (x1), f (x2)g.
La función f es cuasi-convexa estricta en X ()
(8x1, x2 2 X ) (x1 6= x2) (8α 2 (0, 1))
f [αx1 + (1� α)x2] < maxff (x1), f (x2)g.
Fosco (PUC) Math 20 y 25 de abril 2016 63 / 69
Cuasi-concavidad y Optimización - De�niciones
Una función diferenciable f : X � Rn ! R, X abierto, es cuasi-cóncava si
y solo si (8x1, x2 2 X )
si f (x2) � f (x1) , entonces rf (x1) � (x2 � x1) � 0
(Ejercicio 4.73, Carter, p. 489)
Fosco (PUC) Math 20 y 25 de abril 2016 64 / 69
Cuasi-concavidad y Optimización
Funciones cuasi-cóncavas y cuasi-convexas no son necesariamente
continuas en el interior de sus dominios.
Funciones cuasi-cóncavas pueden tener máximos locales que no son
máximos globales y funciones cuasi-convexas pueden tener mínimos
locales que no son mínimos globales.
Las condiciones de primer orden no son su�cientes para identi�car a
veces ni siquiera los óptimos locales...
Entonces?...
Fosco (PUC) Math 20 y 25 de abril 2016 65 / 69
Cuasi-concavidad y Optimización
Theorem (resultado de unicidad)
En el problema P suponga que f es cuasi-cóncava estricta y G convexo.
Entonces cualquier máximo local de f en X es un máximo global de f en
X . Más aún, el conjunto de maximizadores de f en X es vacío o tiene un
único elemento.
Note que es similar al caso en que f es estrictamente cóncava
(convexa).
No requerimos para este resultado que f sea diferenciable.
Fosco (PUC) Math 20 y 25 de abril 2016 66 / 69
Cuasi-concavidad y Optimización
Theorem (cuasiconcavidad)
En el problema de optimización P suponga que
- f es cuasi-cóncava y gj , cuasi-convexas.
- rf (x�) 6= 0 y rgj (x�) 6= 0 para todo j 2 B (x�) (condiciones de
regularidad)
- existe algún ex tal que gj (ex) < 0 para todo j 2 B (x�) (condición de
Slater)
entonces las condiciones KKT son necesarias y su�cientes para un óptimo
global.
(Corolario 5.5.3 CARTER)
Fosco (PUC) Math 20 y 25 de abril 2016 67 / 69
Pseudo-concavidad y Optimización
Una función diferenciable f : X � Rn ! R, X abierto, es pseudo-cóncava
en X () 8x1, x2 2 X :
si f (x2) > f (x1), entonces rf (x1) � (x2 � x1) > 0.
Alternativamente: 8x1, x2 2 X :
si rf (x1) � (x2 � x1) � 0, entonces f (x2) � f (x1).
Fosco (PUC) Math 20 y 25 de abril 2016 68 / 69
Pseudo-concavidad y Optimización
Theorem
(Condiciones su�cientes) Sea el problema P con f pseudo-cóncava y las gj
cuasi-convexas. Si existe un punto x� 2 G que satisface las condiciones de
primer orden de KKT, entonces x� es una solución óptima global de P.
(Carter, Teorema 5.5, pag. 582)
Fosco (PUC) Math 20 y 25 de abril 2016 69 / 69