Preconditioning Subspace Quasi-Newton Method for Large Scale Unconstrained Optimization
Subspace quasi-Newton (SQN) method has been widely used in large scale unconstrained optimization problem. Its popularity is due to the fact that this method can construct subproblems in low dimensions so that the storage requirement as well as the computation cost can be reduced. Besides of this, i...
Saved in:
Main Author: | |
---|---|
Format: | Thesis |
Language: | English |
Published: |
2011
|
Subjects: | |
Online Access: | http://psasir.upm.edu.my/id/eprint/20374/1/IPM_2011_12__ir.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
id |
my-upm-ir.20374 |
---|---|
record_format |
uketd_dc |
spelling |
my-upm-ir.203742022-01-26T04:10:54Z Preconditioning Subspace Quasi-Newton Method for Large Scale Unconstrained Optimization 2011-11 Sim, Hong Sen Subspace quasi-Newton (SQN) method has been widely used in large scale unconstrained optimization problem. Its popularity is due to the fact that this method can construct subproblems in low dimensions so that the storage requirement as well as the computation cost can be reduced. Besides of this, it also can offer a possible way to handle large scale optimization problems and yet it has vast ap- plications in almost every branch of science and technology such as tomography, signal and image deionizing with Basis Pursuit, pattern recognition with Support Vector Machine, and many others. This method can be implemented extremely fast when the objective function is a combination of mappings with computationally cheap non-linear functions for example, quadratics functions. However, the main drawback of the SQN method is that it can be very slow on certain type of nonlinear problem such as ill-conditioned problems. Thus, the focus of this thesis is to overcome this deficiency via preconditioning on the SQN method. In practise, preconditioners can be often adopted to speed up the convergence of the quasi-Newton methods. Hence, we propose a preconditioned SQN method which is generally more effective than the SQN method. For this purpose, we construct a preconditioner which is computationally cheap and is a good approximation to the actual Hessian since the evaluation of actual Hessian is considered as impractical and costly. In order to do this, we propose to use a diagonal updating matrix that has been derived based on the weak quasi-Newton relation instead of using the identity matrix to approximate the initial inverse Hessian. Numerical experiments are performed on quadratics test problems to compare the efficiency and performance of the preconditioned SQN method with the standard SQN method. Our computational results show that the proposed preconditioned SQN method performs better than SQN method that without preconditioning. In addition, the convergence of this method is also presented. Finally, some possible future extensions are to be given to conclude this thesis. Newton-Raphson method Mathematical optimization 2011-11 Thesis http://psasir.upm.edu.my/id/eprint/20374/ http://psasir.upm.edu.my/id/eprint/20374/1/IPM_2011_12__ir.pdf application/pdf en public masters Universiti Putra Malaysia Newton-Raphson method Mathematical optimization Institute for Mathematical Research |
institution |
Universiti Putra Malaysia |
collection |
PSAS Institutional Repository |
language |
English |
topic |
Newton-Raphson method Mathematical optimization |
spellingShingle |
Newton-Raphson method Mathematical optimization Sim, Hong Sen Preconditioning Subspace Quasi-Newton Method for Large Scale Unconstrained Optimization |
description |
Subspace quasi-Newton (SQN) method has been widely used in large scale unconstrained optimization problem. Its popularity is due to the fact that this method can construct subproblems in low dimensions so that the storage requirement as well as the computation cost can be reduced. Besides of this, it also can offer a possible way to handle large scale optimization problems and yet it has vast ap- plications in almost every branch of science and technology such as tomography, signal and image deionizing with Basis Pursuit, pattern recognition with Support Vector Machine, and many others. This method can be implemented extremely fast when the objective function is a combination of mappings with computationally cheap non-linear functions for example, quadratics functions. However, the main drawback of the SQN method is that it can be very slow on certain type of nonlinear problem such as ill-conditioned problems. Thus, the focus of this thesis is to overcome this deficiency via preconditioning on the SQN method. In practise, preconditioners can be often adopted to speed up the convergence of the quasi-Newton methods. Hence, we propose a preconditioned SQN method which is generally more effective than the SQN method. For this purpose, we construct a preconditioner which is computationally cheap and is a good approximation to the actual Hessian since the evaluation of actual Hessian is considered as impractical and costly. In order to do this, we propose to use a diagonal updating matrix that has been derived based on the weak quasi-Newton relation instead of using the identity matrix to approximate the initial inverse Hessian. Numerical experiments are performed on quadratics test problems to compare the efficiency and performance of the preconditioned SQN method with the standard SQN method. Our computational results show that the proposed preconditioned SQN method performs better than SQN method that without preconditioning. In addition, the convergence of this method is also presented. Finally, some possible future extensions are to be given to conclude this thesis. |
format |
Thesis |
qualification_level |
Master's degree |
author |
Sim, Hong Sen |
author_facet |
Sim, Hong Sen |
author_sort |
Sim, Hong Sen |
title |
Preconditioning Subspace Quasi-Newton Method for Large Scale Unconstrained Optimization |
title_short |
Preconditioning Subspace Quasi-Newton Method for Large Scale Unconstrained Optimization |
title_full |
Preconditioning Subspace Quasi-Newton Method for Large Scale Unconstrained Optimization |
title_fullStr |
Preconditioning Subspace Quasi-Newton Method for Large Scale Unconstrained Optimization |
title_full_unstemmed |
Preconditioning Subspace Quasi-Newton Method for Large Scale Unconstrained Optimization |
title_sort |
preconditioning subspace quasi-newton method for large scale unconstrained optimization |
granting_institution |
Universiti Putra Malaysia |
granting_department |
Institute for Mathematical Research |
publishDate |
2011 |
url |
http://psasir.upm.edu.my/id/eprint/20374/1/IPM_2011_12__ir.pdf |
_version_ |
1747811466807869440 |