Métodos de Optimización Matemática, Programación Lineal e Ecuacións Diferenciais

Optimización Matemática e Condicións de Optimalidade

Definicións de Extremos e Convexidade

• Máximo local: Un punto x₀ ∈ X é un máximo local do problema se existe unha contorna B(x₀, r) tal que f(x₀) > f(x) para todos os puntos x ∈ B(x₀, r) ∩ X.
• Máximo global: Un punto x₀ ∈ X é o máximo global do problema se f(x₀) > f(x) para todos os puntos x ∈ X.
• Subconxunto convexo: Un subconxunto X de ℝⁿ é convexo se contén o segmento que une calquera par de puntos de X. Unha función f é convexa (cóncava) nun conxunto convexo X se e só se a matriz Hessiana de f é definida positiva (negativa) en todos os puntos x ∈ X.

Teorema de Weierstrass

Se f é continua e X é compacto (pechado —contén a súa fronteira— e acoutado —contido nunha bola—), o problema ten un máximo e un mínimo globais.

Propiedades de Convexidade

• Se X é convexo e f é convexa, todo mínimo local do problema é un mínimo global.
• Se X é convexo e f é cóncava, todo máximo local é un máximo global.

Clasificación de Matrices Simétricas

Unha condición necesaria e suficiente para que a matriz simétrica A sexa:

1. Definida positiva (SDP): Que todos os seus autovalores sexan positivos.
2. Definida negativa (SDN): Que todos os seus autovalores sexan negativos.
3. Indefinida: Que exista un autovalor de cada signo.

Condicións de Optimalidade

Condición necesaria de optimalidade

(Espazo sen contido adicional no orixinal)

Condicións suficientes de optimalidade

1. Se H_xL(x₀, λ₀) é definida negativa, x₀ é un máximo local para o noso problema.
2. Se H_xL(x, λ₀) é definida negativa (SDN) en todo x ∈ ℝⁿ, x₀ é un máximo global.

Optimización con Restricións e Condicións de Karush-Kuhn-Tucker (KKT)

Conceptos Fundamentais

• Conxunto factible: É o conxunto de puntos de G no que se verifican as restricións: X = {x ∈ G / g(x) < b].
• Lagrangiano asociado: L(x, λ) = f(x) - λ(g(x) - b)
• Solución factible: Solución que satisfai todas as restricións. É unha solución de fronteira se cumpre algunha das restriccións con igualdade; nese caso, dise que satura a restricción ou que a restricción está activa nesa solución. Se a solución cumpre unha restricción con desigualdade estrita, dise que non satura esa restricción.
• Dirección factible: Dado un punto x₀ ∈ X, dise que o vector v ∈ ℝⁿ é unha dirección factible se...
• Punto regular: Un punto x^* ∈ X é un punto regular se verifica...

Condicións Suficientes para Verificar a Hipótese de Regularidade

• Todos os puntos de X son regulares se todas as restriccións son lineais.
• Todos os puntos de X son regulares se todas as restriccións son convexas e o interior do conxunto factible é non baleiro.
• Un punto x^* ∈ X é regular se é un punto interior ou, no caso de ser fronteira, os gradientes das restriccións saturadas en x^* son linealmente independentes.

Esquema de Kuhn-Tucker (KT)

Regular + Óptimo {punto KT se e só se}: Punto crítico do Lagrangiano respecto a x, factible, folguras complementarias e multiplicadores do mesmo signo.

Se f é continua e X é compacto, o Teorema de Weierstrass garante a existencia de máximo e mínimo globais. Se todos os puntos son regulares, o Teorema de KT garante que todos os óptimos son puntos KT. Nestas condicións, o máximo e o mínimo globais serán os puntos KT nos que f tome o seu maior e menor valor, respectivamente.

Teorema de Karush-Kuhn-Tucker (KT) sen necesidade de regularidade

Sexa x^* ∈ X un punto regular que é un mínimo local do problema, entón existen...

Condicións Suficientes de Convexidade

Se (x^*, λ^*) é un punto KT regular do problema e, ademais, X é convexo, verifícase que:

• Se λ^* < 0 e f é convexa, entón x^* é un mínimo global do problema.
• Se λ^* > 0 e f é cóncava, entón x^* é un máximo global do problema.

Condición Suficiente Xeral

Sexa o problema Max f(x) s.a. g(x) < b e (x^*, λ^*) un punto KT regular verificando:

