Spectral Projected Gradient Method for the Procrustes Problem

Juliano de Bem Francisco, Tiara Martini

Abstract


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.

Full Text:

PDF

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.




DOI: https://doi.org/10.5540/tema.2014.015.01.0083

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia