Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download
Contributor : Mohab Safey El Din <>
Submitted on : Monday, December 7, 2015 - 7:42:26 PM
Last modification on : Friday, January 8, 2021 - 5:42:02 PM



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. pp.205-212, ⟨10.1145/2755996.2756666⟩. ⟨hal-01237920⟩



Record views