variables Contraindre d'être dans l'une des deux gammes disjoints dans la programmation quadratique

Question

Comment puis-je résoudre un problème d'optimisation quadratique avec les contraintes suivantes:

Réduire au minimum (1/2) X^tqx + C^TX

Sous réserve de -0,01 < x_i < 0,01 ou 0,05 < x_i < 0,20, pour une x_i en X

où Q est la matrice, C, X sont des vecteurs.

Il semble que je ne peux reformuler les contraintes ci-dessus contraintes contraintes liées standard ou inégalité

Answer 1

Notez que la région réalisable ici est non-convexe - si nous avons une solution réalisable avec x 1 = 0,01 et une autre avec x 1 = 0,05 alors toute combinaison appropriée convexe de ces deux solutions sera impossible. En raison de cela, il est impossible démontrable de reformuler ce problème à un programme quadratique standard en utilisant uniquement des variables continues.

Au lieu de cela, vous aurez besoin de recourir à l'utilisation de variables binaires. Par exemple, on pourrait introduire des variables binaires y_i (un par variable x_i) et reformuler le problème comme:

Minimize (1/2)X^TQX + C^TX 
Subject to -0.01 + 0.06y_i <= x_i <= 0.01 + 0.19y_i, for any x_i in X 
y_i binary 

Notez que maintenant une variable avec y_i = 0 vous avez -0,01 < = x_i < = 0,01, et pour toute variable avec y_i = 1 vous avez 0,05 < = x_i < = 0,20.