A modified n-th section line search in conjugate gradient methods for solving unconstrained optimization / Muhammad Imza Fakhri Jinudin

Conjugate Gradient (CG) method are well-known method for solving unconstrained optimization problems. A lot of efforts have been done in order to improve the efficiency of this CG methods. For unconstrained optimization, line search act as a pillar for solving optimization problems. In this research, a new modification of inexact line search in CG methods is proposed. It is based on classical bisection line search method. Generally, bisection method is the easiest method to solve root of a function. Thus, it is an ideal method to employ as a line search in CG methods. This new modification that was proposed by Hayati (2015) is named as n-th section method. However, n-th section method inherits the same behaviour as bisection method which is slow convergence. Thus, a re-modification on n-th section algorithm is conducted to reduce its CPU time per execution. Overall, six line search methods that are employed in CG methods which are classical bisection, 4th section, 6th section, modified bisection, modified 4th section and modified 6th section are compared through performance profile analysis based on number of iterations and CPU times. These line search methods are tested based on six standard optimization test problems. The CG methods used in this research are classical formulas known as Fletcher- Reeves (FR), Polak-Ribiere-Polyak (PRP) and Rivaie-Mustafa-Ismail-Leong (RMIL). All algorithms are written and executed using Maple 16 software. Numerical results show that modified 6th section is the best method in term of number of iterations while modified 4th section is the best based on CPU times. Other than that, the modified version of n-th section line search method has less amount of CPU time allocated to execute CG's algorithm when compared to the original version of n-th section line search method. In a nutshell, modified n-th section line search method is more promises and efficient compared to the classical bisection line search.