Semidefinite optimization for solving boolean quadratic problems
Keywords:
quadratic optimization, boolean optimization, boolean quadratic problems, semidefinite optimization, semidefinite relaxation, lower and upper bounds.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.
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.
Downloads
Published
Issue
Section
License
Редакція Видання категорично засуджує прояви плагіату в статтях та вживає всіх можливих заходів для його недопущення. Плагіат розглядається як форма порушення авторських прав і наукової етики.
При виявлені у статті більш ніж 25% запозиченого тексту без відповідних посилань та використання лапок, стаття кваліфікується як така, що містить плагіат. У цьому випадку стаття більше не розглядається редакцією, а автор отримує перше попередження.
Автори, в статтях яких повторно виявлено плагіат, не зможуть публікуватися в усіх журналах Видавництва ДВНЗ «Придніпровська державна академія будівництва та архітектури».
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:
- Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
- Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
- Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
