Correo Electrónico
DNINFOA - SIA
Bibliotecas
Convocatorias
Identidad U.N.
Publicado
A Spectral Gradient Projection Method for the Positive Semi-definite Procrustes Problem
Un Método de Gradiente Proyectado Espectral para el Problema de Mínimos Cuadrados Matricial Semi-definido Positivo
DOI:
https://doi.org/10.15446/recolma.v55n1.99100Palabras clave:
Non-monotone algorithm, Constrained optimization, Symmetric positive semi-definite constraints, Least-Square problems (en)Algoritmo no-monótono, optimización con restricciones, restricciones simétricas y semi definidas positivas, problema de mínimos cuadrados (es)
Descargas
This paper addresses the positive semi-deffnite procrustes problem (PSDP). The PSDP corresponds to a least squares problem over the set of symmetric and semi-deffnite positive matrices. These kinds of problems appear in many applications such as structure analysis, signal processing, among others. A non-monotone spectral projected gradient algorithm is proposed to obtain a numerical solution for the PSDP. The proposed algorithm employs the Zhang and Hager's non-monotone technique in combination with the Barzilai and Borwein's step size to accelerate convergence. Some theoretical results are presented. Finally, numerical experiments are performed to demonstrate the effectiveness and efficiency of the proposed method, and comparisons are made with other state-of-the-art algorithms.
En este artículo abordamos el problema de mínimos cuadrados lineales sobre el conjunto de matrices simétricas y definidas positivas (PSDP). Esta clase de problemas surge en un gran número de aplicaciones tales como análisis de estructuras, procesamiento de señales, análisis de componentes principales, entre otras. Para resolver este tipo de problemas, proponemos un método de gradiente proyectado espectral no-monótono. El algoritmo propuesto usa la técnica de globalización no-monótona de Zhang y Hager, en combinación con los tamaños de paso de Barzilai y Borwein para acelerar la convergencia del método. Además, presentamos y comentamos algunos resultados teóricos concernientes al algoritmo desarrollado. Finalmente, llevamos a cabo varios experimentos numéricos con el fin de demostrar la efectividad y la eficiencia del nuevo enfoque, y realizamos comparaciones con algunos métodos existentes en la literatura.
Referencias
Lars-Erik Andersson and Tommy Elfving, A constrained procrustes problem, SIAM Journal on Matrix Analysis and Applications 18 (1997), no. 1, 124-139. DOI: https://doi.org/10.1137/S0895479894277545
Negin Bagherpour and Nezam Mahdavi-Amiri, Efficient algorithms for positive semi-definite total least squares problems, minimum rank problem and correlation matrix computation, arXiv preprint arXiv:1407.3894 (2014).
Jonathan Barzilai and Jonathan M Borwein, Two-point step size gradient methods, IMA journal of numerical analysis 8 (1988), no. 1, 141-148. DOI: https://doi.org/10.1093/imanum/8.1.141
Dimitri P Bertsekas, Nonlinear programming, Journal of the Operational Research Society 48 (1997), no. 3, 334-334. DOI: https://doi.org/10.1057/palgrave.jors.2600425
John E Brock, Optimal matrices describing linear systems., AIAA Journal 6 (1968), no. 7, 1292-1296. DOI: https://doi.org/10.2514/3.4736
Yu-Hong Dai and Roger Fletcher, Projected barzilai-borwein methods for large-scale box-constrained quadratic programming, Numerische Mathematik 100 (2005), no. 1, 21-47. DOI: https://doi.org/10.1007/s00211-004-0569-y
JB Francisco, FS Viloche Bazán, and M Weber Mendonca, Non-monotone algorithm for minimization on arbitrary domains with applications to large-scale orthogonal procrustes problem, Applied Numerical Mathematics 112 (2017), 51-64. DOI: https://doi.org/10.1016/j.apnum.2016.09.018
Nicolas Gillis and Punit Sharma, A semi-analytical approach for the positive semidefinite procrustes problem, Linear Algebra and its Applications 540 (2018), 112-137. DOI: https://doi.org/10.1016/j.laa.2017.11.023
Nicholas J Higham, Computing a nearest symmetric positive semidefinite matrix, Linear algebra and its applications 103 (1988), 103-118. DOI: https://doi.org/10.1016/0024-3795(88)90223-6
Anping Liao and Zhongzhi Bai, Least-squares solution of ax b= d over symmetric positive semidefinite matrices x, Journal of Computational Mathematics (2003), 175-182.
Yurii Nesterov, Introductory lectures on convex programming volume i: Basic course, Lecture notes 3 (1998), no. 4, 5.
Jorge Nocedal and Stephen Wright, Numerical optimization, Springer Science & Business Media, 2006.
Marcos Raydan, The barzilai and borwein gradient method for the large scale unconstrained minimization problem, SIAM Journal on Optimization 7 (1997), no. 1, 26-33. DOI: https://doi.org/10.1137/S1052623494266365
TJ Suffridge and TL Hayden, Approximation by a hermitian positive semidefinite toeplitz matrix, SIAM journal on matrix analysis and applications 14 (1993), no. 3, 721-734. DOI: https://doi.org/10.1137/0614052
Kim-Chuan Toh, An inexact primal-dual path following algorithm for convex quadratic sdp, Mathematical programming 112 (2008), no. 1, 221-254. DOI: https://doi.org/10.1007/s10107-006-0088-y
Kim-Chuan Toh, Michael J Todd, and Reha H Tütüncü, Sdpt3a matlab software package for semidefinite programming, version 1.3, Optimization methods and software 11 (1999), no. 1-4, 545-581. DOI: https://doi.org/10.1080/10556789908805762
Keith G Woodgate, Least-squares solution of f= pg over positive semidefinite symmetric p, Linear algebra and its applications 245 (1996), 171-190. DOI: https://doi.org/10.1016/0024-3795(94)00238-X
Hongchao Zhang and William W Hager, A nonmonotone line search technique and its application to unconstrained optimization, SIAM journal on Optimization 14 (2004), no. 4, 1043-1056. DOI: https://doi.org/10.1137/S1052623403428208
Cómo citar
APA
ACM
ACS
ABNT
Chicago
Harvard
IEEE
MLA
Turabian
Vancouver
Descargar cita
CrossRef Cited-by
1. Clare Wickman, Kasso A. Okoudjou. (2023). Gradient Flows for Probabilistic Frame Potentials in the Wasserstein Space. SIAM Journal on Mathematical Analysis, 55(3), p.2324. https://doi.org/10.1137/21M1425633.
