The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Some NP-complete problems in quadratic and nonlinear programming
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“In fact, global optimization problems are undecidable in unbounded domains [109], and NP-hard on bounded domains [110].”
From Reverse engineering and identification in systems biology: strategies, perspectives and challenges (2014) · cites this paper as [110]
Citations
Cites
(1979) · Cited by 43,841
Theory of Linear and Integer Programming
Letchford, A. N., & Schrijver, A. (2000) · The Journal of the Operational Research Society · doi:10.2307/253980 · Cited by 5,515
Mangasarian, O. L. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971255 · Cited by 3,220
Theory of Linear and Integer Programming
Smith, D. K. (1987) · Journal of the Operational Research Society · doi:10.1057/jors.1987.94 · Cited by 2,708
Nonlinear Programming: Sequential Unconstrained Minimization Techniques
Fiacco, A. V., & McCormick, G. P. (1968) · Defense Technical Information Center (DTIC) · Cited by 2,262
Nonlinear Programming--Sequential Unconstrained Minimization Techniques
Powell, M. J. D. (1969) · The Computer Journal · doi:10.1093/comjnl/12.3.207-a · Cited by 1,757 · cited 3×
“For nonconvex NLPs, under some CQ, necessary conditions for a local minimum are known, and there are some sufficient conditions [ 2 , 4, 7]. There are no known simple conditions, which are both necessary and sufficient for a given point to be a local minimum.”
BackgroundInfluentialLinear complementarity, linear and nonlinear programming
(1989) · European Journal of Operational Research · doi:10.1016/0377-2217(89)90500-6 · Cited by 978
Beale, E. M. L., Künzi, H. P., Krelle, W. E., Oettli, W., & Levin, F. (1968) · Journal of the Royal Statistical Society Series A (General) · doi:10.2307/2343863 · Cited by 713
Allgower, E. L., & Georg, K. (1980) · SIAM Review · doi:10.1137/1022003 · Cited by 439 · cited 1×
“The class of complementary pivot methods or simplicial methods for NLP [ 1 ,5,7, 10] are examples of algorithms in this class (these algorithms convert the system of first order necessary conditions into a Kakutani fixed point problem, which is then solved by complementary pivoting on a triangulation of the space).”
MethodLinear and Combinatorial Programming
Sergeant, C. R., & Murty, K. G. (1977) · Journal of the Operational Research Society · doi:10.2307/3008975 · Cited by 427
Self-citation
Research works printed but not linked: 2
- 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).
Cited by
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization
Parrilo, P. A. (2000) · doi:10.7907/2k6y-ch43 · Cited by 1,802
Semidefinite programming relaxations for semialgebraic problems
Parrilo, P. A. (2003) · Mathematical Programming · doi:10.1007/s10107-003-0387-5 · Cited by 1,527
Adjustable robust solutions of uncertain linear programs
Ben-Tal, A., Goryashko, A., Guslitzer, E., & Nemirovski, A. (2004) · Mathematical Programming · doi:10.1007/s10107-003-0454-y · Cited by 1,380
“But the latter problem is equivalent to the problem of checking copositivity, a problem known to be NP-hard (see, e.g., [15, 16 ]).”
BackgroundqpOASES: a parametric active-set algorithm for quadratic programming
Ferreau, H. J., Kirches, C., Potschka, A., Bock, H. G., & Diehl, M. (2014) · Mathematical Programming Computation · doi:10.1007/s12532-014-0071-1 · Cited by 1,265
“For nonconvex QP problems, finding the global minimum is NP-hard [45], as is the verification of local optimality of a constrained critical point in the case of weakly active constraints [10].”
BackgroundPhase Retrieval via Wirtinger Flow: Theory and Algorithms
Candès, E. J., Li, X., & Soltanolkotabi, M. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2399924 · Cited by 1,049
“We refer to the combination of these two steps, introduced in reverse order below, as the Wirtinger flow (WF) algorithm.”
MethodMost Tensor Problems Are NP-Hard
Hillar, C. J., & Lim, L.-H. (2013) · Journal of the ACM · doi:10.1145/2512329 · Cited by 1,099
Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization
Jaggi, M. (2013) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · Cited by 1,665
Interior Methods for Nonlinear Optimization
Forsgren, A., Gill, P. E., & Wright, M. H. (2002) · SIAM Review · doi:10.1137/s0036144502414942 · Cited by 699
“10); verifying assumption (iii) for all p such that J∗ A p ≥ 0 requires finding the global minimizer of a possibly indefinite quadratic form over a cone, an NP-hard problem [75, 82], not to mention the issue of how to check that (iii) holds for all λ ∈ Mλ.”
BackgroundSums of Squares, Moment Matrices and Optimization Over Polynomials
Laurent, M. (2009) · The IMA Volumes in Mathematics and its Applications · doi:10.1007/978-0-387-09686-5_7 · Cited by 648
“Testing whether a matrix is not copositive is an NP-complete problem [94].”
BackgroundDeep learning without poor local minima
Kawaguchi, K. (2016) · arXiv · doi:10.48550/arxiv.1605.07110 · Cited by 592
Quadratic programming with one negative eigenvalue is NP-hard
Pardalos, P. M., & Vavasis, S. A. (1991) · Journal of Global Optimization · doi:10.1007/bf00120662 · Cited by 510
“Related complexity results on nonconvex quadratic programming can be found in [l], [3], and [7].”
BackgroundHypothalamic POMC neurons promote cannabinoid-induced feeding
Koch, M., Varela, L., Kim, J. G., Kim, J. D., Hernández-Nuño, F., Simonds, S. E., Castorena, C. M., Vianna, C. R., Elmquist, J. K., Morozov, Y. M., et al. (2015) · Nature · doi:10.1038/nature14260 · Cited by 434
Complete search in continuous global optimization and constraint satisfaction
Neumaier, A. (2004) · Acta Numerica · doi:10.1017/s0962492904000194 · Cited by 430
“The COCONUT environment constructs a centred form using slopes and automatic differentiation-like backward propagation, according to formulas given in Schichl and Neumaier (2003), from which linear enclosures are constructed.”
BackgroundInfluentialOptimal Inequalities in Probability Theory: A Convex Optimization Approach
Bertsimas, D., & Popescu, I. (2005) · SIAM Journal on Optimization · doi:10.1137/s1052623401399903 · Cited by 428
“Problem COPOS: Given a matrix H with rational entries, does there exist x ∈ R+ such that x′Hx < 0? This problem is NP-hard (see Murty and Kabadi [29]).”
BackgroundA Joint Precoding Framework for Wideband Reconfigurable Intelligent Surface-Aided Cell-Free Network
Zhang, Z., & Dai, L. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3088755 · Cited by 369
“Note that, the equivalent problem P̂match in (46) is actually a zero-one quadratic programming problem with linear constrains, which is proved to be NP-hard [39].”
BackgroundSolving Systems of Random Quadratic Equations via Truncated Amplitude Flow
Wang, G., Giannakis, G. B., & Eldar, Y. C. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2756858 · Cited by 330
“Even checking quadratic feasibility (i.e., whether a solution to a given quadratic system exists or not) is itself an NP-hard problem [19, Theorem 2.6].”
BackgroundInfluentialA branch-and-reduce approach to global optimization
Ryoo, H. S., & Sahinidis, N. V. (1996) · Journal of Global Optimization · doi:10.1007/bf00138689 · Cited by 349
“Even proving that a solution is not a local minimizer for certain problems is NP-complete (e.g., Murty and Kabadi [ 44 ], Pardalos and Schnitger [49]).”
BackgroundComputational complexity of μ calculation
Braatz, R. P., Young, P. M., Doyle, J. C., & Morari, M. (1994) · IEEE Transactions on Automatic Control · doi:10.1109/9.284879 · Cited by 329
On Cones of Nonnegative Quadratic Functions
Sturm, J. F., & Zhang, S. (2003) · Mathematics of Operations Research · doi:10.1287/moor.28.2.246.14485 · Cited by 319
“, testing whether it does not belong to the co-positive cone is NP-hard; see Murty and Kabadi [12].”
Approximation of the Stability Number of a Graph via Copositive Programming
de Klerk, E., & Pasechnik, D. V. (2002) · SIAM Journal on Optimization · doi:10.1137/s1052623401383248 · Cited by 322
“Semidefinite programming has proved to be a useful tool in formulating approximation algorithms for NP-complete problems in combinatorial optimization.”
BackgroundInfluentialVacuum stability conditions from copositivity criteria
Kannike, K. (2012) · The European Physical Journal C · doi:10.1140/epjc/s10052-012-2093-z · Cited by 315
“In general, testing for copositivity is NP-hard [8].”
BackgroundA global optimization algorithm (GOP) for certain classes of nonconvex NLPs—I. Theory
Floudas, C. A., & Visweswaran, V. (1990) · Computers & Chemical Engineering · doi:10.1016/0098-1354(90)80020-c · Cited by 286
Stability of queueing networks and scheduling policies
Kumar, P. R., & Meyn, S. (1995) · IEEE Transactions on Automatic Control · doi:10.1109/9.341782 · Cited by 280
Global Convergence of a Trust-Region SQP-Filter Algorithm for General Nonlinear Programming
Fletcher, R., Gould, N. I. M., Leyffer, S., Toint, P. L., & Wächter, A. (2002) · SIAM Journal on Optimization · doi:10.1137/s1052623499357258 · Cited by 279
“In this paper, we again consider approximating the objective function by a quadratic model, but, at variance with the latter reference, the method discussed here does not require the global solution of the associated nonconvex quadratic programming (QP) subproblem, which is known to be a theoretically difficult proces…”
MethodAccelerated Methods for NonConvex Optimization
Carmon, Y., Duchi, J. C., Hinder, O., & Sidford, A. (2018) · SIAM Journal on Optimization · doi:10.1137/17m1114296 · Cited by 190
A Survey on Task Offloading in Multi-access Edge Computing
Islam, A., Debnath, A., Ghose, M., & Chakraborty, S. (2021) · Journal of Systems Architecture · doi:10.1016/j.sysarc.2021.102225 · Cited by 271
Algorithms and Software for Convex Mixed Integer Nonlinear Programs
Bonami, P., Kılınç, M. R., & Linderoth, J. (2011) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4614-1927-3_1 · Cited by 270
“…and Software for Convex Mixed Integer Nonlinear Programs Pierre Bonami Mustafa Kilinc Jeff Linderoth Technical Report #1664 October 2009 ha l-0 04 23 41 6, v er si on 2 - 15 O ct 2 00 9 ALGORITHMS AND SOFTWARE FOR CONVEX MIXED INTEGER NONLINEAR PROGRAMS PIERRE BONAMI∗, MUSTAFA KILINdž ,…”
BackgroundFirst-order methods almost always avoid strict saddle points
Lee, J. D., Panageas, I., Piliouras, G., Simchowitz, M., Jordan, M. I., & Recht, B. (2019) · Mathematical Programming · doi:10.1007/s10107-019-01374-3 · Cited by 377
p-bits for probabilistic spin logic
Camsari, K. Y., Sutton, B. M., & Datta, S. (2019) · Applied Physics Reviews · doi:10.1063/1.5055860 · Cited by 225
“This inverse k-sum or subset sum problem is known to be NP-complete 74 and is clearly much more difficult than direct addition.”
BackgroundA tutorial on sum of squares techniques for systems analysis
Papachristodoulou, A., & Prajna, S. (2005) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2005.1470374 · Cited by 257
“Nevertheless, checking nonnegativity of p(x) is an NP-hard problem when the degree of p(x) is at least 4 [28], whereas as argued in the previous paragraph, checking whether p(x) can be written as an SOS is computationally tractable — it can be formulated as a semidefinite program, which has worst-case polynomial time…”
BackgroundLower bounds for non-convex stochastic optimization
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., & Woodworth, B. (2022) · Mathematical Programming · doi:10.1007/s10107-022-01822-7 · Cited by 244
“In general non-convex optimization, it is intractable to find approximate global minima [36] or even to test if a point is a local minimum or a high-order saddle point [34].”
BackgroundReverse engineering and identification in systems biology: strategies, perspectives and challenges
Villaverde, A. F., & Banga, J. R. (2014) · Journal of The Royal Society Interface · doi:10.1098/rsif.2013.0505 · Cited by 229
“In fact, global optimization problems are undecidable in unbounded domains [109], and NP-hard on bounded domains [110].”
BackgroundAhmadi, A. A., & Majumdar, A. (2019) · SIAM Journal on Applied Algebra and Geometry · doi:10.1137/18m118935x · Cited by 198
Solving Standard Quadratic Optimization Problems via Linear, Semidefinite and Copositive Programming
Bomze, I. M., & De Klerk, E. (2002) · Journal of Global Optimization · doi:10.1023/a:1020209017701 · Cited by 219
“In fact, even the problem of determining whether a matrix is not copositive is NP-complete [ 9 ].”
BackgroundHanasusanto, G. A., & Kuhn, D. (2018) · Operations Research · doi:10.1287/opre.2017.1698 · Cited by 208
“s with xed recourse are NPhard. The complexity result of Proposition 3 is also plausible in view of Theorem 5 and the known fact that linear programs over copositive cones are generically intractable [40]. A tractable conservative approximation for (28) can be obtained by replacing the copositive cone Cwith C0 = M2SK:…”
BackgroundA global optimization approach for the BMI problem
Goh, K.-C., Safonov, M. G., & Papavassilopoulos, G. P. (2002) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.1994.411445 · Cited by 212
D.C. Optimization: Theory, Methods and Algorithms
Tụy, H. (1995) · Nonconvex optimization and its applications · doi:10.1007/978-1-4615-2025-2_4 · Cited by 212
Copositive Programming – a Survey
Dür, M. (2010) · Springer eBooks · doi:10.1007/978-3-642-12598-0_1 · Cited by 209
“It has been shown by Murty and Kabadi [44] that checking whether a given matrix A ∈ C is a co-NP-complete decision problem.”
BackgroundLower bounds for finding stationary points I
Carmon, Y., Duchi, J. C., Hinder, O., & Sidford, A. (2019) · Mathematical Programming · doi:10.1007/s10107-019-01406-y · Cited by 209
Finding approximate local minima faster than gradient descent
Agarwal, N., Allen-Zhu, Z., Bullins, B., Hazan, E., & Ma, T. (2017) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3055399.3055464 · Cited by 291
“ently. Unfortunately, this is no longer the case if f is nonconvex; indeed, even a degree four polynomial can be NP-hard to optimize [23], or even just to check whether a point is not a local minimum [25]. Thus, for non-convex optimization one has to settle for the more modest goal of reaching approximate local optima…”
BackgroundOn the Relation Between Option and Stock Prices: A Convex Optimization Approach
Bertsimas, D., & Popescu, I. (2002) · Operations Research · doi:10.1287/opre.50.2.358.424 · Cited by 203
“Theseparation problem is NP-hard because it reduces verifying that the matrix Y is co-positive, which is an NP-hard problem (see Murty and Kabadi 1987).”
BackgroundOn Copositive Programming and Standard Quadratic Optimization Problems
Bomze, I. M., Dür, M., de Klerk, E., Roos, C., Quist, A. J., & Terlaky, T. (2000) · Journal of Global Optimization · doi:10.1023/a:1026583532263 · Cited by 196
“Even without constraints, checking whether or not a matrix belongs to K is co-NP-hard [ 38 ].”
BackgroundMinimum concave-cost network flow problems: Applications, complexity, and algorithms
Guisewite, G. M., & Pardalos, P. M. (1990) · Annals of Operations Research · doi:10.1007/bf02283688 · Cited by 194
Checking local optimality in constrained quadratic programming is NP-hard
Pardalos, P. M., & Schnitger, G. (1988) · Operations Research Letters · doi:10.1016/0167-6377(88)90049-1 · Cited by 183
Staggered projections for frictional contact in multibody systems
Kaufman, D. M., Sueda, S., James, D. L., & Pai, D. K. (2008) · ACM Transactions on Graphics · doi:10.1145/1409060.1409117 · Cited by 182
Floudas, C. A., & Visweswaran, V. (1995) · Nonconvex optimization and its applications · doi:10.1007/978-1-4615-2025-2_5 · Cited by 193
Analysis of Non-polynomial Systems Using the Sum of Squares Decomposition
Papachristodoulou, A., & Prajna, S. (2005) · Lecture notes in control and information sciences · doi:10.1007/10997703_2 · Cited by 185
“Nevertheless, checking nonnegativity of p(x) is an NP-hard problem when the degree of p(x) is at least 4 [8], whereas as argued in the previous paragraph, checking whether p(x) can be written as an SOS is computationally tractable — it can be formulated as an SDP, which has worst-case polynomial time complexity.”
BackgroundMultivariate Nonnegative Quadratic Mappings
Luo, Z.-Q. T., Sturm, J. F., & Zhang, S. (2004) · SIAM Journal on Optimization · doi:10.1137/s1052623403421498 · Cited by 184
“Quadratic programming over a box [0, 1] is well-known to be NP-Complete for general n, see [13].”
BackgroundGradient Descent Converges to MinimizersPreprint
Lee, J. D., Simchowitz, M., Jordan, M. I., & Recht, B. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.04915 · Cited by 198
“Keywords: Gradient descent, smooth optimization, saddle points, local minimum, dynamical systems.”
BackgroundNumerical methods for mixed-integer optimal control problems
Säger, S. (2006) · Cited by 169
Algorithmic Construction of Lyapunov Functions for Power System Stability Analysis
Anghel, M., Milano, F., & Papachristodoulou, A. (2013) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2013.2246233 · Cited by 163
“Even in cases when both the vector field and the Lyapunov function candidate are polynomial, the Lyapunov conditions are essentially polynomial non-negativity conditions which are known to be -hard to test [35].”
BackgroundOperational Research: methods and applications
Petropoulos, F., Laporte, G., Aktaş, E., Alumur, S. A., Archetti, C., Ayhan, H., Battarra, M., Bennell, J. A., Bourjolly, J.-M., Boylan, J. E., et al. (2023) · Journal of the Operational Research Society · doi:10.1080/01605682.2023.2253852 · Cited by 188
On the conservativeness of fuzzy and fuzzy-polynomial control of nonlinear systems
Sala, A. (2009) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2009.02.001 · Cited by 159
“There is a quest in the fuzzy community to find necessary and sufficient conditions for the positivity of (15): unfortunately, the quest is basically futile as the expression (15) is a case of the co-NP-complete matrix copositivity problem in (Murty and Kabadi, 1987).”
BackgroundOn the computational complexity of membership problems for the completely positive cone and its dual
Dickinson, P. J. C., & Gijben, L. (2013) · Computational Optimization and Applications · doi:10.1007/s10589-013-9594-z · Cited by 159
“Motivated by the result of Murty and Kabadi [20] we consider the as yet unanswered question of whether the strong membership problem for the completely positive cone is NP-hard.”
BackgroundResultInfluentialNumerical methods for large-scale nonlinear optimization
Gould, N. I. M., Orban, D., & Toint, P. L. (2005) · Acta Numerica · doi:10.1017/s0962492904000248 · Cited by 159
“Unfortunately, for non-convex problems, even checking if such a critical point is a local minimizer may be (NP) hard (Murty and Kabadi 1987).”
InfluentialA Variational Approach to Copositive Matrices
Hiriart‐Urruty, J., & Seeger, A. (2010) · SIAM Review · doi:10.1137/090750391 · Cited by 158
“[73]).”
When Are Nonconvex Problems Not Scary?Preprint
Sun, J., Qu, Q., & Wright, J. N. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1510.06096 · Cited by 166
“For example, third order saddle points seem to generally demand studying spectral property of three-way tensors, which entails NP-hard computational problems [HL13]; see [AG16] for a recent attempt in this line.”
Dynamic Network Slicing for Multitenant Heterogeneous Cloud Radio Access Networks
Lee, Y. L., Loo, J., Chuah, T. C., & Wang, L. (2018) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2017.2789294 · Cited by 155
“Although (11) is less complicated than (5), it is still generally NP-hard.”
BackgroundInfluentialContinuous Characterizations of the Maximum Clique Problem
Gibbons, L., Hearn, D. W., Pardalos, P. M., & Ramana, M. V. (1997) · Mathematics of Operations Research · doi:10.1287/moor.22.3.754 · Cited by 155
Copositive optimization – Recent developments and applications
Bomze, I. M. (2011) · European Journal of Operational Research · doi:10.1016/j.ejor.2011.04.026 · Cited by 154
“Here the feasible polyhedron is the standard simplex ∆ = x ∈ R n + : e ⊤ x = 1 , where e = [1, . . . , 1] ⊤ ∈ R n : this subclass is also NP-hard (there can be up to ∼ 2 n /(1.25 √ n) local nonglobal solutions [14]).”
BackgroundResultInfluentialKumar, P. R., & Meyn, S. (1996) · IEEE Transactions on Automatic Control · doi:10.1109/9.481604 · Cited by 149
A review of matrix scaling and Sinkhorn's normal form for matrices and positive mapsPreprint
Idel, M. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1609.06349 · Cited by 164
Vacuum stability of a general scalar potential of a few fields
Kannike, K. (2016) · The European Physical Journal C · doi:10.1140/epjc/s10052-016-4160-3 · Cited by 148
“ouplings is in principle always decidable. Nevertheless, the general problem of nding whether a given polynomial is non-negative is an NP-hard problem if the degree of the polynomial is at least four [3], which is the case for renormalisable scalar potentials in four dimensions. The most general quartic potential of r…”
BackgroundSwitched Positive Linear Systems
Blanchini, F., Colaneri, P., & Valcher, M. E. (2015) · Foundations and Trends® in Systems and Control · doi:10.1561/2600000005 · Cited by 153
Semidefinite Programming and Integer Programming
Laurent, M., & Rendl, F. (2005) · Handbooks in operations research and management science · doi:10.1016/s0927-0507(05)12008-8 · Cited by 141
Computational complexity of µ calculation
Braatz, R. D., Young, P. M., Doyle, J. C., & Morari, M. (1993) · doi:10.1109/acc.1993.4176152 · Cited by 141
Data science applications to string theory
Ruehle, F. (2019) · Physics Reports · doi:10.1016/j.physrep.2019.09.005 · Cited by 166
Collaborative data processing in developing predictive models of complex reaction systems
Frenklach, M., Packard, A., Seiler, P. J., & Feeley, R. (2003) · International Journal of Chemical Kinetics · doi:10.1002/kin.10172 · Cited by 137
Mixed-integer quadratic programming is in NP
Pia, A. D., Dey, S. S., & Molinaro, M. (2016) · Mathematical Programming · doi:10.1007/s10107-016-1036-0 · Cited by 136
“By Proposition 4, problem (11) is unbounded if and only if the following QP is: Murty and Kabadi [14] showed that deciding if (12) is unbounded is NP-complete.”
BackgroundScheduling Arrivals to a Stochastic Service Delivery System Using Copositive Cones
Kong, Q., Lee, C., Teo, C., & Zheng, Z. (2013) · Operations Research · doi:10.1287/opre.2013.1158 · Cited by 158
“For instance, the problem of testing if a given matrix is copositive is known to be co-NP-complete (cf. Murty & Kabadi (1987)).”
BackgroundTabu search method with random moves for globally optimal design
Hu, N. (1992) · International Journal for Numerical Methods in Engineering · doi:10.1002/nme.1620350508 · Cited by 134
Nonconvex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances
Razaviyayn, M., Huang, T., Lu, S., Nouiehed, M., Sanjabi, M., & Hong, M. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.3003851 · Cited by 131
“Due to the non-convex nature of problem (Min-Max), finding the global solution is NP-hard in general [22].”
BackgroundTRACTABLE ROBUST EXPECTED UTILITY AND RISK MODELS FOR PORTFOLIO OPTIMIZATION
Natarajan, K., Sim, M., & UICHANCO, J. A. V. (2010) · Mathematical Finance · doi:10.1111/j.1467-9965.2010.00417.x · Cited by 129
“In fact, the complexity of finding the worst-case expected utility under the intersection of these two sets is typically a NP-hard problem (see Murty and Kabadi 1987).”
SOSTOOLS and Its Control Applications
Prajna, S., Papachristodoulou, A., Seiler, P. J., & Parrilo, P. A. (2005) · Lecture notes in control and information sciences · doi:10.1007/10997703_14 · Cited by 128
“Indeed nonnegativity is NP-hard to test [12], whereas the SOS conditions are polynomial time verifiable through solving appropriate semidefinite programs.”
BackgroundNP-hardness of deciding convexity of quartic polynomials and related problems
Ahmadi, A. A., Olshevsky, A., Parrilo, P. A., & Tsitsiklis, J. N. (2011) · Mathematical Programming · doi:10.1007/s10107-011-0499-2 · Cited by 126
“, as a direct consequence of NP-hardness of testing matrix copositivity, a result proven by Murty and Kabadi [33].”
BackgroundResultInfluentialOn affine scaling algorithms for nonconvex quadratic programming
Ye, Y. (1992) · Mathematical Programming · doi:10.1007/bf01580903 · Cited by 126
Near-Optimal Algorithms for Minimax OptimizationPreprint
Lin, T., Jin, C., & Jordan, M. I. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.02417 · Cited by 125
“In general, finding a global saddle point of f is intractable since solving the special case with a singleton Y globally is already NP-hard [Murty and Kabadi, 1987] as mentioned in the main text.”
BackgroundInfluentialComplexity issues in robust stability of linear delay-differential systems
Toker, O., & Özbay, H. (1996) · Mathematics of Control Signals and Systems · doi:10.1007/bf01211858 · Cited by 119
“It is well known that quadratic and bilinear programming over the unit hypercube [- 1, lJ" are JV~-hard [ 22 ].”
BackgroundResultInfluentialComplete Dictionary Recovery Over the Sphere II: Recovery by Riemannian Trust-Region Method
Sun, J., Qu, Q., & Wright, J. N. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2632149 · Cited by 144
Finding a Sparse Vector in a Subspace: Linear Sparsity Using Alternating Directions
Qu, Q., Sun, J., & Wright, J. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2601599 · Cited by 120
“the unit sphere Sn 1, giving min x kxk 1 ; s.t. x 2S;kxk 2 = 1: (II.1) This formulation is still nonconvex, and for general nonconvex problems it is known to be NP-hard to find even a local minimizer [41]. Nevertheless, the geometry of the sphere is benign enough, such that for well-structured inputs it actually will b…”
BackgroundRecent Theoretical Advances in Non-Convex Optimization
Danilova, M., Dvurechensky, P. E., Gasnikov, A. V., Gorbunov, E., Guminov, S. V., Kamzolov, D., & Shibaev, I. (2022) · Springer optimization and its applications · doi:10.1007/978-3-031-00832-0_3 · Cited by 159
Daskalakis, C., & Papadimitriou, C. H. (2011) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973082.62 · Cited by 107
“• An intriguing and deceivingly simple problem in numerical optimization (which had not been considered before in the context of PLS and PPAD) generalizes the last three problems: Find any approximate stationary point of a given multivariate polynomial [16, 26].”
BackgroundMatrix p -Norms Are NP-Hard to Approximate If $p\neq1,2,\infty$
Hendrickx, J. M., & Olshevsky, A. (2010) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/09076773x · Cited by 107
Efficient approaches for escaping higher order saddle points in non-convex optimizationPreprint
Anandkumar, A., & Ge, R. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.05908 · Cited by 137
Global optimality conditions for deep neural networksPreprint
Yun, C., Sra, S., & Jadbabaie, A. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1707.02444 · Cited by 105
A Finite Algorithm for Global Minimization of Separable Concave Programs
Shectman, J. P., & Sahinidis, N. V. (1998) · Journal of Global Optimization · doi:10.1023/a:1008241411395 · Cited by 101
“Even checking whether a given feasible point is a local solution is itself an NPhard problem [48].”
BackgroundInventory placement in acyclic supply chain networks
Magnanti, T. L., Shen, Z. M., Shu, J., Simchi‐Levi, D., & Teo, C. (2005) · Operations Research Letters · doi:10.1016/j.orl.2005.04.004 · Cited by 101
“As shown by Murty and Kabadi [16], the general separable concave minimization problem subject to linear constraints is NP-hard.”
BackgroundComputing the Stability Number of a Graph Via Linear and Semidefinite Programming
Peña, J., Vera, J. C., & Zuluaga, L. F. (2007) · SIAM Journal on Optimization · doi:10.1137/05064401x · Cited by 100
“There is not a simple description of the copositive cone, and in fact the problem of deciding if a matrix is copositive is known to be NP-hard [12].”
BackgroundAn Adaptive Linear Approximation Algorithm for Copositive Programs
Bundfuss, S., & Dür, M. (2009) · SIAM Journal on Optimization · doi:10.1137/070711815 · Cited by 98
“In contrast to N and S + , the cones C and C ∗ are not tractable: it is known that testing whether a given matrix is in C is co-NP-complete (cf. [16]).”
BackgroundInertia-Controlling Methods for General Quadratic Programming
Gill, P. E., Murray, W., Saunders, M. A., & Wright, M. H. (1991) · SIAM Review · doi:10.1137/1033001 · Cited by 96
“Verification of optimality in such instances requires further information, and is in general an NP-hard problem (see Murty and Kabadi [34], Pardalos and Schnitger [36]).”
BackgroundGlobal Guarantees for Enforcing Deep Generative Priors by Empirical Risk
Hand, P., & Voroninski, V. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2935447 · Cited by 122
“As this objective is nonconvex, there is no a priori guarantee of efficiently finding the global minimum [60].”
BackgroundData-driven inverse optimization with imperfect information
Esfahani, P. M., Shafieezadeh-Abadeh, S., Hanasusanto, G. A., & Kühn, D. (2017) · Mathematical Programming · doi:10.1007/s10107-017-1216-6 · Cited by 94
“The proof relies on a reduction from the NP-hard quadratic maximization problem [31].”
Moment Problems and Semidefinite Optimization
Bertsimas, D., & Sethuraman, J. (2000) · International series in management science/operations research/International series in operations research & management science · doi:10.1007/978-1-4615-4381-7_16 · Cited by 93
A Triangulation Approach to Asymptotically Exact Conditions for Fuzzy Summations
Kruszewski, A., Sala, A., Guerra, T., & Ariño, C. V. (2009) · IEEE Transactions on Fuzzy Systems · doi:10.1109/tfuzz.2009.2019124 · Cited by 93
“Checking positive definiteness of the expression ∑r i=1 ∑r j=1 hihjQij is known to be a co-NP problem, which is referred to in the literature as the matrix copositivity problem [12].”
BackgroundThe non-convex geometry of low-rank matrix optimization
Li, Q., Zhu, Z., & Tang, G. (2018) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iay003 · Cited by 130
“Even certifying the local optimality of a point might be an NP-hard problem [38].”
BackgroundRelaxation and decomposition methods for mixed integer nonlinear programming
Nowak, I. (2005) · doi:10.18452/13962 · Cited by 90
Distributed Learning in the Nonconvex World: From batch data to streaming and beyond
Chang, T., Hong, M., Wai, H.-T., Zhang, X., & Lu, S. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2970170 · Cited by 114
“Without assuming convexity for (1), one cannot hope to find an optimal solution using a reasonable amount of effort, since solving a nonconvex problem is, in general, NP-hard [7].”
BackgroundHand-eye and robot-world calibration by global polynomial optimization
Heller, J., Henrion, D., & Pajdla, T. (2014) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2014.6907313 · Cited by 89
“x problem with many local minima. In theory, polynomial optimization problems can be handled using tools of elementary calculus, however, nding the global minimizer x is|in general|an NP-hard problem [23]. In [17], Lasserre cast the problem polynomial optimization over nite-dimensional semialgebraic set S = fx 2Rmjp i…”
Taxi market equilibrium with third-party hailing service
Qian, X., & Ukkusuri, S. V. (2017) · Transportation Research Part B Methodological · doi:10.1016/j.trb.2017.01.012 · Cited by 88
Deterministic Guarantees for Burer‐Monteiro Factorizations of Smooth Semidefinite Programs
Boumal, N., Voroninski, V., & Bandeira, A. S. (2019) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.21830 · Cited by 88
“ain theorems. The starting point of this investigation is the hope to solve (SDP) by solving (P) instead. For smooth, non-convex optimization problems, even verifying local optimality is usually hard [22]. Thus, we wish to restrict our attention to efficiently computable points, such as points which satisfy first- and s…”
BackgroundInfluential
Metadata
- Authors
- Murty, K. G., & Kabadi, S. N.
- Affiliations
- University of Michigan (US)
- University of New Brunswick (CA)
- Venue
- Mathematical Programming
- Published
- 1987-06
- Volume
- 39
- Issue
- 2
- Pages
- 117-129
- ISSN
- 0025-5610 (ISSN-L)
- 1436-4646
- OpenAlex
- W2079135578
- Cited by
- 1,003
- References
- 12
- Citations by year
- 2026: 17 · 2025: 21 · 2024: 32 · 2023: 42 · 2022: 51 · 2021: 79 · 2020: 66 · 2019: 68 · 2018: 62 · 2017: 55 · 2016: 55 · 2015: 38 · 2014: 42 · 2013: 47 · 2012: 27
- FWCI
- 7.23
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Mathematical Programming (publishedVersion)
- Topics
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Graph Theory Research
- Keywords
- NP-completeness, nonconvex nonlinear programming, indefinite quadratic programming, computational complexity, copositive matrices, integer data
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.