Semester 2

The current module deals with  two aspects of optimization. On the one hand,  students are equipped with skills in combinatorial optimization problems including mathematical programming with discrete (Integer or Boolean) variables. Cutting-plane and branch and bound algorithms are described along with their convergence properties. The use of meta-heuristics like genetic algorithm, simulated annealing and Tabu search for solving combinatorial optimization problems is also pondered. Finally exact and heuristic methods presented are applied to the traveling salesman and the vehicle routing problems. On the other hand, students are equipped with practical skills in Numerical Optimization problems including lectures in line search methods, Trust region methods, Conjugate gradient methods, Newton and Quasi-Newton methods, theory on constrained optimization and unconstrained optimization methods, interior point methods, and quadratic programming. It is important to note the following milestones for students taking this module.

1)  Having successfully completed this module, students should be able to demonstrate knowledge and understanding of: Methods that are used in Numerical optimization, the combinatorial optimization problems, the use of meta-heuristics like genetic algorithm, the convergence of described algorithms, some real-life applications of combinational optimization, the classification of combinatorial optimization problems into easy (polynomially solvable) problems and hard (NP-complete) problems

2. Having successfully completed this module, students should be able to Solve combinatorial optimization problems,  Apply  the heuristic methods to Dynamic programming, Apply  the heuristic methods to traveling salesman and the vehicle routing problems, Recognize applications of combinatorial optimization, Solve certain combinatorial optimization problems by exact methods, Develop and apply heuristic methods to various optimization problems, such as the traveling salesman and vehicle routing problems, 

3) Having successfully completed this module, students should be able to: Use mathematical programming language (R, Python, etc) in solving, Numerical optimization problems, Combinatorial optimization problems, Optimization problems (heuristic methods).

Introduction to Computational Linear Algebra

Computational linear algebra is the study and application of numerical methods to solve problems in linear algebra. It is a cornerstone of scientific computing, enabling the efficient handling of large-scale systems of equations, matrix computations, and vector operations. This field bridges theoretical mathematics with practical computation, providing the tools needed to tackle complex problems in science, engineering, and technology.

Key Concepts in Computational Linear Algebra

1. Vectors and Matrices

   • Vectors: Represent data points, directions, or quantities in space.
   • Matrices: Describe transformations, systems of linear equations, or large datasets.

2. Core Operations

   • Matrix-Vector Multiplication: Foundational for solving linear systems.
   • Matrix Decomposition: Techniques like LU, QR, and SVD decompose matrices for efficient computation.
   • Eigenvalues and Eigenvectors: Crucial in understanding systems' behaviors and transformations.

3. Numerical Challenges

   • Scalability: Efficient algorithms for handling large datasets.
   • Stability: Managing errors from finite precision in computer arithmetic.
   • Sparsity: Exploiting matrix structures to save computation and memory.

Importance of Computational Linear Algebra

1. Foundational in Modern Applications

   • Machine learning, computer vision, and natural language processing.
   • Simulations in physics, chemistry, and biology.
   • Optimization problems in economics, logistics, and AI.

2. Efficiency and Feasibility

   • Allows the solution of problems that are computationally intractable using classical methods.
   • Handles high-dimensional datasets and large-scale simulations.

3. Cross-Disciplinary Relevance

   • Provides a universal language and tools for various scientific disciplines.

Examples of Applications

1. Image Processing:

   • Compression algorithms (e.g., JPEG) use Singular Value Decomposition (SVD).
   • Edge detection and filtering rely on convolution operations modeled as matrix multiplication.

2. Machine Learning:

   • Training neural networks involves gradient descent, matrix operations, and solving linear systems.
   • Dimensionality reduction techniques like PCA are matrix-based.

3. Scientific Simulations:

   • Simulating weather patterns or fluid flow requires solving large systems of linear equations.

Tools and Libraries

1. Programming Languages: Python, MATLAB, Julia, and C++.
2. Libraries:
   • NumPy/SciPy: Python libraries for numerical computation.
   • BLAS/LAPACK: Low-level libraries for efficient matrix computations.
   • TensorFlow/PyTorch: Frameworks for machine learning that rely on linear algebra.

Why Study Computational Linear Algebra?

Understanding computational linear algebra empowers one to:

• Develop efficient algorithms for large-scale data problems.
• Grasp the mathematical foundations of modern technologies.
• Innovate in areas like AI, simulation, and optimization.

Facilitator: Dr. Leon Fidele Ruganzu Uwimbabazi: Email ruganzu01@gmail.com, l.uwimbazi@ur.ac.rw, Phone:0784878618