  


NewtonKKT InteriorPoint Methods for Indefinite Quadratic Programming
PierreAntoine Absil (absilcsit.fsu.edu) 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.̃seng 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. Keywords: Interiorpoint algorithms, primaldual algorithms, indefinite quadratic programming, NewtonKKT Category 1: Nonlinear Optimization (Quadratic Programming ) Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization ) Citation: September 2004. Revised August 2005 Download: [PDF] Entry Submitted: 09/19/2004 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  