A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Conjugate Gradient Method: <s> An iterative algorithm is given for solving a system Ax=k of n linear equations in n unknowns. The solution is given in n steps. It is shown that this method is a special case of a very general method which also includes Gaussian elimination. These general algorithms are essentially algorithms for finding an n dimensional ellipsoid. Connections are made with the theory of orthogonal polynomials and continued fractions. <s> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Conjugate Gradient Method: <s> The Conjugate Gradient Method is the most prominent iterative method for solving sparse systems of linear equations. Unfortunately, many textbook treatments of the topic are written so that even their own authors would be mystified, if they bothered to read their own writing. For this reason, an understanding of the method has been reserved for the elite brilliant few who have painstakingly decoded the mumblings of their forebears. Nevertheless, the Conjugate Gradient Method is a composite of simple, elegant ideas that almost anyone can understand. Of course, a reader as intelligent as yourself will learn them almost effortlessly. The idea of quadratic forms is introduced and used to derive the methods of Steepest Descent, Conjugate Directions, and Conjugate Gradients. Eigenvectors are explained and used to examine the convergence of the Jacobi Method, Steepest Descent, and Conjugate Gradients. Other topics include preconditioning and the nonlinear Conjugate Gradient Method. I have taken pains to make this article easy to read. Sixty-two illustrations are provided. Dense prose is avoided. Concepts are explained in several different ways. Most equations are coupled with an intuitive interpretation. <s> BIB002
The conjugate gradient (CG) approach is a very interesting optimization method, which is one of the most effective methods for solving largescale linear systems of equations. It can also be used to solve nonlinear optimization problems  . As we know, the first-order methods are simple but have a slow convergence speed, and the second-order methods need a lot of resources. Conjugate gradient optimization is an intermediate algorithm, which can only utilize the first-order information for some problems but ensures the convergence speed like high-order methods. Early in the 1960s, a conjugate gradient method for solving a linear system was proposed, which is an alternative to Gaussian elimination BIB001 . Then in 1964, the conjugate gradient method was extended to handle nonlinear optimization for general functions  . For years, many different algorithms have been presented based on this method, some of which have been widely used in practice. The main features of these algorithms are that they have faster convergence speed than steepest descent. Next, we describe the conjugate gradient methods. Consider a linear system, where A is a n × n symmetric, positive-definite matrix. The matrix A and vector b are known, and we need to solve the value of θ. The problem (35) can also be considered as an optimization problem that minimizes the quadratic positive definite function, The above two equations have an identical unique solution. It enables us to regard the conjugate gradient as a method for solving optimization problems. The gradient of F (θ) can be obtained by simple calculation, and it equals the residual of the linear system  : Definition 1: Conjugate: Given an n × n symmetric positive-definite matrix A, two non-zero vector d i , d j are conjugate with respect to A if A set of non-zero vector {d 1 , d 2 , d 3 , ...., d n } is said to be conjugate respect to A if any two unequal vectors are conjugate with respect to A  . Next, we introduce the detailed derivation of the conjugate gradient method. θ 0 is a starting point, {d t } n−1 t=1 is a set of conjugate directions. In general, one can generate the update sequence {θ 1 , θ 2 , ...., θ n } by a iteration formula: The step size η t can be obtained by a linear search, which means choosing η t to minimize the object function f (·) along θ t +η t d t . After some calculations (more details in  , BIB002 ), the update formula of η t is The search direction d t obtained by a linear combination of the negative residual and the previous search direction, where r t+1 can be updated by r t+1 = r t +η t Ad t . The scalar β t is the update parameter, which can be determined by satisfying the requirement that d t and d t−1 are conjugate with respect to A, i.e., d  After several derivations of the above formula according to  , the simplified version of β t is The CG method, has a graceful property that generating a new vector d t only using the previous vector d t−1 , which does not need to know all the previous The linear conjugate gradient algorithm is shown in Algorithm 2.