COORDINATE DESCENT FOR SOLVING LINEAR PROGRAMS

Abstract

Linear programming has ubiquitous applications in fields ranging from finance to engineering. Classical algorithms, such as simplex and interior point methods, are efficient for solving linear programs of moderate dimensions but face significant challenges as the dimensions of the problem grow. This capstone project addresses such challenges by proposing a coordinate descent algorithm that optimizes an unconstrained problem with quadratic penalty terms in the objective function and an additional regularization term that penalizes infeasible solutions. We will consider both the theoretical and numerical properties of the algorithm. The algorithm will be tested on randomly generated linear programs to evaluate its computational performance.