Métodos de punto interior para optimización cuadrática convexa con matrices no definidas positivas

• Palencia F., Gonzalo ^[1] ; Hing C., Rosina ^[1] ; Rojas C., Mariledy ^[1] ; Medina S., Denysde ^[1]
  1. [1] Universidad Central

     Universidad Central

     Hospital, Costa Rica

     
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 15, Nº. 1, 2008, págs. 1-12
• Idioma: español
• DOI: 10.15517/rmta.v15i1.284
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    En este art´?culo se obtiene una modificaci´on del algoritmo recursivo de Choleskyque permite la factorizaci´on de matrices semidefinidas positivas, a´un cuando ´estasno sean definidas positivas, sin incrementar el costo computacional. Gracias a estafactorizaci´on se transforman los Problemas de Programaci´on Cuadr´atica Convexa enProblemas C´onicos de Segundo Orden, los cuales se resuelven con la ayuda de lageneralizaci´on del algoritmo predictor-corrector de Menhrotra para dichos problemas.Se realizan experimentos num´ericos para validar los resultados.Palabras clave: programaci´on cuadr´atica convexa, conos de segundo orden, m´etodos depunto interior.

  • English

    In this article a modification of the recursive algorithm of Cholesky is obtainedthat allows the factorization of Semi Definite Positive Matrices, even though theseare not positive defined, without increasing the computational cost. Thanks to thisfactorization Convex Quadratic Programming Problems are transformed into SecondOrder Conical Problems, which are solved with the aid of the generalization of thePredictor-Corrector algorithm of Mehrotra for these problems. There are carried outnumeric experiments for validating the results.Keywords: convex quadratic programming, second-order cones, interior point methods.

• Referencias bibliográficas
  • Alizadeh, F.; Schmieta, S.H. (1997) “Optimization with semidefinite, quadratic and linear constraints”, Rutcor Research Report, RRR 23–97,...
  • Alizadeh, F.; Goldfarb, D. (2001) “Second-Order Cone Programming, Rutcor Research Report.
  • Andersen, E.D.; Ross, C.; Terlaky, T. (2002) “On implementing a primal-dual interior-point method for conic quadratic optimization”, Springer...
  • Arbenz, P.; Dramac, Z. (2000) “On semipositive definite matrices whith null space known”, ETH Zürich, Computer Science Departament, Technical...
  • Ben-Tal, A.; Nemirovski, A. (2001) Lectures on Modern Convex Optimization: Analysis, Algorithms and Engineering Applications. MPS/Siam, Series...
  • Gantmacher, F.R. (1959) The Theory of Matrices. Chelsea, New York.
  • Higham, N. (1996) “The symmetric indefinite pactorization: stability an applications in optimization”.
  • Lustig, J.; Marsten, R.E,; Shanno, D.F.(1994) “Interior point methods for linear programming: computational state of the art”, ORSA J. on...
  • Murty, Kabadi (1987) “Some NP-complete problems in quadratic and nonlinear programming”, Mathematical Programming 39.
  • Neemirovski, A.; Cherinberg, K. (1996) “Extension of Karmarkar algoritm onto convex quadratically constrained quadratic programming”, Mathematical...
  • Nesterov, Y.E.; Todd, M.J. (1997) “Self-scaled barriers and interior-point methods for convex programming”, Math. of Oper. Res. 22(1): 1–42.
  • Nesterov, Y.E.; Todd, M.J. (1998) “Primal-dual interior-point methods for self-scaled cones”, SIAM J. Optim. 8: 324–364.
  • Nocedal, J.; Wright, S.J. (1999) Numerical Optimization. Springer Series in Operations Research, Springer Verlag, New York.
  • Renegar, J. (2001) A Mathematical View of Interior-Point. Methods in Convex Optimization, MPS-SIAM Series en Optimization.
  • Ross, C.; Terlaky, T.; Vial, J. (1997) Theory and Algoritms for Linear Optimization an Interior Point Approach. John Wiley and Sons, New York.
  • Vandenberghe, L. (2002) “The Cholesky factorization”, EE103 Winter, Germany.