| Texto completo | |
| Autor(es): |
Song, Mengmeng
;
Goncalves, Douglas S.
;
Jung, Woosuk L.
;
Lavor, Carlile
;
Mucherino, Antonio
;
Wolkowicz, Henry
Número total de Autores: 6
|
| Tipo de documento: | Artigo Científico |
| Fonte: | Linear Algebra and its Applications; v. 727, p. 34-pg., 2025-12-15. |
| Resumo | |
We consider the nonconvex minimization problem, with quartic objective function, that arises in the exact recovery of a configuration matrix P is an element of R-nxd of n points when a Euclidean distance matrix, EDM, is given with embedding dimension d. It is an open question in the literature whether there are conditions such that the minimization problem admits a local nonglobal minimizer, lngm. We prove that all second-order stationary points are global minimizers whenever n <= d + 1. And, for d = 1 and n >= 7 > d + 1, we present an example where we can analytically exhibit a local nonglobal minimizer. For more general cases, we numerically find a second-order stationary point and then prove that there indeed exists a nearby lngm for the quartic nonconvex minimization problem. Thus, we answer the previously open question about their existence in the affirmative. Our approach to finding the lngm is novel in that we first exploit the translation and rotation invariance to remove the singularities of the Hessian, and reduce the size of the problem from nd variables in P to (n-1)d-d(d-1)/2 variables. This allows for stabilizing Newton's method, and for finding examples that satisfy the strict second order sufficient optimality conditions. The motivation for being able to find global minima is to obtain exact recovery of the configuration matrix, even in the cases where the data is noisy and/or incomplete, without resorting to approximating solutions from convex (semidefinite programming) relaxations. In the process of our work we present new insights into when lngms of the smooth stress function do and do not exist. (c) 2025 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies. (AU) | |
| Processo FAPESP: | 23/08706-1 - Métodos computacionais de otimização |
| Beneficiário: | Ernesto Julián Goldberg Birgin |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria |
| Beneficiário: | Francisco Louzada Neto |
| Modalidade de apoio: | Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs |