User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Newton-KKT interior-point methods for indefinite quadratic programming

Primary tabs

Absil, Pierre-Antoine [UCL] Tits, Andre L.

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.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès restreint
Publication date 2007
Language Anglais
Journal information "Computational Optimization and Applications : an international journal" - Vol. 36, no. 1, p. 5-41 (2007)
Peer reviewed yes
Publisher Springer (New York)
issn 0926-6003
e-issn 1573-2894
Publication status Publié
Affiliation UCL - FSA/INMA - Département d'ingénierie mathématique
Keywords interior-point algorithms
Links
  1. P.-A. Absil, C.G. Baker, and K.A. Gallivan, “A truncated-CG style method for symmetric generalized eigenvalue problems,” J. Comput. Appllied Math., vol. 189, nos. 1–2, pp. 274–285, 2006.
  2. J.F. Bonnans and M. Bouhtou, “The trust region affine interior point algorithm for convex and nonconvex quadratic programming,” RAIRO Rech. Opér., vol. 29, pp. 195–217, 1995.
  3. Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst (eds.), “Templates for the solution of algebraic eigenvalue problems: A practical guide,” Society for Industrial and Applied Mathematics, Philadelphia, 2000.
  4. R.H. Byrd, J.C. Gilbert, and J. Nocedal, “A trust region method based on interior point techniques for nonlinear programming,” Math. Program., vol. 89, pp. 149–185, 2000.
  5. J. F. Bonnans and C. Pola, “A trust region interior point algorithm for linearly constrained optimization,” SIAM J. Optim., vol. 7, no. 3, pp. 717–731, 1997.
  6. S. Bakhtiari and A.L. Tits, “A simple primal-dual feasible interior-point method for nonlinear programming with monotone descent,” Comput. Optim. Appl., vol. 25, pp. 17–38, 2003.
  7. A.R. Conn, N.I.M. Gould, and Ph. L. Toint, “Trust-region methods,” MPS/SIAM Series on Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, and Math. Program. Soc. (MPS), Philadelphia, PA, 2000.
  8. T.F. Coleman and J. Liu, “An interior Newton method for quadratic programming,” Math. Program., vol. 85, pp. 491–523, 1999.
  9. I.I. Dikin, “Iterative solution of problems of linear and quadratic programming,” Sov. Math. Dokl., vol. 8, pp. 674–675, 1967.
  10. C. Dang and L. Xu, “A barrier function method for the nonconvex quadratic programming problem with box constraints,” J. Glob. Optim., vol. 18, no. 2, pp. 165–188, 2000.
  11. A.S. El-Bakry, R.A. Tapia, T. Tsuchiya, and Y. Zhang, “On the formulation and theory of the Newton interior-point method for nonlinear programming,” J. Opt. Theory Appl., vol. 89, pp. 507–541, 1996.
  12. A. Forsgren and P.E. Gill, “Primal-dual interior methods for nonconvex nonlinear programming,” SIAM J. Optim., vol. 8, no. 4, pp. 1132–1152, 1998.
  13. A. Forsgren, P. E. Gill, and M. H. Wright, “Interior methods for nonlinear optimization,” SIAM Rev., vol. 44, no. 4, pp. 525–597, 2002.
  14. A.V. Fiacco and G.P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques Wiley, New-York, 1968.
  15. D.M. Gay, M.L. Overton, and M. H. Wright, “A primal-dual interior method for nonconvex nonlinear programming,” Advances in Nonlinear Programming, Y. Yuan (ed.). Kluwer Academic Publisher, 1998, pp. 31–56.
  16. C. Grossmann and M. Zadlo, “A general class of penalty/barrier path-following Newton methods for nonlinear programming,” Optim., vol. 54, no. 2, pp. 161–190, 2005.
  17. J.N. Herskovits, “Développement d’une méthode numérique pour l’optimization non-linéaire,” Ph.D. thesis, Université Paris IX - Dauphine, Paris, France, January 1982.
  18. J.N. Herskovits, “A two-stage feasible directions algorithm for nonlinear constrained optimization,” Math. Program., vol. 36, no. 1, pp. 19–38, 1986.
  19. R.D.C. Monteiro and I. Adler, “Interior path following primal-dual algorithms. Part ii: Convex quadratic programming,” Math. Program., vol. 44, pp. 43–66, 1989.
  20. J.J. Moré and G. Toraldo, “Algorithms for bound constrained quadratic programming problems,” Numer. Math., vol. 55, no. 4, pp. 377–400, 1989.
  21. R.D.C. Monteiro and T. Tsuchiya, “Global convergence of the affine scaling algorithm for convex quadratic programming,” SIAM J. Optim., vol. 8, no. 1, pp. 26–58, 1998.
  22. Numerical Optimization, ISBN:0387987932, 10.1007/b98874
  23. E.R. Panier, A.L. Tits, and J.N. Herskovits, “A QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization,” SIAM J. Control Optim., vol. 26, no. 4, pp. 788–811, 1988.
  24. H.-D. Qi and L. Qi, “A new QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization,” SIAM J. Optim., vol. 11, no. 1, pp. 113–132, 2000.
  25. P. Tseng, “Convergence properties of Dikin’s affine scaling algorithm for nonconvex quadratic minimization,” J. Glob. Optim., vol. 30, no. 2, pp. 285–300, 2004.
  26. A.L. Tits, A. Wächter, S. Bakhtiari, T.J. Urban, and C.T. Lawrence, “A primal-dual interior-point method for nonlinear programming with strong global and local convergence properties,” SIAM J. Optim., vol. 14, no. 1, pp. 173–199, 2003.
  27. P. Tseng and Y. Ye, “On some interior-point algorithms for nonconvex quadratic optimization,” Math. Program., vol. 93, no. 2, Ser. A, pp. 217–225, 2002.
  28. A.L. Tits and J.L. Zhou, “A simple, quadratically convergent algorithm for linear and convex quadratic programming,” in Large Scale Optimization: State of the Art, W.W. Hager, D.W. Hearn, and P.M. Pardalos (eds.), Kluwer Academic Publishers, pp. 411–427, 1994.
  29. R.J. Vanderbei and D.F. Shanno, “An interior-point algorithm for nonconvex nonlinear programming,” Comp. Optim. Appl., vol. 13, pp. 231–252, 1999.
  30. M. H. Wright, “Ill-conditioning and computational error in interior methods for nonlinear programming,” SIAM J. Optim., vol. 9, no. 1, pp. 84–111, 1998.
  31. H. Yamashita, “A globally convergent primal-dual interior point method for constrained optimization,” Optim. Meth. Softw., vol. 10, pp. 443–469, 1998.
  32. Y. Ye, “Interior algorithms for linear, quadratic, and linearly constrained convex programming,” Ph.D. thesis, Stanford University, 1987.
  33. Y. Ye, “An extension of Karmarkar’s algorithm and the trust region method for quadratic programming,” Progress in Mathematical Programming (Pacific Grove, CA, 1987). Springer, New York, 1989, pp. 49–63.
  34. Y. Ye, “On affine scaling algorithms for nonconvex quadratic programming,” Math. Program., vol. 56, pp. 285–300, 1992.
  35. Y. Ye, “On the complexity of approximating a KKT point of quadratic programming,” Math. Program., vol. 80, pp. 195–211, 1998.
  36. Y.-F. Yang, D.-H. Li, and L. Qi, “A feasible sequential linear equation method for inequality constrained optimization,” SIAM J. Optim., vol. 13, no. 4, pp. 1222–1244, 2003.
  37. Y. Ye and E. Tse, “An extension of Karmarkar’s projective algorithm for convex quadratic programming,” Math. Program., vol. 44, no. 2 (Ser. A), pp. 157–179, 1989.
Bibliographic reference Absil, Pierre-Antoine ; Tits, Andre L.. Newton-KKT interior-point methods for indefinite quadratic programming. In: Computational Optimization and Applications : an international journal, Vol. 36, no. 1, p. 5-41 (2007)
Permanent URL http://hdl.handle.net/2078.1/37601