Semidefinite optimization for solving boolean quadratic problems

A. I. Kosolap, A. S. Peretiatko

Abstract


Abstract.  Purpose.  We consider boolean quadratic optimization problems. Such problems arise in market economy, planning,  project management, artificial intelligence, optimal design and are NP-hard. In this paper we propose a procedure for finding the  lower and upper bounds of the objective functions of boolean quadratic problems.  Methodology. In this paper we propose to convert  the boolean quadratic problem to the general quadratic optimization problem, and then apply semi definite relaxation to it. Findings. The using of semidefinite relaxation has allowed us to find lower bounds of the objective function or global minimum point with a given accuracy in boolean quadratic problems. Moreover, unlike other methods, testing the  optimality of the found solution doesn`t require exponential time and is quite simple. The upper bound of the objective function, which is found by using the lower es timate  of semidefinite relaxation as a starting point for solving the original problem by local search methods, in 91% of cases coincided with the global minimum of the initial problem.  Originality. A new procedure for finding the upper and lower bounds of objective function was proposed.  Practical value.  The considered method of solution can  be used for finding the solution in applications that can be  formulated as boolean quadratic problems. Comparative numerical experiments confirm the efficiency of this approach to solvin g such problems.


Keywords


quadratic optimization; boolean optimization; boolean quadratic problems; semidefinite optimization; semidefinite relaxation; lower and upper bounds.

References


Kosolap A.I. and Peretiatko A.S. Chislennaya effektivnost metodov poluopredelennoy optimizatsii [Numerical efficiency of semidefinite optimization methods]. Problemy upravleniya i informatiki [Problems of control and informatics], 2014, no. 2, pp. 56–64. (in Russian).

Peretiatko A.S. Napivvyznachena optymizatsiia dlia zadachi klasterizatsii danykh k-clustering [Semidefinite optimization for k-klustering problem]. Materialy Vseukrainskoi naukovo-metodychnoi konferentsii «Problemy matematychnogo modeliuvannia (25.05–27.05.2016)» [Proc. of the All Ukrainian Scientific and Methodical Conf. «Problems of mathematical modelling»]. Dniprodzerzinsk, 2016, pp. 57–60. (in Ukrainian).

Blekherman G., Parrilo P.A.and Rekha R.T. Semidefinite Optimization and Convex Algebraic Geometry. SIAM, 2013, 476 p. Available at: http://www.math.washington.edu/~thomas/frg/frgbook/SIAMBookFinalv Nov12-2012.pdf.

Ding Y., Ge D., Wolkowicz H. On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming. 2010, 23 p. Available at: www.optimization-online.org/DB_FILE/2010/04/2606.pdf.

Horst R., Tuy H. Global Optimization: Deterministic Approaches. 3rd ed.,Berlin, Springer–Verlag, 1996, 727 p.

Karger D., Motwani R., Sudan M. Approximate Graph Coloring by Semidefinite programming. 18 p. Available at: http://dl.acm.org/citation.cfm?id=274791.

Karoussi E. Data Mining K-Clustering Problem. University of Agder, 2012, 80 p. Available at:

https://brage.bibsys.no/xmlui/bitstream/handle/11250/137565/masteroppgave.pdf?sequence=1.

Kenneth V.P., Storn R.M., Lampinen J.A. Differential Evolution. A Practical Approach to Global Optimization. BerlinHeidelberg: Springer-Verlag, 2005, 542 p.

Nesterov Y.E., Nemirovskii A. S. Interior point polynomial algorithms in convex programming. SIAMStudies in Applied Mathematics,SIAM:Philadelphia, 1994, Vol. 13, 405 p.

Nocedal J., Wright S.J. Numerical optimization. Springer, 2006, 685 p.

O’Donnell R. Advanced Approximation Algorithms. Lecture 14: Semidefinite Programming and Max-Cut. 2008, 6 p. Available at: www.cs.cmu.edu/ ~anupamg/adv-approx/lecture14.pdf.

Roumili H., Keraghel A., Yassine A. Infeasible Interior Point Method for Semidefinite Programs. Applied Mathematical Sciences, 2007, Vol. 1, No. 21, pp. 1009–1018. Available at: http://www.m-hikari.com/ams/ams-password-2007/ams-password21-24-2007/roumiliAMS21-24-2007.pdf.

Wen Z., Goldfarb D., Yin W. Alternating Direction Augmented Lagrangian Methods for Semidefinite Programming. Math. Prog, 2010, №2, pp. 203–230. Available at: http://mpc.zib.de/index.php/MPC/article/viewFile/40/20.


GOST Style Citations


1.  Косолап, А. И. Численная эффективность методов полуопределенной оптимизации / А. И. Косолап, А. С. Перетятько // Проблемы управления и информатики. – 2014. – № 2. – С. 56–64.

2.  Перетятько,  А.С.  Напіввизначена  оптимізація  для  задачі  кластеризації  даних  k-clustering  /  А.С.  Перетятько  // Матеріали Всеукраїнської науково-методичної конференції «Проблеми математичного моделювання». –  Дніпродзержинськ, 25-27 травня 2016 р. – С. 57–60.

3.  Blekherman, G.  Semidefinite  Optimization  and  Convex  Algebraic  Geometry  /  Grigoriy  Blekherman,  Pablo  A.  Parrilo, Rekha R. Thomas.  –  Електорон.  дані  (1  файл).  – SIAM,  2013.  –  476  p.  –  Режим  доступу:

http://www.math.washington.edu/~thomas/frg/frgbook/SIAMBookFinalv  Nov12-2012.pdf.  -  Назва  з  екрана.  -  Перевірено 20.09.2016.

4.  Ding, Y. On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming / Y. Ding, D. Ge, H. Wolkowicz.  –Електорон. дані (1 файл).  –  2010.  –  23 p.  –  Режим доступу: www.optimization online.org/DB_FILE/2010/04/2606.pdf. Назва з екрана. - Перевірено 21.09.2016.

5.  Horst, R. Global Optimization: Deterministic Approaches /R. Horst, H. Tuy.  –  3rd ed.,Berlin: Springer–Verlag, 1996.  –727 p.

6.  Karger D. Approximate Graph Coloring by Semidefinite programming  / D. Karger, R. Motwani, M. Sudan.  –  Електорон. дані (1 файл). – 18 p. – Режим доступу: http://dl.acm.org/citation.cfm?id=274791.

7.  Karoussi,  E.  Data  Mining  K-Clustering  Problem  /  E.  Karoussi.  –University  of Agder,  2012.  –  80  p.  –  Режим  доступу: https://brage.bibsys.no/xmlui/bitstream/handle/11250/137565/masteroppgave.pdf?sequence=1.  Назва  з  екрана.  -  Перевірено 21.09.2016.

8.  Kenneth,  V.P.  Differential  Evolution.  A  Practical  Approach  to  Global  Optimization  /  V.P.  Kenneth,  R.M.  Storn,  J.A. Lampinen. –BerlinHeidelberg: Springer-Verlag, 2005. – 542 p.

9.  Nesterov, Y. E. Interior point polynomial algorithms in convex programming / Y. E. Nesterov, A. S. Nemirovskii // SIAM Studies in Applied Mathematics. – 2001. – Vol. 13. –SIAM:Philadelphia,USA. – 405 p.

10.  Nocedal,  J.  Numerical  optimization  /  J.  Nocedal,  S.  J.  Wright.  –  Springer,  2006.  –  685  p.  –  Режим  доступу: http://www.bioinfo.org.cn/~wangchao/maa/Numerical_Optimization.pdf. Назва з екрана. - Перевірено 21.09.2016.

11.  O’Donnell R.  Advanced  Approximation  Algorithms.  Lecture  14:  Semidefinite  Programming  and  Max-Cut  [Електронний ресурс]  /  R.  O’Donnell.  –  Електорон.  дані  (1  файл).  –  2008.  –  6  p.  –  Режим  доступу:  www.cs.cmu.edu/  ~anupamg/advapprox/lecture14.pdf. Назва з екрана. - Перевірено 20.09.2016.

12.  Roumili, H. Infeasible Interior Point Method for Semidefinite Programs / H. Roumili, A. Keraghel, A. Yassine // Applied Mathematical Sciences. – Електорон. дані (1 файл). – 2007. – Vol. 1. – No. 21. – P. 1009–1018. – Режим доступу: http://www.mhikari.com/ams/ams-password-2007/ams-password21-24-2007/roumiliAMS21-24-2007.pdf.  Назва  з  екрана.  -  Перевірено 21.09.2016.

13.  Wen, Z. Alternating Direction Augmented Lagrangian Methods for Semidefinite Programming / Z. Wen, D. Goldfarb, W. Yin  //  Math.  Prog.  –  Електорон.  дані  (1  файл).  –  2010.  –  №2.  –  P.  203–230.  –  Режим  доступу: http://mpc.zib.de/index.php/MPC/article/viewFile/40/20. Назва з екрана. - Перевірено 21.09.2016.



Refbacks

  • There are currently no refbacks.