zbMATH — the first resource for mathematics

Checking local optimality in constrained quadratic programming is NP- hard. (English) Zbl 0644.90067
Summary: We prove that the problem of checking local optimality for a feasible point and the problem of checking if a local minimum is strict, are NP- hard problems. As a consequence the problem of checking whether a function is locally strictly convex is also NP-hard.

90C20 Quadratic programming
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Bachem, A.; Hamacher, H.W., Applications of combinatorial methods in mathematical programming: abstracts and open problems, ()
[2] Cook, S.A., The complexity of theorem proving procedures, (), 151-158 · Zbl 0363.68125
[3] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[4] D.G. Luenberser, Linear and Noniinear Programming, 2nd ed., Addison-Wesley, Reading, MA.
[5] McCormick, G.P., Second-order conditions for constrained minima, SIAM J. of applied mathematics, 15, 641-652, (1967) · Zbl 0166.15601
[6] K.G. Murty and S.N. Kabadi,-“Some NP-complete prob- lems in quadratic and nonlinear programming”, Technical Report 85-23, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI. · Zbl 0637.90078
[7] Pardalos, P.M.; Rosen, J.B., Constrained global optimization: algorithms and applications, () · Zbl 0638.90064
[8] Vergis, A.; Steiglitz, K.; Dickinson, B., The complexity of analog computation, Math. and computers in simulation, 28, 91-113, (1986) · Zbl 0594.68040
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.