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 201–300 of 1,000
LMI Approximations for Cones of Positive Semidefinite Forms
Zuluaga, L. F., Vera, J. C., & Peña, J. (2006) · SIAM Journal on Optimization · doi:10.1137/03060151x · Cited by 44
Minimum Distance to the Complement of a Convex Set: Duality Result
Briec, W. (1997) · Journal of Optimization Theory and Applications · doi:10.1023/a:1022697822407 · Cited by 43
On reduced semidefinite programs for second order moment bounds with applications
Natarajan, K., & Teo, C. (2016) · Mathematical Programming · doi:10.1007/s10107-016-1019-1 · Cited by 43
“Thedifficulty arises due to the complexity of characterizing the cone C( n × +1+n) and it’s dual cone, both of which are intractable for general n (see Murty and Kabadi [38], Dickinson and Gibjen [17]).”
BackgroundPower System State Estimation via Feasible Point Pursuit: Algorithms and Cramér-Rao Bound
Wang, G., Zamzam, A. S., Giannakis, G. B., & Sidiropoulos, N. D. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2791977 · Cited by 50
“Nonlinear SCADA measurements however, render the PSSE problem nonconvex and NP-hard in general [9].”
InfluentialOn the accuracy of uniform polyhedral approximations of the copositive cone
Yıldırım, E. A. (2011) · Optimization methods & software · doi:10.1080/10556788.2010.540014 · Cited by 43
“In fact, the problem of deciding whether X ∈ C is NPcomplete [13].”
BackgroundSemidefinite Approximations for Global Unconstrained Polynomial Optimization
Jibetean, D., & Laurent, M. (2005) · SIAM Journal on Optimization · doi:10.1137/04060562x · Cited by 43
“Indeed, it contains the problem of deciding whether a matrix is copositive, which is known to be co-NPhard [21], with an n× n matrix P being copositive if p(x) := ∑n i,j=1 Pijx 2 ix 2 j ≥ 0 for all x ∈ R, i.”
BackgroundFinding Approximate Local Minima for Nonconvex Optimization in Linear Time.Preprint
Agarwal, N., Allen-Zhu, Z., Bullins, B., Hazan, E., & Ma, T. (2016) · arXiv (Cornell University) · Cited by 43
Gao, D. Y., Ruan, N., & Pardalos, P. M. (2011) · Springer optimization and its applications · doi:10.1007/978-0-387-88619-0_3 · Cited by 42
An efficient second-order SQP method for structural topology optimization
Rojas-Labanda, S., & Stolpe, M. (2016) · Structural and Multidisciplinary Optimization · doi:10.1007/s00158-015-1381-2 · Cited by 42
“Since nonconvex optimization problems are NP-hard problems (Murty and Kabadi 1987; Manyem and Ugon 2012), a minimizer of the sub-problem does not guarantee the convergence of the algorithm, see e.g. Prieto (1989).”
BackgroundA Complementary Pivoting Approach to the Maximum Weight Clique Problem
Massaro, A., Pelillo, M., & Bomze, I. M. (2002) · SIAM Journal on Optimization · doi:10.1137/s1052623400381413 · Cited by 42
“All conditions involve checking copositivity, which from a practical point of view should be avoided, as checking copositivity is NP -hard [ 25 ] whereas checking definiteness (see below) can be done in polynomial time.”
BackgroundA Converse Sum of Squares Lyapunov Result With a Degree Bound
Peet, M. M., & Papachristodoulou, A. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2012.2190163 · Cited by 41
“This problem, while NP-hard [26], arises naturally when trying to construct Lyapunov functions for the stability analysis of dynamical systems.”
BackgroundConditionally definite matrices
Икрамов, Х. Д., & Savel'eva, N. V. (2000) · Journal of Mathematical Sciences · doi:10.1007/bf02355379 · Cited by 41
Irreducible elements of the copositive cone
Dickinson, P. J. C., Dür, M., Gijben, L., & Hildebrand, R. (2013) · Linear Algebra and its Applications · doi:10.1016/j.laa.2012.10.014 · Cited by 41
“Linear Algebra and its Applications 439 (2013) 1605–1626 Contents lists available at SciVerse ScienceDirect Linear Algebra and its Applications journal homepage: www.elsevier .com/locate/ laa Irreducible elements of the copositive cone Peter J.C. Dickinsona, Mirjam Dürb,∗, Luuk Gijbena, Roland Hildebrandc a Johann Ber…”
BackgroundCioara, T., Anghel, I. M., Bertoncini, M., Salomie, I., Arnone, D., Mammina, M., Velivassaki, T.-H., & Antal, M. (2016) · Future Generation Computer Systems · doi:10.1016/j.future.2016.05.010 · Cited by 41
Bounding Averages Rigorously Using Semidefinite Programming: Mean Moments of the Lorenz System
Goluskin, D. (2017) · Journal of Nonlinear Science · doi:10.1007/s00332-017-9421-2 · Cited by 41
“Even so it is too difficult in general to decide whether SL(x) ≥ 0 because the computational complexity of this question is NP-hard [23].”
BackgroundA Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors
Nie, J., Yang, Z., & Zhang, X. (2018) · SIAM Journal on Optimization · doi:10.1137/17m115308x · Cited by 41
Han, D., Liao, W., Peng, H., Wu, H., Wu, W. R., & Shen, X. (2021) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2021.3138898 · Cited by 41
“Hence, attaining the global optimal solutions for problems P L and P S is NP-hard and non-tractable [32].”
BackgroundCosares, S., & Hochbaum, D. S. (1994) · Mathematics of Operations Research · doi:10.1287/moor.19.1.94 · Cited by 41
Copositive programming motivated bounds on the stability and the chromatic numbers
Dukanovic, I., & Rendl, F. (2008) · Mathematical Programming · doi:10.1007/s10107-008-0233-x · Cited by 41
The hierarchy of local minimums in polynomial optimization
Nie, J. (2014) · Mathematical Programming · doi:10.1007/s10107-014-0845-2 · Cited by 40
“nclude that u is a local minimizer. For such cases, higher order derivatives are required to make a judgement. Indeed, it is NP-hard to check whether a critical point is a local minimizer or not (cf. [24]). To see this, consider the special case that f is a quartic form (i.e., a homogeneous polynomial of degree four).…”
BackgroundCopositive tensor detection and its applications in physics and hypergraphs
Chen, H., Huang, Z., & Qi, L. (2017) · Computational Optimization and Applications · doi:10.1007/s10589-017-9938-1 · Cited by 40
“Actually, the problem to judge whether a symmetric tensor is copositive or not is NP-complete, even for the matrix case [9,23].”
BackgroundNewton Polytopes and Relative Entropy Optimization
Murray, R., Chandrasekaran, V., & Wierman, A. (2021) · Foundations of Computational Mathematics · doi:10.1007/s10208-021-09497-w · Cited by 40
Solving High-Order Portfolios via Successive Convex Approximation Algorithms
Zhou, R., & Palomar, D. P. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3051369 · Cited by 40
“In general, investors have a preference for odd moments while dislike even moments.”
BackgroundNonconvex Semi-Linear Problems and Canonical Duality Solutions
Gao, D. Y. (2003) · Advances in mechanics and mathematics · doi:10.1007/978-1-4613-0247-6_5 · Cited by 40
“During the last decade, several authors have shown that the general quadratic programming problem (Pb) is an NP-hard problem in global optimization (cf. Murty and Kabadi, 1987; Horst et al, 2000).”
BackgroundGlobal Optimization and Constraint Satisfaction: The Branch-and-Reduce Approach
Sahinidis, N. V. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-39901-8_1 · Cited by 40
“Since both of these problem classes are NP-hard [25, 27], it follows that P is also NP-hard.”
BackgroundTian, Y. (2011) · Nonlinear Analysis · doi:10.1016/j.na.2011.09.003 · Cited by 39
Constructing Lyapunov-Krasovskii functionals for linear time delay systems
Papachristodoulou, A., Peet, M. M., & Lall, S. (2005) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2005.1470401 · Cited by 39
“The converse is not always true: not all positive semi-definite polynomials can be written as SOS, apart from 3 special cases (see [13]) - in fact, testing global non-negativity of a polynomial p(x) is known to be NP-hard when the degree of p(x) is greater than 4 [7], whereas checking whether p can be written as a SOS…”
BackgroundCopositivity Detection of Tensors: Theory and Algorithm
Chen, H., Huang, Z., & Qi, L. (2017) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-017-1131-2 · Cited by 39
“In fact, the copositivity detection of tensors is NP-complete, even for the matrix case [17,18].”
BackgroundChordal and factor-width decompositions for scalable semidefinite and polynomial optimization
Zheng, Y., Fantuzzi, G., & Papachristodoulou, A. (2021) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2021.09.001 · Cited by 39
“However, while verifying polynomial nonnegativity is an NP-hard problem (Murty & Kabadi, 1987), checking whether a polynomial f is SOS can be done in polynomial time by solving an SDP. Specifically, for each exponent α ∈ B + B , let A α ∈ S | B | be the symmetric binary matrix satisfying and observe…”
BackgroundOpen questions in complexity theory for numerical optimization
Pardalos, P. M., & Vavasis, S. A. (1992) · Mathematical Programming · doi:10.1007/bf01581088 · Cited by 39
A Nonconvex Duality with Zero Gap and Applications
Thach, P. T. (1994) · SIAM Journal on Optimization · doi:10.1137/0804002 · Cited by 39
Escaping Saddle Points in Constrained OptimizationPreprint
Mokhtari, A., Ozdaglar, A., & Jadbabaie, A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1809.02162 · Cited by 51
MARINA: Faster Non-Convex Distributed Learning with CompressionPreprint
Gorbunov, E., Burlachenko, K., Li, Z., & Richtárik, P. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.07845 · Cited by 39
“Since finding a global minimum of a non-convex function is, in general, an NP-hard problem (Murty & Kabadi, 1987), many researchers in non-convex optimization focus on relaxed goals such as finding an ε -stationary point.”
Bounding Extreme Events in Nonlinear Dynamics Using Convex Optimization
Fantuzzi, G., & Goluskin, D. (2020) · SIAM Journal on Applied Dynamical Systems · doi:10.1137/19m1277953 · Cited by 38
“(4.4) V(t;x) ( t;x) 0 on ; V(t0;x) 0 on X0g: Under the assumptions outlined above, the three constraints on V and are polynomial inequalities on semialgebraic sets. These are NP-hard in general [55], so a common approach is to certify nonnegativity on semialgebraic sets using weighted sum-of-squares (WSOS) decompositi…”
BackgroundInfluentialThe complexity of gradient descent: CLS = PPAD ∩ PLS
Fearnley, J., Goldberg, P. W., Hollender, A., & Savani, R. (2021) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3406325.3451052 · Cited by 38
“As discussed in Papadimitriou [1994], TFNP is unlikely to have complete problems, and various syntactic subclasses have been used to classify the many diverse problems that belong to it.”
BackgroundInfluentialA finite algorithm for solving general quadratic problems
Bomze, I. M., & Danninger, G. (1994) · Journal of Global Optimization · doi:10.1007/bf01096531 · Cited by 38
“The solution of problems of this type is, from the perspective of worst-case complexity, NP-hard [17]; even checking whether a given feasible point is a local solution is also NP-hard [ 13 ], [16].”
BackgroundAdvantages of simplicial partitioning for Lipschitz optimization problems with linear constraints
Paulavičius, R., & Žilinskas, J. (2014) · Optimization Letters · doi:10.1007/s11590-014-0772-4 · Cited by 37
“Let us note that this operation is exponential in complexity, however global optimization problems are NP-hard (see for example [30,32]).”
BackgroundSignomial and polynomial optimization via relative entropy and partial dualization
Murray, R., Chandrasekaran, V., & Wierman, A. (2020) · Mathematical Programming Computation · doi:10.1007/s12532-020-00193-4 · Cited by 37
“in nvariables, and proceed to iterate over all tuples \t" in [n]4. With probability nlogn=n4, sample a coecient c tfrom the standard normal distribution, and add the term c txt to f, where t 2[4]n has tj = jfi : t i = jgj. The expected number of terms in f after this procedure is roughly nlogn. Once a polynomial…”
Interior Point and Semidefinite Approaches in Combinatorial Optimization
Krishnan, K., & Tamás Terlaky, B. (2005) · Springer eBooks · doi:10.1007/0-387-25592-3_5 · Cited by 37
A Global Optimization Algorithm for Concave Quadratic Programming Problems
Bomze, I. M., & Danninger, G. (1993) · SIAM Journal on Optimization · doi:10.1137/0803042 · Cited by 37
An improved algorithm to test copositivity
Sponsel, J., Bundfuss, S., & Dür, M. (2011) · Journal of Global Optimization · doi:10.1007/s10898-011-9766-2 · Cited by 36
“Like the semidefinite cone it is nonpolyhedral, but its structure is more complex, as testing whether a given matrix A is in C is a co-NP-complete problem [23].”
BackgroundExact and Heuristic Algorithms for Semi-Nonnegative Matrix Factorization
Gillis, N., & Kumar, A. (2015) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/140993272 · Cited by 36
“is nonnegative, is co-NP-complete [22] (a decision problem is co-NP-complete if it is a member of co-NP–, its complement is in NP–, and any problem in co-NP can be reduced to it in polynomial time; see [1] for more details).”
BackgroundEnergy-Efficient Resource Allocation in C-RANs with Capacity-Limited Fronthaul
Younis, A., Tran, T. X., & Pompili, D. (2019) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2019.2942597 · Cited by 36
“It can be seen that P 0 is a MINLP, which is NP-hard [33] and is highly difficult to solve optimally in polynomial time.”
BackgroundOptimization over structured subsets of positive semidefinite matrices via column generation
Ahmadi, A. A., Dash, S., & Hall, G. (2016) · Discrete Optimization · doi:10.1016/j.disopt.2016.04.004 · Cited by 46
“(1)Weak NP-hardness of testing matrix copositivity is originally proven by Murty and Kabadi [32]; its strong NP-hardness is apparent from the work of de Klerk and Pasechnik [18].”
Convergence to Second-Order Stationarity for Constrained Non-Convex OptimizationPreprint
Nouiehed, M., Lee, J. D., & Razaviyayn, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.02024 · Cited by 40
A Statistical Test for Probabilistic Fairness
Taşkesen, B., Blanchet, J., Kühn, D., & Nguyen, V. A. (2021) · ACM Conference on Fairness, Accountability, and Transparency (FAccT) · doi:10.1145/3442188.3445927 · Cited by 58
“Indeed, because ℎ𝛽 is non-convex, even finding the optimal inner solution 𝑥★ 𝑖 for a fixed value of the outer variable 𝛾 ∈ R is generally NP-hard [48].”
BackgroundEfficient heuristics for inventory placement in acyclic networks
Shu, J., & Karimi, I. A. (2009) · Computers & Operations Research · doi:10.1016/j.cor.2009.01.001 · Cited by 35
“Murty and Kabadi [12] showed that the general separable concave minimization problem subject to linear constraints is NP-hard, and it is also NP-hard to check whether a given feasible solution is a local optimum.”
BackgroundStochastic Global Optimization Techniques
Birbil, Ş. İ. (2002) · NCSU Libraries Repository (North Carolina State University Libraries) · Cited by 35
Kumar, P. R., & Meyn, S. (2002) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.1994.411003 · Cited by 35
“Unfortunately, for large matrices, the copositivity test may be computationally intractable, since it has been shown that the determination of copositivity is NP-Complete; see Murty and Kabadi 29].”
BackgroundComplexity Theory: Quadratic Programming
Vavasis, S. A. (2001) · Springer eBooks · doi:10.1007/0-306-48332-7_65 · Cited by 35
Projection Robust Wasserstein Distance and Riemannian OptimizationPreprint
Lin, T., Fan, C., Ho, N., Cuturi, M., & Jordan, M. I. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.07458 · Cited by 35
“Indeed, there is no guarantee for finding a global Nash equilibrium as the special case of nonconvex optimization is already NP-hard [64]; moreover, Sion’s minimax theorem [79] is not applicable here due to the lack of quasi-convex-concave structure.”
BackgroundCanonical dual least square method for solving general nonlinear systems of quadratic equations
Ruan, N., Gao, D. Y., & Jiao, Y. (2008) · Computational Optimization and Applications · doi:10.1007/s10589-008-9222-5 · Cited by 34
Converse results on existence of sum of squares Lyapunov functions
Ahmadi, A. A., & Parrilo, P. A. (2011) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2011.6161493 · Cited by 34
“In fact, even deciding if a given polynomial V of degree four or larger satisfies (2) is NP-hard [1].”
BackgroundQuadratic-programming criteria for copositive matrices
Väliaho, H. (1989) · Linear Algebra and its Applications · doi:10.1016/0024-3795(89)90076-1 · Cited by 34
Minimal zeros of copositive matrices
Hildebrand, R. (2014) · Linear Algebra and its Applications · doi:10.1016/j.laa.2014.07.004 · Cited by 34
“However, verifying copositivity of a given matrix is a co-NPcomplete problem [18].”
BackgroundLi, Y., Xia, M., & Wu, Y. (2019) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2019.2927670 · Cited by 38
“In fact, even finding a feasible point satisfying nonconvex (5c) and (5d) is NP-hard [39].”
BackgroundInfluentialLearning Dynamical Systems with Side Information
Ahmadi, A. A., & Khadir, B. E. (2023) · SIAM Review · doi:10.1137/20m1388644 · Cited by 40
Narrowing the difficulty gap for the Celis–Dennis–Tapia problem
Bomze, I. M., & Overton, M. L. (2014) · Mathematical Programming · doi:10.1007/s10107-014-0836-3 · Cited by 34
“However, while checking -copositivity in the standard case where = R+ is NP-hard [13,24], there are cones for which this condition is easy to check.”
BackgroundDynamic regulatory on/off minimization for biological systems under internal temporal perturbations
Kleeßen, S., & Nikoloski, Z. (2012) · BMC Systems Biology · doi:10.1186/1752-0509-6-16 · Cited by 39
Alternative LP and SOCP Hierarchies for ACOPF Problems
Kuang, X., Ghaddar, B., Naoum‐Sawaya, J., & Zuluaga, L. F. (2016) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2016.2615688 · Cited by 34
“In general, solving problem (PP-P) is NP-hard [18].”
BackgroundConsidering manufacturing cost and scheduling performance on a CNC turning machine
Gürel, S., & Aktürk, M. S. (2006) · European Journal of Operational Research · doi:10.1016/j.ejor.2005.11.029 · Cited by 34
“Although it does not prove NP-hardness of the SCP, we know that in general, computing a global minimum in a nonconvex NLP is an NP-hard problem due to Murty and Kabadi (1987).”
BackgroundBlock pivoting and shortcut strategies for detecting copositivity
Bomze, I. M. (1996) · Linear Algebra and its Applications · doi:10.1016/0024-3795(95)00165-4 · Cited by 33
UTA-poly and UTA-splines: Additive value functions with polynomial marginals
Sobrie, O., Gillis, N., Mousseau, V., & Pirlot, M. (2017) · European Journal of Operational Research · doi:10.1016/j.ejor.2017.03.021 · Cited by 33
First-Order Methods for Nonconvex Quadratic Minimization
Carmon, Y., & Duchi, J. C. (2020) · SIAM Review · doi:10.1137/20m1321759 · Cited by 33
“Global minimization of nonconvex functions is generally intractable [34, 32].”
BackgroundA Coevolutionary Algorithm for Cooperative Platoon Formation of Connected and Automated Vehicles
Deng, Z., Fan, J., Shi, Y., & Shen, W. (2022) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2022.3196366 · Cited by 33
“However, it cannot be solved by off-the-shelf linear or convex programming solvers since the objective function is non-linear and non-convex, resulting in a NP-hard problem [47], [48].”
BackgroundGLOBAL OPTIMIZATION: APPLICATIONS TO ADVANCED REFLECTOR ANTENNAS SYNTHESIS AND DIAGNOSIS TECHNIQUES
Capozzoli, A., & D’Elia, G. (2006) · Electromagnetic waves · doi:10.2528/pier04123001 · Cited by 33
“Also Local Optimization presents, as shown by Murty and Kabadi [52], similar complexity issues.”
BackgroundSitabhra Sinha, A., & Sridhar, S. (2014) · CRC Press eBooks · doi:10.1201/b17821-14 · Cited by 33
Zhang, R. Y., Sojoudi, S., & Lavaei, J. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.01631 · Cited by 33
Linear-Time Copositivity Detection for Tridiagonal Matrices and Extension to Block-Tridiagonality
Bomze, I. M. (2000) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479898341487 · Cited by 31
Scaling relationship between the copositive cone and Parrilo’s first level approximation
Dickinson, P. J. C., Dür, M., Gijben, L., & Hildebrand, R. (2012) · Optimization Letters · doi:10.1007/s11590-012-0523-3 · Cited by 31
“For the 5 × 5 case, we show the more surprising result that we can scale any copositive matrix X into K1 5 and in fact that any scaling D such that (DXD)ii ∈ {0, 1} for all i yields DXD ∈ K15.”
BackgroundComplete Dictionary Recovery Using Nonconvex Optimization
Sun, J., Qu, Q., & Wright, J. N. (2015) · Cited by 31
The computational complexity of evolutionarily stable strategies
Etessami, K., & Lochbihler, A. (2007) · International Journal of Game Theory · doi:10.1007/s00182-007-0095-0 · Cited by 31
Symmetry Approach to Extension of Flutter Boundaries via Mistuning
Shapiro, B. (1998) · Journal of Propulsion and Power · doi:10.2514/2.5288 · Cited by 31
Kaplan, W. (2001) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(01)00351-2 · Cited by 30
“A result of Murty and Kabadi [16] in fact shows that the general problem of testing for copositivity is NP-complete.”
BackgroundAndreani, R., Silva, P. J. S., Haeser, G., & Ramos, A. (2016) · IMA Journal of Numerical Analysis · doi:10.1093/imanum/drw064 · Cited by 29
“Also from the practical point of view, even establishing if SSONC holds is, in general, a NP-hard problem [47] and to our knowledge, no algorithm has been shown to converge to a point at which SSONC”
BackgroundThe economics of electricity generation from Gulf Stream currents
Li, B., de Queiroz, A. R., DeCarolis, J. F., Bane, J. M., He, R., Keeler, A. G., & Neary, V. S. (2017) · Energy · doi:10.1016/j.energy.2017.06.048 · Cited by 29
“This raises concerns about reaching a local instead of a global optimal [64] and requires exhaustive computational time or the use of a metaheuristic technique [65] to find an approximate solution when solving the model.”
BackgroundNiu, S. H., Song, S., & Chiong, R. (2021) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2021.3079133 · Cited by 29
“However, even the problem of determining whether a given matrix is not copositive is NPcomplete [49].”
BackgroundNonnegative Sparse PCA with Provable Guarantees
Asteris, M., Papailiopoulos, D., & Dimakis, A. G. (2014) · Cited by 29
Adaptive Advertising Interval for Electronic Shelf Label System Based on Bluetooth Low Energy
Tseng, H., Kao, H., & Kuo, C. (2022) · IEEE Sensors Journal · doi:10.1109/jsen.2022.3172405 · Cited by 29
Trading performance for stability in Markov decision processes
Brázdil, T., Chatterjee, K., Forejt, V., & Kučera, A. (2016) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2016.09.009 · Cited by 29
Learning Filter Bank Sparsifying Transforms
Pfister, L., & Bresler, Y. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2883021 · Cited by 29
“Direct verification of the PR condition (13) is NP-Hard for K ≥ 2, underlining the difficulty of multidimensional filter bank design [45], [46].”
MethodA Survey of Hidden Convex Optimization
Xia, Y. (2020) · Journal of the Operations Research Society of China · doi:10.1007/s40305-019-00286-5 · Cited by 29
Distributionally robust chance constrained problem under interval distribution information
Ding, K.-W., Wang, M.-H., & Huang, N. (2017) · Optimization Letters · doi:10.1007/s11590-017-1160-7 · Cited by 28
“It is well known that the complexity of solving the worst-case expectation problem under P4 is a NP-hard problem [7].”
BackgroundStatistical guarantees for regularized neural networks
Taheri, M., Xie, F., & Lederer, J. (2021) · Neural Networks · doi:10.1016/j.neunet.2021.04.034 · Cited by 52
Linear-Time Complete Positivity Detection and Decomposition of Sparse Matrices
Dickinson, P. J. C., & Dür, M. (2012) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/110848177 · Cited by 28
“Checking if a matrix is completely positive has been shown to be an NP-hard problem whilst checking if a matrix is copositive has been shown to be a co-NP-complete problem [10, 21].”
BackgroundCopositivity and constrained fractional quadratic problems
Amaral, P. A., Bomze, I. M., & Júdice, J. J. (2013) · Mathematical Programming · doi:10.1007/s10107-013-0690-8 · Cited by 28
“Checking condition X ∈ C∗ n+1 is (co-)NP-hard [20,35], but it is possible to exploit this equality to get a lower bound for the CFQP, using the inclusion C∗ n+1 ⊆ Dn+1 = Pn+1 ∩ Nn+1.”
BackgroundScenario-free stochastic programming with polynomial decision rules
Bampou, D., & Kühn, D. (2011) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2011.6161150 · Cited by 28
On the global minimization of a convex function under general nonconvex constraints
Tụy, H., & Thuong, N. V. (1988) · Applied Mathematics & Optimization · doi:10.1007/bf01443618 · Cited by 28
“Recent investigations on this class of problems have shown that even checking the local optimality of a given feasible point is an NP-hard problem [34], [ 12 ].”
BackgroundCopositivity detection by difference-of-convex decomposition and ω-subdivision
Bomze, I. M., & Eichfelder, G. (2012) · Mathematical Programming · doi:10.1007/s10107-012-0543-x · Cited by 27
“The problem of determining whether a matrix is not copositive is NP-complete [36].”
BackgroundConsidering copositivity locally
Dickinson, P. J. C., & Hildebrand, R. (2016) · Journal of Mathematical Analysis and Applications · doi:10.1016/j.jmaa.2016.01.063 · Cited by 27
Kumar, S., Vidyasagar, A., & Kochmann, D. M. (2019) · International Journal for Numerical Methods in Engineering · doi:10.1002/nme.6280 · Cited by 27
“Figure 15a compares the numerically relaxed energies (59) (extended to 3D) and Equation (64) for a spatial resolution of h = 1∕16 (with an RVE side length of 1).”
BackgroundDür, M., & Rendl, F. (2021) · EURO Journal on Computational Optimization · doi:10.1016/j.ejco.2021.100021 · Cited by 27
“Checking membership in COP is co-NP-complete, as was shown in [81].”
Consensus-Based Optimization for Saddle Point Problems
Huang, H., Qiu, J., & Riedl, K. (2024) · SIAM Journal on Control and Optimization · doi:10.1137/22m1543367 · Cited by 27
“However, as soon as the payoff function becomes nonconvex-nonconcave, finding a global equilibrium is in general an NP hard problem [28].”
BackgroundPreisig, J. C. (1996) · SIAM Journal on Control and Optimization · doi:10.1137/s0363012993251894 · Cited by 27
Sparse solutions to random standard quadratic optimization problems
Chen, X., Peng, J., & Zhang, S. (2012) · Mathematical Programming · doi:10.1007/s10107-012-0519-x · Cited by 27
“It is known that the StQP is NP-hard [25].”
BackgroundA New Computational Tool for Establishing Model Parameter Identifiability
August, E., & Papachristodoulou, A. (2009) · Journal of Computational Biology · doi:10.1089/cmb.2008.0211 · Cited by 27
“Indeed, it is a polynomial non-negativity condition which can be NP hard to test (Murty and Kabadi, 1987).”
Role of copositivity in optimality criteria for nonconvex optimization problems
Danninger, G. (1992) · Journal of Optimization Theory and Applications · doi:10.1007/bf00940491 · Cited by 27
“even the Cottle-Mangasarian-Fromovitz constraint qualifications at the point ff=o are satisfied: indeed, we have I(o) = {1, 2} and, for v=[0, 1 ] r, we obtain”
BackgroundMethodInfluentialThe copositive cone, the completely positive cone and their generalisations
Dickinson, P. J. C. (2013) · University of Groningen research database (University of Groningen / Centre for Information Technology) · Cited by 27
Algorithms for determining the copositivity of a given symmetric matrix
Yang, S., & Li, X. (2008) · Linear Algebra and its Applications · doi:10.1016/j.laa.2008.07.028 · Cited by 26
A deterministic annealing algorithm for approximating a solution of the max-bisection problem
Dang, C., He, L., & Hui, I. K. (2002) · Neural Networks · doi:10.1016/s0893-6080(02)00027-8 · Cited by 26
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.