On globally solving linearly constrained indefinite quadratic minimization problems by decomposition branch and bound method - Université de Lorraine Accéder directement au contenu
Article Dans Une Revue RAIRO - Operations Research Année : 1996

On globally solving linearly constrained indefinite quadratic minimization problems by decomposition branch and bound method

Résumé

The global minimization ofan indefinite quadratic function over a bounded polyhedralset using a décomposition branch and bound approach is considered. The objective functionconsists ofan unseparated convex part and a separated concave part The large-scale problems arecharacterized by hoving the number of convex variables much more thon that of concave variables.The advantages of the method is that it uses the rectangular subdivision on the subspace of concavevariables. Using a easily constmcted convex underestimating function îo the objective function,a lower bound is obtained by solving a convex quadratic programming problem. Three variantsusing exhaustive, adaptive and w-subdivision are discussed. Computational results are presentedfor problems with 10-20 concave variables and up to 200 convex variables.
La minimisation globale d'une forme quadratique indéfinie sur un polyèdre convexeborné par une méthode décomposition-séparation et évaluation est étudiée dans ce papier. Lafonction objectif est la somme d'une forme quadratique convexe et d'une forme quadratique concaveséparable en ses variables. Les problèmes de grande dimension sont caractérisés par le fait quele nombre des variables convexes est beaucoup plus grand que celui des variables concaves.L'avantage de la méthode réside dans l'utilisation de la subdivision rectangulaire uniquementdans le sous-espace des variables concaves. A l'aide d'une minorante très simple à calculer de lapartie concave, une borne inférieure est obtenue en résolvant un programme quadratique convexe.Trois variantes utilisant la subdivision exhautive, la subdivision adaptive et la w-subdivision sontconsidérées. Les simulations numériques sont présentés pour les problèmes ayant 10-20 variablesconcaves et jusqu'à 200 variables convexes.

Dates et versions

hal-01636785 , version 1 (16-11-2017)

Identifiants

Citer

Quynh Phong Thai, Hoai An Le Thi, Tao Pham Dinh. On globally solving linearly constrained indefinite quadratic minimization problems by decomposition branch and bound method. RAIRO - Operations Research, 1996, 30 (1), pp.31 - 49. ⟨10.1051/ro/1996300100311⟩. ⟨hal-01636785⟩
48 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More