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 801–900 of 1,000
Tong, J., Wang, C., Zhao, X., Cui, G., & Wang, W. (2022) · International Journal of Satellite Communications and Networking · doi:10.1002/sat.1445 · Cited by 2
Strong Data Processing Inequalities via Sums of Squares
Faust, O., & Fawzi, H. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834406 · Cited by 2
Reachability Analysis of Neural Feedback Loops using Sparse Polynomial Optimisation
Newton, M., & Papachristodoulou, A. (2022) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc51059.2022.9992719 · Cited by 2
“Checking the nonnegativity of a polynomial is known to be an NP-hard problem [19], so instead we can check if a polynomial is SOS by solving a semide-finite program in polynomial time.”
MethodA Practical Approach to SOS Relaxations for Detecting Quantum Entanglement
Bhardwaj, A. (2023) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-023-02258-5 · Cited by 5
“However, as is well known, testing the nonnegativity of a polynomial p is an NPhard problem [29, 33].”
BackgroundAccelerated analysis on the triple momentum method for a two-layer ReLU neural network
Li, X., & Liu, X. (2024) · Journal of King Saud University - Computer and Information Sciences · doi:10.1016/j.jksuci.2024.102016 · Cited by 2
Ratz, D. (2001) · Springer eBooks · doi:10.1007/978-3-7091-6282-8_15 · Cited by 2
Computational methods for geochemical modelling: applications to carbon dioxide sequestration
Leal, A. M. M. (2014) · Spiral (Imperial College London) · doi:10.25560/24920 · Cited by 5
Binary Solutions for Overdetermined Systems of Linear EquationsPreprint
Das, S. (2014) · arXiv (Cornell University) · doi:10.6084/m9.figshare.1271664.v1 · Cited by 2
Complexity in Automation of SOS Proofs: An Illustrative Example
Gayme, D. F., Fazel, M., & Doyle, J. C. (2006) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2006.377629 · Cited by 2
“The resulting algebraic question is, i n general, NP hard [8], but SOS relaxations and the Positivste llensatz (P-satz) provide a powerful strategy for overcomin g this apparent intractability.”
BackgroundTópicos em condições de otimalidade para otimização não linear
Flor, J. A. R. (2016) · Digital Library of Theses and Dissertations (Universidade de São Paulo) · doi:10.11606/t.45.2016.tde-18102016-101943 · Cited by 2
Algorithm XXX: SC-SR1: Matlab software for solving shape-changing L-SR1 trust-region subproblemsPreprint
Brust, J. J., Burdakov, O. P., Erway, J. B., Marcia, R. F., & Yuan, Y.-X. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1607.03533 · Cited by 2
“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].”
Mencarelli, L. (2018) · 4OR · doi:10.1007/s10288-018-0372-8 · Cited by 2
Quijorna, M. L. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1809.09043 · Cited by 2
“Moreover to solve polynomial optimization problems without constraints already for degree 4 polynomials is NP hard [7], so it is reasonable to expect that to convert these programs into a semidefinite program is hard.”
BackgroundDistributionally Robust Chance Constrained Geometric Optimization
Lisser, A. (2018) · Open Collections · doi:10.14288/1.0371920 · Cited by 2
Sampling Rates for l1-SynthesisPreprint
März, M., Boyer, C., Kahn, J., & Weiss, P. O. (2020) · HAL · Cited by 2
Murray, R., Chandrasekaran, V., & Wierman, A. (2021) · Mathematical Programming Computation · doi:10.1007/s12532-021-00201-1 · Cited by 2
Murty, K. G. (2013) · Springer eBooks · doi:10.1007/978-1-4419-1153-7_838 · Cited by 2
Self-citationAlgorithm Configuration Problem
Iommazzo, G., D’Ambrosio, C., Frangioni, A., & Liberti, L. (2022) · Springer eBooks · doi:10.1007/978-3-030-54621-2_749-1 · Cited by 2
MINLP: Branch and Bound Global Optimization Algorithm
Androulakis, I. P. (2024) · Springer eBooks · doi:10.1007/978-3-030-54621-2_377-1 · Cited by 2
Complexities of Armijo-like algorithms in Deep Learning contextPreprint
Bilel, B. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2412.14637 · Cited by 2
Global Optimization for Parametrized Quantum CircuitsPreprint
Sakos, I., Varvitsiotis, A., Korpas, G., & Lin, W. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2603.21757 · Cited by 2
“Note that, since Hermitian polynomial optimization includes real polynomial optimization as a special case, it is, in general, an NP -hard problem [28].”
A random matrix framework for large dimensional machine learning and neural networks
Liao, Z. (2019) · theses.fr (ABES) · doi:10.70675/a524b5e8zcec6z4ed6z9975zd205cf648ff1 · Cited by 4
The Rank-Collapse Principle for Quadratic OptimizationPreprint
Soltanalian, M., & Mousavi, A. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2608.07828 · Cited by 2
Mélykúti, B. (2010) · Oxford University Research Archive (ORA) (University of Oxford) · doi:10.5287/ora-2zbye6bye · Cited by 2
Hermitian completely positive matrices
Zhou, A., Fan, J., & Zhou, G. (2020) · Linear Algebra and its Applications · doi:10.1016/j.laa.2020.06.007 · Cited by 1
Kurpisz, A., Potechin, A. H., & Wirth, E. (2025) · Mathematics of Operations Research · doi:10.1287/moor.2024.0422 · Cited by 1
The Cone of $$5\times 5$$ Completely Positive Matrices
Pfeffer, M., & Samper, J. A. (2024) · Discrete & Computational Geometry · doi:10.1007/s00454-023-00620-y · Cited by 1
“For instance, determining whether a given matrix is in CP n is a co-NP-complete problem [20].”
DSLS: a simple and efficient local search algorithm for the maximum bisection problem
Tian, X., Ouyang, D., Zhou, H., Sun, R., & Zhang, L. (2023) · Journal of Heuristics · doi:10.1007/s10732-023-09521-y · Cited by 1
“The max-bisection is a fundamental discrete optimization problem and has many important applications in several scientific disciplines (Murty and Kabadi 1987), for example, very large-scale integration design (Barahona et al. 1988; Chang and Du 1987; Cho et al. 1998), data clustering (Ding et al.…”
The Lorenz system as a gradient-like system
Parker, J. P. (2024) · Nonlinearity · doi:10.1088/1361-6544/ad68bb · Cited by 1
“For example, if one has converged a periodic orbit to machine precision for a given system, and the location and period of this periodic orbit appears to be robust to variations in the timestep or discretisation of the numerical solution, then there is every reason to expect that this is a genuine…”
CUBO-to-QUBO Conversion: Reducing Cubic Formulations to Quadratic Formulations
Tsukiyama, S., Li, X., Nakano, K., Parque, V., Ito, Y., Kato, T., Kawamata, Y., & Ii, K. (2025) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw66978.2025.00096 · Cited by 1
“The QUBO problem is classified as NP-hard [1], [2], implying that any problem in NP class can be reduced to a QUBO problem in polynomial time.”
Spectral Methods for Polynomial Optimization
Moreno, E., & Chandrasekaran, V. (2026) · SIAM Journal on Optimization · doi:10.1137/25m1781942 · Cited by 1
Positive definiteness of a class of fourth order three dimensional symmetric tensors
Song, Y. (2026) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2026.117618 · Cited by 1
On the use of convex underestimators in global optimization
Skjäl, A. (2014) · Åbo Akademi University Research Portal · Cited by 1
Sufficient Optimality Criterion for Linearly Constrained, Separable Concave Minimization Problems
Illés, T., & Nagy, Á. B. (2005) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-005-2089-z · Cited by 1
“CB , we define a test point chosen from the set Hf, ¯ x for each inequality of the system defined in ( 3 )–(5).”
BackgroundMethodComputing enclosures for uncertain biochemical systems
August, E., & Koeppl, H. (2012) · IET Systems Biology · doi:10.1049/iet-syb.2011.0091 · Cited by 1
The bounds of feasible space on constrained nonconvex quadratic programming
Zhu, J. (2007) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2007.01.010 · Cited by 1
August, E., Wang, Y., Doyle, F. J., Lu, J. J.-Q., & Koeppl, H. (2011) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2011.5990737 · Cited by 1
“On the other hand, testing positivity of a polynomial is NPhard [24].”
BackgroundDirect Incorporation of $$L_1$$-Regularization into Generalized Matrix Learning Vector Quantization
Lischke, F., Neumann, T., Hellbach, S., Villmann, T., & Böhme, H.-J. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-91253-0_61 · Cited by 1
Control system design using global optimization techniques
Famularo, D., Pugliese, P., & Sergeyev, Y. D. (2007) · Springer eBooks · doi:10.1007/bfb0110537 · Cited by 1
“It is important to recognize that only the global minimum of the problem is of interest [5], in particular when stability has to be imposed or checked, and that this problem belongs to the ./I/.~-Hard complexity class [ 7 ].”
BackgroundBerahas, A. S., Bollapragada, R., & Dong, W. (2026) · Computational Optimization and Applications · doi:10.1007/s10589-025-00759-9 · Cited by 1
“Specifically, our goal is to find ( (cid:15) g , (cid:15) H )-second-order stationary points, i.e., points x ∈ R n that satisfy (cid:107)∇ f ( x ) (cid:107) 2 ≤ (cid:15) g and ∇ 2 f ( x ) where (cid:15) g > 0 and (cid:15) H > 0; see e.g., [15,33,44,51]).”
An Approximation Method for Solving Nonconvex Quadratic Programming Problems
Ahmadian, A., & Afsharinaf, R. (2011) · Journal of Applied Sciences · doi:10.3923/jas.2011.3807.3810 · Cited by 1
A branch bound method for subset sum problem
Wu, S. (1994) · Acta Mathematicae Applicatae Sinica English Series · doi:10.1007/bf02006860 · Cited by 1
A multiple penalty function method for solving Max-Bisection problems
Xu, F., Xu, C., & Xue, H. (2005) · Applied Mathematics and Computation · doi:10.1016/j.amc.2005.04.012 · Cited by 1
Murty, K. G. (2009) · International series in management science/operations research/International series in operations research & management science · doi:10.1007/978-1-4419-1291-6_9 · Cited by 1
Self-citationStructural optimization of stress-constrained indeterminate trusses as a linear programming problem
Ghattas, O. N., & MELOSH, R. J. (1990) · AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference (SDM) · doi:10.2514/6.1990-1096 · Cited by 1
Conic Reformulation of Some Quadratic Programming Problems with Applications
Tian, Y. (2012) · NCSU Libraries Repository (North Carolina State University Libraries) · Cited by 1
Stochastic nonlinear resource allocation problem
Cheng, J., Lisser, A., & Leung, J. (2016) · Electronic Notes in Discrete Mathematics · doi:10.1016/j.endm.2016.03.022 · Cited by 1
Fallahzadeh, R., & Ghasemzadeh, H. G. (2016) · IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD) · doi:10.1109/iccd.2016.7753320 · Cited by 1
“As shown in [5], such discrete optimization is a reduction of Subset Sum Problem which is known to be NP-complete.”
BackgroundA note on the convergence of an augmented Lagrangian algorithm to second-order stationary points
Ndreani, R., & Secchin, L. D. (2018) · Proceeding Series of the Brazilian Society of Computational and Applied Mathematics · doi:10.5540/03.2018.006.01.0302 · Cited by 1
“Unfortunately, checking SSONC is an NP-hard [6] problem.”
BackgroundAn Assessment of North Carolina's Future Electricity System Under Uncertainty.
Li, B. (2017) · NCSU Libraries Repository (North Carolina State University Libraries) · Cited by 1
On cone optimization approaches for semi-supervised support vector machines(S3VM)
Ahmed, F., Iqbal, M. F., & Rafiq, A. (2019) · International Conference on Computing, Mathematics and Engineering Technologies (iCoMET) · doi:10.1109/icomet.2019.8673478 · Cited by 1
“Moreover, to check, if a matrix is copositive, is an NP-hard optimization problem [22].”
BackgroundA Semidefinite Programming Approach for Harmonic Balance Method
Yang, C., & Deng, B. S. (2019) · IEEE Access · doi:10.1109/access.2019.2928375 · Cited by 1
“Unfortunately, even testing whether a given polynomial (of degree 2d ≤ 4) is nonnegative is NP-hard [35].”
BackgroundTwo Algorithms for Fast Mitigating Multi-Congestion in Software Defined Networks
Sun, M., Zhang, X., & Zhang, J. (2019) · IEEE International Conference on High Performance Computing and Communications; IEEE International Conference on Smart City; IEEE International Conference on Data Science and Systems (HPCC/SmartCity/DSS) · doi:10.1109/hpcc/smartcity/dss.2019.00312 · Cited by 1
“Due to its NP-hard [17], we develop an optimal algorithm based on Lagrange relaxation to approximate the optimal solution and construct a heuristic algorithm to quickly solve the FMCP problem.”
MethodThresholded Wirtinger Flow for Fast Millimeter Wave Beam Alignment
Gan, C., Yang, J., & Shen, C. (2020) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/ieeeconf51394.2020.9443380 · Cited by 1
“In fact, even establishing convergence to a local minimum or stationary point can be quite challenging [21].”
BackgroundA modified simplex partition algorithm to test copositivity
Safi, M., Nabavi, S. S., & Caron, R. J. (2021) · Journal of Global Optimization · doi:10.1007/s10898-021-01092-1 · Cited by 1
“The challenge is that Murty and Kabadi [8] have shown that given a square integer matrix A the decision problem “is A not copositive?" is NP-complete.”
BackgroundOn the degree of varieties of sum of squares
Ferguson, A., Ottaviani, G., Din, M. S. E., & Turatti, E. T. (2024) · Journal of Pure and Applied Algebra · doi:10.1016/j.jpaa.2024.107638 · Cited by 1
“However, even for deg f ≥ 4 this is an NP-hard problem [MK87].”
BackgroundBlack-box optimization in a configuration system
Kucher, M., Balyo, T., & Christensen, N. (2022) · International Software Product Line Conference (SPLC) · doi:10.1145/3503229.3547041 · Cited by 1
“1mathematical optimization is in general NP-hard [12] and the attributes to optimize can not be treated as mathematical functions to optimize, because we can not describe them as such.”
BackgroundOptimization-Based Online Flow Fields Estimation for AUVs Navigation
Xu, H., Lu, Y., & Pan, J. (2023) · Springer proceedings in advanced robotics · doi:10.1007/978-3-031-25555-7_24 · Cited by 1
Entropy for Optimal Control on a Simplex with an Application to Behavioral Nudging
Ahdab, M. A., Knudsen, T., Stoustrup, J., & Leth, J. (2023) · IEEE Control Systems Letters · doi:10.1109/lcsys.2023.3288091 · Cited by 1
“However, determining explicit solutions for StQPs is known to be NPhard [9], even though efficient algorithms are available.”
On Types of Isolated KKT Points in Polynomial Optimization
Guo, F., Jiao, L., Kim, D. S., & Phạm, T.-S. (2023) · Journal of Systems Science and Complexity · doi:10.1007/s11424-023-2119-7 · Cited by 1
RIS-Assisted Physical-Layer Key Generation with Discrete Phase Shift Optimization
Li, H., Li, G., Hu, L., Hu, A., & Ng, D. W. K. (2023) · IEEE Vehicular Technology Conference · doi:10.1109/vtc2023-fall60731.2023.10333843 · Cited by 1
“Note that the LBQP problem in OP3 is proved to be NP-hard [11], finding the globally optimal solutions to it is computationally challenging.”
BackgroundA Robustness-aware LEO Satellite Networking and Resource Allocation Strategy
Sun, J., Sun, J., Wang, H., & Lv, H. (2024) · International Conference on Mobile Internet, Cloud Computing and Information Security (MICCIS) · doi:10.1109/miccis63508.2024.00008 · Cited by 1
“Due to the coupling of the networking decision and resource allocation decisions, and the presence of both continuous and binary variables, the problem 0 P is a NP-hard MINLP problem [16].”
BackgroundNonnegative low-rank matrix recovery can have spurious local minima
Zhang, R. Y. (2026) · Optimization Letters · doi:10.1007/s11590-026-02290-0 · Cited by 1
SNIG Property of Matrix Low-Rank Factorization Model
Wang, H., Liu, X., Chen, X., & Yuan, Y. (2018) · Journal of Computational Mathematics · doi:10.4208/jcm.1707-m2016-0796 · Cited by 1
Utility-based downlink power allocation in multicell wireless packet networks
Lim, H.-K., Choi, J., & Bahk, S. (2005) · Globecom · doi:10.1109/glocom.2004.1378964 · Cited by 1
A complete algorithm for determining copositive matrices
Xu, J., & Yao, Y. (2010) · Cited by 1
Semidefinite and Cone Programming Bibliography/Comments
Wolkowicz, H. (2001) · Cited by 1
Still, G. J., & Ahmed, F. (2014) · University of Twente Research Information · Cited by 1
Using Sum of Squares Decomposition for Stability of Hybrid Systems
Badamchizadeh, M. A., Khanmohammadi, S., Alizadeh, G., Aghagolzadeh, A., & Karimian, G. (2007) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1093/ietfec/e90-a.11.2478 · Cited by 1
Solving non-smooth unconstrained optimization problem with LAMGAC in a LAN-WLAN grid domain
Macías, E. M., Suárez, Á., & Ojeda-Guerra, C. N. (2003) · Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP) · doi:10.1109/empdp.2002.994335 · Cited by 1
Towards energy efficient content delivery networks
Ge, C. (2015) · University of Surrey Open Research repository · Cited by 1
Tractable Subcones and LP-based Algorithms for Testing CopositivityPreprint
Tanaka, A., & Yoshise, A. (2015) · arXiv (Cornell University) · Cited by 1
Hybrid Exact Methods for Solving Strictly Convex Integer Quadratic Programs
Ku, W.-Y. (2017) · TSpace (University of Toronto) · Cited by 1
Konar, A. (2017) · University of Minnesota Digital Conservancy (University of Minnesota) · Cited by 1
Non-Convex Phase Retrieval Algorithms and Performance Analysis
Wang, G. (2018) · University of Minnesota Digital Conservancy (University of Minnesota) · Cited by 1
Sankaranarayanan, S. (2018) · Cited by 1
Frank-Wolfe Optimization for Symmetric-NMF under Simplicial ConstraintPreprint
Zhao, H., & Gordon, G. J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.06348 · Cited by 1
On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum OptimizationPreprint
Emmenegger, N., Kyng, R., & Zehmakan, A. N. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.05138 · Cited by 1
“In this setting, finding such a global minimum is in general NP-Complete (Murty and Kabadi, 1987), so theoretical guarantees are expressed in terms of weaker requirements.”
BackgroundThe Inverse Problems of some Mathematical Programming ProblemsPreprint
Huang, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.15337 · Cited by 1
“Are there any other NP-complete optimization problems whose inverse problems are polynomial solvable?”
BackgroundInfluentialImproved Lower Bounds for Global Polynomial OptimisationPreprint
Seidler, H. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2105.14124 · Cited by 1
Achour, E. M., Malgouyres, F., & Gerchinovitz, S. (2021) · HAL · Cited by 2
Minimax Optimization: The Case of Convex-SubmodularPreprint
Adibi, A., Mokhtari, A., & Hassani, H. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.01262 · Cited by 1
“There has been an extensive literature on the design of convergent methods for solving minimax problems for the case that both minimization and maximization variables belong to continuous domains (Tseng, 1995; Nesterov, 2007; Li and Lin, 2015; Ouyang and Xu, 2019; Thekumparampil et al., 2019; Zhao, 2019; Hamedani and…”
A global optimization technique for fixed-order control design
Famularo, D., Pugliese, P., & Sergeyev, Y. D. (1999) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.1999.786427 · Cited by 1
Gould, N. I. M. (2015) · Springer eBooks · doi:10.1007/978-3-540-70529-1_469 · Cited by 1
Second Order Optimality Conditions for Nonlinear Optimization
Murty, K. G. (2008) · Springer eBooks · doi:10.1007/978-0-387-74759-0_576 · Cited by 1
Self-citationConstant rank-type constraint qualifications and second-order optimality conditions
da Silveira, T. P. (2023) · Digital Library of Theses and Dissertations (Universidade de São Paulo) · doi:10.11606/t.45.2023.tde-27122023-192122 · Cited by 1
On Some Properties of Interior Methods for Optimization
Sporre, G. (2003) · KTH Publication Database DiVA (KTH Royal Institute of Technology) · Cited by 1
Algorithmic configuration by learning and optimization
Iommazzo, G. (2021) · theses.fr (ABES) · doi:10.70675/562d6294z3740z4f80z9c00z3d4d297d74cb · Cited by 2
A Complex-Valued Continuous-Variable Quantum Approximation Optimization Algorithm (CCV-QAOA)Preprint
Madani, R., Lisser, A., & Toffano, Z. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2604.25950 · Cited by 1
“The challenge becomes especially severe for continuous-variable tasks naturally defined over Hilbert spaces such as R n and C n [46], where nonconvex problems are NP-hard [4, 33].”
Data-driven discovery of polynomial ODEs with provably bounded solutionsPreprint
Alcalde, A., & Fantuzzi, G. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2604.26933 · Cited by 1
“Problem (2.6) is convex, but is computationally intractable because nonnegativity constraints on polynomials are NP-hard in general [44].”
InfluentialRelations between Semidefinite, Copositive, Semi-infinite and Integer Programming
Ahmed, F. (2010) · Cited by 1
Converging Semidefinite Bounds for Global Unconstrained Polynomial Optimization
Jibetean, D., & Laurent, M. (2004)
Error analysis of approximation algorithm for standard bi-quadratic programmingPreprint
Ling, C., He, H., & Qi, L. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1501.02871
“However, it is wellknown that the problem of checking whether a symmetric matrix belongs to the cone of copositive matrices or not is co-NP-complete [15].”
BackgroundInteger matrices that are not copositive have certificates of less than quadratic complexityPreprint
Hirscher, T. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1306.3867
“is a BFS to (11) and (4) is also satisfied.”
BackgroundInfluentialGeneration of polynomial inequalities as invariants
Zakowski, Y. (2013) · HAL
Relaxing Global Decrescence Conditions in Lyapunov Theorems for Hybrid Systems
Shia, V., Matthew, R. P., Vasudevan, R., & Bajcsy, R. (2014) · IFAC Proceedings Volumes · doi:10.3182/20140824-6-za-1003.01728
“Lyapunov conditions involving positive of functions are generally NP-hard to test [Murty and Kabadi, 1987].”
BackgroundLiu, B., Feng, G., & Guo, W. (2014) · IEICE Transactions on Communications · doi:10.1587/transcom.e97.b.1556
Computational complexity of robust control: A review of theoretical and algorithmic developments
Kim, K. K., & Braatz, R. D. (2013) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2013.6760900
Métodos de punto interior para optimización cuadrática convexa con matrices no definidas positivas
Fernández, G. P., Rosina Hing, C., Mariledy Rojas, C., & Denysde Medina, S. (2008) · Revista de Matemática Teoría y Aplicaciones · doi:10.15517/rmta.v15i1.284
“[9] Murty, Kabadi (1987) “Some NP-complete problems in quadratic and nonlinear programming”, Mathematical Programming 39.”
BackgroundInfluentialTHE VERTEX SEPARATOR PROBLEM AND EDGE-CONCAVE QUADRATIC PROGRAMMING
Hungerford, J. T. (2013)
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.