Efficient semidefinite methods for solving quadratic problems

Authors

  • A. I. Kosolap Department of Specialized Computer Systems, State Higher Education Establishment “Ukrainian State University of Chemical Technology”, 40, Naberezhna Peremogy str., Dnipro, 49005, Ukraine
  • A. S. Peretiatko Department of Specialized Computer Systems, State Higher Education Establishment “Ukrainian State University of Chemical Technology”, 40, Naberezhna Peremogy str., Dnipro, 49005, Ukraine

Keywords:

quadratic problems, semidefinite optimization, improvement of solution bounds, local search, semidefinite relaxation, quadratic optimization

Abstract

Purpose. The purpose of this article is to develop new and effective methods for solving quadratic problems. Such tasks arise in economy, finance, management, technological processes, informatics and other fields. A distinctive feature of these problems is their large dimension and complexity for the numerical attack. In this paper a modification of semidefinite optimization problems is considered, which makes it possible to find more accurate bounds of quadratic problems solutions. Methodology. In this paper quadratic problems are transformed into general semidefinite optimization problem, and then a local search method is applied to solve it. The nonnegativity constraint of variables are written in the form of quadratic constraints xi (xi - a) ≤ 0. The number of such constraints is n. The form of such constraints in the formulation of semidefinite optimization problem is matrix with successive shift of non-zero elements. The value of a is chosen such that the condition x ≤ a is satisfied. When we solve semidefinite optimization problems, we use the variation of the parameter a. Findings. Comparative computational experiments were conducted with the problems of different dimensions. Evolutionary search and semidefinite optimization were used. In all cases, the method of semidefinite optimization with local search gave the best solution. As numerical experiments have shown, the value of parameter a affects the accuracy of bounds of the original quadratic problem solution. Parameter increment allows obtaining more accurate bounds of the solution. Originality. In this paper we propose to use semidefinite optimization methods with local search for solving general quadratic problems, and for improvement the semidefinite relaxation we propose to produce a successive restriction of feasible region by varying the parameter a. Practical value. The considered method can be used to find solution of applications that can be formulated as general quadratic programming problems. Comparative experiments confirm the effectiveness of this approach for solving such problems.

Author Biographies

A. I. Kosolap, Department of Specialized Computer Systems, State Higher Education Establishment “Ukrainian State University of Chemical Technology”, 40, Naberezhna Peremogy str., Dnipro, 49005

Dr. Sc. (Phys.-Math.), Prof.

A. S. Peretiatko, Department of Specialized Computer Systems, State Higher Education Establishment “Ukrainian State University of Chemical Technology”, 40, Naberezhna Peremogy str., Dnipro, 49005

Ph.D. (Phys.-Math.)

References

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

Peretiatko A.S. Napivvyznachena optymizatsiia dlia rozviazuvannia zahalnykh kvadratychnykh zadach [Semidefinite optimization for solving general quadratic problems. Abstract of Ph. D. dissertation]. Kharkivskyi natsionalnyi universytet radioelektroniky [Kharkiv National University of Radio Electronics]. Kharkiv, 2015, 20 p. (in Ukrainian).

Ben-Tal A. and Nemirovski A. Robust Truss Topology Design via Semidefinite Programming. SIAM Journal on Optimization, 1997, Vol. 7, No. 4, pp. 991-1016. Available at: https://doi.org/10.1137/S1052623495291951.

Bie T.D. Deploying SDP for machine learning. Available at: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.1885&rep=rep1&type=pdf.

Dominguez J. and González-Lima M.D. A primal-dual interior-point algorithm for quadratic programming. Numerical Algorithms, 2006, Vol. 42, pp. 1–30. Available at: https://link.springer.com/article/10.1007/s11075-006-9019-5.

Gepp A.A. Review of Semidefinite programming including Financial Applications. 2006, 29 p.

Gill P.E. and Wong E. Methods for Convex and General Quadratic Programming. 2014, 37 p. Available at: http://www.ccom.ucsd.edu/~peg/papers/genqp.pdf.

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

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

Roumili H., Keraghel A. and 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.

So A.M.-C. and Ye Y. Theory of semidefinite programming for Sensor Network Localization. Mathematical Programming, 2007, Vol. 109, pp. 367–384. Available at: https://link.springer.com/article/10.1007/s10107-006-0040-1.

Tuncel L. Some Applications of Semidefinite Optimization from an Operations Research Viewpoint. 2008, 28 p. Available at: https://www.math.uwaterloo.ca/~ltuncel/publications/IOR-invited-survey.pdf.

Wen Z., Goldfarb D. and 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

2017-10-24

Issue

No. 101 (2017)

Section

Computer systems and information technologies in education, science and management

License

Редакція  Видання категорично засуджує прояви плагіату в статтях та вживає всіх можливих заходів для його недопущення. Плагіат розглядається як форма порушення авторських прав і наукової етики.

При виявлені у статті більш ніж 25% запозиченого тексту без відповідних посилань та використання лапок, стаття кваліфікується як така, що містить плагіат. У цьому випадку стаття більше не розглядається редакцією, а  автор отримує перше попередження.

Автори, в статтях яких повторно виявлено плагіат, не зможуть публікуватися в усіх журналах Видавництва ДВНЗ «Придніпровська державна академія будівництва та архітектури».

Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:

  1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
  2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
  3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).