Interior Point Methods and Kernel Functions of a Linear Programming Problem

In this thesis the Interior -- Point Method (IPM) for Linear Programming problem (LP) that is based on the generic kernel function is considered. The complexity (in terms of iteration bounds) of the algorithm is first analyzed for a class of kernel functions defined by (3-1). This class is fairly general; it includes classical logarithmic kernel function, prototype self-regular kernel function as well as non-self-regular functions, thus it serves as a unifying frame for the analysis of IPM. Historically, most results in the theory of IPM are based on logarithmic kernel functions while other two classes are more recent. They were considered with the intention to improve theoretical and practical performance of IPMs. The complexity results that are obtained match the best known complexity results for these methods. Next, the analysis of the IPM was summarized and performed for three more kernel functions. For two of them we again matched the best known complexity results. The theoretical concepts of IPM were illustrated by basic implementation for the classical logarithmic kernel function and for the parametric kernel function both described in (3-1). Even this basic implementation shows potential for a good performance. Better implementation and more numerical testing would be necessary to draw more definite conclusions. However, that was not the goal of the thesis, the goal was to show that IPM with kernel functions different than classical logarithmic kernel function can have best known theoretical complexity.

Name thesis:degree_name

Master of Science in Mathematics (M.S.)

Level thesis:degree_level

Thesis (open access)

Discipline thesis:degree_discipline

Department of Mathematical Sciences

Year dc:date.available

2009

Author dc:creator

• Tanksley, Latriece Y.

Contributors dc:contributor

• Billur Kaymalcalan
• Scott Kersey
• Yan Wu

• ETD
• Interior point methods
• Linear programming
• Kernel functions
• Algorithms

Repository record dc:identifier

https://digitalcommons.georgiasouthern.edu/etd/650

OAI identifier oai:identifier

oai:digitalcommons.georgiasouthern.edu:etd-1650