Some NP-complete problems in quadratic and nonlinear programming |
| |
| Authors: | Katta G. Murty Santosh N. Kabadi |
| |
| Affiliation: | 1. Department of Industrial and Operations Engineering, The University of Michigan, 1205 Beal Avenue, 48109-2117, Ann Arbor, MI, USA
2. Faculty of Administration, University of New Brunswick, E3B 5A6, Fredericton, NB, Canada
|
| |
| Abstract: | In continuous variable, smooth, nonconvex nonlinear programming, we analyze the complexity of checking whether - a given feasible solution is not a local minimum, and
- 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 not copositive, is NP-complete. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
