Abstract
Second-order necessary and sufficient conditions for local optimality in constrained optimization problems are discussed. For global optimality, a criterion recently developed by Hiriart-Urruty and Lemarechal is thoroughly examined in the case of concave quadratic problems and reformulated into copositivity conditions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Murty, K. G., andKabadi, S. N.,Some NP-Complete Problems in Quadratic and Linear Programming, Mathematical Programming, Vol. 39, pp. 117–129, 1987.
Pardalos, P. M., andSchnitger, G.,Checking Local Optimality in Constrained Quadratic Programming Is NP-Hard, OR Letters, Vol. 7, pp. 33–35, 1988.
Bomze, I. M.,Copositivity and Optimization, Proceedings of the 12th SOR Meeting, Athenäum Verlag, Frankfurt, Germany, pp. 27–36, 1989.
Hestenes, M. R.,Optimization Theory: The Finite-Dimensional Case, Wiley, New York, New York, 1975.
Fletcher, R.,Practical Methods of Optimization, Vol. 2: Constrained Optimization, Wiley, New York, New York, 1981.
Bazaraa, M. S., andShetty, C. M.,Nonlinear Programming: Theory and Algorithms, Wiley, New York, New York, 1979.
Danninger, G., andBomze, I. M.,Using Copositivity for Local and Global Optimality Criteria in Smooth Nonconvex Programming Problems, Technical Report 103, Department of Statistics and Computer Sciences, University of Vienna, Vienna, Austria, 1991.
Mangasarian, O. N., andFromovitz, S.,The Fritz John Necessary Optimality Conditions in the Presence of Equality and Inequality Constraints, Journal of Mathematical Analysis and Applications, Vol. 17, pp. 37–47, 1967.
Hiriart-Urruty, J. B.,From Convex Optimization to Nonconvex Optimization, Part 1: Necessary and Sufficient Conditions for Global Optimality, Nonsmooth Optimization and Related Topics, Edited by F. H. Clarke et al., Plenum Press, New York, New York, pp. 219–239, 1989.
Rockafellar, R. T.,Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.
Hiriart-Urruty, J. B., andLemarechal, C.,Testing Necessary and Sufficient Conditions for Global Optimality in the Problem of Maximizing a Convex Quadratic Function over a Convex Polyhedron, Preliminary Report, Seminar of Numerical Analysis, University Paul Sabatier, Toulouse, France, 1990.
Wets, R.,Grundlagen Konvexer Optimierung, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, Berlin, Germany, Vol. 137, 1976.
Diananda, P. H.,On Nonnegative Forms in Real Variables Some or All of Which Are Nonnegative, Proceedings of the Cambridge Philosophical Society, Vol. 58, pp. 17–25, 1962.
Cottle, R. W., Habetler, G. J., andLemke, C. E.,Quadratic Forms Semidefinite over Convex Cones, Proceedings of the Princeton Symposium in Mathematical Programming, Edited by H. W. Kuhn, Princeton University Press, Princeton, New Jersey, pp. 551–565, 1970.
Hadeler, K. P.,On Copositive Matrices, Linear Algebra and Its Applications, Vol. 49, pp. 79–89, 1983.
Bomze, I. M.,Remarks on the Recursive Structure of Copositivity, Journal of Information and Optimization Science, Vol. 8, pp. 243–260, 1987.
Danninger, G.,A Recursive Algorithm for Determining Strict Copositivity of a Symmetric Matrix, Methods of Operations Research, Vol. 62, pp. 45–52, 1990.
Bomze, I. M., andDanninger, G.,A Global Optimization Algorithm for Concave Linear-Quadratic Problems, SIAM Journal on Optimization, 1992 (to appear).
Author information
Authors and Affiliations
Additional information
Communicated by G. Leitmann
Rights and permissions
About this article
Cite this article
Danninger, G. Role of copositivity in optimality criteria for nonconvex optimization problems. J Optim Theory Appl 75, 535–558 (1992). https://doi.org/10.1007/BF00940491
Issue Date:
DOI: https://doi.org/10.1007/BF00940491