Facultad de Derecho y CC. Sociales de Ciudad Real. Matemáticas II ———————————————————————————————————

TEMA 6: ”Introducción a la teoría de optimización” La programación matemática es una parte de la teoría de optimización, y a modo de primera aproximación , podemos decir que el objetivo de esta materia es resolver problemas en los cuales se busca la mejor solución posible entre un conjunto de alternativas.

6.1- Planteamiento y definición de un problema de optimización Planteamiento general de un problema de optimización Para determinar un modelo de programación matemática hemos de especificar: variables de decisión del problema _ Vendrán dadas por el vector x = x 1 , x 2 , . . . , x n . Donde la letra n representará siempre el número de variables de decisión del problema. Función objetivo Es la función f : R n → R, que queremos maximizar o minimizar Restricciones Son las condiciones que se imponen a las variables para que una solución sea admisible como tal. En general consideraremos tres tipos restricciones: _ ● De menor o igual g i x ≤ b i _ ● De mayor o igual g i x ≥ b i _ ● De igualdad g i x = b i _ Donde g i : R n → R, b i ∈ R i = 1, 2, . . . , m. Es decir g i x son las funciones que determinan las restricciones, b i son los términos independientes, y tendremos m restricciones en total. Así podemos decir que resolver un problema de programación matemática es buscar unos valores para las variables de decisión que cumplan las restricciones establecidas, y con los que la función objetivo _alcance su valor óptimo (Max o Min). Cuyo planteamiento general es: Optimizar fx ≤ _ Sujeto a : g i x bi ≥ =

Transformaciones en los problemas de optimización A veces conviene transformar el problema en otro equivalente, donde la solución óptima se calcule fácilmente. Cambio del objetivo _ _ Max fx ≃ Min −fx Eliminación de una constante en la función objetivo _ Si la función objetivo es de la forma: fx + k, siendo k ∈ R. Al eliminar la constante k el problema que obtenemos tiene los mismos óptimos. ————————————— Tema 6: página 1

Facultad de Derecho y CC. Sociales de Ciudad Real. Matemáticas II ——————————————————————————————————— Cambio de una desigualdad _ _ gx ≤ b ≃ −gx ≥ −b Cambio de igualdad por desigualdades _

_

gx = b ≃

gx ≤ b _

gx ≥ b

Cambio de desigualdades por igualdades Aquí introducimos las llamadas variables de holgura _ _ ● gx ≥ b ≃ gx − T = b _ _ ● gx ≤ b ≃ gx + S = b S, T ≥ 0, son las variables de holgura Condiciones de signo ● x i ≤ 0 ≃ −x i  ≥ 0 ● Si x es una variable libre: x = x 1 − x 2 / x 1 ≥ 0 ; x 2 ≥ 0 Nunca hemos de olvidarnos de calcular los valores de las variables del problema original deshaciendo los cambios que hayamos hecho.

6.2- Tipos de problemas. Tipos de soluciones. Clasificación de los programas de optimización Los modelos de optimización, ya hemos visto que se caracterizan por contener: - Variables de decisión. - Ecuaciones de restricción. - Función objetivo. Una breve clasificación de los programas de optimización atendiendo a diversos criterios sería: a. Según la naturaleza de los datos: - Programas deterministas. - Programas estocásticos. b. Según la variable tiempo: - Programas dinámicos. - Programas estáticos. c. Según los objetivos del problema: - Programas con objetivo único. - Programas con objetivos múltiples. d. Según tengan o no restricciones: - Programas sin restricciones. - Programas con restricciones. e. Según la linealidad de las funciones que intervienen: - Programas lineales. - Programas no lineales. f. Según la continuidad de las variables: - Programas continuos. - Programas discretos. ————————————— Tema 6: página 2

Facultad de Derecho y CC. Sociales de Ciudad Real. Matemáticas II ——————————————————————————————————— Nos centraremos en el estudio de aquellos problemas situados en el campo estático y caracterizados por la existencia de un único objetivo, además de tener ausencia de aleatoriedad en las variables de decisión y siendo una de las características de los modelos de optimización la existencia de un único decisor. Así nosotros distinguiremos tres tipos de problemas: ● Programación clásica: - Sin restricciones. - Con restricciones de igualdad. ● Programación no lineal. ● Programación lineal (Para resolver un problema de programación matemática hay que aplicar técnicas diferentes según sus características)