1. λ^* > 0
2. A forma cuadrática h^t H L_x(x^*, λ^*) h restrinxida ao conxunto {h ∈ ℝⁿ / J_kg(x^*)h = Θ}, con K = {k ∈ I / λ^*_k}, é definida negativa.

Entón, x^* é un máximo local do problema.

Programación Lineal e Dualidade

Formulación de Problemas

• Forma matricial: max cx s.a. Ax < b, x > 0
• Forma estándar: Se as restricións son de igualdade e as variables non negativas: max cx s.a. Ax = b, x > 0.

Solucións e Estrutura Xeométrica

• Solución básica: Dado o sistema de m ecuacións e n incógnitas Ax = b, con rang(A) = m < n, sexa B unha submatriz cadrada de orde m regular e x^* unha solución do sistema. Diremos que x^* é unha solución básica de Ax = b respecto da base B se as n - m compoñentes de x^* non asociadas con columnas de B son nulas. As compoñentes asociadas ás columnas de B chámanse variables básicas e a matriz B, matriz básica. Ademais, se nunha solución básica unha ou máis das variables básicas son nulas, a esa solución chámaselle solución básica dexenerada.
• Solución factible: Calquera elemento x ∈ X. Unha solución factible que é solución básica do sistema Ax = b chámase solución factible básica.
• Teorema do Politopo: Sexa X (politopo) o conxunto factible do noso problema de programación lineal. x^* é un vértice de X se e só se é unha solución factible básica.

Teoremas de Dualidade

• Teorema de Existencia: Unha condición necesaria e suficiente para que un problema de programación lineal teña solucións é que tanto o conxunto factible do primal como o conxunto factible do dual sexan non baleiros. Chamando X ao conxunto factible do primal e X' ao conxunto factible do dual, verifícase que...
• Teorema de Dualidade: Unha condición necesaria e suficiente para que unha solución factible sexa óptima para o problema primal é que exista unha solución factible óptima para o problema dual tal que o valor das funcións obxectivo nas solucións correspondentes coincida.
• Teorema de Folgura Complementaria: Sexan x e v solucións do problema primal e dual respectivamente. Unha condición necesaria e suficiente para que x e v sexan solucións óptimas dos problemas primal e dual é que satisfagan as condicións de folgura complementaria: (c - vA)x = e v(b - Ax) = .

Ecuacións en Diferenzas

Conceptos e Definicións

• Ecuación en diferenzas: De orde un, é unha expresión da forma y_t+1 = F(t, y_t), t ∈ ℕ, onde F é unha función de dúas variables reais e con valores en ℝ.
• A ecuación en diferenzas dise autónoma se ten a expresión: y_t+1 = F(y_t), t ∈ ℕ.
• Sucesión: Unha sucesión {z_t} é solución dunha ecuación en diferenzas se, cando se substitúen os termos correspondentes da sucesión na ecuación, esta convértese nunha identidade para cada valor de t ∈ ℕ.
• O problema de determinar a solución dunha ecuación en diferenzas que verifica unha condición inicial dada y₀ denomínase Problema de Valor Inicial (PVI). A solución dun PVI denomínase solución particular.
• Teorema de existencia e unicidade de solución: Dado calquera valor arbitrario y₀ ∈ ℝ, o problema de valor inicial y_t+1 = F(t, y_t), t ∈ ℕ, con y₀ dado, ten unha e só unha solución.
• Solución xeral da ecuación en diferenzas: A solución xeral da ecuación en diferenzas y_t+1 = F(t, y_t) é unha familia de sucesións que depende dunha constante arbitraria ou parámetro (C), z_t = z(t, C), C ∈ ℝ, de xeito que:
  • Para cada valor de C ∈ ℝ, z(t, C) é solución da ecuación.
  • Para cada y₀ ∈ ℝ, é posible atopar un valor C₀ ∈ ℝ tal que a sucesión da familia z(t, C₀) é a solución do P.V.I. y_t+1 = F(t, y_t) con y₀ dado.

Aplicacións Financeiras

• Xuro simple: Ecuación en diferenzas C_n+1 = C_n + i C₀ e solución C_n = C₀ + i C₀ⁿ.
• Xuro composto: Ecuación en diferenzas C_n+1 = (1 + i) C_n e solución C_n = (1 + i)ⁿ C₀.
• Amortización de préstamo: (Espazo sen contido adicional no orixinal)

Estados de Equilibrio e Estabilidade

