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 701–800 of 1,000
Utility-based downlink power allocation in multicell wireless packet networks
Lim, H.-K., Choi, J., & Bahk, S. (2006) · Computer Communications · doi:10.1016/j.comcom.2006.07.010 · Cited by 4
“Since A and S1 are not the convex but NP problems [20], we are not able to solve them in a polynomial time.”
BackgroundShape-Changing L-SR1 Trust-Region MethodsPreprint
Brust, J. J., Burdakov, O. P., Erway, J. B., Marcia, R. F., & Yuan, Y.-X. (2016) · arXiv (Cornell University) · Cited by 4
Chang, T., Hong, M., & Pang, J. (2017) · arXiv (Cornell University) · Cited by 4
Optimal time averages in non-autonomous nonlinear dynamical systemsPreprint
Doering, C. R., & McMillan, A. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.07856 · Cited by 4
“Even determining the non-negativity of a multivariate polynomial is still NP hard, however, except for an extremely limited set of examples such as uni-variate or quadratic polynomials [20].”
BackgroundMethodComputational Statistics and Data Science in the Twenty‐First Century
Holbrook, A. J., Nishimura, A., Ji, X., & Suchard, M. A. (2021) · Wiley eBooks · doi:10.1002/9781118445112.stat08324 · Cited by 4
“Global optimization, or the problem of finding the minimum of a function with arbitrarily many local minima, is NP-complete in general (Murty and Kabadi, 1985), meaning—in layman’s terms—it is impossibly hard.”
BackgroundQuadratic Programming with Bound Constraints
Angelis, P. L. D., & Toraldo, G. (2008) · Springer eBooks · doi:10.1007/978-0-387-74759-0_538 · Cited by 4
SPEAR++: Scaling Gradient Inversion via Sparsely-Used Dictionary LearningPreprint
Bakarsky, A., Dimitrov, D. I., Baader, M., & Vechev, M. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2510.24200 · Cited by 5
“…with decomposing an observed matrix L into a sparse coefficient matrix, in our case ∂ L ∂Z , multiplied by a square and invertible (complete Even though the problem is known to be NP-hard [16], polynomial-time algorithms which succeed with high probability have been devised [21, 19, 1, 9, 13, 22].”
Relaxations in mixed-integer quadratically constrained programming and robust programming
Wang, G. (2016) · theses.fr (ABES) · doi:10.70675/f186db86zfcc8z4f94zaed5z3e5ba7e74a03 · Cited by 4
“And it is well-known that the membership problem of copositive matrix cone is co-NP-complete [127].”
BackgroundA Conservation Law for Equilibrium Propagation and Coupled LearningPreprint
McGinnis, J. A., Kline, A. G., & Mori, Y. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2606.15444 · Cited by 4
“The resulting loss is generally non-convex in the trainable parameters, and non-convex optimization is NP-hard in the worst case [4]; however, certain restricted topologies, such as the bipartite crossbar arrays we treat in Theorem 4.4, admit more tractable structure.”
InfluentialA Random Copositive Matrix Is Completely Positive with Positive Probability
Klep, I., Štrekelj, T., & Zalar, A. (2024) · SIAM Journal on Applied Algebra and Geometry · doi:10.1137/23m1583491 · Cited by 3
Truncated amplitude flow with coded diffraction patterns
Li, H., & Li, J. (2024) · Inverse Problems · doi:10.1088/1361-6420/ad99f8 · Cited by 3
“As a result, this problem is generally NP-hard [39].”
The Complexity of Computing KKT Solutions of Quadratic Programs
Fearnley, J., Goldberg, P. W., Hollender, A., & Savani, R. (2025) · Journal of the ACM · doi:10.1145/3745017 · Cited by 3
Reducing Mobility-Related Signaling With Network Sum Throughput Maximization in 5G
Prado, A., Mehmeti, F., & Kellerer, W. (2025) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2025.3599203 · Cited by 3
“Solving our MINLP problem is challenging since there is absolutely no guarantee to find the global minimum for a non-convex MINLP in polynomial time [32].”
A Scalable and Secure RFID Ownership Transfer Protocol
Mamun, M., & Miyaji, A. (2014) · International Conference on Advanced Information Networking and Applications (AINA) · doi:10.1109/aina.2014.149 · Cited by 3
Some aspects of studying an optimization or decision problem in different computational models
Meer, K., & Weber, G. (2002) · European Journal of Operational Research · doi:10.1016/s0377-2217(02)00269-2 · Cited by 3
Backstepping controller synthesis for piecewise polynomial systems: a sum of squares approach
Samadi, B., & Rodrigues, L. (2009) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2009.5160371 · Cited by 3
“Although verifying nonnegativity of a polynomial is an NP-hard problem [10], the SOS condition can be formulated as a convex problem in polynomial coefficients [11].”
BackgroundOn the interplay of network structure and gradient convergence in deep learning
Ithapu, V. K., Ravi, S. N., & Singh, V. (2016) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2016.7852271 · Cited by 3
“First, note that it is NP-hard to check local minima even for simple non-convex problems [34] — so, an analysis using the norms of the gradients is an attractive alternative, especially, if it leads to a”
Robust Performance of Spectrum Sensing in Cognitive Radio Networks
Gong, S., Wang, P., & Huang, J. (2012) · Advances in wireless technologies and telecommunication book series · doi:10.4018/978-1-4666-2005-6.ch003 · Cited by 3
ElliPose: Stereoscopic 3D Human Pose Estimation by Fitting Ellipsoids
Grund, C., Tanke, J., & Gall, J. (2023) · IEEE Winter Conference on Applications of Computer Vision · doi:10.1109/wacv56688.2023.00289 · Cited by 5
“Due to the non-convex nature of the second part of the equation this problem is NPcomplete [36].”
BackgroundBomze, I. M., Peng, B., Qiu, Y., & Yıldırım, E. A. (2025) · Mathematical Programming Computation · doi:10.1007/s12532-025-00285-z · Cited by 3
“Despite the fact that (CP1A( ρ )) and (CP2A( ρ )) are convex optimization problems, they are, in general, NP-hard [36].”
Meli, N. K., Golyanik, V., Benkner, M. S., & Moeller, M. (2025) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr52734.2025.01064 · Cited by 5
“If X is further non-convex, as e.g., the set B k := { 0 , 1 } k of binary vectors of length k , Problem (2) is generally NP - hard [52] and, very often, can be solved only approximately.”
A Tight SDP Relaxation for the Cubic-Quartic Regularization Problem
Zhou, J., Liu, X., Nie, J., & Tang, X. (2026) · Mathematical Programming · doi:10.1007/s10107-026-02413-6 · Cited by 3
“Moreover, we also show that the inequality (1.6) must hold and the SDP relaxation is tight if either β ≥ 0 or H has a nonpositive eigenvalue.”
InfluentialCopositivity criteria of a class of fourth order symmetric tensors
Song, Y., & Liu, J. (2026) · Revista de la Real Academia de Ciencias Exactas Físicas y Naturales Serie A Matemáticas · doi:10.1007/s13398-026-01835-3 · Cited by 3
“However, it was already well known that it is an NP-hard problem in general to determine the copositivity (or positive semi-definiteness) of a general fourth order tensor [21, 35].”
Athalye, C. D. (2015) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7402369 · Cited by 3
“Checking positive definiteness of simple polynomial functions is also an NP-hard problem when polynomial has degree 4 or higher [8].”
BackgroundStefanov, S. M. (2018) · Journal of Information and Optimization Sciences · doi:10.1080/02522667.2017.1317956 · Cited by 3
“Some NP-complete problems in quadratic and nonlinear programming are considered in [K. G. Murty and S. N. Kabadi 8].”
BackgroundNonconvex min–max fractional quadratic problems under quadratic constraints: copositive relaxations
Amaral, P. A., & Bomze, I. M. (2019) · Journal of Global Optimization · doi:10.1007/s10898-019-00780-3 · Cited by 3
Kamath, U., Liu, J., & Whitaker, J. (2019) · Springer eBooks · doi:10.1007/978-3-030-14596-5_4 · Cited by 3
On types of degenerate critical points of real polynomial functions
Guo, F., & Phạm, T.-S. (2019) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2019.03.004 · Cited by 3
Geometric control of algebraic systems
Legat, B., & Jungers, R. M. (2021) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2021.08.478 · Cited by 3
Balancing Wind and Batteries: Towards Predictive Verification of Smart Grids
Badings, T., Hartmanns, A., Jansen, N., & Suilen, M. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-76384-8_1 · Cited by 3
Performance comparison of two recently proposed copositivity tests
Peng, B. (2022) · EURO Journal on Computational Optimization · doi:10.1016/j.ejco.2022.100037 · Cited by 3
A game-theoretic perspective of deep neural networks
Ren, C., Wu, Z., Xu, D., & Xu, W. (2022) · Theoretical Computer Science · doi:10.1016/j.tcs.2022.09.035 · Cited by 3
Local Optimality Conditions for a Family of Hidden Convex Optimization
Song, M., Xia, Y., & Liu, H. (2023) · INFORMS Journal on Optimization · doi:10.1287/ijoo.2023.0089 · Cited by 3
Hu, J. J., & Ma, H. (2023) · Journal of Modern Power Systems and Clean Energy · doi:10.35833/mpce.2021.000730 · Cited by 3
“Because of the existence of the bi-linear term (5), the orig‐ inal problem in (4) and (5) is non-convex and it cannot be efficiently solved [30].”
BackgroundVárkonyi, P. L. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3333738 · Cited by 3
“In general, there is no efficient computational method to test the nonnegativity of a function or even of a polynomial function [37].”
MethodCopositive Matrices, Sums of Squares and the Stability Number of a Graph
Vargas, L. F., & Laurent, M. (2023) · Springer optimization and its applications · doi:10.1007/978-3-031-38659-6_4 · Cited by 3
Polynomial Optimization, Moments, and Applications
Kočvara, M., Mourrain, B., & Riener, C. (2023) · Springer optimization and its applications · doi:10.1007/978-3-031-38659-6 · Cited by 3
Scalar bounded-from-below conditions from Bayesian active learning
Wojcik, G. N. (2024) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.109.095018 · Cited by 3
“Unfortunately, while it is always possible to determine the positive-definiteness of a given rank-4 tensor [7], the general procedure to do so is NP-hard [7, 9, 10], and hence often not feasible to accomplish even for numerical scans of the model parameter space.”
BackgroundPotential Games on Cubic Splines for Self-Interested Multi-Agent Motion Planning
Williams, S., & Deshmukh, J. V. (2024) · IEEE Control Systems Letters · doi:10.1109/lcsys.2024.3491052 · Cited by 3
“…this theorem proves convergence only to stationary points of φ which is not sufficient for the local NE condition (18), we still consider convergence to these points to be reasonable in our game-theoretic setting as finding a descent direction from a non-strict saddle [24] is an NP-hard problem [25].”
Convex Quadratic Sets and the Complexity of Mixed Integer Convex Quadratic Programming
Pia, A. D. (2025) · SIAM Journal on Optimization · doi:10.1137/24m1636782 · Cited by 3
“In fact, determining whether a nonconvex quadratic programming problem is bounded is NP-hard [22], even if the rank of the quadratic matrix H is three [10].”
BackgroundZhao, H. V., Yue, P., & Fang, C. (2026) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2026.3677732 · Cited by 3
Stability of nonlinear hybrid dynamical systems with time delay via sum of squares decomposition
Badamchizadeh, M. A., Khanmohammadi, S., Alizadeh, G., & Aghagolzade, A. (2009) · International Journal of Control Automation and Systems · doi:10.1007/s12555-009-0301-x · Cited by 3
“In the case where both the vector field f and the Lyapunov function candidate V are polynomials, the Lyapunov conditions are essentially polynomial nonnegativity conditions which can be NP hard to test [ 30 ]; probably this is one of the reasons for the lack of algorithmic construction of Lyapunov functions.”
BackgroundOn a quadratic programming problem involving distances in trees
Bapat, R. B., & Neogy, S. K. (2014) · Annals of Operations Research · doi:10.1007/s10479-014-1743-y · Cited by 3
“Tardos (1986) described a polynomial algorithm for solving the linear programming problems in which the number of arithmetic steps depends only on the size of the numbers in the constraint matrix and is independent of the size of the numbers in the right hand side and the cost coefficients. Granot and Skorin-Kapov (19…”
Global Optimization of Polynomial Functions and Applications
Nie, J. (2006) · Cited by 3
Xiong, Z., & Liu, Z. (2016) · Complex Analysis and Operator Theory · doi:10.1007/s11785-016-0600-1 · Cited by 3
August, E. (2012) · Journal of Computational Biology · doi:10.1089/cmb.2011.0134 · Cited by 3
Pricing A Class of Multiasset Options using Information on Smaller Subsets of Assets
Natarajan, K. (2007) · Cited by 3
Quadratically Constrained Quadratic Programming Problems and Extensions
Jin, Q. (2011) · NCSU Libraries Repository (North Carolina State University Libraries) · Cited by 3
On matrix algebras associated to sum-of-squares semidefinite programs
Cafuta, K. (2013) · Linear and Multilinear Algebra · doi:10.1080/03081087.2012.758261 · Cited by 3
The CP-Matrix Approximation Problem
Fan, J., & Zhou, A. (2016) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/15m1012086 · Cited by 3
“However, checking the membership in CP n has been shown NP-hard, while checking the membership in COP n co-NP-hard [13, 26].”
BackgroundStatistical Data Assimilation: Formulation and Examples From Neurobiology
Miller, A., Li, D., Platt, J. A., Daou, A., Margoliash, D., & Abarbanel, H. D. I. (2018) · Frontiers in Applied Mathematics and Statistics · doi:10.3389/fams.2018.00053 · Cited by 3
“This soundsmore or less straightforward; however, finding the global minimum of a nonlinear function such as A(X) is an NPcomplete problem [13].”
BackgroundJarre, F., & Vavasis, S. A. (2009) · Chapman & Hall/CRC applied algorithms and data structures series · doi:10.1201/9781584888239-c32 · Cited by 3
Partially distributed outer approximation
Murray, A., Faulwasser, T., Hagenmeyer, V., Villanueva, M. E., & Houska, B. (2021) · Journal of Global Optimization · doi:10.1007/s10898-021-01015-0 · Cited by 3
“e MILP with Nninteger variables. This result is summarized in Theorem 2, which analyzes one-step convergence conditions for PaDOA. In the sense that both MICPs as well as MILPs are NP hard in general [19,35], this result is not in con ict with existing complexity results for mixed integer optimization problems. Howeve…”
BackgroundResultAndrei, N. (2017) · Springer optimization and its applications · doi:10.1007/978-3-319-58356-3_10 · Cited by 3
Image guided respiratory motion analysis: time series and image registration
Fessler, J. A., & Ruan, D. (2008) · Deep Blue (University of Michigan) · Cited by 3
Optimization under Moment, Robust, and Data-Driven Models of Uncertainty
Doan, X. V. (2010) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 3
Higher order semi-definite relaxations for quadratic programming
Parrilo, P. A. (2002) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2001.914653 · Cited by 3
The explosive scanning devices allocation problem for airport security systems
Attagara, J. (2006) · ThinkTech (Texas Tech University) · Cited by 3
Machine Learning as Statistical Data AssimilationPreprint
Abarbanel, H. D. I., Rozdeba, P. J., & Shirman, S. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1710.07276 · Cited by 3
“Finding the global minimum is an NP-complete problem [13].”
The relief indicator method as a new approach to constrained global optimization
Tụy, H. (2005) · Springer eBooks · doi:10.1007/bfb0008372 · Cited by 3
Complexity of Ten Decision Problems in Continuous Time Dynamical SystemsPreprint
Ahmadi, A. A., Majumdar, A., & Tedrake, R. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1210.7420 · Cited by 3
“as an immediate consequence of NP-hardness testing matrix copositivity [20].”
BackgroundIll-Posedness and Optimization Geometry for Nonlinear Neural Network TrainingPreprint
O’Leary-Roseberry, T., & Ghattas, O. N. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.02882 · Cited by 3
“Finding a global minimum is NPhard and instead one usually settles for local minimizers (Bertsekas, 1997; Murty & Kabadi, 1987).”
BackgroundYajima, Y. (2008) · Springer eBooks · doi:10.1007/978-0-387-74759-0_537 · Cited by 3
Busygin, S. (2008) · Springer eBooks · doi:10.1007/978-0-387-74759-0_100 · Cited by 3
Graph-theoretic algorithms for polynomial optimization problems
Sojoudi, S., Madani, R., Fazelnia, G., & Lavaei, J. (2014) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2014.7039733 · Cited by 2
“Nevertheless, several classes of optimization problems, including polynomial optimization and quadratically constrained quadratic program (QCQP) as a special case, are nonlinear, non-convex, and NP-hard in the worst case [5], [6].”
BackgroundPower-Aware Classifier Selection in Wireless Sensor Networks.
Xiao, K., Wang, J., Wang, R., & Cui, L. (2016) · Journal of information science and engineering · doi:10.6688/jise.2016.32.2.11 · Cited by 2
“Thus, it is difficult to minimize the objective function in general according to [25].”
BackgroundLinear Regularizers Enforce the Strict Saddle Property
Ubl, M., Hale, M., & Yazdani, K. (2023) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v37i8.26194 · Cited by 2
“Often, one seeks convergence to a local mini-mizer in such problems because finding global minima is known to be NP complete (Murty and Kabadi 1987).”
BackgroundGlobal Convergence of a Second-order Augmented Lagrangian Method Under an Error Bound Condition
Andreani, R., Haeser, G., Prado, R. W., Schuverdt, M. L., & Secchin, L. D. (2025) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-025-02731-3 · Cited by 2
“Nevertheless, even testing such a condition at a given and fixed point is hard [33].”
Extremal copositive matrices with minimal zero supports of cardinality two
Hildebrand, R. (2017) · Linear and Multilinear Algebra · doi:10.1080/03081087.2017.1388355 · Cited by 2
“problems can be reformulated as conic programs over Cn. For a detailed survey of the applications of this cone see, e.g., [11, 4]. Verifying copositivity of a given matrix is a co-NP-complete problem [16], and the complexity of the copositive cone quickly grows with dimension. In this note we focus on the extreme rays…”
BackgroundTrading-Off Computing and Cooling Energies by VM Migration in Data Centers
Song, Y., Zhao, X., Wang, B., & Sun, Y. (2018) · IEICE Transactions on Information and Systems · doi:10.1587/transinf.2017edp7329 · Cited by 2
“The above nonlinear integer programming problem C 2 vmMap is NP hard [6], thus its solution faces the conflict between the online computing and the scalability.”
BackgroundOn Degenerate Doubly Nonnegative Projection Problems
Cui, Y., Liang, L., Sun, D., & Toh, K.-C. (2021) · Mathematics of Operations Research · doi:10.1287/moor.2021.1205 · Cited by 2
“However, both cones are computationally intractable, in the sense that to check whether a given matrix lies in C is co-NP-complete [30] and in Cn,∗ is NP-hard [15].”
BackgroundLocal saddle points for unconstrained polynomial optimization
Zhao, W., & Zhou, G. (2022) · Computational Optimization and Applications · doi:10.1007/s10589-022-00361-3 · Cited by 2
“3), it is mostly open how to identify if it is a local saddle point or not, because detecting local optimality is NP-hard [29].”
BackgroundInfluentialLu, J., She, Z., & Liu, K. (2022) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.6164 · Cited by 2
“2442x 2 2 satisfying constraints (43)–(45).”
Tang, Y., Luo, G., & Yang, Q. (2022) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2022.114915 · Cited by 2
Convex computation of maximal Lyapunov exponents
Oeri, H. E., & Goluskin, D. (2023) · Nonlinearity · doi:10.1088/1361-6544/acecf5 · Cited by 2
“Even for polynomial S the right-hand minimization in (9) is often intractable; deciding nonnegativity of a multivariate polynomial on a given set has NP-hard computational complexity in general [47].”
BackgroundGradient projection method on the sphere, complementarity problems and copositivity
Ferreira, O. P., Gao, Y., Németh, S. Z., & Rigó, P. R. (2024) · Journal of Global Optimization · doi:10.1007/s10898-024-01390-4 · Cited by 2
Global Minimization of Polynomial Integral Functionals
Fantuzzi, G., & Fuentes, F. (2024) · SIAM Journal on Scientific Computing · doi:10.1137/23m1592584 · Cited by 2
“This is an NP-hard problem in general [35].”
Study of the cone of sums of squares plus sums of nonnegative circuit forms
Dressler, M., Kuhlmann, S., & Schick, M. (2025) · Advances in Geometry · doi:10.1515/advgeom-2024-0031 · Cited by 2
“However, deciding membership in the PSD cone is in general NP-hard and hence intractable for practical purposes, see [MK87, BR95].”
Construction of exceptional copositive matrices
Štrekelj, T., & Zalar, A. (2025) · Linear Algebra and its Applications · doi:10.1016/j.laa.2025.08.010 · Cited by 2
“However, the membership problem for COP n is co-NP-complete [MK87] and NP-hard for CP n [DG14].”
Aggarwal, S., & Sharma, U. (2013) · International Journal of Pure and Apllied Mathematics · doi:10.12732/ijpam.v89i4.6 · Cited by 2
“Murty and Kabadi (1987) discussed that non-convex problem is an N-P Hard problem and it is very hard to get the global maxima.”
BackgroundInfluentialExtremal Ranks of Some Nonlinear Matrix Expressions with Applications
Xiong, Z., & Qin, Y. (2013) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-013-0508-0 · Cited by 2
“, [3, 9–12]), in particular, to give the maximal and minimal possible”
BackgroundA FPTAS for Computing a Symmetric Leontief Competitive Economy Equilibrium
Zhu, Z., Dang, C., & Ye, Y. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-92185-1_12 · Cited by 2
Tụy, H. (2016) · Springer optimization and its applications · doi:10.1007/978-3-319-31484-6_5 · Cited by 2
A characterization of solutions for general copositive quadratic Lyapunov inequalities
Kim, K. K., & Braatz, R. D. (2013) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2013.6760403 · Cited by 2
“Notice that copositive programs are convex, but NP-hard [8].”
BackgroundEngau, A. (2014) · Asia Pacific Journal of Operational Research · doi:10.1142/s0217595914500225 · Cited by 2
A New Conic Approach to Semisupervised Support Vector Machines
Tian, Y., Luo, J., & Yan, X. (2016) · Mathematical Problems in Engineering · doi:10.1155/2016/6471672 · Cited by 2
“But, unfortunately, the cone of completely positive matrices is not computable; that is, detecting whether a matrix belongs to the cone is NP-hard [23].”
BackgroundInfluentialA Multi-supplier Inventory Model with Permissible Delay in Payment and Discount
Farhangi, M., & Mehdizadeh, E. (2016) · International journal of industrial mathematics. · Cited by 2
Dickinson, P. J. C., & Povh, J. (2014) · Cited by 2
Birgin, E. G., Ernesto, G., Lobato, Rafael, D., Martínez, & Marío, J. (2016) · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · Cited by 2
Optimal Transformation Estimation with Semantic Cues
Paudel, D. P., Habed, A., & Gool, L. V. (2017) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.499 · Cited by 2
Inductive Two-layer Modeling with Parametric Bregman Transfer.
Ganapathiraman, V., Shi, Z., Zhang, X., & Yu, Y. (2018) · International Conference on Machine Learning · Cited by 4
Paradigm and Paradox in Topology Control of Power Grids
Wang, S., & Baillieul, J. B. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8618888 · Cited by 2
Smart Advertisement for Maximal Clicks in Online Social Networks Without User Data
Hudson, N., Khamfroush, H., Harrison, B. E., & Craig, A. W. (2020) · IEEE International Conference on Smart Computing · doi:10.1109/smartcomp50058.2020.00042 · Cited by 3
“This can be suggested under the observation that global optimization of a non-convex/concave function is found to be NP-hard [33], [34].”
BackgroundConvergence Behavior of Belief Propagation: Estimating Regions of Attraction via Lyapunov Functions
Leisenberger, H., Knoll, C. J., Seeber, R., & Pernkopf, F. (2021) · Uncertainty in Artificial Intelligence · Cited by 2
Two methods for the maximization of homogeneous polynomials over the simplex
Ahmed, F., & Still, G. J. (2021) · Computational Optimization and Applications · doi:10.1007/s10589-021-00307-1 · Cited by 2
A Sum of Squares Characterization of Perfect Graphs
Ahmadi, A. A., & Dibek, C. (2023) · SIAM Journal on Applied Algebra and Geometry · doi:10.1137/22m1530410 · Cited by 2
“Moreover, several combinatorial problems that are NP-hard on general graphs can be solved efficiently on perfect graphs using semidefinite programming [41].”
BackgroundInfluentialA Game-Theoretic Analysis of Deep Neural Networks
Ren, C., Wu, Z., Xu, D., & Xu, W. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-93176-6_31 · Cited by 2
Novel Metaheuristic: Spy Algorithm
Pambudi, D., & Kawamura, M. (2022) · IEICE Transactions on Information and Systems · doi:10.1587/transinf.2021edp7092 · Cited by 2
“…di ffi cult to solve since there are many local optimums, valleys, or plateaus that can trap the algorithm so that it fails to find a global optimum. sin 20 ( Himmelblau The optimization of the non-convex function is categorized as NP-hard [19], so it is suitable for testing metaheuristic algorithms.”
BackgroundMethodGeometric control of hybrid systems
Legat, B., & Jungers, R. M. (2022) · Nonlinear Analysis Hybrid Systems · doi:10.1016/j.nahs.2022.101289 · Cited by 2
“When this cone is the positive orthant, this is called the copositivity which is coNP-complete to decide [21].”
BackgroundProblems of Nonconvex Quadratic Programming Related to the Optimization of Phased Antenna Arrays
Tyunin, N. N. (2021) · Journal of Applied and Industrial Mathematics · doi:10.1134/s1990478921030157 · Cited by 2
“To this end, a procedure of checking the necessary conditions for local optimality was applied [15].”
Method
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.