Convergence Analysis of an Inexact Feasible Interior Point Method for Convex Quadratic Programming
Abstract: In this paper we will discuss two variants of an inexact feasible interior point algorithm for convex quadratic programming. We will consider two different neighbourhoods: a (small) one induced by the use of the Euclidean norm which yields a short-step algorithm and a symmetric one induced by the use of the infinity norm which yields a (practical) long-step algorithm. Both algorithms allow for the Newton equation system to be solved inexactly. For both algorithms we will provide conditions for the level of error acceptable in the Newton equation and establish the worst-case complexity results.
Keywords: Inexact Newton Method, Interior Point Algorithms, Linear Programming, Quadratic Programming, Worst-case Complexity Analysis, Matrix-Free Methods.
Category 1: Linear, Cone and Semidefinite Programming
Citation: Technical Report ERGO-12-008, July 25, 2012 School of Mathematics, Edinburgh University
Entry Submitted: 08/29/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|