Paper Info
Title
Generalized quadratically constrained quadratic programming for signal processing
Abstract
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.
Year
DOI
Venue
2014
10.1109/ICASSP.2014.6855084
Acoustics, Speech and Signal Processing
Keywords
Field
DocType
Newton method,computational complexity,optimisation,polynomial approximation,quadratic programming,signal processing,KKT optimality conditions,Karsuh-Kuhn-Tucker optimality conditions,Newton method,branch-and-bound methods,difference-of-convex functions,generalized QCQP problem,generalized quadratically constrained quadratic programming problem,global optimality,nonconstrained optimization problem,objective functions,one-dimensional convex functions,polynomial-time complexity,quadratic functions,signal communications,signal processing,DC programming,Generalized QCQP problem,array processing,cooperative communications,polynomial-time algorithms
Second-order cone programming,Quadratic growth,Mathematical optimization,Quadratically constrained quadratic program,Computer science,Nonlinear programming,Quadratic function,Quadratic programming,Karush–Kuhn–Tucker conditions,Optimization problem
Conference
ISSN
Citations 
PageRank 
1520-6149
0
0.34
References 
Authors
11
2
Name
Order
Citations
PageRank
Arash Khabbazibasmenj118611.70
sergiy a vorobyov21563113.46