Palabras clave
second-order cones
interior point methods
programación cuadrática convexa
conos de segundo orden
métodos de punto interior
Cómo citar
Resumen
En este artículo se obtiene una modificación del algoritmo recursivo de Cholesky que permite la factorización de matrices semidefinidas positivas, aún cuando éstas no sean definidas positivas, sin incrementar el costo computacional. Gracias a esta factorización se transforman los Problemas de Programación Cuadrática Convexa en Problemas Cónicos de Segundo Orden, los cuales se resuelven con la ayuda de la generalización del algoritmo predictor-corrector de Menhrotra para dichos problemas. Se realizan experimentos numéricos para validar los resultados.
Citas
Alizadeh, F.; Schmieta, S.H. (1997) “Optimization with semidefinite, quadratic and linear constraints”, Rutcor Research Report, RRR 23–97, November.
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 Verlag.
Arbenz, P.; Dramac, Z. (2000) “On semipositive definite matrices whith null space known”, ETH Zürich, Computer Science Departament, Technical Report Research #352, November.
Ben-Tal, A.; Nemirovski, A. (2001) Lectures on Modern Convex Optimization: Analysis, Algorithms and Engineering Applications. MPS/Siam, Series on Optimization, SIAM.
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 Comptutation.
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 Programming 72.
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.