\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming

Abstract Related Papers Cited by
  • In this paper, we provide a computable representation of the cone of nonnegative quadratic forms over a general nontrivial second-order cone using linear matrix inequalities (LMI). By constructing a sequence of such computable cones over a union of second-order cones, an efficient algorithm is designed to find an approximate solution to a completely positive programming problem using semidefinite programming techniques. In order to accelerate the convergence of the approximation sequence, an adaptive scheme is adopted, and ``reformulation-linearization technique'' (RLT) constraints are added to further improve its efficiency.
    Mathematics Subject Classification: Primary: 90C26, 90C59, 90C22; Secondary: 30E10.

    Citation:

    \begin{equation} \\ \end{equation}
  • [1]

    K. Anstreicher, Semidefinite programming versus the Reformulation-Linearization Technique for nonconvex quadratically constrained quadratic programming, Journal of Global Optimization, 43 (2009), 471-484.doi: 10.1007/s10898-008-9372-0.

    [2]

    A. Ben-Tal and A. Nemirovski, "Lectures on Modern Convex Optimization Analysis, Algorithms and Engineering Applications," SIAM, Philadelphis, 2001.doi: 10.1137/1.9780898718829.

    [3]

    I. Bomze and E. de Klerk, Solving standard quadratic optimization problem via linear, semidefinite and copositive programming, Journal of Global Optimization, 24 (2002), 163-185.doi: 10.1023/A:1020209017701.

    [4]

    I. Bomze and G. EichfelderCopositivity Detection by difference-of-convex decomposition and $\omega$-subdivision, to appear in Mathematical Programming. doi: 10.1007/s10107-012-0543-x.

    [5]

    I. Bomze, F. Jarre and F. Rendl, Quadratic factorization heuristics for copositive programming, Mathematical Programming Computation, 3 (2011), 37-57.doi: 10.1007/s12532-011-0022-z.

    [6]

    M. Brockington and J. Culberson, "Camouflaging Independent Sets in Quasi-random Graphs," Clique Coloring and Satisfiability: Second DIMACS Implementation Challenge, 26, Amer Mathematical Society, 1994.

    [7]

    S. Bundfuss and M. Dür, An adaptive linear approximation algorithm for copositive programs, SIAM Journal on Optimization, 20 (2009), 30-53.doi: 10.1137/070711815.

    [8]

    S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Mathematical Programming, 120 (2009), 479-495.doi: 10.1007/s10107-008-0223-z.

    [9]

    S. Burer and K. Anstreicher, Second-order cone constraints for extended trust-region subproblems, submitted to SIAM Journal on Optimization, (2011).doi: 10.1137/110826862.

    [10]

    Z. Deng, S.-C. Fang, Q. Jin and W. Xing, Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme, accepted by European Journal of Operational Research, (2013).doi: 10.1016/j.ejor.2013.02.031.

    [11]
    [12]

    M. Dür, "Copositive Programming: A Survey," Recent Advances in Optimization and Its Application in Engineering, Springer, New York, 2012.

    [13]

    N. Govozdenovic and M. Laurent, The operator $\Psi$ for the chromatic number of a graph, SIAM Journal on Optimization, 19 (2008), 572-591.doi: 10.1137/050648237.

    [14]

    M. Grant and S. Boyd, "CVX: matlab Software for Disciplined Programming," version 1.2, 2010. http://cvxr.com/cvx

    [15]

    P. Hansen, B. Jaumard, M. Ruiz and J. Xiong, Global minimization of indefinite quadratic functions subject to box constraints, Naval Research Logistics, 40 (1993), 373-392.doi: 10.1002/1520-6750(199304)40:3<373::AID-NAV3220400307>3.0.CO;2-A.

    [16]

    K. Ikramov, Linear-time algorithm for verifying the copositivity of an acyclic matrix, Computational Mathematics and Mathmetical Physics, 42 (2002), 1701-1703.

    [17]

    E. de Klerk and D. Pasechnik, Approximation of the stability number of a graph via copositive programming, Journal of Global Optimization, 12 (2002), 875-892.doi: 10.1137/S1052623401383248.

    [18]

    C. Lu, S.-C. Fang, Q. Jin, Z. Wang and W. Xing, KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems, SIAM Journal on Optimization, 21 (2010), 1475-1490.doi: 10.1137/100793955.

    [19]

    C. Lu, Q. Jin, S.-C. Fang, Z. Wang and W. Xing, An LMI based adaptive approximation scheme to cones of nonnegative quadratic functions, Submitted to Mathematical Programming, (2011).

    [20]

    T. Motzkin and E. Straus, Maxima for graphs and a new proof of a theorem of Turan, Canadian Journal of Mathematics, 17 (1965), 533-540.doi: 10.4153/CJM-1965-053-6.

    [21]

    K. Murty and S. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Mathematical Programming, 39 (1987), 117-129.doi: 10.1007/BF02592948.

    [22]

    J. Povh and F. Rendl, Copositive and semidefinite relaxations of the quadratic assignment problem, Discrete Optimization, 6 (2009), 231-241.doi: 10.1016/j.disopt.2009.01.002.

    [23]

    J. Preisig, Copositivity and the minimization of quadratic functions with nonnegativity and quadratic equality constraints, SIAM Journal on Control and Optimization, 34 (1996), 1135-1150.doi: 10.1137/S0363012993251894.

    [24]

    R. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, 1996.

    [25]

    N. Sahinidis and M. Tawarmalani, "BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs," 2010. http://archimedes.cheme.cmu.edu/baron/baron.html

    [26]

    L. Sanchis, Test case construction for the vertex cover problem, in "Computational Support for Discrete Mathematics," DIMACS Series in Discrete Mathematics and Theoretical American Mathematical Society, 15 (1992), Providence, Rhodle Island, (1992).

    [27]

    J. Sturm, SeDuMi 1.02, a matlab tool box for optimization over symmetric cones, Optimization Methods and Software, 11$&$12 (1999), 625-653.doi: 10.1080/10556789908805766.

    [28]

    J. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267.doi: 10.1287/moor.28.2.246.14485.

    [29]

    Y. Ye and S. Zhang, New results on quadratic minimization, SIAM Journal on Optimization, 14 (2003), 245-267.doi: 10.1137/S105262340139001X.

    [30]

    J. Žilinskas, Copositive programming by simplicial partition, Informatica, 22 (2011), 601-614.

  • 加载中
SHARE

Article Metrics

HTML views() PDF downloads(160) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return