NewtonKKTqp swMATH ID: 4820 Software Authors: Absil, P.-A.; Tits, André L Description: Newton-KKT interior-point methods for indefinite quadratic programming Two interior-point algorithms are proposed and analyzed, for the (local) solution of (possibly) indefinite quadratic programming problems. They are of the Newton-KKT variety in that (much like in the case of primal-dual algorithms for linear programming) search directions for the “primal” variables and the Karush-Kuhn-Tucker (KKT) multiplier estimates are components of the Newton (or quasi-Newton) direction for the solution of the equalities in the first-order 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” affine-scaling algorithm ( ‘a la Dikin) [J. of Global Optimization, 30 (2004), no. 2, 285-300], we consider a simple Newton-KKT affine-scaling algorithm. Then, a ” barrier ” version of the same algorithm is considered, which reduces to the affine-scaling 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. Homepage: http://www.montefiore.ulg.ac.be/~absil/Publi/indefQP.htm Dependencies: Matlab Keywords: Interior-point algorithms; Primal-dual algorithms; Newton-KKT Related Software: MINQ; Matlab; Ipopt; CPLEX; CUTEr; MINQ8; reducedLP; GALAHAD; LDL; LADEL; CSparse; NETLIB LP Test Set; lobpcg.m; ALGENCAN; QPALM; HPIPM; CUTEst; qpOASES; Mosek; CHOLMOD Cited in: 12 Publications all top 5 Cited by 22 Authors 3 Tits, André Leon 2 Absil, Pierre-Antoine 1 Adjé, Assalé 1 Bentobache, Mohand 1 Bomze, Immanuel M. 1 Burer, Samuel 1 Flöry, Simon 1 Hermans, Ben 1 Huyer, Waltraud 1 Jung, Jin Hyuk 1 Lu, Ye 1 Mokhtari, Abdelkader 1 Neumaier, Arnold 1 O’Leary, Dianne P. 1 Patrinos, Panagiotis 1 Rudenko, Z. G. 1 Schachinger, Werner 1 Telli, Mohamed 1 Themelis, Andreas 1 Vandenbussche, Dieter 1 Woessner, William P. 1 Yuan, Ya-xiang all top 5 Cited in 8 Serials 4 Computational Optimization and Applications 2 SIAM Journal on Optimization 1 Journal of Optimization Theory and Applications 1 Computer Aided Geometric Design 1 Journal of Global Optimization 1 Automation and Remote Control 1 Mathematical Programming. Series A. Series B 1 Mathematical Programming Computation Cited in 4 Fields 11 Operations research, mathematical programming (90-XX) 3 Calculus of variations and optimal control; optimization (49-XX) 1 Numerical analysis (65-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Citations by Year