The sufficient condition to find an exact dual bound in a separable quadratic optimization problem

Fìz.-mat. model. ìnf. tehnol. 2021, 32:42-45

Abstract

The paper considers nonconvex separable quadratic optimization problems subject to inequality constraints. A sufficient condition is given for finding the value and the point of the global extremum of a problem of this type by calculating the Lagrange dual bound. The peculiarity of this condition is that it is easily verified and requires from the Hessian matrix of the Lagrange function only that its region of positive definiteness is not empty. The result obtained for the dual bound also holds for the bound obtained using SDP relaxation.

References

1. Shor, N. Z., Stetsenko, S. I. (1989). Quadratic extremal problems and nondifferentiable optimization. Naukova Dumka, Kiev.
2. Berezovskyi, O. A. (2017). Zero duality gap in quadratically constrained quadratic programming. Mathematical and computer modelling. Series: Physical and mathematical sciences, 15, 20-25.
3. Nesterov, Y., Wolkowicz, H., Ye, Y. (2000). Semidefinite programming relaxations of nonconvex quadratic optimization. Handbook of semidefinite programming, Springer, New York, 361-419.
   DOI doi.org/10.1007/978-1-4615-4381-7_13
4. Berezovskyi, O. A. (2016). Exactness criteria for SDP-relaxations of quadratic extremum problems. Cybernetics and Systems Analysis, 52(6), 915-920.
   DOI doi.org/10.1007/s10559-016-9893-3