On the complexity of detecting convexity over a box

Amir Ali Ahmadi, Georgina Hall

Research output: Contribution to journalArticle

Abstract

It has recently been shown that the problem of testing global convexity of polynomials of degree four is strongly NP-hard, 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., a hyper-rectangle). In this paper, we show that this problem is also strongly NP-hard, 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 NP-hard. This problem, which was previously shown to be (weakly) NP-hard by Nemirovski, is of independent interest in the theory of robust control.

Original languageEnglish (US)
JournalMathematical Programming
DOIs
StatePublished - Jan 1 2019

Fingerprint

Convexity
NP-complete problem
Polynomial
Testing
Positive semidefinite
Nonlinear Optimization
Quadratic Function
Robust Control
Rectangle
Justify
Interval

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Cite this

@article{0fae30b0fa2840f89dbdb9f8aef96a2c,
title = "On the complexity of detecting convexity over a box",
abstract = "It has recently been shown that the problem of testing global convexity of polynomials of degree four is strongly NP-hard, 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., a hyper-rectangle). In this paper, we show that this problem is also strongly NP-hard, 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 NP-hard. This problem, which was previously shown to be (weakly) NP-hard by Nemirovski, is of independent interest in the theory of robust control.",
author = "Ahmadi, {Amir Ali} and Georgina Hall",
year = "2019",
month = "1",
day = "1",
doi = "https://doi.org/10.1007/s10107-019-01396-x",
language = "English (US)",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",

}

On the complexity of detecting convexity over a box. / Ahmadi, Amir Ali; Hall, Georgina.

In: Mathematical Programming, 01.01.2019.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the complexity of detecting convexity over a box

AU - Ahmadi, Amir Ali

AU - Hall, Georgina

PY - 2019/1/1

Y1 - 2019/1/1

N2 - It has recently been shown that the problem of testing global convexity of polynomials of degree four is strongly NP-hard, 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., a hyper-rectangle). In this paper, we show that this problem is also strongly NP-hard, 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 NP-hard. This problem, which was previously shown to be (weakly) NP-hard by Nemirovski, is of independent interest in the theory of robust control.

AB - It has recently been shown that the problem of testing global convexity of polynomials of degree four is strongly NP-hard, 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., a hyper-rectangle). In this paper, we show that this problem is also strongly NP-hard, 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 NP-hard. This problem, which was previously shown to be (weakly) NP-hard by Nemirovski, is of independent interest in the theory of robust control.

UR - http://www.scopus.com/inward/record.url?scp=85065290066&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85065290066&partnerID=8YFLogxK

U2 - https://doi.org/10.1007/s10107-019-01396-x

DO - https://doi.org/10.1007/s10107-019-01396-x

M3 - Article

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

ER -