Previous Articles     Next Articles

ON DOUBLY POSITIVE SEMIDEFINITE PROGRAMMING RELAXATIONS

Taoran Fu1, Dongdong Ge2, Yinyu Ye3   

  1. 1. School of Mathematical Sciences, Shanghai Jiao Tong University, Shanghai, China;
    2. School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China;
    3. Department of Management Science and Engineering, Stanford University, Stanford, CA 94305
  • Received:2017-05-23 Revised:2017-06-12 Online:2018-05-15 Published:2018-05-15
  • Supported by:

    The second author's research was supported by Program for Innovative Research Team of Shanghai University of Finance and Economics (IRTSHUFE) and by National Natural Science Foundation of China (NSFC) Project 11471205; the third author's research was supported in part by NSF GOALI 0800151.

Taoran Fu, Dongdong Ge, Yinyu Ye. ON DOUBLY POSITIVE SEMIDEFINITE PROGRAMMING RELAXATIONS[J]. Journal of Computational Mathematics, 2018, 36(3): 391-403.

Recently, researchers have been interested in studying the semidefinite programming (SDP) relaxation model, where the matrix is both positive semidefinite and entry-wise nonnegative, for quadratically constrained quadratic programming (QCQP). Comparing to the basic SDP relaxation, this doubly-positive SDP model possesses additional O(n2) constraints, which makes the SDP solution complexity substantially higher than that for the basic model with O(n) constraints. In this paper, we prove that the doubly-positive SDP model is equivalent to the basic one with a set of valid quadratic cuts. When QCQP is symmetric and homogeneous (which represents many classical combinatorial and nonconvex optimization problems), the doubly-positive SDP model is equivalent to the basic SDP even without any valid cut. On the other hand, the doubly-positive SDP model could help to tighten the bound up to 36%, but no more. Finally, we manage to extend some of the previous results to quartic models.

CLC Number: 

[1] P. Biswas, T.C. Lian, T.C. Wang and Y. Ye, Semidefinite programming based algorithms for sensor network localization, ACM Trans. Sens. Netw., 2:2(2006), 188-220.

[2] I.M. Bomze and E. de Klerk, Solving standard quadratic optimization problems via linear, semidefinite and copositive programming, J. Global Optim., 24:2(2002), 163-185. Dedicated to Professor Naum Z. Shor on his 65th birthday.

[3] S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 120:2(2009), 479-495.

[4] S. Burer, K.M. Anstreicher and M. Dür, The difference between 5×5 doubly nonnegative and completely positive matrices, Linear Algebra Appl., 431:9(2009), 1539-1552.

[5] H. Dong and K. Anstreicher, Separating doubly nonnegative and completely positive matrices, Math. Program., 137:1(2013), 131-153.

[6] M.X. Goemans and D.P. Williamson, Improved approximation algorithms for Maximum Cut and Satisfiability problems using semidefinite programming, J. ACM, 42:6(1995), 1115-1145.

[7] B. Jiang, Z. Li and S. Zhang, On cones of nonnegative quartic forms, Found. Comput. Math., 17:1(2017), 161-197.

[8] B. Jiang, S. Ma and S. Zhang, Tensor principal component analysis via convex optimization, Math. Program., 150:2(2015), 423-457.

[9] P.M. Kleniati, P. Parpas and B.Rustem, Procedure for Polynomial Optimization:Application to Portfolio Decisions with Higher Order Moments, COMISEF, 2009.

[10] Q. Kong, C. Lee, C.P. Teo and Z. Zheng, Scheduling Arrivals to a Stochastic Service Delivery System using Copositive Cones, Oper. Res., 61:3(2013), 711-726.

[11] K. Natarajan, C.P. Teo and Z. Zheng, Mixed zero-one linear programs under objective uncertainty:a completely positive representation, Oper. Res., 59:3(2011), 713-728.

[12] Yu.E. Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optimiz. Meth. Software, 9:1(1998), 141-160. Special Issue Celebrating the 60th Birthday of Professor Naum Shor.

[13] P. Parrilo, Structured Semidefinite Programs and Semi-algebraic Geometry Methods in Robustness and Optimization, PhD thesis, California Institute of Technology, 2000.

