60 research outputs found
An investigation of stochastic trust-region based algorithms for finite-sum minimization
No full text
Updating constraint preconditioners for KKT systems in quadratic programming via low-rank corrections
No full textThis work focuses on the iterative solution of sequences of KKT linear systems arising in interior point methods applied to large convex quadratic programming problems. This task is the computational core of the interior point procedure, and an efficient preconditioning strategy is crucial for the efficiency of the overall method. Constraint preconditioners are very effective in this context; nevertheless, their computation may be very expensive for large-scale problems, and resorting to approximations of them may be convenient. Here we propose a procedure for building inexact constraint preconditioners by updating a seed constraint preconditioner computed for a KKT matrix at a previous interior point iteration. These updates are obtained through low-rank corrections of the Schur complement of the (1,1) block of the seed preconditioner. The updated preconditioners are analyzed both theoretically and computationally. The results obtained show that our updating procedure, coupled with an adaptive strategy for determining whether to reinitialize or update the preconditioner, can enhance the performance of interior point methods on large problems
On the update of constraint preconditioners for regularized KKT systems
No full textWe address the problem of preconditioning sequences of regularized KKT systems, such as those arising in interior point methods for convex quadratic programming. In this case, constraint preconditioners (CPs) are very effective and widely used; however, when solving large-scale problems, the computational cost for their factorization may be high, and techniques for approximating them appear as a convenient alternative. Here, given a block LDLT factorization of the CP associated with a KKT matrix of the sequence, called seed matrix, we present a technique for updating the factorization and building inexact CPs for subsequent matrices of the sequence. We have recently proposed an updating procedure that performs a low-rank correction of the Schur complement of the (1,1) block of the CP for the seed matrix. Now we focus on KKT sequences with nonzero (2,2) blocks and make a step further, by enriching the low-rank correction of the Schur complement by an additional cheap update. The latter update takes into account information not included in the former one and expressed as a diagonal modification of the low-rank correction. Theoretical results and numerical experiments show that the new strategy can be more effective than the procedure based on the low-rank modification alone
A preconditioning framework for sequences of diagonally modified linear systems arising in optimization
No full textWe propose a framework for building preconditioners for sequences of linear systems of the form (A+Δk)xk = bk, where A is symmetric positive semidefinite and Δk is diagonal positive semidefinite. Such sequences arise in several optimization methods, e.g., in affine-scaling methods for bound-constrained convex quadratic programming and bound-constrained linear least squares, as well as in trust-region and overestimation methods for convex unconstrained optimization problems and nonlinear least squares. For all the matrices of a sequence, the preconditioners are obtained by updating any preconditioner for A available in the LDL(Table Presented) form. The preconditioners in the framework satisfy the natural requirement of being effective on slowly varying sequences; furthermore, under an additional property they are also able to cluster eigenvalues of the preconditioned matrix when some entries of Δk are sufficiently large. We present two low-cost preconditioners sharing the above-mentioned properties and evaluate them on sequences of linear systems generated by the reflective Newton method applied to bound-constrained convex quadratic programming problems and on sequences arising in solving nonlinear least-squares problems with the regularized Euclidean residual method. The results of the numerical experiments show the effectiveness of these preconditioners. © 2012 Society for Industrial and Applied Mathematics
On the update of constraint preconditioners for regularized KKT systems
No full textWe address the problem of preconditioning sequences of regularized KKT systems, such as those arising in interior point methods for convex quadratic programming. In this case, constraint preconditioners (CPs) are very effective and widely used; however, when solving large-scale problems, the computational cost for their factorization may be high, and techniques for approximating them appear as a convenient alternative. Here, given a block  LDL^T factorization of the CP associated with a KKT matrix of the sequence, called seed matrix, we present a technique for updating the factorization and building inexact CPs for subsequent matrices of the sequence. We have recently proposed an updating procedure that performs a low-rank correction of the Schur complement of the (1,1) block of the CP for the seed matrix. Now we focus on KKT sequences with nonzero (2,2) blocks and make a step further, by enriching the low- rank correction of the Schur complement by an additional cheap update. The latter update takes into account information not included in the former one and expressed as a diagonal modification of the low- rank correction. Theoretical results and numerical experiments show that the new strategy can be more effective than the procedure based on the low-rank modification alone
Efficient preconditioner updates for shifted linear systems
No full textWe present a technique for building effective and low cost preconditioners for sequences of shifted linear systems (A + αI) x_α = b, where A is symmetric positive definite and α > 0. This technique updates a preconditioner for A, available in the form of an LDL^T factorization, by modifying only the nonzero entries of the L factor in such a way that the resulting preconditioner mimics the diagonal of the shifted matrix and reproduces its overall behavior. This approach is supported by a theoretical analysis as well as by numerical experiments, showing that it works efficiently for a broad range of values of α
Updating constraint preconditioners for KKT systems in quadratic programming via low-rank corrections
No full textThis work focuses on the iterative solution of sequences of KKT linear systems arising in interior point methods applied to large convex quadratic programming problems. This task is the computational core of the interior point procedure, and an efficient preconditioning strategy is crucial for the efficiency of the overall method. Constraint preconditioners are very effective in this context; nevertheless, their computation may be very expensive for large-scale problems, and resorting to approximations of them may be convenient. Here we propose a procedure for building inexact constraint preconditioners by updating a seed constraint preconditioner computed for a KKT matrix at a previous interior point iteration. These updates are obtained through low-rank corrections of the Schur complement of the (1,1) block of the seed preconditioner. The updated preconditioners are analyzed both theoretically and computationally. The results obtained show that our updating procedure, coupled with an adaptive strategy for determining whether to reinitialize or update the preconditioner, can enhance the performance of interior point methods on large problems
Efficient Preconditioner Updates for Shifted Linear Systems
No full textWe present a technique for building effective and low cost preconditioners for sequences of shifted linear systems , where A is symmetric positive definite and alpha > 0. This technique updates a preconditioner for A, available in the form of an factorization, by modifying only the nonzero entries of the L factor in such a way that the resulting preconditioner mimics the diagonal of the shifted matrix and reproduces its overall behavior. This approach is supported by a theoretical analysis as well as by numerical experiments, showing that it works efficiently for a broad range of values of
A Preconditioning Framework for Sequences of Diagonally Modified Linear Systems Arising in Optimization
No full textWe propose a framework for building preconditioners for sequences of linear systems of the form , where is symmetric positive semidefinite and is diagonal positive semidefinite. Such sequences arise in several optimization methods, e.g., in affine-scaling methods for bound-constrained convex quadratic programming and bound-constrained linear least squares, as well as in trust-region and overestimation methods for convex unconstrained optimization problems and nonlinear least squares. For all the matrices of a sequence, the preconditioners are obtained by updating any preconditioner for available in the form. The preconditioners in the framework satisfy the natural requirement of being effective on slowly varying sequences; furthermore, under an additional property they are also able to cluster eigenvalues of the preconditioned matrix when some entries of are sufficiently large. We present two low-cost preconditioners sharing the above-mentioned properties and evaluate them on sequences of linear systems generated by the reflective Newton method applied to bound-constrained convex quadratic programming problems and on sequences arising in solving nonlinear least-squares problems with the regularized Euclidean residual method. The results of the numerical experiments show the effectiveness of these preconditioners
- …
