2020, issue 1, p. 15-22
Received 03.03.2020; Revised 07.03.2020; Accepted 10.03.2020
Published 31.03.2020; First Online 26.04.2020
https://doi.org/10.34229/2707-451X.20.1.2
Previous | Full text (in Ukrainian) | Next
Improving LagrangE Dual bounds for Quadratic Extremal Problems
Oleg
Berezovskyi 1 * 
1 V.M. Glushkov Institute of Cybernetics, Kyiv, Ukraine
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. Due to the fact that quadratic extremal problems are generally NP-hard, various convex relaxations to find bounds for their global extrema are used, namely, Lagrangian relaxation, SDP-relaxation, SOCP-relaxation, LP-relaxation, and others. This article investigates a dual bound that results from the Lagrangian relaxation of all constraints of quadratic extremal problem. The main issue when using this approach for solving quadratic extremal problems is the quality of the obtained bounds (the magnitude of the duality gap) and the possibility to improve them. While for quadratic convex optimization problems such bounds are exact, in other cases this issue is rather complicated. In non-convex cases, to improve the dual bounds (to reduce the duality gap) the techniques, based on ambiguity of the problem formulation, can be used. The most common of these techniques is an extension of the original quadratic formulation of the problem by introducing the so-called functionally superfluous constraints (additional constraints that result from available constraints). The ways to construct such constraints can be general in nature or they can use specific features of the concrete problems.
The purpose of the article is to propose methods for improving the Lagrange dual bounds for quadratic extremal problems by using technique of functionally superfluous constraints; to present examples of constructing such constraints.
Results. The general concept of using functionally superfluous constraints for improving the Lagrange dual bounds for quadratic extremal problems is considered. Methods of constructing such constraints are presented. In particular, the method proposed by N.Z. Shor for constructing functionally superfluous constraints for quadratic problems of general form is presented in generalized and schematized forms. Also it is pointed out that other special techniques, which employ the features of specific problems for constructing functionally superfluous constraints, can be used.
Conclusions. In order to improve dual bounds for quadratic extremal problems, one can use various families of functionally superfluous constraints, both of general and specific type. In some cases, their application can improve bounds or even provide an opportunity to obtain exact values of global extrema.
Keywords: quadratic extremal problem, Lagrangian relaxation, dual bound, functionally superfluous constraints.
Cite as: Berezovskyi O. Improving Lagrange Dual Bounds for Quadratic Extremal Problems. Cybernetics and Computer Technologies. 2020. 1. 15–22. (in Ukrainian) https://doi.org/10.34229/2707-451X.20.1.2
References
1. Shor N.Z., Stetsenko S.I. Quadratic extremal problems and nondifferentiable optimization. Kiev, Naukova Dumka, 1989. 208 с. (in Russian)
2. Lemaréchal C. Lagrangian relaxation. Computational combinatorial optimization. 2001. P. 112–156. https://doi.org/10.1007/3-540-45586-8_4
3. Nesterov Y., Wolkowicz H., Ye Y. Semidefinite programming relaxations of nonconvex quadratic optimization. Handbook of semidefinite programming. New York: Springer US, 2000. P. 361–419. https://doi.org/10.1007/978-1-4615-4381-7_13
4. Kim S., Kojima M. Second order cone programming relaxation of nonconvex quadratic optimization problems. Optimization methods and software. 2001. 15(3). P. 201–224. https://doi.org/10.1080/10556780108805819
5. Qualizza A., Belotti P., Margot F. Linear programming relaxations of quadratically constrained quadratic programs. Mixed Integer Nonlinear Programming. NY: Springer. 2012. P. 407–426. https://doi.org/10.1007/978-1-4614-1927-3_14
6. Berezovskyi O.A. On the accuracy of dual bounds for quadratic extremum problems. Cybernetics and Systems Analysis. 2012. 48 (1). P. 26–30. https://doi.org/10.1007/s10559-012-9389-8
7. Berezovskyi O.A. On Solving of a Special Optimization Problem Connected with Determination of Invariant Sets of Dynamical Systems, Journal of Automation and Information Sciences, 2015. 47 (5). P. 69–77. https://doi.org/10.1615/JAutomatInfScien.v47.i5.60
8. Stetsyuk P.I. Functionally redundant constraints for Boolean quadratic-type optimization problems. Cybernetics and Systems Analysis. 2005. 41 (6). P. 932–935. https://doi.org/10.1007/s10559-006-0029-z
9. Sherali H.D., Adams W.P. A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Dordrecht: Kluwer, 1998. 516 p. https://doi.org/10.1007/978-1-4757-4388-3
10. Yajima Y., Fujie T. A polyhedral approach for nonconvex quadratic programming problems with box constraints. Journal of Global Optimization. 1998. 13. P. 151–170. https://doi.org/10.1023/A:1008293029350
11. Stetsyuk P.I. New quadratic models for the maximum weighted cut problem. Cybernetics and Systems Analysis. 2006. 42 (1). P. 54–64. https://doi.org/10.1007/s10559-006-0037-z
12. Berezovskyi O.A. On the lower bound for a quadratic problem on the Stiefel manifold. Cybernetics and Systems Analysis. 2008. 44 (5). P. 709–715. https://doi.org/10.1007/s10559-008-9038-4
13. Fujit T., Kojima M. Semidefinite programming relaxation for nonconvex quadratic problems. Journal of Global Optimization. 1997. 10. P. 367–380. https://doi.org/10.1023/A:1008282830093
14. Berezovskyi O.A. Exactness Criteria for SDP-Relaxations of Quadratic Extremum Problems. Cybernetics and Systems Analysis. 2016. 52 (6). P. 915–920. https://doi.org/10.1007/s10559-016-9893-3
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | Full text (in Ukrainian) | Next