Clases de soluciones Una solución de un problema de programación matemática es cualquier valor posible para sus variables de decisión. Y conviene clasificarlas de la siguiente manera: ● Soluciones factibles: Una solución factible de un problema es una solución que satisface todas las restricciones. Y al conjunto de todas las soluciones factibles se le llama conjunto de oportunidades. Y dentro de estas soluciones factibles distinguiremos entre: - Soluciones frontera: Son aquellas soluciones que cumplen alguna de las restricciones con igualdad. Y en tal caso se dice que satura la restricción. - Soluciones interiores: Son aquellas soluciones que cumplen todas las retricciones con desigualdad estricta. ● Soluciones infactibles: Una solución es infactible cuando no satisface alguna de las restricciones.

Clases de óptimos Sea la función objetivo: f : R n → R, y un conjunto de oportunidades S ∈_ R n . - Máximo global o absoluto: Se dice que f tiene un máximo global en x ∗ ∈ S si _∗ _ _ fx  ≥ fx ∀ x ∈ S _ - Mínimo global o absoluto: Se dice que f tiene un mínimo global en x ∗ ∈ S si _∗ _ _ fx  ≤ fx ∀ x ∈ S _ _ - Máximo local_ o relativo: Se dice que f tiene un máximo local en x ∗ ∈ S si ∃Ux ∗  ⊂ S _∗ _ _∗ / fx  ≥ fx ∀ x ∈ Ux  _∗ _∗ Mínimo local o relativo: Se dice que f tiene un mínimo local en x ∈ S si ∃U x ⊂S _ _ _ _ / fx ∗  ≤ fx ∀ x ∈ Ux ∗  _

Punto crítico: Suponiendo que la función objetivo f sea diferenciable en x ∗ ∈ S, decimos _ _ _ que x ∗ es un punto crítico si dfx ∗  = 0. De tal forma que x ∗ puede ser un máximo, un mínimo o un punto de silla. En un problema de programación matemática, se buscán los óptimos globales.

Clases de problemas según su solución ● Problemas factibles: Sí que existen soluciones que satisfacen las restricciones del problema, y pueden ser: - Problemas con solución óptima global. - Problemas no acotados ● Problemas infactibles: No existe ninguna solución que satisfaga las restricciones del problema. ————————————— Tema 6: página 3

Facultad de Derecho y CC. Sociales de Ciudad Real. Matemáticas II ———————————————————————————————————

Teorema de Weierstrass Una función objetivo continua sobre un conjunto de oportunidades compacto no vacío tiene al menos un máximo y un mínimo global.

Teorema Todo conjunto S ⊂ R n definido mediante restricciones de ≤ , ≥ , = con funciones continuas es un conjunto cerrado.

Aspectos geométricos de los programas matemáticos Dado el programa matemático: _ Optimizar fx ≤ _ bi Sujeto a : g i x ≥ = Distinguimos: Curvas de nivel de la función objetivo: Es el conjunto de puntos de R n caracterizados _ _ porque en ellos dicha función toma un mismo valor. Esto es: x∈ R n / fx = k , k ∈ R . El conjunto de las distintas curvas de nivel que se obtienen al variar la constante k se denomina mapa de curvas de nivel. En el caso de que la función objetivo f sea diferenciable, el gradiente de f nos dirige hacia las curvas de nivel del valor más elevado. Conjunto factible: Es el conjunto de los puntos de R n que verifican las restricciones del ≤ problema:

_

_

x∈ R / g i x n

≥

bi

= Geométricamente, y dentro de los límites indicados para las dimensiones, podemos localizar los máximos (mínimos) globales de un programa matemático encontrando aquel o aquellos puntos del conjunto factible que tocan a la curva de nivel de mayor (menor) valor

6.3- Convexidad de conjuntos y funciones. Combinación lineal convexa Sea M un conjunto de m vectores x i : M = x 1 , x 2 , . . . x m  ∈ R n . Decimos que el vector y es m

una combinación lineal de los elementos de M si y = λ 1 x 1 + λ 2 x 2 +. . . +λ m x m =∑ λ i x i ∀ λ i ∈ R, no todas iguales a cero.

i=1 m

Una combinación lineal es convexa si ∀λ i ≥ 0 y ∑ λ i = 1. i=1

