Linear-Time Algorithm for Complex Uniform CDT Subproblem Based on Hidden Convexity
Mathematics · 14.07.2026 · 14 (14) · 2539
DOI: 10.3390/math14142539 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics, online erschienen am 14.07.2026. Verfasst von Zhuoyi Xu und 2 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China, Interdisciplinary Research Project for Young Teachers of USTB, Beijing Natural Science Foundation.
Abstract (Originalsprache)
In this paper, we study the nonconvex quadratic programming over the intersection of two balls in n-dimensional complex space, which is called the uniform CDT subproblem and is significant in both optimization theory and applications. We first prove the hidden convexity of the problem by using the S-lemma. In order to construct an algorithm, we prove the hidden convexity again by reformulating it as a convex problem (C). Subsequently, we employ the eigenvalue approximation method and the generalized Nesterov’s accelerated gradient descent algorithm to solve the problem (C) within an error tolerance of ϵ. Then, we prove that the proposed algorithm is linear-time with respect to the density of the matrix in the objective function. The density is related to the number of non-zero entries of the matrix. We do numerical experiments to compare the proposed linear-time algorithm with the CVX solver, with the method proposed by Burer and with the algorithm proposed by Sakaue et al. Numerical results show that the linear-time algorithm performs much better than other methods, which verify that the proposed algorithm is applicable to many large-scale problems nowadays.
Förderung
- National Natural Science Foundation of China
- Interdisciplinary Research Project for Young Teachers of USTB
- Beijing Natural Science Foundation
Zitieren
APA
Xu, Z., Ma, C., & Yang, M. (2026). Linear-Time Algorithm for Complex Uniform CDT Subproblem Based on Hidden Convexity. Mathematics, 14(14), 2539. https://doi.org/10.3390/math14142539
Vancouver
Xu Z, Ma C, Yang M. Linear-Time Algorithm for Complex Uniform CDT Subproblem Based on Hidden Convexity. Mathematics. 2026;14(14):2539. doi:10.3390/math14142539
BibTeX
@article{Xu2026,
author = {Xu, Zhuoyi and Ma, Chenyang and Yang, Meijia},
title = {Linear-Time Algorithm for Complex Uniform CDT Subproblem Based on Hidden Convexity},
journal = {Mathematics},
year = {2026},
volume = {14},
number = {14},
pages = {2539},
doi = {10.3390/math14142539}
}
EUVIMED