Some NP-complete problems in quadratic and nonlinear programming
The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
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
Items 101–200 of 1,000
Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic GamesPreprint
Zhang, K., Yang, Z., & Başar, T. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.00729 · Cited by 118
“Since nonconvex optimization problems are NP-hard [17] in the worst case, so is finding an NE in nonconvex-nonconcave saddlepoint problems [18].”
BackgroundBalasubramanian, K., & Ghadimi, S. (2021) · Foundations of Computational Mathematics · doi:10.1007/s10208-021-09499-8 · Cited by 160
A distributionally robust optimization approach for surgery block allocation
Wang, Y., Zhang, Y., & Tang, J. (2018) · European Journal of Operational Research · doi:10.1016/j.ejor.2018.08.037 · Cited by 84
A Complete Characterization of the Gap between Convexity and SOS-Convexity
Ahmadi, A. A., & Parrilo, P. A. (2013) · SIAM Journal on Optimization · doi:10.1137/110856010 · Cited by 84
“, as an immediate corollary of NP-hardness of deciding matrix copositivity [30]).”
BackgroundProcess Flexibility: A Distribution-Free Bound on the Performance of K-Chain
Wang, X., & Zhang, J. (2013) · Operations Research · doi:10.1287/opre.2015.1370 · Cited by 84
Low-Barrier Nanomagnets as p-Bits for Spin Logic
Faria, R., Camsari, K. Y., & Datta, S. (2017) · IEEE Magnetics Letters · doi:10.1109/lmag.2017.2685358 · Cited by 84
Neural Text Generation: Past, Present and Beyond
Lu, S., Zhu, Y., Zhang, W., Wang, Y.-X., & Yu, Y. H. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.07133 · Cited by 49
“Natural language processing (NLP) problems, especially nat-ural language generation (NLG), have long been considered as among the most challenging computational tasks [Murty and Kabadi, 1987].”
Machine Learning: Deepest Learning as Statistical Data Assimilation Problems
Abarbanel, H. D. I., Rozdeba, P. J., & Shirman, S. (2018) · Neural Computation · doi:10.1162/neco_a_01094 · Cited by 85
“This is an NP-complete problem (Murty & Kabadi, 1987) and suggests one cannot find a global minimum of the ML problem, as set, unless there is a special circumstance.”
Scholtes, S., & Stöhr, M. (2001) · Mathematics of Operations Research · doi:10.1287/moor.26.4.851.10007 · Cited by 81
“Even in the case of a smooth nonlinear program, verifying second order conditions is in general NP-hard (Murty and Kabadi 1987, Pardalos and Schnitger 1988). Therefore, an efficient method can only be guaranteed to converge to points satisfying second order conditions under assumptions which make this verification pro…”
MethodAlgorithmic copositivity detection by simplicial partition
Bundfuss, S., & Dür, M. (2007) · Linear Algebra and its Applications · doi:10.1016/j.laa.2007.09.035 · Cited by 80
“More precisely, for a given matrix A ∈ R n × n the problem to decide whether A / ∈ C is NP-complete, cf. [23].”
BackgroundApproximation algorithms for indefinite quadratic programming
Vavasis, S. A. (1992) · Mathematical Programming · doi:10.1007/bf01581085 · Cited by 80
Active RIS-Aided NOMA-Enabled Space- Air-Ground Integrated Networks With Cognitive Radio
Li, J., Yang, L., Wu, Q., Lei, X., Zhou, F., Shu, F., Mu, X., Liu, Y., & Fan, P. (2024) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2024.3460067 · Cited by 86
“Indeed, (73) is a MINLP problem for which the solution is NP-hard [39].”
Energy-efficient shortest routes for electric and hybrid vehicles
Strehler, M., Merting, S., & Schwan, C. (2017) · Transportation Research Part B Methodological · doi:10.1016/j.trb.2017.03.007 · Cited by 78
Complete dictionary recovery over the sphere
Sun, J., Qu, Q., & Wright, J. N. (2015) · International Conference on Sampling Theory and Applications · doi:10.1109/sampta.2015.7148922 · Cited by 86
Optimization-based methods for nonlinear and hybrid systems verification
Prajna, S. (2005) · CaltechTHESIS (California Institute of Technology) · doi:10.7907/s3bj-4m47 · Cited by 78
A simple effective heuristic for embedded mixed-integer quadratic programming
Takapoui, R., Moehle, N., Boyd, S., & Bemporad, A. (2016) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2016.7526551 · Cited by 83
Power-Aware Activity Monitoring Using Distributed Wearable Sensors
Ghasemzadeh, H., Panuccio, P., Trovato, S., Fortino, G., & Jafari, R. (2014) · IEEE Transactions on Human-Machine Systems · doi:10.1109/thms.2014.2320277 · Cited by 75
“The optimization problem presented in (6) poses several difficulties in arriving at an optimal solution: 1) The communication cost in (4) is a concave function, and minimizing a concave function is considered to be hard in general [30].”
BackgroundA direct active set algorithm for large sparse quadratic programs with simple bounds
Coleman, T. F., & Hulbert, L. A. (1989) · Mathematical Programming · doi:10.1007/bf01589112 · Cited by 75
On validation and invalidation of biological models
Anderson, J., & Papachristodoulou, A. (2009) · BMC Bioinformatics · doi:10.1186/1471-2105-10-132 · Cited by 74
“Polynomial non-negativity is a very important property (as many problems in optimization and systems theory can be reduced to it) which is however very difficult to test (it has been shown to be NP-hard for polynomials of degree greater than or equal to 4 [ 19 ]).”
BackgroundOpen problems in the theory of completely positive and copositive matrices
Berman, A., Dür, M., & Shaked-Monderer, N. (2015) · Electronic Journal of Linear Algebra · doi:10.13001/1081-3810.2943 · Cited by 73
“It has been proved in [50] that checking whether a given matrix is in COPn is a co-NP-complete problem.”
BackgroundTransient Stability Analysis of Large-scale Power Systems: A Survey
Wu, Q.-H., Lin, Y., Hong, C., Su, Y., Wen, T., & Liu, Y. (2023) · CSEE Journal of Power and Energy Systems · doi:10.17775/cseejpes.2022.07110 · Cited by 72
“If both f and V are polynomial, Lyapunov conditions can be regarded as polynomial non-negativity conditions, which are NP-hard to test [86].”
Canonical Duality Theory and Solutions to Constrained Nonconvex Quadratic Programming
Gao, D. Y. (2004) · Journal of Global Optimization · doi:10.1023/b:jogo.0000048034.94449.e3 · Cited by 72
“During the last decade, several authors have shown that the general quadratic programming problem is an NP-hard problem in global optimization (cf. Murty and Kabadi, 1987; Horst et al., 2000).”
BackgroundBomze, I. M., Schachinger, W., & Uchida, G. (2011) · Journal of Global Optimization · doi:10.1007/s10898-011-9749-3 · Cited by 81
“To check whether a given matrix is copositive is NP-hard, see [214]; for the completely positive side, see [99], cf.”
BackgroundMixed 0-1 Linear Programs Under Objective Uncertainty: A Completely Positive Representation
Natarajan, K., Teo, C., & Zheng, Z. (2011) · Operations Research · doi:10.1287/opre.1110.0918 · Cited by 71
“For instance, the problem of testing if a given matrix is copositive is known to be in the co-NP-complete class [31].”
BackgroundA Copositive Programming Approach to Graph Partitioning
Povh, J., & Rendl, F. (2007) · SIAM Journal on Optimization · doi:10.1137/050637467 · Cited by 71
“This does not make the problem tractable, since linear optimization over this cone is NP-hard [13], but suggests a new family of tractable relaxations, which we get by approximating the copositive constraint with a tractable one, for example by using the hierarchy of cones, suggested by Parillo [14], which approximate…”
MethodOptimizing a polyhedral-semidefinite relaxation of completely positive programs
Burer, S. (2010) · Mathematical Programming Computation · doi:10.1007/s12532-010-0010-8 · Cited by 71
“Specifically, the separation problem for K is widely thought to have exponential or worse complexity [3,17].”
BackgroundComputational complexity of norm-maximization
Bodlaender, H. L., Gritzmann, P., Klee, V. L., & Leeuwen, J. V. (1990) · COMBINATORICA · doi:10.1007/bf02123011 · Cited by 71
“The following theorem and its proof are due to Mangasarian and Shiau [28], a closely related result to Freund and Orlin [8], and weaker related results to Sahni [37] and Murty and Kabadi [ 31 ].”
ResultSome applications of polynomial optimization in operations research and real-time decision making
Ahmadi, A. A., & Majumdar, A. (2015) · Optimization Letters · doi:10.1007/s11590-015-0894-3 · Cited by 70
“The task of optimizing over nonnegative polynomials or even checking nonnegativity of a given polynomial, either globally or on a basic semialgebraic set, is known to be NP-hard [33].”
BackgroundGharavol, E. A., & Larsson, E. G. (2012) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2222379 · Cited by 70
Stochastic robustness metric and its use for static resource allocations
Shestak, V., Smith, J. C., Maciejewski, A. A., & Siegel, H. J. (2008) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2008.01.002 · Cited by 79
“However, condition (b) makes the ILP form NP-complete [31], so that for large-scale problems a Linear Programming (LP) relaxation is required to the ILP form that implies that condition (a) is relaxed to real numbers, i.”
BackgroundAn analytical approach to global optimization
Hansen, P., Jaumard, B., & Lu, S.-H. (1991) · Mathematical Programming · doi:10.1007/bf01582889 · Cited by 70
Akrotirianakis, I. G., & Floudas, C. A. (2004) · Journal of Global Optimization · doi:10.1007/s10898-004-6455-4 · Cited by 69
“Even proving that a solution of (1) is not a local minimum is an NP-complete problem (see ( Murty and Kabadi(1987) ) and (Pardalos and Schni tger (1988)).”
BackgroundBurer, S. (2011) · International series in management science/operations research/International series in operations research & management science · doi:10.1007/978-1-4614-0769-0_8 · Cited by 68
Graph Partitioning and Continuous Quadratic Programming
Hager, W. W., & Krylyuk, Y. (1999) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480199335829 · Cited by 68
“For a general quadratic program, deciding whether a given point is a local minimizer is NP-hard (see [37], [39]).”
BackgroundOtto, J., Vogel‐Heuser, B., & Niggemann, O. (2017) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2017.2718729 · Cited by 67
“Mixed integer nonlinear programming (MINLP) problems consist of a nonlinear objective function, linear or nonlinear constraints, continuous and discrete variables [13].”
BackgroundInfluentialThe analysis of local search problems and their heuristics
Yannakakis, M. (1990) · Lecture notes in computer science · doi:10.1007/3-540-52282-4_52 · Cited by 66
Solutions to quadratic minimization problems with box and integer constraints
Gao, D. Y., & Ruan, N. (2009) · Journal of Global Optimization · doi:10.1007/s10898-009-9469-0 · Cited by 65
Copositive realxation for genera quadratic programming
Quist, A. J., de Klerk, E., Roos, C., & Tamás Terlaky, B. (1998) · Optimization methods & software · doi:10.1080/10556789808805692 · Cited by 65
Staggered projections for frictional contact in multibody systems
Kaufman, D. M., Sueda, S., James, D. L., & Pai, D. K. (2008) · ACM SIGGRAPH Conference and Exhibition on Computer Graphics and Interactive Techniques in Asia (SIGGRAPH Asia) · doi:10.1145/1457515.1409117 · Cited by 85
“In general, the solution of non-convex QPs is an NP-hard problem in global optimization [Murty and Kabadi 1987].”
MethodBurer, S., & Saxena, A. (2011) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4614-1927-3_13 · Cited by 64
“Although this cone is apparently intractable [42], it can be approximated from the outside to any precision using a seqence of polyhedral-semidefinite relaxations [26, 47].”
BackgroundComputational complexity of vacua and near-vacua in field and string theory
Halverson, J., & Ruehle, F. (2019) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.99.046015 · Cited by 72
Bomze, I. M. (2002) · SIAM Review · doi:10.1137/s00361445003756 · Cited by 64
Methods for convex and general quadratic programming
Gill, P. E., & Wong, E. (2014) · Mathematical Programming Computation · doi:10.1007/s12532-014-0075-x · Cited by 63
“Murty and Kabadi [48], Pardalos and Schnitger [50], and Pardalos and Vavasis [51]).”
BackgroundEnergy-Aware 3D Unmanned Aerial Vehicle Deployment for Network Throughput Optimization
Chou, S.-F., Pang, A., & Yu, Y.-J. (2019) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2019.2946822 · Cited by 67
“…of constraint (6), the formulated optimization problem (9) is non-convex and non-linear regardless of the convexity and linearity of the objective function and other constraints and therefore falls into the category of non-convex non-linear programs, which are in general hard to solve [36], [37].”
BackgroundImproved Bounds for the Crossing Numbers of Km,n and Kn
de Klerk, E., Maharry, J., Ṗasechnik, D. V., Richter, R. B., & Salazar, G. (2006) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480104442741 · Cited by 63
Llewellyn, D. C., Tovey, C. A., & Trick, M. A. (1989) · Discrete Applied Mathematics · doi:10.1016/0166-218x(89)90025-5 · Cited by 63
Universal gradient descentPreprint
Gasnikov, A. V. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1711.00394 · Cited by 65
“, например, [18, 23, 30, 39, 70, 71, 94, 114, 118, 132, 138, 140, 148, 150, 152, 174, 215, 217, 221, 222, 228, 230, 231, 234, 267, 270, 291, 292, 293, 312, 339, 346, 347, 349, 361, 383, 386, 387, 401, 419, 423, 429, 430, 441, 480, 481, 482, 507, 509, 515, 516, 521, 535, 536, 540] и цитированную там литературу.”
Robust Shortest Path Problem With Distributional Uncertainty
Zhang, Y., Song, S., Shen, Z. M., & Wu, C. (2017) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2017.2709798 · Cited by 62
“In fact, it is co-NP-complete to check whether a given matrix is co-positive on Rn + [23].”
BackgroundAdvanced Methods and Algorithms for Biological Networks Analysis
El‐Samad, H., Prajna, S., Papachristodoulou, A., Doyle, J. C., & Khammash, M. (2006) · Proceedings of the IEEE · doi:10.1109/jproc.2006.871776 · Cited by 65
“…as SOS—in fact, as mentioned earlier, testing global nonnegativity of a polynomial is known to be -hard when the degree of is greater than 4 [41], whereas checking whether can be written as an SOS is computationally tractable—it can be formulated as an LMI which has a worst case…”
BackgroundOn the solution of concave knapsack problems
Morè, J. J., & Vavasis, S. A. (1990) · Mathematical Programming · doi:10.1007/bf01588800 · Cited by 61
A Robust Optimization Model for Managing Elective Admission in a Public Hospital
Meng, F., Qi, J., Zhang, M., Ang, J. S. K., Chu, S., & Sim, M. (2015) · Operations Research · doi:10.1287/opre.2015.1423 · Cited by 60
“41l5l∈L 2 0 3⁄41l3⁄41l′ 3⁄401∀l1l ∈L1 l>l91 ∈T0 Problem (5) is a maximization problem over a probability distribution function, which is generally an intractable optimization problem; see, for instance, Murty and Kabadi (1987). However, under our model of uncertainty, we will show an equivalent formulati…”
BackgroundControl and verification of high-dimensional systems with DSOS and SDSOS programming
Majumdar, A., Ahmadi, A. A., & Tedrake, R. (2014) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2014.7039413 · Cited by 60
“However, checking nonnegativity is NP-hard even when the functions are restricted to the set of polynomials [9].”
BackgroundOn the Design of Sparse but Efficient Structures in Operations
Yan, Z., Gao, S. Y., & Teo, C. (2017) · Management Science · doi:10.1287/mnsc.2017.2761 · Cited by 60
Mixed logical dynamical modeling and hybrid model predictive control of public transport operations
Sırmatel, I. İ., & Geroliminis, N. (2018) · Transportation Research Part B Methodological · doi:10.1016/j.trb.2018.06.009 · Cited by 66
“Such MIQPs, although still non-convex and NP-hard, can be solved much more efficiently compared to the more general integer/mixed integer NLPs with non-convex subproblems, since there exist powerful algorithms for solving the convex QP subproblems (Bonami et al., 2012).”
BackgroundQuadratic Programming with Box Constraints
Angelis, P. L. D., Pardalos, P. M., & Toraldo, G. (1997) · Nonconvex optimization and its applications · doi:10.1007/978-1-4757-2600-8_5 · Cited by 60
Semidefinite programming relaxations for graph coloring and maximal clique problems
Dukanovic, I., & Rendl, F. (2006) · Mathematical Programming · doi:10.1007/s10107-006-0026-z · Cited by 60
“However just checking whether a matrix is completely positive is co-NP-complete [28].”
BackgroundDepth with nonlinearity creates no bad local minima in ResNets
Kawaguchi, K., & Bengio, Y. (2019) · Neural Networks · doi:10.1016/j.neunet.2019.06.009 · Cited by 70
“…with a general non-convex function and with a certain non-convex function induced by some specific neural networks are both known to be NP-hard (Murty and Kabadi, 1987; Blum and Rivest, 1992), which would pose no serious challenge if only it were not high-dimensional (Kawaguchi et al., 2015,…”
BackgroundMélykúti, B., August, E., Papachristodoulou, A., & El-Samad, H. (2010) · BMC Systems Biology · doi:10.1186/1752-0509-4-38 · Cited by 58
Lookahead: A Far-Sighted Alternative of Magnitude-based Pruning
Park, S., Lee, J., Mo, S., & Shin, J. (2020) · arXiv · doi:10.48550/arxiv.2002.04809 · Cited by 58
“(3) is NP-hard by showing the reduction from the following binary quadratic programming which is NP-hard (Murty & Kabadi, 1987): for some symmetric matrix A ∈ R n × n .”
BackgroundQuantum Metrology in the Finite-Sample Regime
Meyer, J. J., Khatri, S., França, D. S., Eisert, J., & Faist, P. (2025) · PRX Quantum · doi:10.1103/qbn1-p6bq · Cited by 74
“…the optimal minimax success probability is given by the quadratic form The optimal probe state is hence obtained by solving the optimization problem Because of the positivity constraint on the entries of the vector, this is in general an NP-hard optimization problem [107] in worst-case complexity.”
Bounds on mean energy in the Kuramoto–Sivashinsky equation computed using semidefinite programming
Goluskin, D., & Fantuzzi, G. (2019) · Nonlinearity · doi:10.1088/1361-6544/ab018b · Cited by 58
“(23) Even with computer assistance it is prohibitively difficult in general to decide whether a polynomial is nonnegative—the computational complexity is NP-hard [38].”
BackgroundMultilevel Combinatorial Optimization across Quantum Architectures
Ushijima-Mwesigwa, H., Shaydulin, R., Negre, C. F. A., Mniszewski, S. M., Alexeev, Y., & Safro, I. (2021) · ACM Transactions on Quantum Computing · doi:10.1145/3425607 · Cited by 57
“At the time of writing the best known upper bound is that the problem of optimizing β,γ is as hard as finding a global minimizer to a nonconvex problem, where even verifying a feasible point is a local minimizer is NP-hard [58].”
BackgroundKronberger, G., Burlacu, B., Kommenda, M., Winkler, S., & Affenzeller, M. (2024) · Chapman & Hall/CRC eBooks · doi:10.1201/9781315166407 · Cited by 71
A Gentle Introduction to Optimization
Guenin, B., Könemann, J., & Tunçel, L. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781107282094 · Cited by 69
Scalable analysis of nonlinear systems using convex optimization
Papachristodoulou, A. (2005) · doi:10.7907/5yg6-jg32 · Cited by 55
On Designing Energy-Efficient Heterogeneous Cloud Radio Access Networks
Liu, Q., Han, T., Ansari, N., & Wu, G. (2018) · IEEE Transactions on Green Communications and Networking · doi:10.1109/tgcn.2018.2835451 · Cited by 55
“With the binary RB assignment, the NEE optimization problem is a mixed integer non-linear programming (MINLP) problem which is NP-hard and difficult to be solved [13], [23], [34].”
BackgroundMethodSufficient conditions for the synthesis ofH? fixed-order controllers
Mattei, M. (2000) · International Journal of Robust and Nonlinear Control · doi:10.1002/1099-1239(20001230)10:15 · Cited by 55
A continuous approach to nonlinear integer programming
Ge, R., & Huang, C. (1989) · Applied Mathematics and Computation · doi:10.1016/0096-3003(89)90005-2 · Cited by 55
Energy Management in Cross-Domain Content Delivery Networks: A Theoretical Perspective
Ge, C., Sun, Z., Wang, N., Xu, K., & Wu, J. (2014) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2014.2346956 · Cited by 54
“Problem (P) has been shown to be NP-hard in [20] since it can be reduced from a smooth non-convex nonlinear programming problem.”
BackgroundA convex polynomial that is not sos-convex
Ahmadi, A. A., & Parrilo, P. A. (2011) · Mathematical Programming · doi:10.1007/s10107-011-0457-z · Cited by 54
“Unfortunately, this problem is known to be NP-hard even when the degree of the polynomial is equal to four [21], [17].”
BackgroundCriteria for copositive matrices using simplices and barycentric coordinates
Andersson, L., Chang, G., & Elfving, T. (1995) · Linear Algebra and its Applications · doi:10.1016/0024-3795(94)00161-6 · Cited by 53
On the complexity of approximating a KKT point of quadratic programming
Ye, Y. (1998) · Mathematical Programming · doi:10.1007/bf01581726 · Cited by 53
“Finding a local minimal and checking the existence of a KKT point are NP-complete problems (see, e.g., [ 16 ,8,9,19,20]).”
BackgroundKim, S., Kojima, M., & Toh, K.-C. (2015) · Mathematical Programming · doi:10.1007/s10107-015-0874-5 · Cited by 53
Extensions of Gauss Quadrature Via Linear Programming
Ryu, E. K., & Boyd, S. (2014) · Foundations of Computational Mathematics · doi:10.1007/s10208-014-9197-9 · Cited by 53
“The problem of deciding polynomial nonnegativity in Rd is NP-hard [25], and we will reduce it to problem (2) with Lasserre’s approach to convexifying the polynomial nonnegativity problem [20].”
BackgroundScalable Solvers of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
Wang, G., Giannakis, G. B., & Chen, J. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2652392 · Cited by 55
“ic terms in (3) and (4). It is well known that nonconvex functions may exhibit many stationary points, and minimizing nonconvex objectives is in general NP-hard, and hence computationally intractable [23]. It is worth stressing that it is NP-hard to establish convergence to a local minimum due to the existence of comp…”
BackgroundUndecidability and hardness in mixed-integer nonlinear programming
Liberti, L. (2018) · RAIRO - Operations Research · doi:10.1051/ro/2018036 · Cited by 53
“Moreover, [68] also shows that deciding copositivity of a given matrix is co-NP -hard; it further proves co-NP -hardness of verifying that a point is not a local optimum in unconstrained minimization (of a polynomial of degree 4).”
BackgroundInfluentialA global solution to the nonlinear model predictive control algorithms using polynomial ARX models
Sriniwas, G. R., & Arkun, Y. (1997) · Computers & Chemical Engineering · doi:10.1016/s0098-1354(96)00279-7 · Cited by 52
A convex polynomial that is not sos-convexPreprint
Ahmadi, A. A., & Parrilo, P. A. (2012) · Cited by 52
An exact algorithm for graph partitioning
Hager, W. W., Phan, D. T., & Zhang, H. (2011) · Mathematical Programming · doi:10.1007/s10107-011-0503-x · Cited by 51
“This is in contrast to the general quadratic programming problem for which deciding whether a given point is a local minimizer is NP-hard (see [29, 30]).”
Inexact Nonconvex Newton-Type Methods
Yao, Z., Xu, P., Roosta, F., & Mahoney, M. W. (2021) · INFORMS Journal on Optimization · doi:10.1287/ijoo.2019.0043 · Cited by 61
Efficient Revenue-Based MEC Server Deployment and Management in Mobile Edge-Cloud Computing
Zhang, Y., Wei, W., Ren, J., Huang, J., He, S., & Zhang, Y. (2022) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2022.3217280 · Cited by 51
“The optimization problem P is a mixed-integer nonlinear programming problem (MINLP), which is NP-hard [33].”
BackgroundSwitched Positive Linear Systems
Blanchini, F., Colaneri, P., & Valcher, M. E. (2015) · now publishers, Inc. eBooks · doi:10.1561/9781680830712 · Cited by 56
Canonical Duality Theory: Connections between Nonconvex Mechanics and Global Optimization
Gao, D. Y., & Sherali, H. D. (2009) · Advances in mechanics and mathematics · doi:10.1007/978-0-387-75714-8_8 · Cited by 49
“During the last decade, several authors have shown that the general quadratic programming problem (P) is an NP-hard problem in global optimization (cf. Murty and Kabadi, 1987; Horst et al., 2000).”
BackgroundOptimization and analysis of the profitability of tariff structures with two-part tariffs
Schlereth, C., Stepanchuk, T., & Skiera, B. (2010) · European Journal of Operational Research · doi:10.1016/j.ejor.2010.03.038 · Cited by 49
UNCERTAINTY- IMMUNIZED SOLUTIONS IN LINEAR PROGRAMMING
Guslitser, E. (2002) · Cited by 49
Effect of Depth and Width on Local Minima in Deep Learning
Kawaguchi, K., Huang, J., & Kaelbling, L. P. (2019) · Neural Computation · doi:10.1162/neco_a_01195 · Cited by 62
“Finding a global minimum of a general nonconvex function is NP-hard (Murty & Kabadi, 1987), and nonconvex optimization to train certain types of neural networks is also known to be NP-hard (Blum & Rivest, 1992).”
BackgroundThe Complexity of Gradient Descent: CLS = PPAD ∩ PLS
Fearnley, J., Goldberg, P. W., Hollender, A., & Savani, R. (2022) · Journal of the ACM · doi:10.1145/3568163 · Cited by 48
Optimality conditions for nonconvex semidefinite programming
Forsgren, A. L. (2000) · Mathematical Programming · doi:10.1007/pl00011370 · Cited by 48
“However, it can be observed that verification of optimality conditions that involve nonnegative curvature over a cone is an NP-hard problem, even for the case of nonconvex quadratic programming, if strict complementarity does not hold (and if the cone is not a subspace), see Murty and Kabadi [18] and Pardalos and Schn…”
BackgroundThe extreme rays of the 5 × 5 copositive cone
Hildebrand, R. (2012) · Linear Algebra and its Applications · doi:10.1016/j.laa.2012.04.017 · Cited by 47
Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points
Birgin, E. G., Haeser, G., & Ramos, A. (2017) · Computational Optimization and Applications · doi:10.1007/s10589-017-9937-2 · Cited by 47
“In contrast, checking the positive semidefiniteness of a matrix on a pointed cone is an NP-hard problem [56].”
BackgroundQoE-Driven Transmission-Aware Cache Placement and Cooperative Beamforming Design in Cloud-RANs
Sun, R., Wang, Y., Cheng, N., Lyu, L., Zhang, S., Zhou, H., & Shen, X. (2019) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2019.2952726 · Cited by 49
“According to [32], finding global maximizers to nonconvex problems is a daunting task.”
BackgroundData-dependent Gaussian Prior Objective for Language Generation
Li, Z., Wang, R., Chen, K., Utiyama, M., Sumita, E., Zhang, Z., & Zhao, H. (2020) · International Conference on Learning Representations · Cited by 72
On Finite-Time Convergence of Actor-Critic Algorithm
Qiu, S., Yang, Z., Ye, J., & Wang, Z. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3078754 · Cited by 47
“Even finding a local minimum via gradient-based updates can be NP-hard in the worst case [18].”
BackgroundLim, L. (2021) · Acta Numerica · doi:10.1017/s0962492921000076 · Cited by 68
Numerical Methods for Large-Scale Non-Convex Quadratic Programming
Gould, N. I. M., & Toint, P. L. (2002) · Applied optimization · doi:10.1007/978-1-4613-0263-6_8 · Cited by 46
“…methods that can guarantee to be within a certain fraction of local criticality in polynomial time (see, Ye, 1997)—as is even establishing that a given first-order critical (constrained stationary) point is a local minimizer (see, e.g., Murty and Kabadi, 1987, and Pardalos and Schnitger, 1988).”
BackgroundBlack-Box Complexity of Local Minimization
Vavasis, S. A. (1993) · SIAM Journal on Optimization · doi:10.1137/0803004 · Cited by 46
Elimination of All Bad Local Minima in Deep LearningPreprint
Kawaguchi, K., & Kaelbling, L. P. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.00279 · Cited by 46
“Indeed, it is NP-hard to find a global minimum of a general non-convex function (Murty & Kabadi, 1987), and of non-convex objective functions used to train certain types of neural networks (Blum & Rivest, 1992), which poses a concern regarding high-dimensional problems (Kawaguchi et al., 2015).”
BackgroundCopositive Lyapunov functions for switched systems over cones
Bundfuss, S., & Dür, M. (2009) · Systems & Control Letters · doi:10.1016/j.sysconle.2008.12.006 · Cited by 44
Branch-and-bound approaches to standard quadratic optimization problems
Bomze, I. M. (2002) · Journal of Global Optimization · doi:10.1023/a:1013886408463 · Cited by 44
Global extremal conditions for multi-integer quadratic programming
Wang, Z., Fang, S., Gao, D. Y., & Xing, W. (2008) · Journal of Industrial and Management Optimization · doi:10.3934/jimo.2008.4.213 · Cited by 44
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.