Abstract
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 not copositive, is NP-complete.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. Allgower and K. Georg, “Simplicial and continuation methods for approximating fixed points and solutions to systems of equations,”SIAM Review 22 (1980) 28–85
A.V. Fiacco and G.P. McCormick,Nonlinear Programming: Sequential Unconstrained Minimization Techniques (Wiley, New York, 1968).
M.R. Garey and D.S. Johnson,Computers and Intractability, A Guide to the Theory of NP-completeness (Freeman, New York, 1980).
O.L. Mangasarian,Nonlinear Programming (McGraw-Hill, New York, 1969).
O.H. Merrill, “Application and extensions of an alogirithm that computes fixed points of upper semicontinous point to set mappings” Ph.D. Dissertation, University of Michigan, Ann Arbor, MI (1972).
K.G. Murty,Linear Programming (Wiley, New York, 1983).
K.G. Murty,Linear Complementarity, Linear and Nonlinear Programming (Heldermann-Verlag, West Berlin, 1987), to appear.
K.G. Murty,Linear and Combinatorial Programming (Krieger Publishing Company, Malabar, FL, 1976).
A. Schrijver,Theory of Linear and Integer Programming (Wiley-Interscience, New York, 1986).
M.J. Todd,The Computation of Fixed Points and Applications (Springer-Verlag, Berlin, Heidelberg New York, 1976).
Author information
Authors and Affiliations
Additional information
Research partially supported by NSF Grants No. ECS-8401081 and ECS-8521183.
Research partially supported by NSERC (Canada) Grant No. A8085.
Rights and permissions
About this article
Cite this article
Murty, K.G., Kabadi, S.N. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming 39, 117–129 (1987). https://doi.org/10.1007/BF02592948
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02592948