Active constraints,indefinite quadratic test problems,and complexity

The observation that at leasts constraints are active when the Hessian of the Lagrangian hass negative eigenvalues at a local minimizer is used to obtain two results: (i) a class of nearly concave quadratic minimization problem can be solved in polynomial time; (ii) a class of indefinite quadratic test problems can be constructed with a specified number of positive and negative eigenvalues and with a known global minimizer.The authors thank the reviewers for their constructive comments. The first author was supported by the National Science Foundation Grant DMS-85-20926 and by the Air Force Office of Scientific Research Grant AFOSR-ISSA-86-0091.