| Summary: | Quasi Newton (QN) method is one of the commonly used tools in solving
unconstrained optimization problems. One of the main advantages of QN method is its
superlinear convergence rate which is very fast. However, this method often yields
high number of CPU time when used for solving large scale problems due to the
presence of Hessian matrix in its formula which has high memory requirement.
Moreover, the convergence property of QN algorithm is local, hence the optimal point
obtained might not be the most minimum point for the tested problem. In this study,
the QN method is combined with the conjugate gradient (CG) method to produce new
hybrid search directions. The CG method is chosen due to its global convergence
properties and its low memory requirement. These properties enable the CO method to
solve large scale problems with better efficiency. To overcome these problems, a new
CG method for solving unconstrained problems has been proposed. They are denoted
as WAM (Wan, Asrul and Mustafa). This WAM method is then combined with the
QN method to produce two new hybrid search directions which are QN - W AM and
QN-WAM+. The Davidon-Fletcher-Powell (DFP) and Broyden-Fletcher-Goldfarb
Shanno (BFGS) update formulas are used to determine the approximate of the inverse
Hessian for each of the new hybrid QN-WAM and QN-WAM+ methods. These new
methods are referred as the DFP-WAM, BFGS-WAM, DFP-WAM+ and BFGS
WAM+ methods. They are all tested along with the original DFP and BFGS methods
by using twenty-six standard optimization functions from small scale to large scale.
For each functions, four initial points are selected, starting from a point near the
optimal point to a point located far from it. All of the computations are conducted
through Matlab software. The effectiveness of the proposed search directions is
analyzed by using performance profile introduced by Dolan and More. Based on the
numerical test results, the new algorithms are more efficient compared with the
ordinary DFP and BFGS methods in terms of number of iterations and CPU time. In
general, the proposed algorithms show the highest percentage of problems solved. The
hybrid DFP- W AM and BFGS-W AM methods solve 96.10% and 97.27% of the tested
problem respectively while the DFP- W AM+ and BFGS- W AM+ methods successfully
solve 100% of the tested problems. In comparison, the DFP method and the BFGS
method only solve 93.36% and 93.75% of the tested problems, respectively. The new
hybrid methods with DFP and BFGS update have also been proven to fulfil sufficient
descent condition and possess global convergence properties. All the proposed
methods have shown the best efficiency in solving the selected optimization test
functions compared with the other tested QN methods. They are also theoretically
proven to be globally convergent.
|
|---|