DIRECCIÓN DE DESCENSO EN EL PROBLEMA DE MÍNIMOS CUADRADOS DE UN MÉTODO DE PUNTO INTERIOR PARA PROGRAMACIÓN LINEAL

• Autores: Jenny Rojas Jerónimo, Carlos De la Cruz Chávez
• Localización: Selecciones Matemáticas, ISSN-e 2411-1783, Vol. 2, Nº. 2, 2015 (Ejemplar dedicado a: Agosto - Diciembre), págs. 129-145
• Idioma: español
• DOI: 10.17268/sel.mat.2015.02.07
• Títulos paralelos:
  • ADDRESS DECLINE IN THE LEAST SQUARES PROBLEM OF A INTERIOR POINT METHOD FOR LINEAR PROGRAMMING
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    En este artculo presentamos una mejora en la solucion del problema de mnimos cuadrados que requiere el algoritmo del elipsoide interior para determinar la direccion de descenso; y resolver as problemasde programacion lineal usando este metodo de puntos interiores. Resolvemos el problema de mnimos cuadrados usando la funcion auxiliar con barrera logartmica y una aproximacion a la factorizacion dela matriz inicial mediante una matriz con actualizacion de rango uno para nalmente usar la formula de Sherman-Morrison-Woodburry y determinar la inversa de la matriz actualizada resolviendo as elproblema de mnimos cuadrados y obteniendo una aproximacion a la direccion de descenso.

  • English

    This research work solves the problem of least squares that requires inner elipsoid algorithm to determine the descent direction; giving solution to linear programming problems by means of this methodof interior points. We solve the least squares problem using auxiliary function with logarithmic barrier and an approximation of the original matrix factorization by a matrix of rank one update to nally use the Sherman-Morrison-Woodburry formula and determining the inverse of the current matrix thus solving the least squares problem and obtaining a approximation to the descent direction.

• Referencias bibliográficas
  • Angel Salamanca Fernández, Jesús Juan Ruiz, Algoritmo del elipsoide interior para Programación Lineal, Questiió, 1991; 69-93.
  • Aeneas Marxen, Primal barrier methods for Linear Programming, Sol, 1989; 89-96.
  • C.T. Kelley, Iterative Methods for Linear and Nonlinear Equations, SIAM. 1998.
  • George B. Dantzig, Mukund N. Thapa, Linear Programming Introduction, 3era ed., Peter Glynn. 1997.
  • George B. Dantzig, Mukund N. Thapa, Linear Programming Theory and Extensions, 3era ed., Peter Glynn. 1997.
  • J.E. Dennis y Robert B. Schnabel, A View of Unconstrained Optimization. Operations Research and Management Science, 1988; 03-86.
  • Klee, V.Y, G.J. Minty, How good is the Simplex Algorithm? In Inequalities III. Shissha Ed Academic Press, New York, 1979; 159-175.