  


On the Complexity of Detecting Convexity over a Box
Amir Ali Ahmadi (a_a_aprinceton.edu) Abstract: It has recently been shown that the problem of testing global convexity of polynomials of degree four is {strongly} NPhard, answering an open question of N.Z. Shor. This result is minimal in the degree of the polynomial when global convexity is of concern. In a number of applications however, one is interested in testing convexity only over a compact region, most commonly a box (i.e., hyperrectangle). In this paper, we show that this problem is also strongly NPhard, in fact for polynomials of degree as low as three. This result is minimal in the degree of the polynomial and in some sense justifies why convexity detection in nonlinear optimization solvers is limited to quadratic functions or functions with special structure. As a byproduct, our proof shows that the problem of testing whether all matrices in an interval family are positive semidefinite is strongly NPhard. This problem, which was previously shown to be (weakly) NPhard by Nemirovski, is of independent interest in the theory of robust control. Keywords: Convexity detection, convex optimization, computational complexity, interval positive semidefiniteness Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Category 2: Global Optimization Category 3: Nonlinear Optimization Citation: 11 pages. Download: [PDF] Entry Submitted: 06/15/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  