[14] S. Poljak, F. Rendl and H. Wolkowicz. A recipe for semidefinite relaxation for (0, 1)-quadratic programming. J. Global Optim., 7:1(1995), 51-73.

[15] W.F. Sheppard, On the calculation of the double integral expressing normal correlation, Trans. Camb. Philos. Soc., 19(1900), 23-66.

[16] Y. Ye, Approximating quadratic programming with bound and quadratic constraints, Math. Program., 84:2(1999), 219-226.

[17] Y. Ye, A.699-approximation algorithm for Max-Bisection, Math. Program., 90:1(2001), 101-111.
[1] Yaolin Jiang, Zhen Miao. QUASI-NEWTON WAVEFORM RELAXATION BASED ON ENERGY METHOD [J]. Journal of Computational Mathematics, 2018, 36(4): 542-562.
[2] Xi Yang. ON SOLVABILITY AND WAVEFORM RELAXATION METHODS FOR LINEAR VARIABLE-COEFFICIENT DIFFERENTIAL-ALGEBRAIC EQUATIONS [J]. Journal of Computational Mathematics, 2014, 32(6): 696-720.
[3] Haibao Chen, Yaolin Jiang. AN ACCELERATED WAVEFORM RELAXATION APPROACH BASED ON MODEL ORDER REDUCTION FOR LARGE COUPLING SYSTEMS [J]. Journal of Computational Mathematics, 2013, 31(2): 190-208.
[4] Mohammed Seaid . MULTIDIMENSIONAL RELAXATION APPROXIMATIONS FOR HYPERBOLIC SYSTEMS OFCONSERVATION LAWS [J]. Journal of Computational Mathematics, 2007, 25(4): 440-457.
[5] Yao-lin Jiang. WAVEFORM RELAXATION METHODS OF NONLINEAR INTEGRAL-DIFFERENTIAL-ALGEBRAIC EQUATIONS [J]. Journal of Computational Mathematics, 2005, 23(1): 49-128.
[6] Jian Yu PAN, Zhong Zhi BAI. ON THE CONVERGENCE OF WAVEFORM RELAXATION METHODS FOR LINEAR INITIAL VALUE PROBLEMS [J]. Journal of Computational Mathematics, 2004, 22(5): 681-698.
[7] Zhong Zhi BAI,YU Guang HUANG. A CLASS OF ASYNCHRONOUS PARALLEL MULTISPLITTING RELAXATION METHODS FOR LARGE SPARSE LINEAR COMPLEMENTARITY PROBLEMS$^*1$ [J]. Journal of Computational Mathematics, 2003, 21(6): 773-790.
[8] Zhong Zhi BAI,Xue Bin CHI. ASYMPTOTICALLY OPTIMAL SUCCESSIVE OVERRILAXATION METHODS FOR SYSTEMS OF LINEAR EQUATIONS$^*1$ [J]. Journal of Computational Mathematics, 2003, 21(5): 603-612.
[9] Da Chuan XU,Ji Ye HAN. APPROXIMATION ALGORITHM FOR MAX-BISECTION PROBLEM WITH THE POSITIVE SEMIDEFINITE RELAXATION [J]. Journal of Computational Mathematics, 2003, 21(3): 357-366.
[10] Zhong Zhi BAI,Yu Guang HUANG. RELAXED ASYNCHRONOUS ITERATIONS FOR THE LINEAR COMPLEMENTARITY PROBLEM [J]. Journal of Computational Mathematics, 2002, 20(1): 97-112.
[11] Zhong-zhi Bai,Tin-zhu Huang. ON THE CONVERGENCE OF THE RELAXATION METHODS FOR POSITIVE DEFINITELINEAR SYSTEMS [J]. Journal of Computational Mathematics, 1998, 16(6): 527-538.
[12] Zhong-zhi Bai,De-ren Wang,D.J. Evans. A CLASS OF ASYNCHRONOUS MATRIX MULTI-SPLITTING MULTI-PARAMETERRELAXATION ITERATIONS [J]. Journal of Computational Mathematics, 1998, 16(3): 221-238.
Viewed
Full text


Abstract