Definición de segmento en R n Dados dos vectores x, y ∈ R n , el segmento entre dichos vectores es el conjunto formado por todos los vectores obtenidos mediante la fórmula λx + 1 − λy ∀λ ∈ 0, 1. Dicho de otro modo, llamamos segmento entre dos puntos x e y al conjunto formado por todas las combinaciones linales convexas de dichos puntos. ————————————— Tema 6: página 4

Facultad de Derecho y CC. Sociales de Ciudad Real. Matemáticas II ———————————————————————————————————

Conjuntos convexos Un conjunto S ⊂ R n es convexo si todo segmento entre dos puntos del conjunto está contenido en el mismo. Utilizando la definición de segmento que ya conocemos, decimos que un conjunto S es convexo si: ∀x, y ∈ S –> z ∈ S / z = λx + 1 − λy ∀λ ∈ 0, 1.

Propiedades de los conjuntos convexos Sean S 1 y S 2 conjuntos convexos: 1.- Sea S = S 1 ∪ S 2 , S no tiene por qué ser un conjunto convexo (en general no lo es). 2.- Sea S = S 1 ∩ S 2 , S es un conjunto convexo. 3.- Sea S = k S 1 , ∀ k ∈ R. S es un conjunto convexo. 4.- Sea S = S 1 + S 2 . S es un conjunto convexo. 5.- Sea S = S 1 xS 2 verifica que S es convexo.

Puntos Frontera Llamamos n-bola de centro a y radio r, a ∈ R n −> a = a 1 , a 2 , . . . , a n , r ∈ R, al conjunto de elementos x ∈ R̸ n / ‖x − a‖ ≤ r (‖ ‖ significa distancia). Si X = x 1 , x 2 , . . . , x n  −> ‖x, a‖ = ± x 1 − a 1  2 + x 2 − a 2  2 +. . . +x n − a n  2 . Decimos que un elemento x de un conjunto S es un punto frontera de S si ∀ n-bola de centro x, dicha n-bola contiene elementos que pertenecen a S y elementos que no pertenecen a S.

Puntos Extremos de un conjunto convexo Decimos que un elemento x de un conjunto S es un punto extremo de S si x no puede ser expresado como combinación lineal convexa de otros dos puntos cualesquiera de S [en otras palabras, si no forma parte del segmento entre otros dos puntos cualesquiera de S]. Si un conjunto no tiene puntos frontera, entonces tampoco tiene puntos extremos (todo punto extremo también es un punto frontera, pero al revés no es cierto).

Envolvente Convexa de un conjunto (o Casco Convexo) La envolvente convexa de un conjunto S es un conjunto formado por todas las combinaciones lineales convexas posibles de los elementos de S. Dicha envolvente convexa es el conjunto convexo más pequeño que contiene a S (si S es convexo, coincide con su envolvente convexa).

Hiperplano Se llama Hiperplano al conjunto formado por los elementos x ∈ R n que resuelvan la ecuación lineal c 1 x 1 + c 2 x 2 +. . . +c n x n = b, c i ∈ R. Dicha ecuación define al hiperplano: H =

x ∈ R n / cx = b .

————————————— Tema 6: página 5

Facultad de Derecho y CC. Sociales de Ciudad Real. Matemáticas II ———————————————————————————————————

Semiespacios n

1. CERRADO POSITIVO: Llamamos así al conjunto de elementos x ∈ R n que verifican

∑ c i x i ≥ b / c i , b ∈ R. Se expresa como H + = i=1

2. CERRADO NEGATIVO: H − = o+

3. ABIERTO POSITIVO: H

o−

4. ABIERTO NEGATIVO: H

= =

x ∈ R n / cx ≥ b

x ∈ R n / cx ≤ b . x ∈ R n / cx > b . x ∈ R n / cx < b .

Criterios de convexidad 1- Un conjunto definido por una restricción de igualdad a partir de una función lineal es un hiperplano, y los hiperplanos son siempre conjuntos convexos. 2- Un conjunto definido por una restricción de ≤ o ≥ a partir de una función lineal es uns semiespacio, y los semiespacios son siempre conjuntos convexos. 3- Un conjunto definido por una restricción de ≤ a partir de una función convexa es convexo. 4- Un conjunto definido por una restricción de ≥ a partir de una función cóncava es convexo.

