Optimizing a Parametric Linear Function over a Non-compact Real Algebraic Variety

Abstract : We consider the problem of optimizing a parametric linear function over a non-compact real trace of an algebraic set. Our goal is to compute a representing polynomial which defines a hypersurface containing the graph of the optimal value function. Rostalski and Sturmfels showed that when the algebraic set is irreducible and smooth with a compact real trace, then the least degree representing polynomial is given by the defining polynomial of the irreducible hypersurface dual to the projective closure of the algebraic set. First, we generalize this approach to non-compact situations. We prove that the graph of the opposite of the optimal value function is still contained in the affine cone over a dual variety similar to the one considered in compact case. In consequence, we present an algorithm for solving the considered parametric optimization problem for generic parameters' values. For some special parameters' values, the representing polynomials of the dual variety can be identically zero, which give no information on the optimal value. We design a dedicated algorithm that identifies those regions of the parameters' space and computes for each of these regions a new polynomial defining the optimal value over the considered region.
Type de document :
Communication dans un congrès
The 2015 ACM on International Symposium on Symbolic and Algebraic Computation, Jul 2015, Bath, United Kingdom. ACM, Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, pp.205-212, 2015, 〈10.1145/2755996.2756666〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01237920
Contributeur : Mohab Safey El Din <>
Soumis le : lundi 7 décembre 2015 - 19:42:26
Dernière modification le : jeudi 11 janvier 2018 - 06:24:00

Identifiants

Collections

Citation

Feng Guo, Mohab Safey El Din, Wang Chu, Lihong Zhi. Optimizing a Parametric Linear Function over a Non-compact Real Algebraic Variety . The 2015 ACM on International Symposium on Symbolic and Algebraic Computation, Jul 2015, Bath, United Kingdom. ACM, Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, pp.205-212, 2015, 〈10.1145/2755996.2756666〉. 〈hal-01237920〉

Partager

Métriques

Consultations de la notice

109