On the complexity of finding stationary points of nonconvex quadratic programs

On the complexity of finding stationary points of nonconvex quadratic programs

0.00 Avg rating0 Votes
Article ID: iaor19971699
Country: India
Volume: 33
Issue: 3
Start Page Number: 162
End Page Number: 166
Publication Date: Sep 1996
Journal: OPSEARCH
Authors: ,
Keywords: programming: quadratic
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.