Funciones cóncavas y convexas. Sea la función fx, donde x ∈ S ⊂ R n , siendo S un conjunto convexo. Se dice que fx es una función convexa si ∀x 1 , x 2 ∈ S se verifica que fλx 1 + 1 − λx 2  ≤ λfx 1  + 1 − λfx 2  ∀λ ∈ 0, 1. Si la desigualdad anterior es estricta, se dice que fx es estrictamente convexa. Sin embargo, si fλx 1 + 1 − λx 2  ≥ λfx 1  + 1 − λfx 2  ∀λ ∈ 0, 1, se dice que fx es cóncava (si la desigualdad es estricta, será estrictamente cóncava). Geométricamente, fx será convexa si el segmento que une dos puntos cualesquiera de la gráfica de la función, se sitúa siempre encima o a la altura de esta (si se sitúa por debajo será cóncava). Propiedades 1- Si fx es convexa –> −fx es cóncava y viceversa. 2- Si fx es convexa (cóncava) –> cfx es convexa (cóncava)∀c ∈ R + . 3- La suma de funciones convexas (cóncavas) es una función convexa (cóncava). 4- La combinación lineal, con coeficientes no negativos, de funciones convexas (cóncavas) es una función convexa (cóncava).

Caracterización de las funciones cóncavas y convexas. Siempre que una función fx sea dos veces derivable, se puede determinar su carácter convexo o cóncavo de la siguiente forma: 1. Para funciónes de una variable ( y = fx en un intervalo considerado I ) ′′

Si ∀x ∈ I

f x ≥ 0 −> fx es convexa (si > 0 estrictamente convexa) ′′

f x ≤ 0 −> fx es cóncava (si < 0 estrictamente cóncava)

————————————— Tema 6: página 6

Facultad de Derecho y CC. Sociales de Ciudad Real. Matemáticas II ——————————————————————————————————— 2. Para funciones de dos variables ( fx, y definida en un conjunto convexo S ) Si f

′′ x 2 x, y

f

′′ x 2 x, y

≥ 0; f

′′ y 2 x, y

≤ 0; f

′′ y 2 x, y

≥ 0;

∀x, y ∈ S ≤ 0;

′′

′′

′′

′′

′′

′′

′′

′′

f x 2 x, y f xy x, y f yx x, y f y 2 x, y f x 2 x, y f xy x, y f yx x, y f y 2 x, y

≥ 0 –> fx, y es convexa

≥ 0 –> fx, y es cóncava

Si las desigualdades anteriores son estrictas, la función será ESTRICTAMENTE CONVEXA/CÓNCAVA. 3. Para funciones de n variables ( fx definida en S ⊂ R n ) Matriz Hessiana Sea fx una función definida ∀x ∈ S ⊂ R n , siendo derivable dos veces en S. Se llama matriz Hessiana de la función fx [Hfx], a la matriz cuadrada de orden n de elementos ′′ h i,j / h i,j = f x i x j x. Menores Principiales Dominantes Se llaman Menores Principales Dominantes de la matriz Hx a los siguientes ′′

f x 21 x n determinantes D k x =

f

′′ x 2 x 1 x

... f

′′ x k x 1 x

... f

′′ x 1 x k x

f x 22 x

... f

′′ x 2 x k x

...

... ...

f

′′ x 1 x 2 x ′′

f

′′ x k x 2 x

k = 1, 2, . . . , n

′′

. . . f x 2k x

a) Si ∀ k −> D k x > 0 −> fx es estrictamente convexa en S. b) Si ∀ k −> −1 k D k x > 0 −> fx es estrictamente cóncava en S. Para estudiar convexidades y concavidades no estrictas hay que definir el concepto: Menores Principales de orden r Son cada uno de los determinantes que se obtienen al eliminar n − r filas y n − r columnas (del mismo índice que las filas suprimidas) de la matriz Hessiana (se representan como Δ r x). a) Si ∀x ∈ S; ∀Δ r x −> Δ r x ≥ 0; r = 1, 2, . . . , n –> fx es convexa en S. (si la desigualdad es estricta para todos los casos posibles, entonces fx es estrictamente convexa). b) Si ∀x ∈ S; ∀Δ r x −> −1 r Δ r x ≥ 0; r = 1, 2, . . . , n –> fx es cóncava en S. (si la desigualdad es estricta para todos los casos posibles, entonces fx es estrictamente cóncava). En R 2 , llamamos Punto de Inflexión al punto en el que una función pasa de ser convexa a cóncava o viceversa. En R 3 o mayor, a esto lo llamaríamos Punto de silla. ————————————— Tema 6: página 7

