Keywords
second-order cones
interior point methods
programación cuadrática convexa
conos de segundo orden
métodos de punto interior
How to Cite
Abstract
In this article a modification of the recursive algorithm of Cholesky is obtained that allows the factorization of Semi Definite Positive Matrices, even though these are not positive defined, without increasing the computational cost. Thanks to this factorization Convex Quadratic Programming Problems are transformed into Second Order Conical Problems, which are solved with the aid of the generalization of the Predictor-Corrector algorithm of Mehrotra for these problems. There are carried out numeric experiments for validating the results.
References
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.