Numerical Analysis

In this thesis, our main focus is on the design, analysis, and implementation of such algorithms. In particular, we are interested in developing stochastic iterative methods for solving large-scale linear systems, linear feasibility, and linear programming problems.

In this work, we shed light on the so-called Kaczmarz method for solving Linear System (LS) and Linear Feasibility (LF) problems from a optimization point of view. We introduce well-known optimization approaches such as Lagrangian penalty and Augmented Lagrangian in the Randomized Kaczmarz (RK) method. In doing so, we propose two variants of the RK method namely the Randomized Penalty Kacmarz (RPK) method and Randomized Augmented Kacmarz (RAK) method.

In this work, we first propose a Stochastic Steepest Descent (SSD) framework that connects SP methods with the well-known Steepest Descent (SD) method for solving positive-definite linear system of equations. We then introduce two greedy sampling strategies in the SSD framework that we generalize the existing sampling rules into one framework and develop an efficient version of SP methods. Furthermore, we incorporated the Polyak momentum technique into the SSD method to accelerate the resulting algorithms.