Scribd
Upload
10 views3 pages

Conjugate Gradient Optimization Python Code

The Conjugate Gradient (CG) method is an efficient iterative algorithm for solving linear equations with symmetric positive-definite matrices and for optimizing unconstrained nonlinear functions. The document provides a detailed implementation of the Linear CG algorithm from scratch, as well as examples using the SciPy library for both linear systems and nonlinear optimization. Key mathematical concepts include the orthogonality of residuals and the conjugacy of search directions, with specific use cases for large, sparse systems and SPD matrices.

Uploaded by

asiaworld0234
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views3 pages

Conjugate Gradient Optimization Python Code

The Conjugate Gradient (CG) method is an efficient iterative algorithm for solving linear equations with symmetric positive-definite matrices and for optimizing unconstrained nonlinear functions. The document provides a detailed implementation of the Linear CG algorithm from scratch, as well as examples using the SciPy library for both linear systems and nonlinear optimization. Key mathematical concepts include the orthogonality of residuals and the conjugacy of search directions, with specific use cases for large, sparse systems and SPD matrices.

Uploaded by

asiaworld0234
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

The Conjugate Gradient (CG) method is an iterative algorithm used primarily for solving

systems of linear equations where the matrix is symmetric and positive-definite, or for optimizing
unconstrained nonlinear functions.
Below is a clean, "from-scratch" implementation of the Linear CG algorithm, followed by how
you would typically do it using the standard scipy library.

1. Scratch Implementation (Linear CG)


This version solves the problem Ax = b. It is much more efficient than gradient descent because
each search direction is "conjugate" to the previous ones, meaning it doesn't undo the progress
made in earlier steps.
import numpy as np​
​
def conjugate_gradient(A, b, x0=None, tol=1e-10, max_iter=1000):​
"""​
Solves Ax = b using the Conjugate Gradient method.​
​
Parameters:​
A: Symmetric, positive-definite matrix​
b: Right-hand side vector​
x0: Initial guess (defaults to zeros)​
"""​
n = len(b)​
if x0 is None:​
x = [Link](n)​
else:​
x = x0​
​
# Initial residual​
r = b - [Link](A, x)​
# Initial search direction​
p = [Link]()​
rs_old = [Link](r, r)​
​
for i in range(max_iter):​
Ap = [Link](A, p)​
​
# Step size alpha​
alpha = rs_old / [Link](p, Ap)​
​
# Update solution and residual​
x = x + alpha * p​
r = r - alpha * Ap​
​
rs_new = [Link](r, r)​
​
# Check convergence​
if [Link](rs_new) < tol:​
print(f"Converged in {i+1} iterations.")​
break​
​
# Compute beta for the next conjugate direction​
beta = rs_new / rs_old​
p = r + beta * p​
rs_old = rs_new​
​
return x​
​
# --- Example Usage ---​
A = [Link]([[4, 1], [1, 3]])​
b = [Link]([1, 2])​
​
x_sol = conjugate_gradient(A, b)​
print("Solution:", x_sol)​

2. Using SciPy (The "Pro" Way)


For production or complex research, you should use [Link] or [Link]. These
are highly optimized and handle edge cases (like sparse matrices) much better.

For Linear Systems (Ax=b):


from [Link] import cg​
​
# A and b from the previous example​
x_sol, exit_code = cg(A, b)​
print("SciPy Linear CG Solution:", x_sol)​

For Nonlinear Optimization:


If you want to minimize a general function f(x) using the Conjugate Gradient method (specifically
the Polak-Ribière or Fletcher-Reeves variations):
from [Link] import minimize​
​
def objective(x):​
return (x[0] - 3)**2 + (x[1] - 5)**2​
​
x0 = [0, 0]​
# 'CG' specifies the nonlinear conjugate gradient algorithm​
res = minimize(objective, x0, method='CG')​
​
print("Nonlinear CG Result:", res.x)​
Key Mathematical Logic
The power of CG lies in the orthogonality of the residuals and the A-orthogonality (conjugacy) of
the search directions.
●​ Alpha (\alpha): Minimizes the function along the current search direction p_k.
●​ Beta (\beta): Ensures the new search direction is conjugate to all previous directions.

When should you use this?


●​ Large, Sparse Systems: When A is too big to invert but you can compute the product Ax
quickly.
●​ Symmetric Positive Definite (SPD) Matrices: CG is strictly for SPD matrices. If your
matrix isn't symmetric, look into BiCGSTAB or GMRES.

You might also like