Newton-KKT interior-point methods for indefinite quadratic programming |
| |
Authors: | P-A Absil André L Tits |
| |
Institution: | (1) Département d’ingénierie mathématique, Université catholique de Louvain, 1348 Louvain-la-Neuve, Belgium;(2) Department of Electrical and Computer Engineering and Institute for Systems Research, University of Maryland, College Park, MD 20742, USA |
| |
Abstract: | 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
(à 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.
The work of the first author was supported in part by the School of Computational Science of Florida State University through
a postdoctoral fellowship. Part of this work was done while this author was a Research Fellow with the Belgian National Fund
for Scientific Research (Aspirant du F.N.R.S.) at the University of Liège. The work of the second author was supported in
part by the National Science Foundation under Grants DMI9813057 and DMI-0422931 and by the US Department of Energy under Grant
DEFG0204ER25655. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors
and do not necessarily reflect the views of the National Science Foundation or those of the US Department of Energy. |
| |
Keywords: | Interior-point algorithms Primal-dual algorithms Indefinite quadratic programming Newton-KKT |
本文献已被 SpringerLink 等数据库收录! |
|