| Quadratic Programming (QP) has been an increasingly important topic in mathematical programming since the 1980s, especially with the rise in popularity of nonlinear programming algorithms, which require the solution of a QP problem to determine the search direction at each iteration. Recently, with the advent of Karmakar's projective algorithm for linear problems, interior point methods for QP have attracted more attention than others.;The early interior point algorithms required a feasible starting point that satisfies all the constraints. Recently, several algorithms, which are so-called "infeasible" interior point algorithms, have been proposed. For these infeasible interior point algorithms the starting point is positive but not necessarily feasible for the constraints. There are several advantages for the infeasible interior point methods; for example, there is no longer a need to use big-M or an extra phase to find the feasible starting point.;In this dissertation, we investigate three infeasible path-following algorithms (a class of interior point methods) for convex linearly-constrained QP problems, namely, Newton algorithm, the Newton-Central algorithm, and the Monomial algorithm. The last two algorithms are shown to follow a path on the complementarity surface. In this dissertation, the convergence for the Newton-Central algorithm is proven by using a so-called "auxiliary sequence." The auxiliary sequence which we construct always satisfies both primal and dual feasibility. Our strategy then is to reduce the gap between the sequence of iterates generated by the Newton-Central and the auxiliary sequence. In addition, we also derive and compare several properties of these three algorithms.;Both separable and nonseparable convex QP problems are used to test the three algorithms. In addition, numerical results are reported for a discretization of obstacle problems (a class of engineering problems), and, using a set of continuous quadratic knapsack test problems, the variability in the computation times is reported for each of these three algorithms. |
