Minimum L∞ norm solutions to finite dimensional algebraic underdetermined linear systems
Date
2015-02-04
Authors
Earle, Adam Christopher
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A new method of solution to the problem of nding the minimum `1 norm solution to an
algebraic underdetermined linear system is developed. The new method is a geometrically
clear, primal method. Like some existing methods, the new method can be logically divided
into two parts. A number of new techniques are suggested in this
part of the algorithm, including an iterative ascent procedure.
In the second part of the solution process, the particular solution obtained in the rst part
is iteratively improved. We have developed a number of new techniques here corresponding
to both single and multi-element exchange procedures. Central to the new method is the
development of descent criteria for a direction vector, and the stopping condition.The performance of
our algorithm is also compared with two well-known methods from the literature. Our
method is shown to be much superior to these well known-methods with respect to both
the number of iterations and the wall-clock time required. The iterative computational
complexity of the new method also compares favourably with most well-known methods.
A geometric heuristic is developed for initial active constraint set selection and a number of
theoretical results are given. The heuristic stands to be much more valuable if the results presented herein can be generalised
Description
A dissertation submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in fulfilment of requirements for the degree of Master of Science. September 2014.