Heuristics For Implementation Of A Hybrid Preconditioner For Interior-point Methods

dc.creatorFontova M.I.V.
dc.creatorde Oliveira A.R.L.
dc.creatorCampos F.F.
dc.date2011
dc.date2015-06-30T20:34:23Z
dc.date2015-11-26T14:51:33Z
dc.date2015-06-30T20:34:23Z
dc.date2015-11-26T14:51:33Z
dc.date.accessioned2018-03-28T22:03:11Z
dc.date.available2018-03-28T22:03:11Z
dc.identifier
dc.identifierPesquisa Operacional. , v. 31, n. 3, p. 579 - 591, 2011.
dc.identifier1017438
dc.identifier
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-80855129505&partnerID=40&md5=781fd8a8fe69ab3a9b66f34a61419dc9
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/108461
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/108461
dc.identifier2-s2.0-80855129505
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1254507
dc.descriptionThis article presents improvements to the hybrid preconditioner previously developed for the solution through the conjugate gradient method of the linear systems which arise from interior-point methods. The hybrid preconditioner consists of combining two preconditioners: controlled Cholesky factorization and the splitting preconditioner used in different phases of the optimization process. The first, with controlled fill-in, is more efficient at the initial iterations of the interior-point methods and it may be inefficient near a solution of the linear problem when the system is highly ill-conditioned; the second is specialized for such situation and has the opposite behavior. This approach works better than direct methods for some classes of large-scale problems. This work has proposed new heuristics for the integration of both preconditioners, identifying a new change of phases with computational results superior to the ones previously published. Moreover, the performance of the splitting preconditioner has been improved through new orderings of the constraint matrix columns allowing savings in the preconditioned conjugate gradient method iterations number. Experiments are performed with a set of large-scale problems and both approaches are compared with respect to the number of iterations and running time. © 2011 Bralizian Operations Research Society.
dc.description31
dc.description3
dc.description579
dc.description591
dc.descriptionAdler, I., Karmarkar, N., Resende, M.G.C., Veiga, G., Data structures and programming techniques for the implementation of Karmarkar's algorithm (1989) ORSA Journal on Computing, pp. 84-106
dc.descriptionBergamaschi, L., Gondzio, J., Zilli, G., Preconditioning Indefinite Systems in Interior Point Methods for Optimization (2004) Computational Optimization and Applications, 28, pp. 149-171
dc.descriptionBocanegra, S., Campos, F.F., Oliveira, A.R.L., Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods (2007) Computational Optimization and Applications, (1-2), pp. 149-164. , Specialissueon"LinearAlgebraIssuesarisinginInteriorPointMethods"
dc.descriptionBurkard, R.S., Karisch, S., Rendl, F., QAPLIB-A quadratic assignment problem library (1991) European Journal of Operations Research, 55, pp. 115-119
dc.descriptionCampos, F.F., Birkett, N.R.C., An efficient solver for multi-right-hand-side linear systems based on the CCCG(η) method with applications to implicit time-dependent partial differential equations (1998) SIAM J Sci Comput, 19 (1), pp. 126-138
dc.descriptionCzyzyk, J., Mehrotra, S., Wagner, M., Wright, S.J., PCx an interior point code for linear programming (1999) Optimization Methods and Software, 11 (2), pp. 397-430
dc.descriptionGolub, G.H., van Loan, C.F., (1996) Matrix Computations, , Third Edition, The Johns Hopkins University Press, Baltimore
dc.descriptionJones, M.T., Plassmann, P.E., An improved Incomplete Cholesky Factorization (1995) ACM Trans on Math Software, 21 (1), pp. 5-17
dc.descriptionLustig, I.J., Marsten, R.E., Shanno, D.F., On Implementing Mehrotra's Predictor-Corrector Interior Point Method for Linear Programming (1990) TR SOR, pp. 03-90
dc.descriptionMehrotra, S., On the Implementation of a Primal-Dual Interior Point Method (1992) SIAM Journal on Optimization, 2 (4), pp. 575-601
dc.descriptionMehrotra, S., Implementations of Affine Scaling Methods: Approximate Solutions of Systems of Linear Equations Using Preconditioned Conjugate Gradient Methods (1992) ORSA Journal on Computing, 4 (2), pp. 103-118
dc.descriptionMonteiro, R.D.C., Ilan, A.D.L.E.R., Resende, M.G.C., A Polynomial-time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and its Power Series Extension (1990) Mathematics of Operations Research, 15, pp. 191-214
dc.descriptionOliveira, A.R.L., Sorensen, D.C., A new class of preconditioners for large-scale linear systems from interior point methods for linear programming (2005) Linear Algebra and its applications, 394, pp. 1-24
dc.descriptionPadberg, M., Rijal, M.P., (1996) Location, Scheduling, Design and Integer Programming, , Kluwer Academic, Boston
dc.descriptionWang, W., O'Leary, D.P., Adaptive use of iterative methods in predictor-corrector interior point methods for linear programming (2000) Numerical Algorithms, 25, pp. 387-406
dc.descriptionWright, S.J., (1996) Primal-Dual Interior-Point Methods, , SIAM Publications, SIAM, Philadelphia, PA, USA
dc.languageen
dc.publisher
dc.relationPesquisa Operacional
dc.rightsaberto
dc.sourceScopus
dc.titleHeuristics For Implementation Of A Hybrid Preconditioner For Interior-point Methods
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución