Article ID: | iaor19971699 |
Country: | India |
Volume: | 33 |
Issue: | 3 |
Start Page Number: | 162 |
End Page Number: | 166 |
Publication Date: | Sep 1996 |
Journal: | OPSEARCH |
Authors: | Murty Katta G., Judice Joaquim |
Keywords: | programming: quadratic |
The authors establish that a linear complementarity problem associated with an indefinite or negative semidefinite symmetric matrix is NP-hard. Using this results they show that even the problem of finding a stationary point of a concave or nonconvex quadratic program is NP-hard, and that the same holds for bilinear programs.