On degeneracy in exploration of combinatorial tree in multi-parametric quadratic programming

Parisa Ahmadi-Moshkenani 1 Tor Johansen 1 Sorin Olaru 2, 3
2 DISCO - Dynamical Interconnected Systems in COmplex Environments
L2S - Laboratoire des signaux et systèmes, Inria Saclay - Ile de France, SUPELEC, CNRS - Centre National de la Recherche Scientifique : UMR8506
Abstract : The recently proposed combinatorial approach for multi-parametric quadratic programming (mpQP) has shown to be more efficient than geometric approaches in finding the complete solution when dealing with systems with high dimension of the parameter vector. This method, however, tends to become very slow as the number of constraints increases. Recently, a modification of the combinatorial method is proposed which exploits some of the underlying geometric properties of adjacent critical regions to exclude a noticeable number of feasible but not optimal candidate active sets from the combinatorial tree. This method is followed by a post-processing algorithm based on the geometric operations to assure that the complete solution is found which is time-consuming and prone to numerical errors in high-dimensional systems. In this paper, we characterize degenerate optimal active sets and modify the exploration algorithm such that the complete solution is guaranteed to be found in a general case, which can have degeneracies as well, concurrent with the exploration of combinatorial tree. Simulation results confirm the reliability of the suggested method in finding all critical regions while decreasing the computational time significantly.
Type de document :
Communication dans un congrès
55th IEEE Conference on Decision and Control (CDC 2016), Dec 2016, Las Vegas, United States. 26, pp.2320 - 2326, 2016, 〈10.1109/CDC.2016.7798609〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal-centralesupelec.archives-ouvertes.fr/hal-01408493
Contributeur : Sorin Olaru <>
Soumis le : mardi 10 janvier 2017 - 19:35:41
Dernière modification le : jeudi 26 avril 2018 - 16:26:22
Document(s) archivé(s) le : mardi 11 avril 2017 - 13:21:34

Fichier

CDC16_0950_FI.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Parisa Ahmadi-Moshkenani, Tor Johansen, Sorin Olaru. On degeneracy in exploration of combinatorial tree in multi-parametric quadratic programming. 55th IEEE Conference on Decision and Control (CDC 2016), Dec 2016, Las Vegas, United States. 26, pp.2320 - 2326, 2016, 〈10.1109/CDC.2016.7798609〉. 〈hal-01408493〉

Partager

Métriques

Consultations de la notice

750

Téléchargements de fichiers

84