[en] This paper introduces a new iterative approach to solve or to approximate the solutions of the nonconvex quadratically constrained quadratic programs (QCQP). First, this constrained problem is transformed to an unconstrained problem using a specialized penalty-based method. A tight upper-bound for the alternative unconstrained objective is introduced. Then an efficient minimization approach to the alternative unconstrained objective is proposed and further studied. The proposed approach involves power iterations and minimization of a convex scalar function in each iteration, which are computationally fast. The important design problem of multigroup multicast beamforming is formulated as a nonconvex QCQP and solved using the proposed method.
Centre de recherche :
SnT-SigCom
Disciplines :
Ingénierie électrique & électronique
Auteur, co-auteur :
GHARANJIK, Ahmad ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
SHANKAR, Bhavani ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Soltanalian, Mojtaba; University of Illinois at Chicago (UIC) > Department of Electrical and Computer Engineering > Assistant Professor in Information Systems,
OTTERSTEN, Björn ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
An Iterative Approach to Nonconvex QCQP with Applications in Signal Processing
Date de publication/diffusion :
10 juillet 2016
Nom de la manifestation :
2016 IEEE Sensor Array and Multichannel Signal Processing Workshop (SAM)
Organisateur de la manifestation :
IEEE
Lieu de la manifestation :
Rio de Janeiro, Brésil
Date de la manifestation :
10-7-2016 to 12-7-2016
Manifestation à portée :
International
Titre de l'ouvrage principal :
2016 IEEE Sensor Array and Multichannel Signal Processing Workshop (SAM)
P. M. Pardalos and S. A. Vavasis, "Quadratic programming with one negative eigenvalue is NP-hard, " Journal of Global Optimization, vol. 1, no. 1, pp. 15-22, 1991.
M. Bengtsson and B. Ottersten, Optimal and Suboptimal Transmit Beamforming, ser. Electrical Engineering & Applied Signal Processing Series, L. Chand Godara, Ed. CRC Press, 2001.
E. Karipidis, N. D. Sidiropoulos, and Z.-Q. Luo, "Quality of service and max-min fair transmit beamforming to multiple cochannel multicast groups, " IEEE Transactions on Signal Processing, vol. 56, no. 3, pp. 1268-1279, 2008.
N. D. Sidiropoulos, T. N. Davidson, and Z.-Q. T. Luo, "Transmit beamforming for physical-layer multicasting, " IEEE Transactions on Signal Processing, vol. 54, no. 6, pp. 2239-2251, 2006.
Y. Huang and D. P. Palomar, "Randomized algorithms for optimal solutions of double-sided qcqp with applications in signal processing, " IEEE Transactions on Signal Processing, vol. 62, no. 5, pp. 1093-1108, 2014.
A. De Maio, Y. Huang, M. Piezzo, S. Zhang, and A. Farina, "Design of optimized radar codes with a peak to average power ratio constraint, " IEEE Transactions on Signal Processing, vol. 59, no. 6, pp. 2683-2697, 2011.
A. Aubry, A. De Maio, M. Piezzo, M. M. Naghsh, M. Soltanalian, and P. Stoica, "Cognitive radar waveform design for spectral coexistence in signal-dependent interference, " in IEEE Radar Conference, 2014, pp. 0474-0478.
P. Stoica, J. Li, and Y. Xie, "On probing signal design for MIMO radar, " IEEE Transactions on Signal Processing, vol. 55, no. 8, pp. 4151-4161, 2007.
Z.-Q. Luo, W.-K. Ma, A.-C. So, Y. Ye, and S. Zhang, "Semidefinite relaxation of quadratic optimization problems, " IEEE Signal Processing Magazine, vol. 27, no. 3, pp. 20-34, 2010.
E. J. Candes, T. Strohmer, and V. Voroninski, "Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming, " Communications on Pure and Applied Mathematics, vol. 66, no. 8, pp. 1241-1274, 2013.
I. Waldspurger, A. d'Aspremont, and S. Mallat, "Phase recovery, maxcut and complex semidefinite programming, " Mathematical Programming, vol. 149, no. 1-2, pp. 47-81, 2015.
M. U. Torun, A. N. Akansu, and M. Avellaneda, "Portfolio risk in multiple frequencies, " IEEE Signal Processing Magazine, vol. 28, no. 5, pp. 61-71, 2011.
A. d'Aspremont and S. Boyd, "Relaxations and randomized methods for nonconvex QCQPs, " EE392o Class Notes, Stanford University.
S. Boyd and L. Vandenberghe, Convex optimization. Cambridge university press, 2009.
K. M. Anstreicher, "On convex relaxations for quadratically constrained quadratic programming, " Mathematical programming, vol. 136, no. 2, pp. 233-251, 2012.
H. D. Sherali and W. P. Adams, A reformulation-linearization technique for solving discrete and continuous nonconvex problems. Springer Science & Business Media, 2013, vol. 31.
A. Beck, A. Ben-Tal, and L. Tetruashvili, "A sequential parametric convex approximation method with applications to nonconvex truss topology design problems, " Journal of Global Optimization, vol. 47, no. 1, pp. 29-51, 2010.
B. R. Marks and G. P. Wright, "Technical note-a general inner approximation algorithm for nonconvex mathematical programs, " Operations Research, vol. 26, no. 4, pp. 681-683, 1978.
L.-N. Tran, M. F. Hanif, and M. Juntti, "A conic quadratic programming approach to physical layer multicasting for large-scale antenna arrays, " IEEE Signal Processing Letters, vol. 21, no. 1, pp. 114-117, 2014.
O. Mehanna, K. Huang, B. Gopalakrishnan, A. Konar, and N. Sidiropoulos, "Feasible point pursuit and successive approximation of non-convex qcqps, " IEEE Signal Processing Letters, vol. 22, no. 7, pp. 804-808, 2015.
M. Soltanalian and P. Stoica, "Designing unimodular codes via quadratic optimization, " IEEE Transactions on Signal Processing, vol. 62, no. 5, pp. 1221-1234, March 2014.
G. H. Golub and C. F. Van Loan, Matrix computations. JHU Press, 2012, vol. 3.
M. Soltanalian, A. Gharanjik, B. Shankar, and B. Ottersten, "Grabn-Pull: An optimization framework for fairness-achieving networks, " accepted to IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, 2016.
A. Gharanjik, B. Shankar M. R. R, P.-D. Arapoglou, M. Bengtsson, and B. Ottersten, "Robust precoding design for multibeam downlink satellite channel with phase uncertainty, " in IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, April, 2015, pp. 3083-3087.
