Back to search

Georgia Southern University

Path-Following Interior Point Method With Improved Iteration Bounds For Monotone Linear Complementarity Problem

Abstract

dc:description.abstract

In this thesis, we present a path-following interior point method (IPM) algorithm to solve a monotone linear complementarity problem (LCP). A new eligible kernel function will be used to help improve the theoretical iteration bounds for the path-following IPM algorithm. IPM algorithms have two types of updates called large-step updates and small-step updates. Small-step updates have a better theoretical iteration bound than large-step updates, even though large-step updates perform better in practice than small-step updates. It is shown in this thesis, that using this new eligible kernel function will lead to the small-step and large-step updates to have the same theoretical iteration bound, matching the best know iteration bound. These results help close the ironic gap between theoretical complexity and practical use of path-following IPMs.

Degree

thesis:*
Name thesis:degree_name
Master of Science in Mathematics (M.S.)
Level thesis:degree_level
Thesis (restricted to Georgia Southern)
Discipline thesis:degree_discipline
Department of Mathematical Sciences

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Williams, Tiffani
Contributors dc:contributor
  • Hua Wang
  • Ionut Iacob

Subjects

dc:subject × 5

Rights

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.georgiasouthern.edu/etd/2153

Chain of custody

source
Harvested from
Georgia Southern University
Base URL
digitalcommons.georgiasouthern.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Williams, Tiffani. Path-Following Interior Point Method With Improved Iteration Bounds For Monotone Linear Complementarity Problem. Thesis (restricted to Georgia Southern) thesis, https://digitalcommons.georgiasouthern.edu/etd/2153