Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

The Conjugate Gradients Method (CG)

In course

MATH-512: Optimization on manifolds

We develop, analyze and implement numerical algorithms to solve optimization problems of the form min f(x) where x is a point on a smooth manifold. To this end, we first study differential and Riemannian geometry (with a focus dictated by computational con ...

Description

This lecture introduces the Conjugate Gradients method, a technique for solving linear systems with a positive definite operator. Starting with the definition and properties of CG, the instructor explains the iterative process, the computation of residuals, and the concept of conjugate directions. The lecture covers the convergence properties and the necessary conditions for quadratic convergence, emphasizing the importance of linear independence among the conjugate directions. The instructor also discusses the representation of Hessians and the Riemannian distance on a manifold, providing insights into the practical implementation of CG.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructor

Nicolas Boumal

Official source

Related concepts (32)

System of linear equations

In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables. For example, is a system of three equations in the three variables x, y, z. A solution to a linear system is an assignment of values to the variables such that all the equations are simultaneously satisfied. A solution to the system above is given by the ordered triple since it makes all three equations valid. The word "system" indicates that the equations should be considered collectively, rather than individually.

Iterative method

In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the n-th approximation is derived from the previous ones. A specific implementation with termination criteria for a given iterative method like gradient descent, hill climbing, Newton's method, or quasi-Newton methods like BFGS, is an algorithm of the iterative method.

Linear algebra

Linear algebra is the branch of mathematics concerning linear equations such as: linear maps such as: and their representations in vector spaces and through matrices. Linear algebra is central to almost all areas of mathematics. For instance, linear algebra is fundamental in modern presentations of geometry, including for defining basic objects such as lines, planes and rotations. Also, functional analysis, a branch of mathematical analysis, may be viewed as the application of linear algebra to spaces of functions.

Basis (linear algebra)

In mathematics, a set B of vectors in a vector space V is called a basis (: bases) if every element of V may be written in a unique way as a finite linear combination of elements of B. The coefficients of this linear combination are referred to as components or coordinates of the vector with respect to B. The elements of a basis are called . Equivalently, a set B is a basis if its elements are linearly independent and every element of V is a linear combination of elements of B.

Linear independence

In the theory of vector spaces, a set of vectors is said to be if there exists no nontrivial linear combination of the vectors that equals the zero vector. If such a linear combination exists, then the vectors are said to be . These concepts are central to the definition of dimension. A vector space can be of finite dimension or infinite dimension depending on the maximum number of linearly independent vectors. The definition of linear dependence and the ability to determine whether a subset of vectors in a vector space is linearly dependent are central to determining the dimension of a vector space.

Related lectures (49)

Truncated Conjugate Gradients for Trust-Region Subproblem

Explores truncated conjugate gradients for solving the trust-region subproblem in optimization on manifolds efficiently.

Conjugate Gradient Method

Covers the Conjugate Gradient method for solving linear systems efficiently.

Linear Systems: Convergence and Methods

Explores linear systems, convergence, and solving methods with a focus on CPU time and memory requirements.

Computing the Newton Step: GD as a Matrix-Free Way

Explores matrix-based and matrix-free approaches for computing the Newton step in optimization on manifolds.

Momentum methods and nonlinear CG