LP relaxations for a class of linear semi-infinite programming problems. (4th May 2017)

• Record Type: Journal Article
• Authors: Guo, Feng; Sun, Xiaoxia
• Is Part Of: Optimization. Volume 66:Number 5(2017)
• Page Start: 657
• Page End: 673
• Publication Date: 2017-05-04
• Subjects: Linear semi-infinite programming -- LP relaxations -- Handelman's representation -- polynomial optimization; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2017.1295458
• Languages: English
• ISSNs: 0233-1934

Abstract

Abstract : In this paper, we consider a subclass of linear semi-infinite programming problems whose constraint functions are polynomials in parameters and index sets are polyhedra. Based on Handelman's representation of positive polynomials on a polyhedron, we propose two hierarchies of LP relaxations of the considered problem which respectively provide two sequences of upper and lower bounds of the optimum. These bounds converge to the optimum under some mild assumptions. Sparsity in the LP relaxations is explored for saving computational time and avoiding numerical ill behaviors.