Optimization Online


Convergence Analysis of an Inexact Feasible Interior Point Method for Convex Quadratic Programming

Jacek Gondzio(J.Gondzio***at***ed.ac.uk)

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

Download: [PDF]

Entry Submitted: 08/29/2012
Entry Accepted: 08/29/2012
Entry Last Modified: 08/29/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society