UNIVERSIDAD NACIONAL DE TRUJILLO ESCUELA DE POSTGRADO
SECCIÓN DE CIENCIAS FÍSICAS Y MATEMÁTICAS
SOLUCIÓN DE SISTEMAS DE ECUACIONES RESTRINGIDAS MEDIANTE MÉTODO DE
PUNTOS INTERIORES
Trabajo de tesis para obtener el grado de: Maestro en Ciencias
Autor:
PATRICIA EDITH ALVAREZ RODRIGUEZ
Asesor: Dr. EDMUNDO VERGARA MORENO
Trujillo - Perú 2016
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
2
JURADO DICTAMINADOR
---------------------------------------------------------
Dra Jenny Margarita Rojas Jerónimo
PRESIDENTE
---------------------------------------------------------
Ms Nelson Aragonés Salazar
SECRETARIO
---------------------------------------------------------
Dr Edmundo Vergara Moreno
ASESOR
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
3
DEDICATORIA
Mi tesis la dedico con todo mi amor y cariño
A DIOS que me dio la
oportunidad de existir y
darme dos hijos hermosos.
A mis hijos Sebastián y Brisa, esperando ser
para ellos un modelo de perseverancia, que
alcanzar y superar en esta vida.
A mis padres Segundo y Rosa que me dieron la vida
y me enseñaron a superarme cada día , con su constante
apoyo incondicional .Gracias Papá y Mamá, por darme una
carrera para mi futuro y por creer en mí, los amo mucho.
A mi esposo Javier por su paciencia y
Compresión, Te amo
PATRICIA EDITH ALVAREZ RODRIGUEZ
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
4
AGRADECIMIENTO
A mi madre Rosa por estar conmigo en todo este tiempo donde he vivido
momentos felices y tristes, gracias Mamita por ser mi mejor amiga.
A mi asesor Edmundo Vergara Moreno por confiar en mí, al profesor Nelson
Aragonés y profesora Jenny Rojas por su apoyo constante. Muchas gracias .
Agradezco el haber tenido unos profesores de excelente calidad y ejemplo a
seguir .
A todos mis docentes de la Facultad de Ciencias Físicas y Matemáticas por
contribuir en mi formación como profesional. Y a todos mis amigos que me
rodean gracias por estar conmigo durante este tiempo, siempre los llevare en
mi corazón.
PATRICIA EDITH ALVAREZ RODRIGUEZ
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
5
ÍNDICE
ÍNDICE ............................................................................................................... 2
RESUMEN ......................................................................................................... 6
ABSTRACT ........................................................................................................ 7
I. INTRODUCCIÓN ......................................................................................... 8
II. MATERIALES Y METODOS ..................................................................... 11
III. RESULTADOS ....................................................................................... 12
3.1. El Modelo Básico .................................................................................. 12
3.2. Hipótesis Asumidas ............................................................................. 13
3.3. Problema de Complementariedad ....................................................... 14
3.4. Sistemas KKT ....................................................................................... 19
IV. DISCUSIÓN............................................................................................ 23
4.1. Método de los puntos interiores ......................................................... 23
4.2. Algoritmo de Reducción de la Función Potencial ............................. 27
V. CONCLUSIONES ................................................................................... 33
VI. REFERENCIAS BIBLIOGRÁFICAS ...................................................... 35
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
6
RESUMEN
SOLUCIÓN DE SISTEMAS DE ECUACIONES RESTRINGIDAS MEDIANTE
UN MÉTODO DE PUNTOS INTERIORES
Autor: Lic. Mat. Patricia E. Alvarez Rodríguez
Asesor: Dr. Edmundo Vergara Moreno
En este trabajo se estudia la solución del problema de un Sistema de
Ecuaciones no Lineales Restringidos, mediante la combinación del método de
Newton Amortiguado Clásico para ecuaciones sin restricciones, y el método de
Reducción del Potencial para Puntos Interiores, dado que los sistemas de
ecuaciones Restringidos abarcan una variedad de problemas, como problemas
de complementariedad de varios órdenes y sistemas Karush-Kuhn – Tucker de
desigualdades variacionales, problemas no lineales. En tal sentido se establece
un algoritmo para hallar la solución.
Palabras clave: Sistemas de Ecuaciones Restringidas, Método de Puntos
Interiores, Método de Newton, Desigualdades Variacionales.
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
7
ABSTRACT
SOLUTION OF SYSTEMS OF RESTRICTED EQUATIONS THROUGH A
METHOD OF INTERIOR POINTS
In this work the problem of the solution of a System of Restricted Nonlinear
Equations is studied, by means of the combination of Newton's Method of
Classical Damping for unrestricted equations and the Method of Reduction of
the Potential for Inner Points, since the systems of equations Restrictions
encompass a variety of problems, such as complementarity problems of
various orders and Karush-Kuhn-Tucker systems of variational inequalities,
non-linear problems. In this sense an algorithm is established to find the
solution.
Keywords: Restricted Equation Systems, Internal Point Method, Newton's
Method, Variational Inequalities.
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
8
I. INTRODUCCIÓN
Los problemas de optimización pueden clasificarse de acuerdo a la naturaleza
de la función objetivo y de las restricciones en: lineales, no lineales, convexos,
no convexos, etc , por el número de variables (de gran escala, mediana o
pequeña escala), por la suavidad de las funciones (diferenciables).
Sin embargo una clasificación importante es la clasificación respecto a la
acotación de las variables:
a. Problemas de optimización restringida (con variables acotadas ó
variables encajonadas).
b. Problemas de optimización no restringida (con variables sin restricciones
ó variables libres).
Los problemas de optimización no restringida tienen muchas aplicaciones
prácticas; así también surgen de reformulaciones de problemas de optimización
restringida, por ejemplo el Lagrangiano, método de Penalización, método de
Barrera.
Los Problemas no restringidos son de la forma:
( )
donde f es una función de varias variables de valor real y S Rn. Cuando
S = Rn, corresponde al caso totalmente sin restricciones.
Los problemas de optimización restringida surgen de modelos que incluyen
restricciones explícitas de las variables. Estas restricciones pueden ser: cotas,
restricciones lineales o desigualdades no lineales que expresan relaciones más
complejas entre las variables [5].
Dentro de los problemas de optimización lineal, el Método Simplex ha sido
considerado como uno de los métodos más importante para resolver dichos
problemas; sin embargo desde el punto de vista teórico, el tiempo del cálculo
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
9
requerido por este método crece exponencialmente con el tamaño del
problema, teniendo 2n – 1 iteraciones, en el peor de los casos definido [5. 4].
Muchos investigadores han tratado de desarrollar algoritmos cuyos tiempos de
cálculos tuviesen un crecimiento polinomial con el tamaño del problema [9].
Todos los intentos realizados hasta 1984 fallaron ya fuese desde el punto de
vista teórico o desde el punto de vista práctico. En 1984 Karmarkar propuso un
algoritmo cuya complejidad computacional era polinomial y que resultó
altamente competitivo frente al Método Simplex para resolver problemas de
programación lineal de gran tamaño [2]. A partir del trabajo de Karmarkar se
reactivó la investigación en esta rama matemática, dando origen a una serie de
algoritmos que se denominaron en conjunto “métodos de puntos interiores”.
Esta denominación se debe a que mediante tales algoritmos la aproximación a
la solución óptima es a través de los puntos interiores de la región factible,
mientras que el algoritmo simplex es a través de los puntos de la frontera [5].
Como veremos, las ecuaciones restringidas provienen de una formulación
común para muchos problemas de programación matemática incluyendo los
problemas de complementariedad y el sistema de inecuaciones variacionales
Karush-kuhn- Tucker (KKT) y programas no lineales [11].
Las ecuaciones restringidas provienen aplicando el teorema de Dualidad de la
programación lineal y el teorema de la Dualidad Fuerte de un problema de
programación lineal, es decir:
Min Ct x Max bt y
→
libre
Usando el teorema de Dualidad y Dualidad fuerte, se tiene
Cx = by
Aty = C
Ax = b
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
10
El problema de solucionar sistema de ecuaciones no lineales, es un tipo clásico
cuya importancia persiste en la matemática aplicada. La versión tradicional de
este problema es buscar un vector en un espacio Euclidiano de dimensión finita
que satisfaga un sistema de ecuaciones definido por una función vectorial
suave [14]. Así, el Método de Newton es uno de los métodos más usados para
resolver un sistema de ecuaciones lineales y no lineales pero debido a costo
computacional se usaran un Método de Puntos Interiores.
Estos métodos se han utilizado con éxito en la Programación no lineal y
programación lineal, en resumen combinando la simplicidad del Método de
Newton con la eficiencia de los algoritmos de Puntos Interiores es de presumir
que se obtendrá un algoritmo simple eficiente.
En tal sentido en el presente trabajo se estudia el uso de los métodos de los
puntos interiores para solucionar Sistemas de Ecuaciones Restringidas.
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
11
II. MATERIALES Y METODOS
Como el tema nuestro del presente trabajo, está en marcada en el área de
optimización con conjuntos no convexos, funciones lineales, funciones no
lineales, sistemas de ecuaciones lineales, sistemas con restricciones.
Los métodos usados corresponden a una familia de métodos llamados
métodos de los puntos interiores.
La técnica consiste en hacer búsquedas al interior de los conjuntos.
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
12
III. RESULTADOS
En esta sección se estudiarán los conceptos relacionados a Sistemas de
Ecuaciones con Restricciones. Estos sistemas involucran una variedad de
problemas particulares como problemas de complementariedad, sistemas KKT,
etc.
3.1. El Modelo Básico
Sea un conjunto cerrado con interior
ɸ; y no
necesariamente convexo.
Sea H : , una aplicación continua
( ) ( ( ) ( ))
Ahora, considerar el problema de hallar tal que:
H(w) = 0 (1)
Esto equivale a tener un sistema de ecuaciones, en general no lineal:
{
( )
( )
( )
(2)
w
o.
n
H(w)
o.
..
n
H
Fig. Nº 1. Conjunto de definición de H.
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
13
Ahora, considerar una descomposición de , en la forma:
Luego:
( ) [ ( )
( )] (3)
donde:
,
( ) ( )
son las funciones coordenadas de H.
w
n
..
n
H
H(w)
F(w)0
C(w)
n1
Fig. Nº 2. Descomposición del espacio de llegada.
Definición 3.1.1. Sea , el conjunto
* ( ) + (4)
es llamado el conjunto base de (1); donde la desigualdad ( ) ,
indica que ( ) .
3.2. Hipótesis Asumidas
Ahora, enunciamos los supuestos asumidos por Wang y Coworkers,
necesarios para el desarrollo del presente trabajo:
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
14
(A1) , y * ( ) +.
(A2) La aplicación ( ).
(A3) La matriz Jacobiana H’(w) es no singular para todo .
El supuesto (A1) es equivalente a decir que es no vacío y abierto.
Los supuestos (A2) y (A3) son necesarios para poder aplicar al método
de Newton en la solución de la ecuación (1).
Definición 3.2.1. La función definida por:
( ) , ( ) ( ) ( )- ∑ ( ( )) (5)
donde:
, e = (1, 1,…,1), es llamada la función de Potencial Asociada al
problema (1).
Esta función de Potencial, es necesaria para determinar las direcciones
en el proceso iterativo para hallar la solución del sistema (1) restringido
al conjunto
En lo que sigue, el problema de hallar tal que
H(w) = 0 (6)
será llamado un sistema de Ecuaciones con restricciones.
3.3. Problema de Complementariedad
Sistemas de Ecuaciones Restringidas (6) se pueden utilizar para
modelar problemas de Complementariedad de varios órdenes.
Ahora, considerar el problema de Complementariedad No Lineal
Estándar:
Sea f: una función continua y de clase C1 en ,
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
15
donde:
* +
= *( ) +,
*( )
+
En particular:
* +
0
+
Fig. Nº 3: Caso 1-dimensional
*( ) +
x
2+
0
Fig. Nº 4: Caso 2-dimensional
Luego, el problema de Complementariedad No Lineal Estándar está
dada por:
Hallar un vector , tal que:
x 0, f(x) 0, xT f(x) = 0 (7)
Si n = 2, entonces x = (x1, x2), x1 0 , x2 0.
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
16
f:
( ) [ ( )
( )]
Entonces:
( ) ( ) [ ( )
( )]
( ) ( )
Por tanto, el problema es:
Hallar ( ) , tal que
{ ( ) ( )
( ) ( )
Un problema de Complementariedad (7) es análogo al concepto de
Punto Estacionario en problemas de extremos de funciones, es decir, si
el punto x = 0 es un Mínimo Local de una función real diferenciable,
, , la desigualdad F’(x) > 0, junto con la condición de
complementariedad (7): ( ) , es una condición necesaria puesto
que:
( ) ( )
lo cual indica que “x” es un Punto Crítico.
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
17
y=F(x)
x
y
Fig. Nº 5: Condición necesaria para Punto Crítico.
Ahora, si x > 0, entonces la condición de Mínimo necesario se reduce a
( ) .
y = F(x)
x
y
Fig. Nº 6: Condición Necesaria
Los dos casos se reducen a:
x 0, F’(x) 0, xF’(x) = 0
En forma general, sea una función diferenciable,
( ) un punto donde F alcanza un Mínimo Local.
Sobre un octante no negativo , las condiciones necesarias para que
esto se cumpla es que:
( ) ,y
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
18
( )
Ahora bien, si hacemos:
( )
( )
se tiene:
( ) ∑
( )
Luego, la relación (8) se puede escribir como:
( ) ( )
Ahora, sea ( )
( ) [ ( )
] [ ( )
( )] (9)
donde es el producto de Hadamard de los vectores x e y; es decir si
x = (x1, x2,…, xn), y = (y1, …, yn):
( )
Luego, si ( ) , entonces
( )
( )
Además, si ; entonces
y
(8)
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
19
( ) ∑
( )
Por tanto:
( ) ( ) (10)
Análogamente, se prueba que si se verifica (10) se obtiene (7).
Por tanto, un problema de Complementariedad Estándar es equivalente
a solucionar un Sistema de Ecuaciones Restringidas (7).
3.4. Sistemas KKT
Para problemas de optimización no lineal con restricciones de
desigualdad, los óptimos tienen que satisfacer condiciones necesarias,
las cuales fueron publicadas por primera vez (1939) en la tesis de
William Karush; las cuales fueron renombradas tras un artículo en una
conferencia de Harold W. Kuhn y Albert W. Tucker en 1951.
Las condiciones de Karush – Kuhn – Tucker (KKT) son una
generalización del método de los multiplicadores de Legrange para
restricciones de desigualdad.
Ejemplo:
Sea
( ) ( )
( )
Considerar el problema de Optimización Restringido
{
( )
( ) (11)
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
20
g(x)= 0
1-1
-1
1
x1
x2
Curvas de nivel de f(x)
Fig. Nº 7: Curva de Nivel de f(x)
El punto ( ) es un mínimo global irrestricto de ( ), el cual está
en la región factible.
Una condición necesaria y suficiente para un mínimo local sobre la
restricción, es la misma que para un mínimo local irrestricto:
( ) ( )
Ahora, considerar definida por:
( ) ( ) ( )
, luego el problema es:
{
( )
( ) (12)
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
21
g(x)< 0
x2
x1
Curvas de nivel de f(x)
Fig. Nº 8: Región Factible
Observar que en este caso, un óptimo local ocurre cuando ( ) y
( ) son paralelos:
( ) ( ) (13)
x2
x11-1
Fig. Nº 9: Mínimo Local Restringido.
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
22
A partir de (13), se define la Lagrangiana por:
( ) ( ) ( ). (14)
Luego, para el problema de optimización:
{
( )
( ) (15)
Entonces, para el problema (15), se tiene:
x* es un mínimo local tal que:
{
) ( ) )
) ( )
) ( )
) ( )
(16)
Las relaciones dadas en (16) son llamadas las condiciones KKT.
En forma general, sea un conjunto cerrado, y una
aplicación.
El problema de Desigualdades Variacionales, denotado por VI(K,f)
consiste en hallar , tal que:
( ) ( ) (17)
Si f es una aplicación gradiente:
( ) ( )
donde es una función diferenciable, VI(K,f) es equivalente al
problema de hallar Puntos Estacionarios para el problema de
minimización:
{ ( )
(18)
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
23
IV. DISCUSIÓN
En esta sección enunciamos los conceptos necesarios para el desarrollo del
tema central. Para ello es fundamental analizar el método de los puntos
interiores.
4.1. Método de los puntos interiores
El método de los puntos interiores a estudiar en este trabajo, es el
presentado por Wang y Monteiro en [12 ].
Sea un subconjunto cerrado,
Según (3) ,
( ) [ ( )
( )]
donde:
, y
Además:
* ( ) +
Según la definición (3.2.1) la función Potencial Asociada al problema (6)
está dado por:
definida por:
( ) , ( ) ( ) ( )- ∑ ( ( )) (19)
donde: ( ).
Si , entonces (19) se reduce a:
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
24
( ) , ( ) ( )-,
, ( ) ( )-
( )
( ) ( ) ( ) (
( )) ( )
Donde es la función Merit del método de Newton Amortiguado para
resolver el sistema de Ecuaciones Restringidas:
F(w) = 0 (21)
Por tanto, la función ( ) juega un rol análogo a la función de Merit en
el proceso de generación de la iteración wK para determinar un algoritmo
propuesto por Wang, el cual permitirá resolver (6).
Este algoritmo iterativo en cada iteración usa la dirección de Newton
Perturbada para reducir el valor de la función Potencial sobre ++.
Esto permitirá mantener la estructura cerca de la ruta central del
conjunto ++; como lo hace el método del Punto Interior.
La existencia de la ruta central para (6), está dada en [10]
Definición 4.1.1. Sea una Dirección de Newton Perturbada d ,
en w con respecto a la partición (2), es la solución del sistema de
ecuaciones lineales:
( ) [ ( ) ( )
] [ ( )
( ) ( ) ] (22)
donde
( ) ( ( )
,
El parámetro , es llamado parámetro de centro.
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
25
En general, la solución “d” si existe, es una disección de decrecimiento
para la función en w. Como se demuestra es el siguiente lema.
Considerar la función definida por:
Definida por:
( ) ( ) ( ) ( ) (23)
Observar que si , entonces ( )
Lema 4.1.2. Sea . Bajo las hipótesis (A1) y (2), y para todo
⟨ ⟩, se tiene:
1) ( ) ( ) ( ) (24)
2) ( ); además:
( )
( ), ( ) ( ) ( ) - ( ) ( ) ( )
donde ( ) es el vector cuya i-ésima componente es ( )
3) Si d es solución de (22), entonces:
( ) ( )( ), (26)
por tanto existe , tal que ⟨ ],
( ) ( ) ( )( ) ( )
DEMOSTRACIÓN
2) Para cada , se tiene
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
26
( )
( )[∑ ( )
( )
∑ ( )
] ∑ ( ) ( )
Entonces:
( )
( ), ( ) ( ) ( ) - ( ) ( )
3) Usando (22) y (23) y parte (2), se tiene:
( )
( ), ( ) ( ) ( ) - ( ( ) ) ( )
( )( ( ) ( ( )) ( ( )) ( ) ) ( )
( )
( )( ( ) ( ) ( ) ( ))
( )
( )
( ) [∏ ( )
]
[∏ ( )
]
( ) ( ) ( )( )
( ) ( )( )
Además, usando (A2), y como es abierto, entonces , tal que
⟨ ], se tiene que ; y además:
( ) ( ) ( ( ) ( )( )( ))
( )( ).
Así, , es el factor en la búsqueda lineal del método de Newton
Amortiguado; donde el lado derecho de la desigualdad es siempre
positivo.
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
27
□
A continuación presentamos un algoritmo de reducción de la función de
Potencial, para resolver el problema (6).
4.2. Algoritmo de Reducción de la Función Potencial
En esta sección se enuncia el algoritmo propuesto por Wang, y otros [12]
el cual permitirá resolver iterativamente el problema (6).
Hallar el , tal que:
{ ( )
Paso 1: Inicialización
Sea ⟨ - , ⟩ ⟨ ⟩
Elegir , - , sea k = 0
Paso 2: Generación de Direcciones
Resolver el sistema de ecuaciones lineales (22) en
( ) [ ( )
( ) ] [
( )
( ) ]
donde
( )
para obtener la dirección buscada: dk.
Paso 3: Determinación de la longitud de Paso
Sea mk el entero no negativo más pequeño “m”, tal que las siguientes
indicaciones son ciertas:
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
28
, (28)
( ) ( ) ( )( ) (29)
Hacer .
Paso 4: Fin
Observaciones:
1. La dirección determinada en (2), está bien definida en vista de
(A3)
2. Lema 4.1.2. garantiza que el centro mk esté bien definido.
3. La sucesión * ( )+ es estrictamente decreciente.
Ahora, se establecen algunas propiedades de la sucesión * ( )+.
Lema 4.2.1.
Sea una función definida por:
( ) (‖ ‖ ) ∑
entonces , se tiene:
{( ) ‖ ‖ ( ) } (30)
es un conjunto compacto.
Para una demostración ver [34]
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
29
Teorema 4.2.2.
Supones que (A1), (A2), (A3) son válidos.
Entonces la sucesión * + generada por el algoritmo de Reducción
Potencial satisface las siguientes propiedades:
a) La sucesión * ( )+ es acotada
b) Cada punto de acumulación de * + si existe, es una solución del
sistema
H(w) = 0
c) Si la sucesión * + es acotada, entonces
( ) (31)
d) Si H es propia con respecto a , entonces (31) es válida.
DEMOSTRACIÓN
a) Según Lema (4.1.2), y el hecho * ( )+ es decreciente, se tiene:
( ) [ ( )
] [
( )
]
para toda . Entonces:
* ( )+ es acotada.
b) Sea , donde { } es una subsucesión de * +
Entonces , pues es cerrado.
Afirmamos que ( ) .
En efecto, suponer que ( ) , entonces para algún >0, se tiene
que:
( )
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
30
Como * ( )+ es acotada superiormente por ( ), se sigue a
partir del Lema (4.2.1) que * ( ) ⁄ + está contenido en un
subconjunto compacto de . Así, ( ) , y por (A1), se
sigue que .
Por (A3), la matriz jacobiana ( ) es una singular, entonces la
sucesión:
( ) ( ) .
Además, como , se tiene:
, ⟩.
Como, para cada
( ) ( ( ) [
])
donde ( )
, se concluye que
, verificando
( ) ( ) [
]
donde ( )
Por tanto, por el Lema (4.1.2), y , ⟩, se tiene:
( ) ( )( ) (32)
Además:
Usando la continuidad de , se tiene:
( ) ( )
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
31
Como * ( )+ es estrictamente decreciente, tenemos
( ) ( )
Luego:
( ) ( )
Como , -, de Paso (3), del algoritmo se tiene:
Como es abierto conteniendo a , * ⁄ + es acotada, y
como , suficientemente grande:
, para
Por tanto, (29) no se verifica para suficientemente
grande.
Luego:
( ) ( ) ( )( )
suficientemente grande.
Dividiendo la desigualdad por y haciendo se obtiene:
( ) ( )( ),
lo cual contradice (32)
Por tanto ( ) .
c) Si * + es acotada, entonces:
( )
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
32
Además, como * + tiene ahora a lo más un punto de acumulación,
se tiene que existe una solución de H(w) = 0.
d) Suponer que para algún conjunto infinito de índices * + la
sucesión * ( ) ⁄ + converge en un límite positivo, entonces
para >0, n >0, se tiene:
* ⁄ + * ( ) ( ) ⁄ +
[{( )
‖ ‖ ( ) }]
el cual es completo.
Entonces la subsucesión * ⁄ + es acotada, y por (b)
( )
Lo cual es una contradicción, en consecuencia el resultado está
probado.
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
33
V. CONCLUSIONES
En el presente trabajo se estudió la formulación de un algoritmo basado en el
método del punto interior, para solucionar un Sistema de Ecuaciones
Restringida, obteniendo las siguientes conclusiones:
1. El uso del método del punto interior, permite obtener una sucesión de
puntos * +, en el interior de la región de restricción , de tal manera
que:
donde: H(w*) = 0.
2. Un problema de Complementariedad No Lineal Estándar:
{
( ) ( )
es equivalente al problema de solución de Sistemas de Ecuación
Restringidos:
{ ( )
( ) [ ( )
] .
3. Un sistema KKT de desigualdades variacionales VI(K,f), donde
de C1, * ( ) ( ) ⁄ +,
de clase C2, es equivalente a un Sistema de
Funciones Restringidas:
H(w) = 0
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
34
donde:
( ) [ ( )
] ( ) [
( )
( )
( )] ,
( )
( ) ( ) ∑
( ) ∑
( )
es la función Lagrangiana.
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
35
VI. REFERENCIAS BIBLIOGRÁFICAS
[1] A. AMBROSETTI y G. PRODI. A Primer of Nonlinear Analysis
Cambridge University Press, Cambridge 1993.
[2] ARBEL, AMI. Exploring Interior-Point Linear Programming: Algorithms
and Software. mit Press; London, 1993.
[3] KARMARKAR, N.A. New Polynomial-Time Algorithm for Linear
Programming, Combinatorica. 4(1981); 373-395.
[4] KHACHIYAN, L.G. A Polynomial Algorithm for Linear Programming.
Soviet Mathematics Doklady; 20(1979), 191-194
[5] KLEE. V. Y,G.j. Minty, How good is the Simple?. Algorithm. In
Inequalities III. Press, New York, 1972, 159-175
[6] K.O.K.KORTANEK y H.NO, A second order affine, scaling algorithm for
the geometry programming dual with logarithmic Barrier. Optimization
23(1992)303-322.
[7] I.J.LUSTIG, Feasibility issues in a primal-dual interior-point method for
linear programming. Mathematical Programming 49(1990/1991)145-162
[8] M. KOJIMA, T. NOMA y A. YOSHISE, Global convergence in infeasible
interior point algorithms, mathematical programming. 65(1994)43-72
[9] MOKHTAR S. BAZARAA, HANIF D. SHERALI, C. M. SHETTY,
Nonlinear Programming: Theory and Algorithms, Interscience (2006)
[10] R.D.C.MONTEIRO y J.S.PANG, Properties of an interior point mapping
for mixed complementarity problem, Mathematic of operation research, to
appear.
[11] ROBERT M. FREUND y MICHAEL J. TODD, Barrier Functions and
Interior-Point Algorithms for Linera Programming with Zero-, One, or Two
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
36
sided Bounds on the Variables. Mathematics of Operations Research;
Vol.20, No 2 , May 1975, USA
[12] TAO WANG A, RENATO D.C. MONTEIRO B, JONG-SHI PANG. An
interior point potential reduction method for constrained equations.
Mathematical Programming 74 (1996) 159-195
[13] S. WRIGHT AND D. RALPH, A superlinear infeasible interior point
algorithm for monotone nonlinear complementarity problems, Technical
report MCS-P344-I292, Mathematics and Computer Science Division,
Argonne National Laboratory (1993).
[14] Y. ZHANG. R.TAPIA y F.POTRA, On the superlineal convergence of
interior point algorithms for a general class of problem, SIAM journal on
optimization 3 (1993)413-422.
Biblioteca Digital - Dirección de Sistemas de Informática y Comunicación
Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No Comercial-Compartir bajola misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licences/by-nc-sa/2.5/pe/
BIBLIO
TECA D
E POSGRADO
Top Related