Quadratic third-order tensor optimization problem with quadratic constraints

  • Lixing Yang Department of Electrical and Computer Engineering, New Jersey Institute of Technology, USA
  • Qingzhi Yang Nankai University, China
  • Xiaoming Zhao Nankai University, China
DOI: https://doi.org/10.19139/soic.v2i2.67

Abstract

Quadratically 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.

References

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

Published
2014-06-01
How to Cite
Yang, L., Yang, Q., & Zhao, X. (2014). Quadratic third-order tensor optimization problem with quadratic constraints. Statistics, Optimization & Information Computing, 2(2), 130-146. https://doi.org/10.19139/soic.v2i2.67
Issue
Vol 2 No 2 (2014)
Section
Research Articles
Authors who publish with this journal agree to the following terms:

    1. 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.
    2. 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.
    3. 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).