1,721,076 research outputs found
Planar-Conjugate Gradient algorithm for Large Scale Unconstrained Optimization, Part 2: Application
No full textIn this paper, we present a new conjugate gradient (CG) based algorithm in the class of planar conjugate gradient methods. These methods aim at solving systems of linear equations whose coefficient matrix is indefinite and nonsingular. This is the case where the application of the standard CG algorithm by Hestenes and Stiefel (Ref. 1) may fail, due to a possible division by zero. We give a complete proof of global convergence for a new planar method endowed with a general structure; furthermore, we describe some important features of our planar algorithm, which will be used within the optimization framework of the companion paper (Part 2, Ref. 2). Here, preliminary numerical results are reported
Lanczos-Conjugate Gradient method and pseudoinverse computation, in unconstrained optimization
No full textThis paper extends some theoretical properties of the Conjugate Gradient-type method FLR
[Fas05], for iteratively solving indefinite linear systems of equations. The latter algorithm is a
generalization of the Conjugate Gradient (CG) by Hestenes and Stiefel [HS52].
On one hand, here we carry out a complete relationship between algorithm FLR and the Lanczos
process, in case of indefinite and possibly singular matrices. On the other hand we develop
simple theoretical results for algorithm FLR, in order to construct an approximation of the Moore-Penrose pseudoinverse of an indefinite matrix. Our approach supplies theory for applications within nonconvex optimization
Uso delle Direzioni Coniugate negli algoritmi per l'Ottimizzazione Non Vincolata a grande dimensione
Full text linkConjugate Gradient (CG)-type Method for the Solution of Newton's equation within Optimization Frameworks
No full textA conjugate gradient (CG)-type algorithm CG Plan is introduced for calculating an approximate solution of Newton’s
equation within large-scale optimization frameworks. The approximate solution must satisfy suitable properties to
ensure global convergence. In practice, the CG algorithm is widely used, but it is not suitable when the Hessian matrix
is indefinite, as it can stop prematurely. CG Plan is a symmetric variant of the composite step Bi-CG method of Bank
and Chan, suitably adapted for optimization problems. It is an alternative to CG that copes with the indefinite case.
We showconvergence for CG Plan, then prove that the practical implementation always provides a gradient related
direction within a truncated Newton method (algorithm TN_Plan). Some preliminary numerical results support the
theory
Notes on a 3-term Conjugacy Recurrence forthe Iterative Solution of Symmetric Linear Systems
No full textWe consider a 3-term recurrence, namely CG_2step, for the iterative solution of symmetric linear systems. The new algorithm generates conjugate directions and extends some standard theoretical properties of the Conjugate Gradient (CG) method [10]. We prove the finite convergence of CG_2step, and we provide some error analysis.
Then, we introduce preconditioning for CG_2step, and we prove that standard error bounds for the CG also hold for our proposal
Planar-Conjugate Gradient algorithm for Large Scale Unconstrained Optimization, Part I: Theory
No full textTechnical Report INSEAN 2004-015, Italy
Krylov-Subspace Methods for Quadratic Hypersurfaces: A Grossone–based Perspective
No full textWe study the role of the recently introduced infinite number grossone, to deal with two renowned Krylov-subspace methods for symmetric (possibly indefinite) linear systems. We preliminarily explore the relationship between the Conjugate Gradient (CG) method and the Lanczos process, along with their specific role of yielding tridiagonal matrices which retain large information on the original linear system matrix. Then, we show that on one hand there is not immediate evidence of an advantage from embedding grossone within the Lanczos process. On the other hand, coupling the CG with grossone shows clear theoretical improvements. Furthermore, reformulating the CG iteration through a grossone-based framework allows to encompass also a certain number of Krylov-subspace methods relying on conjugacy among vectors. The last generalization remarkably justifies the use of a grossone-based reformulation of the CG to solve also indefinite linear systems. Finally, pairing the CG with the algebra of grossone easily provides relevant geometric properties of quadratic hypersurfaces
A framework of conjugate direction methods for symmetric linear systems in optimization
Full text linkIn this paper we introduce a parameter dependent class of Krylov-based methods, namely CD, for the solution of symmetric linear systems. We give evidence that in our
proposal we generate sequences of conjugate directions, extending some properties of the standard Conjugate Gradient (CG) method, in order to preserve the conjugacy. For specific values of the parameters in our framework we obtain schemes equivalent to both the CG and the scaled-CG. We also prove the finite convergence of the algorithms in CD, and we provide some error analysis. Finally, preconditioning is introduced for CD, and we show
that standard error bounds for the preconditioned CG also hold for the preconditioned CD
A Class of Preconditioners for Large Indefinite Linear Systems, as by-product of Krylov subspace Methods: Part II
Full text linkIn this paper we consider the parameter dependent class of preconditioners M(a,d,D) defined in the companion paper The latter was constructed by using information from a Krylov subspace method, adopted to solve the large symmetric linear system Ax = b. We first estimate the condition number of the preconditioned matrix M(a,d,D). Then our preconditioners, which are independent of the choice of the Krylov subspace method adopted, proved to be effective also when solving sequences of slowly changing linear systems, in unconstrained optimization and linear algebra frameworks. A numerical experience is provided to give evidence of the performance of M(a,d,D)
Preconditioning Newton–Krylov methods in nonconvex large scale optimization
No full textWe consider an iterative preconditioning technique for large
scale optimization, where the objective function is possibly
non-convex. First, we refer to the solution of a generic indefinite linear system by means of a Krylov subspace method,
and describe the iterative construction of the preconditioner
which does not involve matrices products or matrix storage. The set of directions generated by the Krylov subspace method is also used, as by product, to provide an
approximate inverse of the system matrix. Then, we experience our method within Truncated Newton schemes for
large scale unconstrained optimization, in order to speed
up the solution of the Newton equation. Actually, we use a
Krylov subspace method to approximately solve the Newton equation at current iterate (where the Hessian matrix
is possibly indefinite) and to construct the preconditioner
to be used at the current outer iteration. An extensive numerical experience show that the preconditioning strategy
proposed leads to a significant reduction of the overall inner
iterations on most of the test problems considered
- …
