Improving Lagrange Dual Bounds for Quadratic Extremal Problems

Abstract

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: 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 of improving them. When for quadratic convex optimization problems such bounds are exact, for other cases this question is rather complicated. For non-convex cases for improving the dual bounds (reducing the duality gap) techniques based on the ambiguity of the problem formulations 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 existing constraints). The ways to construct such constraints can be general in nature or use the features of a specific problem. 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. The possibility of using other special techniques, which use the features of specific problems, for constructing functionally superfluous constraints is also noted. 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