Descarga la aplicación para disfrutar aún más
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
Compartir