Some NP-complete problems in quadratic and nonlinear programming (Q3778558)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4039650
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Some NP-complete problems in quadratic and nonlinear programming |
scientific article; zbMATH DE number 4039650 |
Statements
Some NP-complete problems in quadratic and nonlinear programming (English)
0 references
1987
0 references
continuous variable, smooth, nonconvex nonlinear programming
0 references
indefinite quadratic programs
0 references
NP-complete
0 references
integer square matrix
0 references
copositive
0 references
0 references
0.8562727570533752
0 references
0.8356437087059021
0 references
0.8227005004882812
0 references
0.82218337059021
0 references
0.8157374262809753
0 references
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.
0 references