Estado de equilibrio da ecuación: Dise que y_e ∈ ℝ é un estado de equilibrio da ecuación y_t+1 = F(y_t) se a sucesión constante igual a y_e é solución da ecuación.

Sexa y_e unha solución de equilibrio para a ecuación y_t+1 = F(y_t). Diremos que y_e é:

• Estable: Se as solucións que parten de condicións iniciais nun determinado intervalo centrado en y_e converxen a y_e.
• Inestable: Se as solucións que parten de calquera intervalo centrado en y_e non converxen a y_e e son sucesións non acoutadas.
• Marxinalmente estable: Se as solucións que parten de calquera intervalo centrado en y_e non converxen a y_e pero son sucesións acoutadas.

Modelo da Tela de Araña (Cobweb Model)

Foi introducido para explicar as flutuacións que se producen nos prezos dos mercados agrícolas debido ao desfase entre a toma de decisións sobre a produción e o momento no que esta se coloca no mercado. A decisión da cantidade que se produce debe tomarse no período anterior ao da súa venda. Supoñendo as seguintes hipóteses para o establecemento do modelo:

• Partindo dun prezo p₀ coñecido.
• A demanda é función dos prezos vixentes en cada período: d_t = a - b p_t, con a, b > 0, t ∈ ℕ.
• A oferta en cada período é función do prezo anterior: s_t+1 = -c + d p_t, con c, d > 0, t ∈ ℕ.
• En cada período o mercado está en equilibrio: d_t+1 = s_t+1, t ∈ ℕ.

A partir do equilibrio, obtemos a ecuación en diferenzas para o prezo p_t+1 = - .... Obsérvase que o prezo é de equilibrio en cada período, pero se non se parte inicialmente do equilibrio, o prezo flutuará de período a período. A solución de equilibrio global obtense como... e, polo tanto, o prezo de equilibrio é... e como solución xeral temos: ...

Condicións nas que o prezo de equilibrio de mercado p_t converxe ao estado de equilibrio p_e, particularizando o estudo feito para a ecuación lineal y_t+1 = a y_t + b:

• Se [ ] < 1, as solucións converxen de xeito oscilante ao estado de equilibrio; os prezos tenden ao prezo de equilibrio (equilibrio asintoticamente estable).
• Se [ . ] > 1, as solucións diverxen de xeito oscilante; trátase de oscilacións explosivas. Neste caso, o modelo só ten sentido para un período de tempo limitado, precisamente o período de tempo no que aparecen os prezos negativos (equilibrio inestable).
• Se [ . ] = 1, as solucións teñen oscilacións constantes (equilibrio marxinalmente estable).

O nome deste modelo vén da forma que adopta a traxectoria do prezo no diagrama de representación das funcións de oferta e demanda.

Ecuacións Diferenciais Ordinarias

Definicións e Conceptos

• Ecuación diferencial: Unha ecuación diferencial ordinaria de 1ª orde en forma explícita ten a expresión: y'(t) = F(t, y(t)), t ∈ I ⊆ ℝ. Diremos que é autónoma cando a relación entre a variable de estado e a súa derivada non depende do tempo: y'(t) = F(y(t)), t ∈ ℝ.
• Unha solución da ecuación diferencial y'(t) = F(t, y(t)) no intervalo [a, b] é unha función h(t) derivable en [a, b] que verifica a ecuación h'(t) = F(t, h(t)), t ∈ [a, b].
• Problema de Cauchy: É o problema de determinar a solución dunha ecuación diferencial ordinaria de 1ª orde que verifica a condición inicial y(t₀) = y₀. Escríbese: y'(t) = F(t, y(t)), y(t₀) = y₀.
• Teorema de existencia e unicidade de solución: Se na ecuación diferencial y' = F(t, y) a función F(t, y) e a súa derivada parcial D₂F(t, y) son continuas nun aberto de ℝ², e se (t₀, y₀) é un punto deste aberto, entón existe unha única solución definida nunha contorna de t₀ para o problema de Cauchy y' = F(t, y), y(t₀) = y₀.
• Solución xeral da ecuación diferencial: É unha familia de funcións y(t, C), C ∈ ℝ que verifica:
  • Para cada C ∈ ℝ, y(t, C) é solución da ecuación diferencial.
  • Calquera que sexa a condición inicial y(t₀) = y₀, pódese determinar un valor C₀ tal que a función y(t, C₀) verifica a condición inicial dada.
• Solución xeral da ecuación lineal completa: É a suma da solución xeral da homoxénea asociada e unha solución particular da completa.