Quadratic third-order tensor optimization problem with quadratic constraints
AbstractQuadratically constrained quadratic programs (QQPs) problems play an important modeling role for many diverse problems. These problems are in general NP hard and numerically intractable. Semidenite programming (SDP) relaxations often provide good approximate solutions to these hard problems. For several special cases of QQP, e.g., convex programs and trust region subproblems, SDP relaxation provides the exact optimal value, i.e., there is a zero duality gap. However, this is not true for the general QQP, or even the QQP with two convex constraints, but a nonconvex objective.In this paper, we consider a certain QQP where the variable is neither vector nor matrix but a third-order tensor. This problem can be viewed as a generalization of the ordinary QQP with vector or matrix as it's variant. Under some mild conditions, we rst show that SDP relaxation provides exact optimal solutions for the original problem. Then we focus on two classes of homogeneous quadratic tensor programming problems which have no requirements on the constraints number. For one, we provide an easily implemental polynomial time algorithm to approximately solve the problem and discuss the approximation ratio. For the other, we show there is no gap between the SDP relaxation and itself.
Bader B W, Kolda T G. Algorithm 862: MATLAB tensor classes for fast algorithm prototyping. ACM Trans Math Software, 2006, 32: 635- 653
Beck A. Quadratic matrix programming. SIAM J Optim, 2006, 17(4): 1224-1238
Ben-Tal A, Teboulle M. Hidden convexity in some nonconvex quadratically constrained quadratic programming. Math Program, 1996, 72(1): 51-63
Dogan M C, Mendel J. Applications of cumulants to array processing .I. aperture extension and array calibration. IEEE Trans Sig Proc, 1995, 43(5): 1200- 1216
Fortin C,Wolkowicz H. The trust region subproblem and semidenite programming. Optim Methods Softw, 2004, 19: 41-67
Ghaoui L El, Lebret H. Robust solutions to least-squares problems with uncertain data. SIAM J Matrix Anal Appl, 1997, 18: 1035-1064
Kim S, Kojima M. Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations. Comput Optim Appl, 2003, 26: 143-154
Kolda T G, Bader B W. Tensor Decompositions and Applications. SIAM Review, 2009,51(3): 455- 500
Lathauwer L de, Castaing J. Tensor-based techniques for the blind separation of ds-cdma signals. Signal Processing, 2007, 87(2): 322- 336
Luo Z Q, Sidiropoulos N D, Tseng P, Zhang S Z. Approximation Bounds for Quadratic Optimization with Homogeneous Quadratic Constraints. SIAM J Optim, 2007, 18(1): 1-28
Pakati G. On the rank of extreme matrices in semidenite programs and the multiplicity of optimal eigenvalues. Math Oper Res, 1998, 23: 339-358
Polyak B T. Convexity of quadratic transformations and its use in control and optimization, J Optim Theory Appl, 1998, 99: 553-583
Sidiropoulos N D, Giannakis G B, Bro R. Blind PARAFAC receivers for DS-CDMA systems. IEEE Trans on Sig Proc, 2000, 48(3): 810- 823
So A M-C, Ye Y Y, Zhang J W. A unified theorem on SDP rank reduction. Math Oper Res, 2008, 33: 910-920
Stern R J, Wolkowicz H. Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations. SIAM J Optim, 1995, 5: 286-313
Swami A, Giannakis G, Shamsunder S. Multichannel ARMA processes IEEE Trans Sig Proc, 1994, 42(4): 898- 913
Ye Y Y, Zhang S Z. New results on quadratic minimization. SIAM J Optim, 2003, 14:245-267
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).