Paper ID sheet UCLINMA2005.134
 Title

NewtonKKT interiorpoint methods for indefinite quadratic programming
 Authors
 P.A. Absil, A. L. Tits
 Abstract

Two interiorpoint algorithms are proposed and analyzed, for the (local)
solution of (possibly) indefinite quadratic programming problems. They are of
the NewtonKKT variety in that (much like in the case of primaldual algorithms
for linear programming) search directions for the `primalÂ´ variables and the
KarushKuhnTucker (KKT) multiplier estimates are components of the Newton (or
quasiNewton) direction for the solution of the equalities in the firstorder
KKT conditions of optimality or a perturbed version of these conditions. Our
algorithms are adapted from previously proposed algorithms for convex quadratic
programming and general nonlinear programming. First, inspired by recent work
by P. Tseng based on a 'primal' affinescaling algorithm (Ã la Dikin)
[J. of Global Optimization, 30 (2004), no 2, 285300], we consider a simple
NewtonKKT affinescaling algorithm. Then, a 'barrier' version
of the same algorithm is considered, which reduces to the affinescaling
version when the barrier parameter is set to zero at every iteration, rather
than to the prescribed value. Global and local quadratic convergence are
proved under nondegeneracy assumptions for both algorithms. Numerical
results on randomly generated problems suggest that the proposed algorithms
may be of great practical interest.
 Key words
 interiorpoint algorithms; primaldual algorithms; indefinite quadratic programming; NewtonKKT
 Status
 Computational Optimization and Applications, Volume 36, Number 1, January, 2007
 Download

[Home]