Generalized quadratically constrained quadratic programming for signal processing

摘要

In this paper, we introduce and solve a particular generalization of the quadratically constrained quadratic programming (QCQP) problem which is frequently encountered in different fields of signal processing and communications. Specifically, we consider such generalization of the QCQP problem that comprises compositions of one-dimensional convex and quadratic functions in the constraint and the objective functions. We show that this class of problems can be precisely or approximately recast as the difference-of-convex functions (DC) programming problem. Although the DC programming problem can be solved through the branch-and-bound methods, these methods do not have any worst-case polynomial-time complexity guarantees. Therefore, we develop a new approach with worst-case polynomial-time complexity that can solve the corresponding DC problem of a generalized QCQP problem. It is analytically guaranteed that the point obtained by this method satisfies the Karsuh-Kuhn-Tucker (KKT) optimality conditions. Furthermore, the global optimality can be proved analytically under certain conditions. The new proposed method can be interpreted in terms of the Newton's method as applied to a non-constrained optimization problem.