An Efficient Row Reduction Algorithm for Solving Fourier-Constrained Linear Programs Using the Simplex Method

Abstract

This dissertation is meant to explain an algorithm that can increase the efficiency of solving a family of linear programs whose constraints follow a certain pattern using the simplex method. We refer to a linear program as Fourier-constrained if the constraint set is comprised of discrete Fourier transforms (DFT) of the variables, in addition to their upper and lower bound.

In this paper we look at the specific case in which the Fourier transform is 2-dimensional and there is symmetry about the $x-$ and $y-$ axes. This allows the transform to remain real-valued. When the constraints representing the 2D Fourier transform are broken down into two steps using the fast Fourier transform (FFT), the constraint matrix is sparse and the non-zeros form a known pattern within the constraint matrix. As each pivot of the simplex method involves row-reduction of the constraint matrix using Gaussian elimination, the ordering of the variables and constraints determines how many operations are performed. By setting up a system of rules to determine the ordering of rows and columns after each pivot, we can develop a heuristic that reduces the number of pivots and operations needed to solve the problem using the simplex method. We show that there is a statistically significant reduction in average solving time using this heuristic in comparison to generalized simplex method algorithms that do not make assumptions about the locations of non-zeros within the constraints.

Fourier-constrained linear programs are commonplace in real-world optimization problems, as the Fourier transform is used to describe various naturally occurring relations. The main example that we will explore is the design of a telescopic tool known as a shaped pupil, used for planet detection. Because the equation for mapping propagation of light through a telescope is proportional to the DFT, determining a design for the shaped pupil can be reduced to a linear program with Fourier constraints. By comparing the performance of the proposed heuristic to generalized algorithms used to solve sparse and non-sparse representations of this problem, we exemplify the benefits of adopting this row-reduction algorithm.