Moment approximations for set-semidefinite polynomials. (English) Zbl 1293.90049
The paper provides outer approximations to the set of set-semidefinite polynomials which, by definition, is the set of polynomials that are nonnegative over a subset of the nonnegative orthant. Further specifications of the polynomials are permitted. Set-semidefinite polynomials have applications, for example, in combinatorial optimization, signal processing, quantum mechanics, and statistics. In their analysis the authors relate to results of J. B. Lasserre [SIAM J. Optim. 21, No. 3, 864–885 (2011; Zbl 1242.90176)] who previously used moments to provide an outer approximation of the set of polynomials which are nonnegative over a general closed subset of the real space. Through restriction to completely positive moment matrices, a new outer approximation hierarchy for the set of set-semidefinite polynomials can be provided. The ideas used yield new insights into the application of moments for the construction of such type of approximations. The convergence of the proposed hierarchies is demonstrated for some small-scale examples.
Reviewer: Rembert Reemtsen (Cottbus)
Keywords:
nonnegative polynomials; set-semidefinite polynomials; copositive programming; doubly nonnegative matrices; moments; completely positive matricesCitations:
Zbl 1242.90176References:
| [1] | Bomze, I.M.: Copositive optimization—Recent developments and applications. Eur. J. Oper. Res. 216(3), 509-520 (2012) · Zbl 1262.90129 · doi:10.1016/j.ejor.2011.04.026 |
| [2] | Bomze, I.M., Dür, M., Teo, C.-P.: Copositive optimization. Optima Newsl. 89, 2-8 (2012) |
| [3] | Burer, S.: Copositive Programming. International Series in Operations Research & Management Science, vol. 166, pp. 201-218. Springer, Berlin (2012) · Zbl 1334.90098 |
| [4] | Dür, M.; Diehl, M. (ed.); Glineur, F. (ed.); Jarlebring, E. (ed.); Michiels, W. (ed.), Copositive programming—a survey, 3-20 (2010), Berlin · doi:10.1007/978-3-642-12598-0_1 |
| [5] | Hiriart-Urruty, J.-B., Seeger, A.: A variational approach to copositive matrices. SIAM Rev. 52(4), 593-629 (2010) · Zbl 1207.15037 · doi:10.1137/090750391 |
| [6] | Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39(2), 117-129 (1987) · Zbl 0637.90078 · doi:10.1007/BF02592948 |
| [7] | Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120(2), 479-495 (2009) · Zbl 1180.90234 · doi:10.1007/s10107-008-0223-z |
| [8] | de Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875-892 (2002) · Zbl 1035.90058 · doi:10.1137/S1052623401383248 |
| [9] | Povh, J., Rendl, F.: A copositive programming approach to graph partitioning. SIAM J. Optim. 18(1), 223-241 (2007) · Zbl 1143.90025 · doi:10.1137/050637467 |
| [10] | Povh, J., Rendl, F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6(3), 231-241 (2009) · Zbl 1167.90597 · doi:10.1016/j.disopt.2009.01.002 |
| [11] | Eichfelder, G., Jahn, J.: Set-semidefinite optimization. J. Convex Anal. 15(4), 767-801 (2008) · Zbl 1172.90013 |
| [12] | Eichfelder, G.; Jahn, J., Foundations of set-semidefinite optimization, No. 35, 259-284 (2010), New York · Zbl 1181.90213 · doi:10.1007/978-1-4419-0158-3_18 |
| [13] | Eichfelder, G., Povh, J.: On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets. Optim. Lett. (2013, in print). doi:10.1007/s11590-012-0450-3 · Zbl 1298.90064 |
| [14] | Dickinson, P.J.C., Eichfelder, G., Povh, J.: Erratum to the paper “On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets”. Optim. Lett. (2013, to appear) · Zbl 1298.90063 |
| [15] | Anjos, M.F., Lasserre, J.B.: Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications. International Series in Operational Research and Management Science, vol. 166. Springer, Berlin (2012) · Zbl 1235.90002 · doi:10.1007/978-1-4614-0769-0 |
| [16] | Lasserre, J.B.: New approximations for the cone of copositive matrices and its dual. Preprint. (2012, submitted). Available at: http://arxiv.org/abs/1012.2552 · Zbl 1292.15034 |
| [17] | Lasserre, J.B.: A new look at nonnegativity on closed sets and polynomial optimization. SIAM J. Optim. 21(3), 864-885 (2011) · Zbl 1242.90176 · doi:10.1137/100806990 |
| [18] | Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College Press Optimization Series, vol. 1. Imperial College Press, London (2010) · Zbl 1211.90007 |
| [19] | Laurent, M., Sums of squares, moment matrices and optimization over polynomials, No. 149, 157-270 (2009), New York · Zbl 1163.13021 · doi:10.1007/978-0-387-09686-5_7 |
| [20] | Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific, River Edge (2003) · Zbl 1030.15022 · doi:10.1142/9789812795212 |
| [21] | Dickinson, P.J.C., Gijben, L.: On the computational complexity of membership problems for the completely positive cone and its dual. Preprint. (2012, submitted). Available at: http://www.optimization-online.org/DB_HTML/2011/05/3041.html · Zbl 1330.90103 |
| [22] | Maxfield, J.E., Minc, H.: On the matrix equation X′X=A. Proc. Edinb. Math. Soc. 13(02), 125-129 (1962) · Zbl 0112.25101 · doi:10.1017/S0013091500014681 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
