Spectral Projected Gradient Method for the Procrustes Problem
DOI:
https://doi.org/10.5540/tema.2014.015.01.0083Abstract
We study and analyze a nonmonotone globally convergent method for minimization on closed sets. This method is based on the ideas from trust-region and Levenberg-Marquardt methods. Thus, the subproblems consists in minimizing a quadratic model of the objective function subject to the constraint set. We incorporate concepts of bidiagonalization and calculation of the SVD "with inaccuracy'' to improve the performance of the algorithm, since the solution of the subproblem by traditional techniques, which is required in each iteration, is computationally expensive. Other feasible methods are mentioned, including a curvilinear search algorithm and a minimization along geodesics algorithm. Finally, we illustrate the numerical performance of the methods when applied to the Orthogonal Procrustes Problem.References
T. A. Arias, A. Edelman, S. T. Smith. "The geometry of algorithms with ortogonality constraints''. SIAM Journal on Matrix Analysis and Applications, v. 20, n. 2, pp. 303-353, 1998.
A. Aspremont, L. E. Ghaoui, M. Jordan and G. R. Lanckriet. "A direct formulation for sparse pca using semidefinite programming''. SIAM Review, n. 49, pp. 434-448, 2007.
J. Barzilai, J. M. Borwein. "Two point step size gradient methods''. IMA Journal of Numerical Analysis, v. 8, pp. 141-148, 1988.
T. Bell. "Global Positioning System-Based Attitude Determination and the Orthogonal Procrustes Problem''. Journal of guidance, control and dynamics, v. 26, n. 5, pp. 820-822, 2003.
E. G. Birgin, J. M. Martínez, M. Raydan. "Nonmonotone spectral projected gradient methods on convex sets''. SIAM Journal on Optimization, v. 10, pp. 1196-1211, 2000.
A. W. Bojanczyk and A. Lutoborski. "The Procrustes Problem for Orthogonal Stiefel Matrices''. SIAM Journal on Scientific Computing, v.21, pp. 1291-1304, 1998.
Y. Chahlaoui, K. Gallivan, P. Van Dooren. "Recursive calculation of dominant singular subspaces''.
SIAM Journal on Matrix Analysis and Applications, v. 25, n. 2, pp. 445-463, 1999.
W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver. "Combinatorial optimization''. John Wiley & Sons, Canadá, 1997.
T. F. Cox, M. A. A. Cox. "Multidimensional scaling''. Chapman and Hall, Londres, 2000.
A. Edelman, R. Lippert. "Nonlinear Eigenvalue Problems with Orthogonality Constraints''. In Templates for the Solution of Algebraic Eigenvalue Problems, A Practical Guide, pp. 290-314, Philadelphia, 2000.
L. Eldén, H. Park. "A procrustes problem on Stiefel manifolds''. Numerishe Mathematik, v. 82, pp. 599-619, 1999.
J. B. Francisco and J. M. Martínez and L. Martínez. "Globally convergent trust-region methods for self-consistent fiel electronic structure calculations''. Journal of Chemical Physics, v.121, pp. 10863-10878, 2004.
J. B. Francisco and F. S. Viloche Bazán. "Nonmonotone algorithm for minimization on closed sets with application to minimization on Stiefel manifolds''. Journal of Computational and Applied Mathematics, v. 236, n. 10, pp. 2717-2727, 2012.
G. H. Golub, W. Kahan. "Calculating the singular values and pseudoinverse of a matrix''. SIAM Journal on Numerical Analysis, v. 2, pp. 205-224, 1965.
L. Grippo, F. Lampariello, S. Lucidi. "A nonmonotone line search technique for Newton's method''. SIAM Journal on Numerical Analysis, v. 23, n. 4, pp. 707-716, 1986.
N. J. Higham. "The symmetric procrustes problem''. BIT Numerical Mathematics, v. 28, n. 1, pp. 133-143, 1988.
J. R. Hurley, R. B. Cattell. "The procrustes program: Producing direct rotation to test a hypothesized factor structure''. Behavioral Science, n. 7, pp. 258-262, 1962.
%R. Janin. "Direction derivative of the marginal function in nonlinear programming''. Mathematical Programming Study, v. 21, pp. 127-138, 1984.
E. Klerk, M. Laurent, P. A. Parrilo. "A PTAS for the minimization of polynomials of fixed degree over the simplex''. Theoretical Computer Science, pp. 210-225, 2006.
C. Lanczos. "An iteration method for the solution of the eigenvalue problem of linear differential and integral operators''. Journal of Research of the National Bureau of Standards, v. 45, n. 4, pp. 255-282, 1950.
J. M. Martínez, S. A. Santos. "A trust region strategy for minimization on arbitrary domains''. Mathematical Programming, n. 68, pp. 267-302, 1995.
J. Nocedal, S. J. Wright. "Numerical Optimization''. Springer, New York, 2006.
C. C. Paige, M. A. Saunders. "LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares''. ACM Transactions on Mathematical Software, v. 8, n. 1, pp. 43-71, 1982.
I. Söderkvist, P. Wedin, "On Condition Numbers and Algorithms for Determining a Rigid Body Movement''. BIT, v. 34, pp. 424-436, 1994.
Z. Wen, W. Yin. "A feasible method for optimization with orthogonality constraints''. Optimization Online, pp. 1-30, 2010.
Z. Zhang, K. Du. "Successive projection method for solving the unbalanced procrustes problem''. Science in China: Series A Mathematics, v. 49, n. 7, pp. 971-986, 2006.
H. Zhang, W. W. Hager. "A nonmonotone line search technique and its application to unconstrained optimization''. SIAM Journal Optimization, v. 14, n. 4, pp. 1043-1056, 2004.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish in this journal agree to the following terms:
Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.
Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).
This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
author. This is in accordance with the BOAI definition of open access
Intellectual Property
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.