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 401–500 of 1,000
Bounding Multivariate Trigonometric Polynomials
Pfister, L., & Bresler, Y. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2883925 · Cited by 16
“Unfortunately, determining the extremal values of a multivariate polynomial given its coefficients is NP-Hard [3], [4].”
BackgroundLi, Y., & Liu, Y. (2024) · IEEE Transactions on Communications · doi:10.1109/tcomm.2024.3385919 · Cited by 22
“In fact, it is even NP-hard to find a feasible solution satisfying (3b) [41].”
BackgroundA Copositive Framework for Analysis of Hybrid Ising-Classical Algorithms
Brown, R., Bernal, D. E., Venturelli, D., & Pavone, M. (2024) · SIAM Journal on Optimization · doi:10.1137/22m1514581 · Cited by 21
“Finally, we explicitly show how cutting-plane algorithms can be used to solve copositive optimization problems given a copositivity oracle and discuss how to implement a copositivity oracle using an Ising solver.”
MethodLifting for Simplicity: Concise Descriptions of Convex Sets
Fawzi, H., Gouveia, J., Parrilo, P. A., Saunderson, J., & Thomas, R. R. (2022) · SIAM Review · doi:10.1137/20m1324417 · Cited by 25
Chen, J., Peng, J., & Lin, D. K. J. (2021) · Computers & Industrial Engineering · doi:10.1016/j.cie.2021.107773 · Cited by 16
Johnson, C. R., Smith, R. L., & Tsatsomeros, M. J. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108778619 · Cited by 16
Multi-activity influence and intervention
Kor, R., & Zhou, J. (2022) · Games and Economic Behavior · doi:10.1016/j.geb.2022.11.007 · Cited by 16
A new treatment of inconsistent quadratic programs in a SQP-based algorithm
de Gouvêa, M. T., & Odloak, D. (1998) · Computers & Chemical Engineering · doi:10.1016/s0098-1354(98)00231-2 · Cited by 16
Shestak, V., Chong, E. K. P., Siegel, H. J., Maciejewski, A. A., Benmohamed, L., Wang, I.-J., & Daley, R. A. (2007) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2007.05.011 · Cited by 16
“Constraint (II) makes the Integer Linear Programming problem NP-complete [32].”
BackgroundInfluentialOn the exhaustivity of simplicial partitioning
Dickinson, P. J. C. (2013) · Journal of Global Optimization · doi:10.1007/s10898-013-0040-7 · Cited by 16
A New ILS Algorithm for Cast Planning Problem in Steel Industry
Tang, L., & Luo, J. (2007) · ISIJ International · doi:10.2355/isijinternational.47.443 · Cited by 16
Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme
Deng, Z., Fang, S., Jin, Q., & Xing, W. (2013) · European Journal of Operational Research · doi:10.1016/j.ejor.2013.02.031 · Cited by 15
Jargalsaikhan, B. (2013) · Electronic Journal of Linear Algebra · doi:10.13001/1081-3810.1685 · Cited by 15
A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits
Lee, J., Yun, S.-Y., & Jun, K.-S. (2024) · neural information processing systems · doi:10.52202/079017-3960 · Cited by 15
Kishida, M., Rumschinski, P., Findeisen, R., & Braatz, R. D. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2321230 · Cited by 15
Protecting location privacy and query privacy: a combined clustering approach
Lin, C., Wu, G., & Yu, C. W. (2014) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.3244 · Cited by 15
“This problem is nearly identical with the set covering problem [36, 37], which is NP-hard [38, 39].”
BackgroundEntangled symmetric states and copositive matrices
Marconi, C., Aloy, A., Tura, J., & Sanpera, A. (2021) · Quantum · doi:10.22331/q-2021-10-07-561 · Cited by 15
“Thus, detecting entanglement of ρDS in d ≥ 5, is equivalent to check the membership of the corresponding copositive matrix H ∈ COPd \ (PSDd +Nd), which is, in general, a co-NP-hard problem [19].”
BackgroundDiscriminant analysis of distributional data via fractional programming
Dias, S., Brito, P., & Amaral, P. A. (2021) · European Journal of Operational Research · doi:10.1016/j.ejor.2021.01.025 · Cited by 15
“…C ∗ n with rank(Γ) = 1, and considering that γ (cid:48) Wγ = W • Γ, following Amaral et al. (2014) we obtain the following completely positive reformulation of (16): Murty and Kabadi (1987); Dickinson and Gijben (2011), but knowing that the cone of symmetric, non-negative and semi-definite…”
BackgroundTesting copositivity with the help of difference-of-convex optimization
Dür, M., & Hiriart‐Urruty, J. (2013) · Mathematical Programming · doi:10.1007/s10107-012-0625-9 · Cited by 15
The CP-Matrix Completion Problem
Zhou, A.-W., & Fan, J.-Y. (2013) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/130919490 · Cited by 21
“Some NP-hard problems can be formulated as linear optimization problems over the cone of CP-matrices (cf. [22, 27, 34]).”
BackgroundComplexity of ten decision problems in continuous time dynamical systems
Ahmadi, A. A., Majumdar, A., & Tedrake, R. (2013) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2013.6580838 · Cited by 15
“as an immediate consequence of NP-hardness testing matrix copositivity [20].”
BackgroundA fresh CP look at mixed-binary QPs: new formulations and relaxations
Bomze, I. M., Cheng, J., Dickinson, P. J. C., & Lisser, A. (2017) · Mathematical Programming · doi:10.1007/s10107-017-1109-8 · Cited by 15
Immobile Indices and CQ-Free Optimality Criteria for Linear Copositive Programming Problems
Kostyukova, O. I., Tchemisova, T. V., & Dudina, O. S. (2020) · Set-Valued and Variational Analysis · doi:10.1007/s11228-019-00527-y · Cited by 15
“Although the copositive problems are convex, they are known to be NP-hard, with difficulties caused by the copositive cone constraint since testing of copositivity of matrices is co-NP-complete [33].”
BackgroundReflection groups and cones of sums of squares
Debus, S., & Riener, C. (2023) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2023.03.001 · Cited by 15
“≥5,whichfinishestheproof. 3.4. LMIs and non-negativity testing. In general testing non-negativity of a polynomial in more than two variables is already for quartics an NP-hard problem (see e.g. [8] or [27]). On the other hand, certifying that a given polynomial is a sum of squares can be done with socalledsemi-definitep…”
BackgroundInfluentialA cone programming approach to the bilinear matrix inequality problem and its geometry
Mesbahi, M., & Papavassilopoulos, G. P. (1997) · Mathematical Programming · doi:10.1007/bf02614437 · Cited by 15
Semidefinite programming based tests for matrix copositivity
Parrilo, P. A. (2002) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2001.914655 · Cited by 15
The relief indicator method for constrained global optimization
Thach, P. T., & Tụy, H. (1990) · Naval Research Logistics (NRL) · doi:10.1002/1520-6750(199008)37:4 · Cited by 15
Complete Dictionary Learning via $\ell^4$-Norm Maximization over the Orthogonal GroupPreprint
Zhai, Y., Yang, Z., Liao, Z., Wright, J. N., & Ma, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.02435 · Cited by 15
On Difference-of-SOS and Difference-of-Convex-SOS Decompositions for Polynomials
Niu, Y.-S., Thi, H. A. L., & Dinh, T. P. (2024) · SIAM Journal on Optimization · doi:10.1137/22m1495524 · Cited by 14
“It is well-known that deciding nonnegativity of a polynomial of degree ≥ 4 is NP-hard [33] (since deciding matrix copositivity is NP-complete).”
BackgroundA network decomposition approach for efficient sum of squares programming based analysis
Anderson, J., & Papachristodoulou, A. (2010) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2010.5530945 · Cited by 14
“network to 3 interacting subsystems of lower state dimension with the following state partitions; I1 = [1, 3, 7, 8, 9], I2 = [2, 6, 10, 15, 16] and I3 = [4, 5, 11, 12, 13, 14].”
BackgroundReexamining low rank matrix factorization for trace norm regularization
Ciliberto, C., Pontil, M., & Stamos, D. (2022) · Mathematics in Engineering · doi:10.3934/mine.2023053 · Cited by 14
Indefinite Linear Quadratic Optimal Control: Strict Dissipativity and Turnpike Properties
Berberich, J., Köhler, J., Allgöwer, F., & Müller, M. A. (2018) · IEEE Control Systems Letters · doi:10.1109/lcsys.2018.2842142 · Cited by 14
“Thus, our approach can be seen as a relaxation for indefinite QCQPs which are, in general, np-hard [16].”
BackgroundThe extreme rays of the $$6\times 6$$ copositive cone
Afonin, A., Hildebrand, R., & Dickinson, P. J. C. (2020) · Journal of Global Optimization · doi:10.1007/s10898-020-00930-y · Cited by 14
Safety Verification of Controlled Advanced Life Support System Using Barrier Certificates
Glavaški, S., Papachristodoulou, A., & Ariyur, K. B. (2005) · Lecture notes in computer science · doi:10.1007/978-3-540-31954-2_20 · Cited by 14
“This is because testing non-negativity even in the case of polynomial functions of degree greater than or equal to 4 is NP-hard [ 7 ].”
BackgroundA FPTAS for computing a symmetric Leontief competitive economy equilibrium
Zhu, Z., Dang, C., & Ye, Y. (2010) · Mathematical Programming · doi:10.1007/s10107-010-0348-8 · Cited by 14
“Computing or checking the existence of a KKT point are NP-complete problems as general LCPs are (see, e.g., Murty and Kabadi [16]), however there exists an FPTAS for computing an (cid:2) -approximate KKT point of general quadratic programming with bounded feasible region (see, e.g. [23]): where ,…”
BackgroundExtended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations
Bomze, I. M., Jeyakumar, V., & Li, G. (2018) · Journal of Global Optimization · doi:10.1007/s10898-018-0607-4 · Cited by 14
“Checking copositivity is NP-hard for most cones Γ of interest, see [16, 31] for the classical case Γ = R+ studied already by Motzkin [30] who coined the notion back in 1952.”
BackgroundSeparation and relaxation for cones of quadratic forms
Burer, S., & Dong, H. (2011) · Mathematical Programming · doi:10.1007/s10107-011-0495-6 · Cited by 14
“Generally, even testing whether a matrix is in C∗ is co-NP-complete [23].”
BackgroundNew reformulations of distributionally robust shortest path problem
Cheng, J., Leung, J. M. Y., & Lisser, A. (2016) · Computers & Operations Research · doi:10.1016/j.cor.2016.05.002 · Cited by 19
Time domain validation of structured uncertainty model sets
Toker, O., & Chen, J. (2002) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.1996.574309 · Cited by 14
Simchowitz, M., Alaoui, A. E., & Recht, B. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1704.04548 · Cited by 16
“Particular attention has been devoted to avoiding saddle points in nonconvex landscapes [50, 39, 45, 78], which, without further regularity assumptions, are known to render the task of finding even local minimizers computationally hard [55].”
BackgroundMultivariate Nonnegative Quadratic MappingsPreprint
Luo, Z.-Q. T., Zhang, S., & Sturm, J. F. (2004) · SSRN Electronic Journal · doi:10.2139/ssrn.545582 · Cited by 14
The loss landscape of deep linear neural networks: a second-order analysisPreprint
Achour, E. M., Malgouyres, F., & Gerchinovitz, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.13289 · Cited by 16
“However, in general, finding a global optimum of a non-convex function is an NP-complete problem [35]; this is in particular the case for a simple 3-node neural network [8].”
BackgroundAn algorithm for determining copositive matrices
Xu, J., & Yao, Y. (2011) · Linear Algebra and its Applications · doi:10.1016/j.laa.2011.04.038 · Cited by 13
“In general, it is an NP-complete problem to determine whether a given n × n symmetric matrix is not copositive [37, 38].”
BackgroundHigher-order Newton methods with polynomial work per iteration
Ahmadi, A. A., Chaudhry, A., & Zhang, J. (2024) · Advances in Mathematics · doi:10.1016/j.aim.2024.109808 · Cited by 13
Bosonic Quantum Computational Complexity
Chabaud, U., Joseph, M., Mehraban, S. A., & Motamedi, A. (2026) · Quantum · doi:10.22331/q-2026-05-20-2110 · Cited by 16
“This problem is known to be co - NP -complete [36].”
Robust Performance of Spectrum Sensing in Cognitive Radio Networks
Gong, S., Wang, P., & Huang, J. (2013) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2013.040213.120781 · Cited by 13
Improving performance by network-aware virtual machine clustering and consolidation
Luo, G., Qian, Z., Dong, M., Ota, K., & Lu, S. (2017) · The Journal of Supercomputing · doi:10.1007/s11227-017-2104-9 · Cited by 13
“[11] proved that nonlinear programming is NP-Hard.”
Complexity aspects of local minima and related notions
Ahmadi, A. A., & Zhang, J. (2021) · Advances in Mathematics · doi:10.1016/j.aim.2021.108119 · Cited by 13
Tong, J., Wang, C., Zhao, X., Cui, G., & Wang, W. (2022) · Electronics · doi:10.3390/electronics11030299 · Cited by 13
“In Algorithm 2, the computational complexity of using the interior-point method in CVX is O((KL)Ni) [16], where Ni is the iteration times of the SCA method.”
MethodConic Relaxations for Semi-supervised Support Vector Machines
Bai, Y., & Yan, X. (2015) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-015-0843-4 · Cited by 13
“However, the weakness of CPP problems is that they may be NP-hard [24].”
BackgroundWhen Are Nonconvex Optimization Problems Not Scary?
Sun, J. (2016) · doi:10.7916/d8251j7h · Cited by 13
Fallahzadeh, R., Pagán, J., & Ghasemzadeh, H. G. (2017) · Design, Automation, and Test in Europe · doi:10.23919/date.2017.7927136 · Cited by 13
“As shown in [10], such discrete optimization is a reduction of Subset Sum Problem which is known to be NP-complete.”
BackgroundBreaking Bandwidth Limitation for Mission-Critical IoT Using Semisequential Multiple Relays
Hsu, S.-H., Lin, C.-H., Wang, C.-Y., & Chen, W.-T. (2017) · IEEE Internet of Things Journal · doi:10.1109/jiot.2017.2776403 · Cited by 13
“We observe that the relay selection problem is a quadratic constraint optimization problem, which has been shown to be NP-hard [26], [27].”
BackgroundMachine Learning of Time Series Using Time-Delay Embedding and Precision Annealing
Ty, A. J. A., Fang, Z., Gonzalez, R. A., Rozdeba, P. J., & Abarbanel, H. D. I. (2019) · Neural Computation · doi:10.1162/neco_a_01224 · Cited by 15
Device‐centric communication in IoT: An energy efficiency perspective
Ahmad, M., Ali, M., Naeem, M., Ahmed, A., Iqbal, M. N., Ejaz, W., & Anpalagan, A. (2019) · Transactions on Emerging Telecommunications Technologies · doi:10.1002/ett.3750 · Cited by 13
Algebraic Perspectives on Signomial Optimization
Dressler, M., & Murray, R. (2022) · SIAM Journal on Applied Algebra and Geometry · doi:10.1137/21m1462568 · Cited by 13
“Since matrix copositivity is NP-hard [52] it follows that signomial nonnegativity is intractable in the general”
BackgroundLinear slices of hyperbolic polynomials and positivity of symmetric polynomial functions
Riener, C., & Schabert, R. (2023) · Journal of Pure and Applied Algebra · doi:10.1016/j.jpaa.2023.107552 · Cited by 13
A Barrier Function Method for the Nonconvex Quadratic Programming Problem with Box Constraints
Dang, C., & Xu, L. (2000) · Journal of Global Optimization · doi:10.1023/a:1008397325409 · Cited by 13
“It is an NP-hard problem (Murty and Kabadi, 1987) and has many diverse applications (Pardalos and Rosen, 1987).”
BackgroundOn computational complexity of invalidating structured uncertainty models
Toker, O., & Chen, J. (1998) · Systems & Control Letters · doi:10.1016/s0167-6911(97)00131-x · Cited by 13
Alberge, F., Nikolova, M., & Duhamel, P. (2006) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2005.861787 · Cited by 14
“In the nonconvex case, the quadratic programming problem subject to linear constraints is NP-complete [21].”
BackgroundDerandomization in Combinatorial Optimization
Srivastav, A. (2001) · Combinatorial optimization · doi:10.1007/978-1-4615-0013-1_18 · Cited by 14
A Finite Algorithm for Global Minimization of Separable Concave Programs
Shectman, J. P., & Sahinidis, N. V. (1996) · Nonconvex optimization and its applications · doi:10.1007/978-1-4613-3437-8_20 · Cited by 13
Efficiently avoiding saddle points with zero order methods: No gradients requiredPreprint
Flokas, L., Vlatakis-Gkaragkounis, E.-V., & Piliouras, G. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.13021 · Cited by 19
“In fact, discovering global optima is an NP hard problem in general and even for quartic functions verifying local optima is a co-NP complete problem [Murty and Kabadi, 1987, Lee et al., 2019].”
BackgroundEscaping Saddle Points Faster with Stochastic MomentumPreprint
Wang, J.-K., Lin, C.-H., & Abernethy, J. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.02985 · Cited by 14
Limitations of Implicit Bias in Matrix Sensing: Initialization Rank MattersPreprint
Eftekhari, A., & Zygalakis, K. C. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.12091 · Cited by 14
“1(ii), we cannot in general hope to efficiently find any matrix that achieves zero training error! Such peculiarities are not uncommon in nonconvex optimization [26].”
BackgroundLuo, G., Qian, Z., Dong, M., Ota, K., & Lu, S. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-11197-1_20 · Cited by 12
Solving Integer Quadratic Programming via Explicit and Structural Restrictions
Eiben, E., Ganian, R., Knop, D., & Ordyniak, S. (2019) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v33i01.33011477 · Cited by 12
“A simple reduction from S UBSET S UM given in (Murty and Kabadi 1987, Example 2) shows that IQP remains NP -hard even if all variables are binary and the instance has only box constraints.”
BackgroundMethodInfluentialAdaptive regularization minimization algorithms with nonsmooth norms
Gratton, S., & Toint, P. L. (2022) · IMA Journal of Numerical Analysis · doi:10.1093/imanum/drac005 · Cited by 12
A new Lagrangian net algorithm for solving max-bisection problems
Xu, F., Ma, X., & Chen, B. (2011) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2011.01.015 · Cited by 12
“3), since it is better than changing the diagonal element of Q̄ to >0 [1].”
Copositivity tests based on the linear complementarity problem
Brás, C. P., Eichfelder, G., & Júdice, J. J. (2015) · Computational Optimization and Applications · doi:10.1007/s10589-015-9772-2 · Cited by 12
On linear conic relaxation of discrete quadratic programs
Nie, T., Fang, S., Deng, Z., & Lavery, J. E. (2016) · Optimization methods & software · doi:10.1080/10556788.2015.1134528 · Cited by 12
“Each variable may take h possible values { d i 1 , d i 2 , . . . , Problem (DQP) is known to be NP-hard [16], even for the simple version of binary quadratic programming problems.”
BackgroundHierarchical Signal Processing for Tractable Power Flow Management in Electric Grid Networks
Srikantha, P., & Kundur, D. (2018) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2018.2858750 · Cited by 13
“Problems falling in this class cannot be solved in a tractable manner especially for large systems [5].”
BackgroundFallahzadeh, R., & Ghasemzadeh, H. G. (2018) · ACM Transactions on Design Automation of Electronic Systems · doi:10.1145/3198457 · Cited by 12
“As shown in Murty and Kabadi (1987), such discrete optimization is a reduction of the subset sum sroblem, which is known to be NP-complete.”
BackgroundExploiting Partial Correlations in Distributionally Robust Optimization
Padmanabhan, D., Natarajan, K., & Murthy, K. (2018) · Mathematical Programming · doi:10.1007/s10107-019-01453-5 · Cited by 12
On semidefinite representations of non-closed sets
Netzer, T. (2010) · Linear Algebra and its Applications · doi:10.1016/j.laa.2010.02.005 · Cited by 12
“e, for any dimension k, since it is convex and semialgebraic. On the other hand, the problem of deciding wether a given integer matrix is not copositive is shown to be NP-complete my Kabadi and Murty [15]. This suggests that the cone of copositive matrices may either not be semidefinite representable, or at least the…”
BackgroundEvery Local Minimum Value Is the Global Minimum Value of Induced Model in Nonconvex Machine Learning
Kawaguchi, K., Huang, J., & Kaelbling, L. P. (2019) · Neural Computation · doi:10.1162/neco_a_01234 · Cited by 12
“unctions used to train deep models. In general, theoretical understanding of non-convex high-dimensional optimization is challenging. Indeed, finding a global minimum of a general non-convex function (Murty and Kabadi, 1987) and training certain types of neural networks (Blum and Rivest, 1992) are both NP-hard. Conside…”
BackgroundAn Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix
Badenbroek, R., & de Klerk, E. (2021) · INFORMS journal on computing · doi:10.1287/ijoc.2021.1108 · Cited by 12
“question if C ∈CPd or not, and if not, we immediately have an X ∈COPd that induces a valid cut. It should be noted that determining if a matrix X lies in COPd is co-NP-complete, see Murty and Kabadi [31]. The classical copositivity test is due to Gaddum [19], but his procedure requires performing a test for all princi…”
BackgroundInexact Newton-CG algorithms with complexity guarantees
Yao, Z., Xu, P., Roosta, F., Wright, S. J., & Mahoney, M. W. (2022) · IMA Journal of Numerical Analysis · doi:10.1093/imanum/drac043 · Cited by 22
“Capped-CG, proposed by Royer et al. [2020] and presented in Procedure 1 for completeness, is an original way to leverage and detect such negative curvature directions, when they are encountered during CG iterations.”
BackgroundData-Driven Control of Positive Linear Systems using Linear Programming
Miller, J., Dai, T., Sznaier, M., & Shafai, B. (2023) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc49753.2023.10383859 · Cited by 12
“2) Copositive Functions: Definition 2.2: Copositivity of the linear function V ( x ) = v T x and the dual-linear function V ( x ) = max( x./v ) may be checked by verifying that v > 0 , but testing copositivity of a matrix function such as x T Mx for some M ∈ R n × n is generically NP-hard [46].”
BackgroundInfluentialKéri, G. (2001) · Applied optimization · doi:10.1007/978-1-4613-0295-7_9 · Cited by 12
Cardinality constrained portfolio selection problem: A completely positive programming approach
Tian, Y., Fang, S., Deng, Z., & Jin, Q. (2015) · Journal of Industrial and Management Optimization · doi:10.3934/jimo.2016.12.1041 · Cited by 12
Nouiehed, M., & Razaviyayn, M. (2020) · SIAM Journal on Optimization · doi:10.1137/19m1256415 · Cited by 12
Mo, C., Li, C., Wang, X., & Wei, Y. (2019) · Computational and Applied Mathematics · doi:10.1007/s40314-019-0926-1 · Cited by 12
Second-Order Information in Non-Convex Stochastic Optimization: Power and LimitationsPreprint
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Sekhari, A., & Sridharan, K. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.13476 · Cited by 12
“[28] Katta G Murty and Santosh N Kabadi.”
BackgroundRouting of Electric Vehicles: Constrained Shortest Path Problems with Resource Recovering Nodes
Merting, S., Schwan, C., & Strehler, M. (2015) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2015.29 · Cited by 11
On standard quadratic programs with exact and inexact doubly nonnegative relaxations
Gökmen, Y. G., & Yıldırım, E. A. (2021) · Mathematical Programming · doi:10.1007/s10107-020-01611-0 · Cited by 11
Dong, L., Loyka, S. L., & Li, Y. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3010451 · Cited by 15
“Provable convergence to a global optimum in this case is out of reach [35], [44]–[46].”
BackgroundChernyavsky, A. I., Bramburger, J. J., Fantuzzi, G., & Goluskin, D. (2023) · SIAM Journal on Optimization · doi:10.1137/21m1455127 · Cited by 11
Chen, L., Shen, C., Vogelstein, J. T., & Priebe, C. E. (2015) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2456913 · Cited by 11
“argmin x kxk 0 subject to ˚= Dx; (12) where kk 0 is the number of nonzero entries in x. We denote the sparsity level of xby s, i.e., s= kxk 0. Directly solving the L 0 minimization problem is NP-hard [22], that is, the complexity of the search in L 0 minimization grows exponentially with n. One may solve the L 0 minim…”
BackgroundMullaoğlu, G., & Yıldırım, E. A. (2015) · Journal of Global Optimization · doi:10.1007/s10898-015-0269-4 · Cited by 11
“Similarly, themembership problem for the dual cone C∗ is also NP-hard [10,15].”
BackgroundInfluentialUnbounded convex sets for non-convex mixed-integer quadratic programming
Burer, S., & Letchford, A. N. (2012) · Mathematical Programming · doi:10.1007/s10107-012-0609-9 · Cited by 11
“The CVP was shown to be strongly NP-hard in [41].”
BackgroundInfluentialGpoSolver: a Matlab/C++ toolbox for global polynomial optimization
Heller, J., & Pajdla, T. (2016) · Optimization methods & software · doi:10.1080/10556788.2015.1121489 · Cited by 11
A robust Lagrangian-DNN method for a class of quadratic optimization problems
Arima, N., Kim, S., Kojima, M., & Toh, K.-C. (2016) · Computational Optimization and Applications · doi:10.1007/s10589-016-9879-0 · Cited by 11
“These CPP reformulations of QOPs are mainly for theoretical interests since CPP problems are numerically intractable [17].”
BackgroundA Lanczos Method for Large-Scale Extreme Lorentz Eigenvalue Problems
Zhang, L., Shen, C., Yang, W. H., & Júdice, J. J. (2018) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/17m1111401 · Cited by 11
“It is known that there are a couple of equivalent statements for copositivity [25]; however, unfortunately, testing whether A is copositive is challenging and indeed a coNP-complete problem, meaning that testing whether A is not copositive is NP-complete [27].”
BackgroundA guide to conic optimisation and its applications
Letchford, A. N., & Parkes, A. J. (2018) · RAIRO - Operations Research · doi:10.1051/ro/2018034 · Cited by 11
“) On the other hand, testing whether a rational matrix is completely positive is NP-hard [72].”
BackgroundStability of the linear complementarity problem properties under interval uncertainty
Hladík, M. (2021) · Central European Journal of Operations Research · doi:10.1007/s10100-021-00745-6 · Cited by 11
“ntary pivot algorithm for solving the LCP works. A strictly copositive matrix in addition implies that the LCP has a solution for each q ∈ Rn. Checking whether A is copositive is a co-NP-hard problem [19]. From the definition immediately follows: Proposition 3. Ais strongly (strictly) copositive if and only if A is (st…”
BackgroundKurpisz, A., Potechin, A., & Wirth, E. S. (2021) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.icalp.2021.90 · Cited by 11
“This claim is supported by the fact that high degree optimization problems attracted limited attention, especially since solving an NP-complete problem can be reduced in polynomial time to proving nonnegativity of a degree-4 even form [37].”
(2021) · Lecture notes in computer science · doi:10.1007/978-3-030-76384-8 · Cited by 11
PGP for portfolio optimization: application to ESG index family
Abid, I., Urom, C., Peillex, J., Karmani, M., & Ndubuisi, G. O. (2023) · Annals of Operations Research · doi:10.1007/s10479-023-05460-w · Cited by 11
“Asamatter offact,whenincludinghigher-ordermoments,theobjectivefunctionsbecomenon-convex, whichmakestheproblemsingeneralNP-hard(Murty&Kabadi,1985).”
New Analysis on Sparse Solutions to Random Standard Quadratic Optimization Problems and Extensions
Chen, X., & Peng, J. (2015) · Mathematics of Operations Research · doi:10.1287/moor.2014.0692 · Cited by 11
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.