Linear-Time Algorithm for Complex Uniform CDT Subproblem Based on Hidden Convexity

Abstract

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.