Quadratic third-order tensor optimization problem with quadratic constraints

Lixing Yang, Qingzhi Yang, Xiaoming Zhao

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

Full Text: PDF

DOI: 10.19139/soic.v2i2.67

Refbacks

• There are currently no refbacks.