Completely positive reformulations for polynomial optimization

详细信息    查看全文

• 作者：Javier Pe?a ; Juan C. Vera ; Luis F. Zuluaga
• 关键词：Polynomial optimization ; Copositive programming ; Completely positive tensors ; Quadratic programming ; 90C26 ; 90C20
• 刊名：Mathematical Programming
• 出版年：2015
• 出版时间：July 2015
• 年：2015
• 卷：151
• 期：2
• 页码：405-431
• 全文大小：667 KB
• 参考文献：1.Amaral, P., Bomze, I.M., Júdice, J.: Copositivity and constrained fractional quadratic problems. Math. Program. 146(1-), 325-50 (2014)View Article MATH MathSciNet
  2.Anjos, M., Lasserre, J.B. (eds.): Handbook on Semidefinite, Conic and Polynomial Optimization Handbook on Semidefinite, Conic and Polynomial Optimization, volume 166 of International Series in Operations Research & Management Science. Springer, Berlin (2012)
  3.Arima, N., Kim, S., Kojima, M. A Quadratically Constrained Quadratic Optimization Model for Completely Positive Cone Programming. Technical Report B-468, Dept. of Math. and Comp. Sciences, Tokyo Institute of Technology. http://?www.?optimization-online.?org/?DB_?FILE/-012/-9/-600.?pdf (2012)
  4.Bai, L., Mitchell, J.E., Pang, J.: On QPCCs, QCQPs and Copositive Programs. Technical report, Rensselaer Polytechnic Institute. http://?eaton.?math.?rpi.?edu/?faculty/?Mitchell/?papers/?QCQP_?QPCC.?html (2012)
  5.Bertsekas, D.P.: Non-linear Programming. Athena Scientific, Belmont, MA (1995)
  6.Bertsimas, D., Popescu, I.: On the relation between option and stock prices: an optimization approach. Oper. Res. 50, 358-74 (2002)View Article MATH MathSciNet
  7.Bertsimas, D., Popescu, I.: Optimal inequalities in probability theory: a convex optimization approach. SIAM J. Optim. 15(3), 780-04 (2005)View Article MATH MathSciNet
  8.Blekherman, G., Parrilo, P., and Thomas, R. (eds): Semidefinite Optimization and Convex Algebraic Geometry, volume 13 of MOS-SIAM Series on Optimization. SIAM, Philadelphia (2012)
  9.Bomze, I., de Klerk, E.: Solving standard quadratic optimization problems via semidefinite and copositive programming. J. Global Optim. 24(2), 163-85 (2002)View Article MATH MathSciNet
  10.Bomze, I., Jarre, F.: A note on Burer’s copositive representation of mixed-binary QPs. Optim. Lett. 4(3), 465-72 (2010)View Article MATH MathSciNet
  11.Bomze, I.M.: Copositive optimization. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, 2nd edn, pp. 561-64. Springer, Berlin (2009)View Article
  12.Bomze, I.M.: Copositive Relaxation Beats Lagrangian Dual Bounds In Quadratically And Linearly Constrained QPs. Technical Report NI13064-POP, Isaac Newton Institute (2013)
  13.Bomze, I.M.: Copositive-Based Approximations for Binary and Ternary Fractional Quadratic Optimization. Technical Report NI14043-POP, Isaac Newton Institute (2014)
  14.Bomze, I.M., Dür, M., De Klerk, E., Roos, C., Quist, A.J., Terlaky, T.: On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18, 301-20 (2000)View Article MATH
  15.Bomze, I.M., Jarre, F., Rendl, F.: Quadratic factorization heuristics for copositive programming. Math. Program. Comput. 3(1), 37-7 (2011)View Article MATH MathSciNet
  16.Bundfuss, S.: Copositive Matrices, Copositive Programming, and Applications. Ph.D. thesis, TU Darmstadt (2009)
  17.Bundfuss, S., Dür, M.: An adaptive linear approximation algorithm for copositive programs. SIAM J. Optim. 20(1), 30-3 (2009)View Article MATH MathSciNet
  18.Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120(2), 479-95 (2009)View Article MATH MathSciNet
  19.Burer, S., Dong, H.: Representing quadratically constrained quadratic programs as generalized copositive programs. Oper. Res. Lett. 40(3), 203-06 (2012)View Article MATH MathSciNet
  20.Burer, S., Kim, S., Kojima, M.: Faster, but weaker, relaxations for quadratically constrained quadratic programs. Comput. Optim. Appl. 59(1-), 27-5 (2014)
  21.Chen, J., Burer, S.: Globally solving nonconvex quadratic programming problems via completely positive programming. Math. Program. Comput. 4(1), 33-2 (2012)View Article MATH MathSciNet
  22.de Klerk, E., Laurent, M., Parrilo, P.A.: A PTAS for the minimization of polynomials of fixed degree over the simplex. Theor. Comput. Sci. 361(2-), 210-25 (2006)View Article MATH
  23.de Klerk, E., Pasechnik, D.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875-92 (2002)View Article MATH MathSciNet
  24.Dickinson, P.J., Eichfelder, G., Povh, J.: Erratum to: On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets [optim. letters, 2012]. Optim. Lett. 7(6), 1387-397 (2013)
  25.Doherty, A.C., Parrilo, P.A., Spedalieri, F.M.: An inequality for circle packings proved by semidefinite programming. Phys. Rev. A 69, 022308 (2004)View Article
  26.Dong, H.: Symmetric tensor approximation hierarchies for the completely positive cone. SIAM J. Optim. 23(3), 1850-866 (2013)View Article MATH MathSciNet
  27.Dong, H., Anstreicher, K.: Separating doubly nonnegative and completely positive matrices. Math. Program. Ser. A 137, 131-53 (2013)View Article MATH MathSciNet
  28.Dukanovic, I., Rendl, F.: Copositive programming motivated bounds on the stability and the chromatic numbers.
• 作者单位：Javier Pe?a (1)
  Juan C. Vera (2)
  Luis F. Zuluaga (3)
  
  1. Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA, 15213, USA
  2. Tilburg School of Economics and Management, Tilburg University, Tilburg, The Netherlands
  3. Industrial and Systems Engineering, Lehigh University, Bethlehem, PA, 18015, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well established body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of completely positive matrices, or its conic dual, the cone of copositive matrices. As a result of this reformulation approach, novel solution schemes for quadratic polynomial optimization problems have been designed by drawing on conic programming tools, and the extensively studied cones of completely positive and of copositive matrices. In particular, this approach has been applied to solve key combinatorial optimization problems. Along this line of research, we consider polynomial optimization problems that are not necessarily quadratic. For this purpose, we use a natural extension of the cone of completely positive matrices; namely, the cone of completely positive tensors. We provide a general characterization of the class of polynomial optimization problems that can be formulated as a conic program over the cone of completely positive tensors. As a consequence of this characterization, it follows that recent related results for quadratic problems can be further strengthened and generalized to higher order polynomial optimization problems. Also, we show that the conditions underlying the characterization are conceptually the same, regardless of the degree of the polynomials defining the problem. To illustrate our results, we discuss in further detail special and relevant instances of polynomial optimization problems.