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 601–700 of 1,000
Optimization and analysis of three-part tariff pricing strategies
Lin, S., Merdikawati, S., Wu, S.-F., & Yeh, R.-H. (2023) · OR Spectrum · doi:10.1007/s00291-023-00730-2 · Cited by 7
“It is a straightforward and effective method for solving NP-hard optimization problems (Altmemi et al. 2020).”
BackgroundStability Analysis of Discrete-Time Linear Complementarity Systems
Raghunathan, A. U., & Linderoth, J. (2025) · SIAM Journal on Optimization · doi:10.1137/20m1387377 · Cited by 6
“It is well-known that checking whether a given matrix is copositive is a co-NP-complete problem [28].”
Open weak CAD and its applications
Han, J., Dai, L., Hong, H., & Xia, B. (2016) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2016.07.032 · Cited by 7
“In general, to check whether a given integer square matrix is not copositive, is NPcomplete (Murty and Kabadi, 1987).”
BackgroundFacets of a mixed-integer bilinear covering set with bounds on variables
Rahman, H., & Mahajan, A. (2019) · Journal of Global Optimization · doi:10.1007/s10898-019-00783-0 · Cited by 6
Optimality conditions for linear copositive programming problems with isolated immobile indices
Kostyukova, O. I., & Tchemisova, T. V. (2018) · Optimization · doi:10.1080/02331934.2018.1539482 · Cited by 6
“Being formally very similar to that of SDP, the copositive programs are NP-hard since testing copositivity of matrices is co-NP-complete [13].”
BackgroundAhmed, F., & Still, G. J. (2019) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-019-01498-8 · Cited by 6
Souaiby, M., Tanwani, A., & Henrion, D. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3061557 · Cited by 6
“The fundamental question in most of these works boils down to checking the positivity of certain functions over the state space, which is a challenging problem numerically [34].”
BackgroundOn monotonicity and search strategies in face-based copositivity detection algorithms
G.-Tóth, B., Hendrix, E. M. T., & Casado, L. G. (2021) · Central European Journal of Operations Research · doi:10.1007/s10100-021-00737-6 · Cited by 6
Factorization of completely positive matrices using iterative projected gradient steps
Boţ, R. I., & Nguyen, D. (2021) · Numerical Linear Algebra with Applications · doi:10.1002/nla.2391 · Cited by 6
Estimating high dimensional monotone index models by iterative convex optimization
Khan, S. A., Lan, X., Tamer, E., & Yao, Q. (2024) · Journal of Econometrics · doi:10.1016/j.jeconom.2024.105901 · Cited by 6
Fukuda, E. H., Haeser, G., & Mito, L. M. (2023) · Set-Valued and Variational Analysis · doi:10.1007/s11228-023-00676-1 · Cited by 6
“However, deciding the positivity of a matrix over a cone is an NP-hard class problem [60], and so is checking the semi-strong condition.”
BackgroundTsirukis, A. G., & Reklaitis, G. V. (1993) · Annals of Operations Research · doi:10.1007/bf02023178 · Cited by 6
“It is well known that the global optimization problem is NP-hard [ 4 ].”
BackgroundOptimal placements of flexible objects. II. A simulated annealing approach for the bounded case
Albrecht, A. A., Cheung, S. K., Hui, K.-H., Leung, K. S., & Wong, C. K. (1997) · IEEE Transactions on Computers · doi:10.1109/12.609279 · Cited by 6
“The main stochastic approaches to finding optimal placements of rigid objects are from quadratic programming [10], [16], [7] and simulated annealing [8], [12], [9], [6], [18], [1], [11], [15], [4], [13].”
BackgroundA Simple Effective Heuristic for Embedded Mixed-Integer Quadratic Programming
Takapoui, R., Moehle, N., Boyd, S., & Bemporad, A. (2015) · IMT Institutional Repository (IMT School for Advanced Studies Lucca) · doi:10.48550/arxiv.1509.08416 · Cited by 9
MAP Clustering under the Gaussian Mixture Model via Mixed Integer Nonlinear OptimizationPreprint
Flaherty, P., Wiratchotisatian, P., Lee, J. A., Tang, Z., & Trapp, A. C. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.04285 · Cited by 7
“Computational Complexity Problems in the MINLP class are NP-hard in general, and the MAP problem in particular presents two primary computational challenges (Murty and Kabadi, 1987).”
BackgroundAxeChain: A Secure and Decentralized blockchain for solving Easily-Verifiable problemsPreprint
Zheng, W., Chen, X., Zheng, Z., Luo, X., & Cui, J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.13999 · Cited by 6
“In addition, non-linear integer programming problems can also be submitted to AxeChain, most of which were proved to be NPcomplete [29], [30].”
BackgroundBomze, I. M. (2008) · Springer eBooks · doi:10.1007/978-0-387-74759-0_99 · Cited by 6
MINLP: Branch and Bound Global Optimization Algorithm
Androulakis, I. P. (2008) · Springer eBooks · doi:10.1007/978-0-387-74759-0_377 · Cited by 6
Designing unit Ising models for logic gate simulation through integer linear programming
Tsukiyama, S., Nakano, K., Parque, V., Ito, Y., Kato, T., Kawamata, Y., & Ii, K. (2024) · International Journal of Parallel Emergent and Distributed Systems · doi:10.1080/17445760.2024.2438043 · Cited by 5
“Following this, D-Wave Systems launched an even more sophisticated quantum annealer, the D-Wave Advantage [22].”
Hou, D., Tang, T., & Toh, K.-C. (2026) · Mathematical Programming · doi:10.1007/s10107-026-02395-5 · Cited by 5
“Testing tensor copositivity for general t is co-NP-hard [8, 29], and can be reformulated as the polynomial optimization problem min hB , ⊗ t x i | e ⊤ x = 1 , x ≥ 0 .”
Single or Multiple Frames Content Delivery for Next-Generation Networks?
Abedi, M. R., Mokari, N., Javan, M. R., & Jorswieck, E. A. (2019) · IEEE Access · doi:10.1109/access.2019.2948389 · Cited by 5
“oblem (22) consisting of non-convex objective function and both integer and continuous variables. Hence, it is mixed-integer nonlinear programming (MINLP), non-convex, intractable and NP-hard problem [40]. 7 Lemma 1. The optimization problem (22) is NP-hard. Proof. Please see Appendix A. It is very difficult to find the…”
MethodPartial Lagrange Multiplier Expressions and Disjunctive Decompositions for Bilevel Optimization
Nie, J., Ye, J. J., & Zhong, S. (2026) · SIAM Journal on Optimization · doi:10.1137/24m1635624 · Cited by 5
“It is interesting to note that the task of verifying local optimality is NP-hard [41].”
Nested nonnegative cone analysis
Zhang, L., Lü, S., & Marron, J. S. (2015) · Computational Statistics & Data Analysis · doi:10.1016/j.csda.2015.01.008 · Cited by 5
“In general, nonconvex optimization problems are very hard to solve, see, e.g., Murty and Kabadi (1987); Vandenberghe and Boyd (1996); Ben-Tal and Nemirovski (2001); Boyd and Vandenberghe (2004)).”
BackgroundBackstepping controller synthesis for piecewise affine systems: A sum of squares approach
Samadi, B., & Rodrigues, L. (2007) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.2007.4414046 · Cited by 5
“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].”
BackgroundKim, K. K., & Braatz, R. D. (2013) · Computers & Chemical Engineering · doi:10.1016/j.compchemeng.2013.09.018 · Cited by 5
Fast NMPC with Mixed-Integer Controls Using Quasi-Translations
Maitland, A., & McPhee, J. (2018) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2018.11.057 · Cited by 5
Bramburger, J. J., & Goluskin, D. (2020) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.2020.0450 · Cited by 5
“ing boundaries are equivalent to various polynomial expressions being nonnegative on specied parts of phase space. Although deciding nonnegativity of a multivariable polynomial is NP-hard in general [50], nonnegativity can be replaced by the stronger but more tractable condition that the polynomial admits a representa…”
BackgroundAn adaptive high order method for finding third-order critical points of nonconvex optimization
Zhu, X., Han, J., & Jiang, B. (2022) · Journal of Global Optimization · doi:10.1007/s10898-022-01151-1 · Cited by 5
“llenging task. Even a less challenging work of nding a local optimum is computationally hard in the worst case [35]. In fact, it is even NP-hard to check whether a critical point is a local minimizer [30]. On the other hand, the concept of critical point can be divided into a few subcategories. Classical gradient desc…”
BackgroundA proximal DC approach for quadratic assignment problem
Jiang, Z., Zhao, X., & Ding, C. (2021) · Computational Optimization and Applications · doi:10.1007/s10589-020-00252-5 · Cited by 5
Sums of Separable and Quadratic Polynomials
Ahmadi, A. A., Dibek, C., & Hall, G. (2022) · Mathematics of Operations Research · doi:10.1287/moor.2022.1295 · Cited by 5
Algorithm 1030: SC-SR1: MATLAB Software for Limited-memory SR1 Trust-region Methods
Brust, J. J., Burdakov, O. P., Erway, J. B., & Marcia, R. F. (2022) · ACM Transactions on Mathematical Software · doi:10.1145/3550269 · Cited by 5
“The infinity-norm is sometimes used to define the subproblem; however, when B is indefinite, as can be the case when B is a L-SR1 matrix, the subproblem is NP-hard [11, 12].”
An LP-based Algorithm to Test Copositivity
Tanaka, A., & Yoshise, A. (2014) · Cited by 5
Yıldırım, E. A. (2016) · Optimization methods & software · doi:10.1080/10556788.2016.1245732 · Cited by 5
“Indeed, deciding if a given matrix belongs to CP n is a computationally intractable problem [14, 20].”
BackgroundImproved approximation results on standard quartic polynomial optimization
Ling, C., He, H., & Qi, L. (2016) · Optimization Letters · doi:10.1007/s11590-016-1094-5 · Cited by 5
“It is well-known that the problem of checking whether a symmetric matrix belongs to the cone of copositive matrices or not is co-NP-complete [12].”
BackgroundOTP-IoT: An ownership transfer protocol for the Internet of Things
Mamun, M., Su, C., Yang, A., Miyaji, A., & Ghorbani, A. A. (2018) · Journal of Information Security and Applications · doi:10.1016/j.jisa.2018.10.009 · Cited by 5
Generative Adversarial Networks for Text Using Word2vec Intermediaries
Budhkar, A., Vishnubhotla, K., Hossain, S., & Rudzicz, F. (2019) · Workshop on Representation Learning for NLP (RepL4NLP) · doi:10.18653/v1/w19-4303 · Cited by 5
Cache hit ratio maximization in device-to-device communications overlaying cellular networks
Zhong, L., Zheng, X., Liu, Y., Wang, M., & Cao, Y. (2020) · China Communications · doi:10.23919/jcc.2020.02.018 · Cited by 6
“According to the above formulation, the model is exactly a non-linear integer programming problem, which is NP-hard [10].”
BackgroundSecond-order guarantees in centralized, federated and decentralized nonconvex optimization
Vlaski, S., & Sayed, A. H. (2020) · Communications in Information and Systems · doi:10.4310/cis.2020.v20.n3.a4 · Cited by 5
Beyond submodular maximization via one-sided smoothness
Ghadiri, M., Santiago, R., & Shepherd, F. B. (2025) · Mathematical Programming · doi:10.1007/s10107-025-02301-5 · Cited by 7
Model-Agnostic Local Explanations with Genetic Algorithms for Text Classification
Du, Q. (2021) · Proceedings/Proceedings of the ... International Conference on Software Engineering and Knowledge Engineering · doi:10.18293/seke2021-040 · Cited by 5
Simulated Annealing for Convex Optimization: Rigorous Complexity Analysis and Practical Perspectives
Badenbroek, R., & de Klerk, E. (2022) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-022-02034-x · Cited by 5
“Although—as mentioned earlier—deciding if a matrix is copositive is a co-NP-complete problem [22], there are a number of procedures to test for copos123”
BackgroundMethodSampling Rates for $$\ell ^1$$-Synthesis
März, M., Boyer, C., Kahn, J., & Weiss, P. O. (2022) · Foundations of Computational Mathematics · doi:10.1007/s10208-022-09580-w · Cited by 5
“The notion of a minimum conic singular value is related to the concept of co-positivity [HS10c] and its computation is known to be an NP-hard task for general matrices and cones [HS10c; MK87].”
The minimizer of the sum of two strongly convex functions
Kuwaranancharoen, K., & Sundaram, S. (2024) · Optimization · doi:10.1080/02331934.2024.2402923 · Cited by 6
“However, extending our approach to more complex loss functions, such as those arising from neural networks, presents challenges due to the intractability of searching for optimal parameters for each function [60, 58].”
Deng, Z., Bai, Y., Fang, S., Tian, Y., & Xing, W. (2013) · Journal of Systems Science and Systems Engineering · doi:10.1007/s11518-013-5234-5 · Cited by 5
“The portfolio selection model with marginal risk control results in a nonconvex quadratically constrained quadratic programming (QCQP) problem, which is NP-hard in general (see Murty & Kabadi (1987)).”
Background7 Mathematical programming — A computational perspective
Hager, W. W., Horst, R., & Pardalos, P. M. (1993) · Handbook of statistics · doi:10.1016/s0169-7161(05)80131-2 · Cited by 5
Derat, B., & Bolomey, J. (2006) · IEEE Transactions on Electromagnetic Compatibility · doi:10.1109/temc.2006.884619 · Cited by 5
“Generally, it cannot be guaranteed that such a question can be solved in a reasonable time [9], [10].”
BackgroundMinimizing upload latency for critical tasks in cellular-based IoT networks using multiple relays
Hsu, S.-H., Lin, C.-H., Wang, C.-Y., & Chen, W.-T. (2017) · International Conference on Communications · doi:10.1109/icc.2017.7997421 · Cited by 5
“We may show that the relay selection problem is a quadratic constraint optimization problem, which has been shown to be NP-hard [10], [11].”
BackgroundExact Methods for Two-Stage Robust Optimization with Applications in Gas Networks
Aßmann, D. (2019) · Directory of Open access Books (OAPEN Foundation) · doi:10.25593/978-3-96147-234-5 · Cited by 7
A Feasible Direction Algorithm Without Line Search for Solving Max-Bisection Problems
Xu, F., Xu, C.-X., & Xue, H. (2005) · Journal of Computational Mathematics · doi:10.4208/jcm.v23.n6.p619 · Cited by 5
Deciding uniqueness in norm maximization
Gritzmann, P., & Klee, V. L. (1992) · Mathematical Programming · doi:10.1007/bf01581081 · Cited by 5
“As general references, we mention [3] and [7] for background material concerning NP and other complexity classes, [2] and [8] for relations between optimization problems and the corresponding decision problems, [1], [4], [9], [11], and [12] for NP-hardness results dealing with quadratic optimization, and [10], [11], a…”
BackgroundNew Conic Optimization Techniques for Solving Binary Polynomial Programming Problems
Ghaddar, B. (2011) · UWSpace (University of Waterloo) · Cited by 5
Manyopt: An Extensible Tool for Mixed, Non-Linear Optimization Through SMT SolvingPreprint
D’Iddio, A. C., & Huth, M. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1702.01332 · Cited by 5
“Notwithstanding, several efforts have been made to solve MINLP problems, supported by decomposition or transformation techniques specific to subclasses of MINLP: Solving a generic NLP problem has been proven to be NP-hard [36], but many effective methods and algorithms have been developed in the last four decades (see…”
BackgroundMachine Learning, Deepest Learning: Statistical Data Assimilation ProblemsPreprint
Abarbanel, H. D. I., Rozdeba, P. J., & Shirman, S. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1707.01415 · Cited by 7
“This is an NP-complete problem [25] and as such suggests one cannot find a global minimum of the machine learning problem, as set, unless there is a special circumstance.”
MINLP: Branch and Bound Global Optimization Algorithm
Androulakis, I. P. (2001) · Springer eBooks · doi:10.1007/0-306-48332-7_287 · Cited by 5
On Difference of SOS Decompositions and Difference of SOS Convex Decompositions for PolynomialsPreprint
Niu, Y.-S. (2018) · arXiv (Cornell University) · Cited by 5
Souaiby, M., Tanwani, A., & Henrion, D. (2020) · HAL · Cited by 5
Submodular + ConcavePreprint
Mitra, S., Feldman, M., & Karbasi, A. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.04769 · Cited by 7
“It is also very well known that finding the global minimum of a general non-convex function is indeed computationally intractable [Murty and Kabadi, 1987].”
BackgroundXu, Z., Wang, Y., Chen, T., Zhang, H., Dong, T., & Lund, P. D. (2026) · Journal of Energy Storage · doi:10.1016/j.est.2026.120926 · Cited by 4
Hesse’s Redemption: Efficient Convex Polynomial Programming
Slot, L., Steurer, D., & Wiedmer, M. (2026) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3798129.3800760 · Cited by 4
Warping trajectories for video synchronization
Shankar, S., Lasenby, J., & Kokaram, A. C. (2013) · doi:10.1145/2510650.2510654 · Cited by 4
“In general, finding a global minimum in a nonconvex optimization problem can be NP-hard (with an NP-complete formulation being a special case) [13].”
BackgroundCopositive Programming by Simplicial Partition
Žilinskas, J. (2011) · Informatica · doi:10.15388/informatica.2011.345 · Cited by 4
Gherari, M., Dieye, M., Elbiaze, H., Ghamri-Doudane, Y. M., & Glitho, R. (2024) · Globecom · doi:10.1109/globecom52923.2024.10901375 · Cited by 4
“Thus, our problem is a Mixed Integer Non-Linear Problem, proven to be NP-Hard [16], [17].”
Sparse Polynomial Matrix Optimization
Miller, J., Wang, J., & Guo, F. (2026) · SIAM Journal on Optimization · doi:10.1137/24m1719761 · Cited by 4
Entanglement in the Dicke subspace
Gulati, A., Nechita, I., & Pellegrini, C. (2026) · Quantum · doi:10.22331/q-2026-07-01-2150 · Cited by 6
Scheduling for a processor sharing system with linear slowdown
Ravner, L., & Nazarathy, Y. (2017) · Mathematical Methods of Operations Research · doi:10.1007/s00186-017-0583-3 · Cited by 4
Zhan, Y., Wu, J., Wang, C., & Xie, J. (2012) · IEEE International Conference on Tools with Artificial Intelligence (ICTAI) · doi:10.1109/ictai.2012.121 · Cited by 4
World-Base Calibration by Global Polynomial Optimization
Heller, J., & Pajdla, T. (2014) · International Conference on 3D Vision (3DV) · doi:10.1109/3dv.2014.78 · Cited by 4
“In real life however, this is not always tractable, as it can be shown that general problem of minimizing polynomial function is NP-hard [11], if the degree of the polynomial is at least four.”
BackgroundZhang, D., Li, J., Lu, B., Ding, S. X., Wang, Z., & Zhao, C. (2016) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2016.11.007 · Cited by 4
Iterative Constrained Least Squares for Robust Constant Modulus Beamforming
Jiang, X., So, H. C., Zeng, W., Yasotharan, A., & Kirubarajan, T. T. (2017) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2017.2710778 · Cited by 4
“The objective function of the conventional CM criterion is a quartic (fourth-order) polynomial of the beamformer coefficients, whose minimization is known as nonconvex and NP-hard [33], [34].”
BackgroundLP-based tractable subcones of the semidefinite plus nonnegative cone
Tanaka, A., & Yoshise, A. (2018) · Annals of Operations Research · doi:10.1007/s10479-017-2720-z · Cited by 4
“It has been shown that the above problem is co-NP-complete [31][19][20] and many algorithms have been proposed to solve it (see, e.”
BackgroundNew Proximal Newton-Type Methods for Convex Optimization
Adler, I., Hu, Z. T., & Lin, T. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9304423 · Cited by 4
“In general, finding one global optimal solution is NPhard [24] but standard for convex composite optimization.”
BackgroundA more efficient deterministic annealing neural network algorithm for the max-bisection problem
Jiang, S., & Dang, C. (2021) · Neurocomputing · doi:10.1016/j.neucom.2021.06.050 · Cited by 4
Tian, Y., Fang, S., Deng, Z., & Xing, W. (2013) · Journal of Industrial and Management Optimization · doi:10.3934/jimo.2013.9.701 · Cited by 4
Feedback control design using sum of squares optimisation
August, E., & Papachristodoulou, A. (2022) · European Journal of Control · doi:10.1016/j.ejcon.2022.100683 · Cited by 4
Obstacle Aware Sampling for Path Planning
Tukan, M., Maalouf, A., Feldman, D., & Poranne, R. (2022) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros47612.2022.9981428 · Cited by 4
“In fact, this is a quadratic optimization over a positive-definite matrix, which is known to be NP-hard [22].”
BackgroundGenerating extreme copositive matrices near matrices obtained from COP-irreducible graphs
Manainen, M., Seliugin, M., Tarasov, R., & Hildebrand, R. (2023) · Linear Algebra and its Applications · doi:10.1016/j.laa.2023.09.026 · Cited by 4
“Verifying copositivity of a given matrix is a co-NP-complete problem [15].”
BackgroundSymmetries in Polynomial Optimization
Moustrou, P., Riener, C., & Verdure, H. (2023) · Springer optimization and its applications · doi:10.1007/978-3-031-38659-6_3 · Cited by 4
Notoriously hard (mixed-)binary QPs: empirical evidence on new completely positive approaches
Bomze, I. M., Cheng, J., Dickinson, P. J. C., Lisser, A., & Liu, J. (2018) · Computational Management Science · doi:10.1007/s10287-018-0337-6 · Cited by 4
Globally solving extended trust region subproblems with two intersecting cuts
Deng, Z., Lu, C. Z., Tian, Y., & Luo, J. (2019) · Optimization Letters · doi:10.1007/s11590-019-01484-z · Cited by 4
Best Nonnegative Rank-One Approximations of Tensors
Hu, S., Sun, D., & Toh, K.-C. (2019) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/18m1224064 · Cited by 4
“The problem of deciding the copositivity 187 of a tensor is therefore co-NP-hard [14,36], i.”
BackgroundProbabilistic Bounds on Vehicle Trajectory Prediction Using Scenario Approach
Shen, X., Zhang, X., & Raksincharoensak, P. (2020) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2020.12.038 · Cited by 4
Copositive Conditions for LMI-Based Controller and Observer Design
Arceo, J. C., & Lauber, J. (2020) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2020.12.2195 · Cited by 4
“Verifying that a matrix Q is not copositive is a well known NP-complete problem Murty and Kabadi (1987), it can not be verified by checking its eigenvalues, all the positive definite matrices are copositive, but the converse is false.”
BackgroundInfluentialInferring properties of dust in supernovae with neural networks
Ansari, Z., Gall, C., Wesson, R., & Krause, O. (2022) · Astronomy and Astrophysics · doi:10.1051/0004-6361/202243078 · Cited by 4
August, E., & Barahona, M. (2022) · Journal of Computational Dynamics · doi:10.3934/jcd.2022017 · Cited by 4
“It is well known that testing positivity of a polynomial is NP-hard [22, 26], except in very particular cases.”
BackgroundSolution to nonconvex quadratic programming with both inequality and box constraints
Zhang, X., Zhu, J., & Gao, D. Y. (2008) · Optimization and Engineering · doi:10.1007/s11081-008-9062-2 · Cited by 4
“Actually, it is known that quadratic minimization problems with only box constraints are NP-hard (Murty and Kabadi 1987; Pardalos 1988).”
BackgroundMoment Approximations for Set-Semidefinite Polynomials
Dickinson, P. J. C., & Povh, J. (2013) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-013-0279-7 · Cited by 4
“In this paper we show that in the special case of considering nonnegativity over a subset of the nonnegative orthant, we can provide a new outer approximation hierarchy based on the completely positive moment matrices, which is a new idea and implies other approximations which are at least as good…”
BackgroundInteger Quadratic Quasi-polyhedra
Letchford, A. N. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13036-6_20 · Cited by 4
“Unfortunately, this additional information does not help us much, because a complete linear description of the completely positive cone is unknown, and unlikely to be found for general n [12].”
BackgroundConstrained quadratic optimization: Theory and application for wireless communication systems
Hons, E. S. (2001) · Cited by 4
Necessary and sufficient condition for local minima of a class of nonconvex quadratic programs
Cao, J. (1995) · Mathematical Programming · doi:10.1007/bf01585567 · Cited by 4
“Nevertheless, in general nonconvex case, Murty and Kabadi showed that the problem of checking whether a feasible solution x m) is a local minimum is NP-complete [ 6 ] (see also [8]).”
BackgroundA new bound-and-reduce approach of nonconvex quadratic programming problems
Gao, Y., & Wei, F. (2014) · Applied Mathematics and Computation · doi:10.1016/j.amc.2014.10.077 · Cited by 4
“As is well-known to all, nonconvex quadratic programming problem is NP-Hard [6,7].”
BackgroundControl problems and the polynomial time hierarchy
Tierno, J. E., & Doyle, J. C. (2002) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.1995.478587 · Cited by 4
Optimality conditions for maximizing a function over a polyhedron
Hager, W. W., & Hungerford, J. T. (2013) · Mathematical Programming · doi:10.1007/s10107-013-0644-1 · Cited by 4
“In [12,16] it is shown that checking local optimality for an indefinite quadratic programming problem can be NP-hard.”
BackgroundOn Approximation Algorithms for Concave Mixed-Integer Quadratic Programming
Pia, A. D. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-33461-5_1 · Cited by 4
Antal, M., Pop, C. D., Cioara, T., Anghel, I. M., Tamas, I., & Salomie, I. (2017) · IEEE International Conference on Intelligent Computer Communication and Processing (ICCP) · doi:10.1109/iccp.2017.8117058 · Cited by 4
“It can be shown that the resulting decision problem is NP-complete [2], and most approximation algorithms are also NP-complete [3].”
BackgroundQuasi-translations for fast hybrid nonlinear model predictive control
Maitland, A., & McPhee, J. (2020) · Control Engineering Practice · doi:10.1016/j.conengprac.2020.104352 · Cited by 4
Matrix Relaxations in Combinatorial Optimization
Rendl, F. (2011) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4614-1927-3_17 · Cited by 4
“In contrast, it is NP-complete to decide if a matrix does not belong to C, see [49].”
BackgroundA note on the solution of a class of BMIs for H/sub ∞/ problems
Mattei, M. (2002) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2000.914221 · Cited by 4
“The BMI optimisation problems are non convex and NPhard to solve [ 4 ], [5], however many ad hoc numerical algorithms can be found in the literature of the past decade giving local or global solutions to them.”
BackgroundDuality Gap, Computational Complexity and NP Completeness: A SurveyPreprint
Manyem, P. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1012.5568 · Cited by 4
“[19] If an optimization problem is non-convex, it is NP-hard.”
BackgroundToward unified analysis and controller synthesis for a class of hybrid systems
Rodrigues, L., & How, J. P. (2006) · Nonlinear Analysis · doi:10.1016/j.na.2006.02.048 · Cited by 4
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.