Semidefinite relaxation bounds for bi-quadratic optimization problems with quadratic constraints
Tóm tắt
This paper studies the relationship between the so-called bi-quadratic optimization problem and its semidefinite programming (SDP) relaxation. It is shown that each r-bound approximation solution of the relaxed bi-linear SDP can be used to generate in randomized polynomial time an
$${\mathcal{O}(r)}$$
-approximation solution of the original bi-quadratic optimization problem, where the constant in
$${\mathcal{O}(r)}$$
does not involve the dimension of variables and the data of problems. For special cases of maximization model, we provide an approximation algorithm for the considered problems.
Tài liệu tham khảo
Ben-Tal A., Nemirovski A., Roos C.: Robust solutions of uncertain quadratic and conic quadratic problems. SIAM J. Optim. 13, 535–560 (2002)
Berkelaar A.B., Sturm J.F., Zhang S.Z.: Polynomial primal-dual cone affine scaling for semidefinite programming. Appl. Numer. Math. 29, 317–333 (1999)
Cardoso J.F.: High-order contrasts for independent component analysis. Neural Comput. 11, 157–192 (1999)
Comon P.: Independent component analysis, a new concept?. Signal Process. 36, 287–314 (1994)
Dahl G., Leinaas J.M., Myrheim J., Ovrum E.: A tensor product matrix aproximation problem in quantum physics. Linear Algebra Appl. 420, 711–725 (2007)
De Lathauwer, L., Comon, P., De Moor, B., Vandewalle, J.: Higher-order power method—application in independent component analysis. In: Proceedings of the International Symposium on Nonlinear Theory and its Applications (NOLTA’95), Las Vegas, NV, pp. 91–96 (1995)
De Lathauwer L., De Moor B., Vandewalle J.: On the best rank-1 and rank-(R 1, R 2, . . . , R N ) approximation of higher-order tensor. SIAM J. Matrix Anal. Appl. 21, 1324–1342 (2000)
Einstein A., Podolsky B., Rosen N.: Can quantum-mechanical description of physical reality be considered complete?. Phys. Rev. 47, 777–780 (1935)
Fujisawa, K., Futakata, Y., Kojima, M., Matsuyama, S., Nakamura, S., Nakata, K., Yamashita, M.: SDPA-M (SemiDefinite Programming Algorithm in MATLAB). http://homepage.mac.com/klabtitech/sdpa-homepage/download.html
Grigorascu, V.S., Regalia, P.A.: Tensor displacement structures and polyspectral matching. In: Kailath, T., Sayed, A.H. Chapter 9 of Fast Reliable Algorithms for Structured Matrices, SIAM Publications, Philadeliphia (1999)
Han D., Dai H.H., Qi L.: Conditions for strong ellipticity of anisotropic elastic materials. J. Elast. 97, 1–13 (2009)
He S.M., Luo Z.Q., Nie J., Zhang S.Z.: Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization. SIAM J. Optim. 19, 503–523 (2008)
Horst R., Pardalos P.M., Thoai N.V.: Introduction to Global Optimization. Kluwer, Dordrecht (2000)
Huang Y.M., Zhang S.Z.: Complex matrix decomposition and quadratic programming. Math. Oper. Res. 32, 758–768 (2007)
Knowles J.K., Sternberg E.: On the ellipticity of the equations of the equations for finite elastostatics for a special material. J. Elast. 5, 341–361 (1975)
Kofidis E., Regalia P.A.: On the best rank-1 approximation of higher-order supersymmetric tensors. SIAM J. Matrix Anal. Appl. 23, 863–884 (2002)
Ling C., Nie J., Qi L., Ye Y.: Bi-quadratic optimization over unit spheres and semidefinite programming relaxations. SIAM J. Optim. 20, 1286–1310 (2009)
Luo Z.Q., Sidiropoulos N., Tseng P., Zhang S.Z.: Approximation bounds for quadratic optimization with homogeneous quadratic constraints. SIAM J. Optim. 18, 1–28 (2007)
Luo, Z.Q., Zhang, S.Z.: A semidefinite relaxation scheme for multivariate quartic polynomial optimization with quadratic constraints, Technical Report Seem 2008-06, Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong (2009)
Nemirovski A., Roos C., Terlaky T.: On maximization of quadratic form over intersection of ellipsoids with common center. Math. Program. 86, 463–473 (1999)
Nikias C.L., Petropulu A.P.: Higher-Order Spectra Analysis, A Nonlinear Signal Processing Framework. Prentice-Hall, Englewood Cliffs, NJ (1993)
Pardalos P.M., Wolkowicz H.: Topics in Semidefinite and Interior-Point Methods, Fields Institute Communications, Vol. 18. AMS, Providence, Rhode Island (1998)
Pataki G.: On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. 23, 339–358 (1998)
Qi L., Dai H.H., Han D.: Conditions for strong ellipticity and M-eigenvalues. Front. Math. China 4, 349–364 (2009)
Ramana, M., Pardalos, P.M.: Semidefinite programming. In: Terlaky, T. Interior Point Methods of Mathematical Programming, pp. 369–398. Kluwer, Dordrecht, The Netherlands (1996)
Rosakis P.: Ellipticity and deformations with discontinuous deformation gradients in finite elastostatics. Arch. Ration. Mech. Anal. 109, 1–37 (1990)
So A.M.-C., Ye Y., Zhang J.: A unified theorem on SDP rank reduction. Math. Oper. Res. 33, 910–920 (2008)
Sturm J.F., Zhang S.Z.: On cones of nonnegative quadratic functions. Math. Oper. Res. 28, 246–267 (2003)
Tseng P.: Further results on approximating nonconvex quadratic optimization by semidefinite programming relaxation. SIAM J. Optim. 14, 263–283 (2003)
Wang Y., Aron M.: A reformulation of the strong ellipticity conditions for unconstrained hyperelastic media. J. Elast. 44, 89–96 (1996)
Wang Y., Qi L., Zhang X.: A practical method for computing the largest M-eigenvalue of a fourth-order partially symmetric tensor. Numer. Linear Algebra Appl. 16, 589–601 (2009)
Ye Y., Zhang S.Z.: New results on quadratic minimization. SIAM J. Optim. 14, 245–267 (2003)
Zhang T., Golub G.H.: Rank-1 approximation of higher-order tensors. SIAM J. Matrix Anal. Appl. 23, 534–550 (2001)