Facultad de Derecho y CC. Sociales de Ciudad Real. Matemáticas II ———————————————————————————————————

Cuasiconvexidad y Cuasiconcavidad Sea fx una función definida en un subconjunto convexo M de R n . ● f es cuasiconvexa en M sii ∀x 1 , x 2 ∈ M / fx 1  ≥ fx 2  y ∀ λ ∈ 0, 1 −> fλx 1 + 1 − λx 2  ≤ fx 1 . ● f es cuasicóncava en M sii ∀x 1 , x 2 ∈ M / fx 1  ≥ fx 2  y ∀ λ ∈ 0, 1 −> fλx 1 + 1 − λx 2  ≥ fx 2 . Se verifica que, si fx es convexa/cóncava ∀x ∈ M ⊂ R n , también es cuasiconvexa/cuasicóncava en dicho conjunto, pero al contrario, por lo general, no es cierto. En caso de que fx sea diferenciable en M, el estudio de la cuasiconvexidad/cuasiconcavidad, se puede realizar de la siguiente forma: ● fx es cuasiconvexa si ∀x 1 , x 2 ∈ M / fx 2  ≤ fx 1  −> ∇fx 1 x 2 − x 1  ≤ 0. ● fx es cuasicóncava si ∀x 1 , x 2 ∈ M / fx 2  ≤ fx 1  −> ∇fx 1 x 1 − x 2  ≥ 0.

Teorema Local-Global Sea A un subconjunto convexo no vacío de R n y f una función definida en el conjunto A, que toma valores en R. a) Si la función f es (estrictamente) convexa y posee en el punto a ∈ A un mínimo local, entonces dicho mínimo es global. b) Si la función f es (estrictamente) cóncava y posee en el punto a ∈ A un máximo local, entonces dicho máximo es global.

Otros Teoremas 1. Sea una función f estrictamente convexa (cóncava) sobre un conjunto convexo A. Si f presenta un mínimo (máximo) éste es único. 2. Si la función f es convexa (cóncava) en el conjunto convexo A, y en los puntos x 1 , x 2 ∈ A se cumple fx 1  = fx 2  y es un mínimo (máximo) para la función f. Entonces, en cualquier combinación convexa de x 1 y x 2 también se alcanza el mínimo (máximo). Y podemos asegurar que el conjunto de puntos en los que la función f convexa (cóncava) alcanza el mínimo (máximo) es un conjunto convexo. 3. Sea A un subconjunto convexo no vacío, convexo y compacto de R n , cuyo conjunto de puntos extremos es finito, y f una función convexa (cóncava) definida en el conjunto A, que toma valores en R, entonces f posee en A un mínimo (máximo) global, y se encuentra en uno de sus extremos. 4. Si una función convexa tiene un máximo global en el interior de su dominio convexo, entonces la función es constante en su dominio.

Programas convexos (Este apartado justifica el estudio anterior de los conjuntos y funciones convexas.) Todo óptimo global, como ya se ha visto, lo es también local, pero no sucede así al contrario. En capítulos posteriores, estudiaremos métodos para hallar óptimos locales. No obstante, para la economía, es más interesante obtener óptimos globales. Es útil, por lo tanto, conocer la definición de programa convexo pues, al estudiar un programa de este tipo, todos los óptimos obtenidos son óptimos globales (estamos ante una condición suficiente, pero no necesaria, ya que hay muchos programas no convexos que presentan óptimos globales). Existen dos tipos de programas convexos, que son los siguientes: ————————————— Tema 6: página 8

Facultad de Derecho y CC. Sociales de Ciudad Real. Matemáticas II ———————————————————————————————————

1. Dado el programa

Minimizar fx 1 , x 2 , . . . x n sujeto a x 1 , x 2 , . . . x n  ∈ B ⊂ R n

Dicho programa es convexo si f es convexa en B y B es un conjunto convexo.

2. Dado el programa

Maximizar fx 1 , x 2 , . . . x n sujeto a x 1 , x 2 , . . . x n  ∈ B ⊂ R n

Dicho programa es convexo si f es cóncava en B y B es un conjunto convexo.

————————————— Tema 6: página 9