Summary

Proceedings of the 2012 International Symposium on Nonlinear Theory and its Applications

2012

Session Number:B3L-B

Session:

Number:431

A Modified Multiplicative Update Algorithm for Convex Quadratic Programming Problems with Nonnegativity Constraints

Jiro Katayama,  Norikazu Takahashi,  

pp.431-434

Publication Date:

Online ISSN:2188-5079

DOI:10.15248/proc.1.431

PDF download (274.8KB)

Summary:
A multiplicative update for solving convex quadratic programming problems with nonnegativity constraints, which was proposed by Sha et al., has three advantages: 1) nonnegativity of solutions is automatically satisfied, 2) no parameter tuning is needed, and 3) implementation is easy because of simple update formula. However, the global convergence of the update is not always guaranteed. In this paper, we propose a modified version of the multiplicative update and prove its global convergence without any assumption on the problem. We also show experimentally that our modification affects neither the computation time nor the number of iterations

References:

[1] D. D. Lee and H. S. Seung, “Algorithms for nonnegative matrix factorization,” in T. K. Leen, T. G. Dietterich and V. Tresp (Eds.), Advances in Neural Information Processing Systems, vol. 13, pp. 556-562, 2001.

[2] A. Cichocki, R. Zdunek, A. H. Phan and S.-I. Amari, Nonnegative Matrix and Tensor Factorizations, John Wiley & Sons, 2009.

[3] F. Sha, Y. Lin, L. K. Saul, D. D. Lee, “Multiplicative updates for nonnegative quadratic programming,” Neural Computation, vol. 19, pp. 2004-2031, 2007.

[4] N. Gillis and F. Glineur, “Nonnegative factorization and the maximum edge biclique problem,” ArXiv, 0810.4225, Oct. 2008.

[5] R. Hibi and N. Takahashi, “A modified multiplicative update algorithm for Euclidean distance-based nonnegative matrix factorization and its global convergence,” Proc. 18th International Conference on Neural Information Processing, Part-II, pp. 655-662, 2011.

[6] W. I. Zangwill, Nonlinear Programming: A Unified Approach, Prentice-Hall, 1969.

[7] D. G. Luenberger, Linear and Nonlinear Programming, Second Edition, Addison-Wesley Publishing Company, 1984.