zbMATH — the first resource for mathematics

Some NP-complete problems in quadratic and nonlinear programming. (English) Zbl 0637.90078
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.

90C30 Nonlinear programming
90C20 Quadratic programming
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] 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 · Zbl 0432.65027
[2] A.V. Fiacco and G.P. McCormick,Nonlinear Programming: Sequential Unconstrained Minimization Techniques (Wiley, New York, 1968). · Zbl 0193.18805
[3] M.R. Garey and D.S. Johnson,Computers and Intractability, A Guide to the Theory of NP-completeness (Freeman, New York, 1980). · Zbl 0411.68039
[4] O.L. Mangasarian,Nonlinear Programming (McGraw-Hill, New York, 1969).
[5] 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).
[6] K.G. Murty,Linear Programming (Wiley, New York, 1983).
[7] K.G. Murty,Linear Complementarity, Linear and Nonlinear Programming (Heldermann-Verlag, West Berlin, 1987), to appear.
[8] K.G. Murty,Linear and Combinatorial Programming (Krieger Publishing Company, Malabar, FL, 1976). · Zbl 0334.90032
[9] A. Schrijver,Theory of Linear and Integer Programming (Wiley-Interscience, New York, 1986). · Zbl 0665.90063
[10] M.J. Todd,The Computation of Fixed Points and Applications (Springer-Verlag, Berlin, Heidelberg New York, 1976). · Zbl 0332.54003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.