Some NP-complete problems in quadratic and nonlinear programming

From MaRDI portal





In continuous variable, smooth, nonconvex nonlinear programming, we analyze the complexity of checking whether (a) a given feasible solution is not a local minimum, and (b) the objective function is not bounded below on the set of feasible solutions. We construct a special class of indefinite quadratic programs, with simple constraints and integer data, and show that checking (a) or (b) on this class is NP-complete. As a corollary, we show that checking whether a given integer square matrix is no copositive, is NP-complete.




Cited in
(only showing first 100 items - show all)








This page was built for publication: Some NP-complete problems in quadratic and nonlinear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3778558)