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 901–1,000 of 1,000
ON SEMIDEFINITE REPRESENTATIONS OF SETSPreprint
Netzer, T. (2009) · arXiv (Cornell University)
der Doktorw, E. (2005)
Optimal mistuning - An analysis of flutter boundaries in turbomachines
Shapiro, B., & Shapiro, B. (1997) · AIAA/ASME/SAE/ASEE Joint Propulsion Conference and Exhibit · doi:10.2514/6.1997-2657
On the Second Order Optimality Conditions for Optimization Problems with Inequality Constraints
Naffouti, M. (2013) · Open Journal of Optimization · doi:10.4236/ojop.2013.24014
“Second order optimality conditions for (P) are related to copositivity and are NP-hard [7].”
BackgroundComputing the stability number of a graph via semidefinite and linear programming
Vera, J. C., & Peña, J. (2005)
SOME PROBLEMS OF QUADRATIC RATIONAL DIFFERENCE EQUATIONS 1
Anisimova, A., & Bula, I. (2011)
Pursuits in Structured Non-Convex Matrix FactorizationsPreprint
Khanna, R., Tschannen, M., & Jaggi, M. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.04208
On LP-based approximation for copositive formulation of stable set problem
Tono, K. (2015) · JSIAM Letters · doi:10.14495/jsiaml.7.69
“In fact, determining whether a matrix is copositive is co-NP-complete [6].”
BackgroundComputing the distance between the linear matrix pencil and the completely positive cone
Fan, J., & Zhou, A. (2016) · Computational Optimization and Applications · doi:10.1007/s10589-016-9825-1
“As shown in [9,19], checking the membership in CP n is NP-hard, while checking the membership in COP n is co-NP-hard.”
BackgroundProduct design and product portfolio modeled integration and optimization
Smith, B. V. (2010) · Rutgers University Community Repository (Rutgers University) · doi:10.7282/t35x28p0
“Furthermore, the challenges encountered in determining the global solution of the MINLP problems are well documented in the literature (Murty and Kabadi 1987), (Pardalos and Schnitger 1988).”
BackgroundIntegrative and sustainable port hinterland intermodal development with green concerns
Gu, Y. (2014) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/61845
Mathematical Programs for Belief Propagation and ConsensusPreprint
Kim, K. K. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1501.04538
“However, checking if M i (cid:23) ∆ 0 is indeed NP-hard [15].”
On the Computational Complexity of Partitioning Weighted Points into a Grid of Quadrilaterals
Idelberger, A., & Liśkiewicz, M. (2014) · Canadian Conference on Computational Geometry
Second Order Optimality Conditions for Nonlinear Optimization
Murty, K. G. (2001) · Springer eBooks · doi:10.1007/0-306-48332-7_439
Self-citationDevelopement of a Pseudo-Gradient Augmented Heuristic Optimization Method
Chiam, T. W., & Bloebaum, C. (2004) · AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference (MAO) · doi:10.2514/6.2004-4388
Copositive Programming - a Survey
Bernoulli, J. (2010)
Deng, Z. (2013) · NCSU Libraries Repository (North Carolina State University Libraries)
NP-Hardness Results for Some Linear and
Problems, Q. (1994)
Optimality conditions in nonlinear programming
(2005) · Springer eBooks · doi:10.1007/bfb0000037
A novel conic section classifier with tractable geometric learning algorithms
Vemuri, B. C., Banerjee, A., & Kodipaka, S. (2009)
Multiple Operator Metaheuristics for Graph Partitioning Problems
Ma, F. (2016) · theses.fr (ABES) · doi:10.70675/b37ff544zd808z4fa8zbc26zb76155c913a9
Determining a heuristic for pick location design in an end user warehouse
Klein, N. (2014) · MOspace Institutional Repository (University of Missouri) · doi:10.32469/10355/44297
Essays on Electric Vehicle Adoption
Kuppusamy, S. (2014) · OhioLink ETD Center (Ohio Library and Information Network)
Some aspects of the optimization over the copositive and the completely positive cone
Witzel, J. (2013) · Hochschulschriftenserver der Universität Trier (Universität Trier) · doi:10.25353/ubtr-xxxx-c3c9-eb0a/
Polynomial Optimization Methods
vanEeghen, P. (2013) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands
Quadratic Programming with Discrete Variables
Nie, T. (2016) · NCSU Libraries Repository (North Carolina State University Libraries)
He, A., Chen, Z., Li, W., Li, X., Li, H., & Zhao, X. W. (2017) · doi:10.1145/3144789.3144815
Self-adaptive task scheduler for dynamic allocation in energy efficient data centers
Antal, M., Burnete, A., Pop, C. D., Cioara, T., Anghel, I. M., & Salomie, I. (2017) · IEEE International Conference on Intelligent Computer Communication and Processing (ICCP) · doi:10.1109/iccp.2017.8117059
“The resulting problem, known to be NP-hard, is solved using genetic algorithms.”
MethodTwo FPTAS for the Constrained Shortest Path Problem Applied to Hybrid Vehicle Routing
Schwan, C., & Strehler, M. (2017) · Springer eBooks · doi:10.1007/978-3-319-67168-0_18
Zafalon, G. F. D. (2014) · Digital Library of Theses and Dissertations (Universidade de São Paulo) · doi:10.11606/t.3.2014.tde-28082015-120515 · Cited by 2
Convexification of Neural GraphPreprint
Xiao, H. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1801.02901
PPD-IPM: Outer primal, inner primal-dual interior-point method for nonlinear programmingPreprint
Neuenhofen, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.01829
“Letting q be a nonconvex approximation could result in prohibitive cost for solving the subproblem [17] and is thus not considered a practical option.”
BackgroundAslan, Ö. (2017) · ERA: Education and Research Archive (University of Alberta) · doi:10.7939/r3bc3t87s
Contributions to nonlinear system modelling and controller synthesis via convex structures
Ruiz, R. R. (2018) · RiuNet (Universitat Politècnica de València) · doi:10.4995/thesis/10251/100848
Shirman, S., & Abarbanel, H. D. I. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.09838
A robust unscented transformation for uncertain moments
Kussaba, H. T. M., Ishihara, J. Y., & de Menezes, L. R. A. X. (2019) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2019.02.018
“It is known that this problem is NP-Hard in general [8], but despite this, it is possible to approximate a POP by convex optimization problems which are computationally feasible using Lasserre’s hierarchy of semidefinite programming relaxations [9, 10].”
MethodEvery Local Minimum is a Global Minimum of an Induced Model.Preprint
Kawaguchi, K., & Kaelbling, L. P. (2019) · arXiv (Cornell University)
Optimal resource allocation In base stations for mobile wireless communications
Zhong, Z. (2018) · Lancaster EPrints (Lancaster University) · doi:10.17635/lancaster/thesis/474
“While convex optimisation is now a somewhat mature technique, it has been proven in [61] that a non-linear programme with a non-convex quadratic function is NP-hard even when the only constraints present are non-negativity constraints.”
BackgroundKomeiji, H., Kim, S., & Yamashita, M. (2019) · Computational Optimization and Applications · doi:10.1007/s10589-019-00118-5
Click Maximization in Online Social Networks Using Optimal Choice of Targeted Interests.Preprint
Hudson, N., Khamfroush, H., Harrison, B. E., & Craig, A. W. (2019) · arXiv (Cornell University)
Optimization Strategies for Myopic and Forecasted Divergence-Based Sensor Tasking Objectives
Gualdoni, M. J., & DeMars, K. J. (2020) · AIAA SciTech Forum · doi:10.2514/6.2020-0720
Low Rank Saddle Free Newton: Algorithm and AnalysisPreprint
O’Leary-Roseberry, T., Alger, N., & Ghattas, O. N. (2020) · arXiv (Cornell University)
A sufficient conditions for global quadratic optimization
Naffouti, M., & Baccari, A. (2020) · Croatian Operational Research Review · doi:10.17535/crorr.2020.0002
“This problem is an NP–hard global optimization problem, see [7, 9, 10].”
BackgroundOn the facet defining inequalities of the mixed-integer bilinear covering set
Rahman, H., & Mahajan, A. (2020) · Mathematical Methods of Operations Research · doi:10.1007/s00186-020-00723-9
Complexity Aspects of Fundamental Questions in Polynomial OptimizationPreprint
Zhang, J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.12170
“3) ≥4 NP-hard NP-hard NP-hard [75] Table 1.”
BackgroundInfluentialDetermining Asymptotic Stability and Robustness of Networked Systems
August, E. (2020) · Systems · doi:10.3390/systems8040039
“Testing for non-negativity is NP-hard [22].”
Efficient Higher-Order Optimization for Machine Learning
Bullins, B. (2019)
Finding Critical and Gradient-Flat Points of Deep Neural Network Loss Functions
Frye, C. G. (2020) · DigitalCommons-IMSA (Illinois Mathematics and Science Academy)
Nguyen, H.-Q., & Sheu, R.-L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.10299
Maximizing perturbation radii for robust convex quadratically constrained quadratic programs
Yu, P., Gao, R., & Xing, W. (2021) · European Journal of Operational Research · doi:10.1016/j.ejor.2020.12.032
Grasp Stability Analysis with Passive ReactionsPreprint
Haas-Heger, M. (2021) · arXiv (Cornell University) · doi:10.7916/d8-0kbt-ze07 · Cited by 2
Heat Transport in Reduced Order Convection Models
Olson, M. (2020) · Deep Blue (University of Michigan)
Phase Retrieval in Acoustical Signal Processing
Yatabe, K. (2021) · IEICE ESS FUNDAMENTALS REVIEW · doi:10.1587/essfr.15.1_25
Wang, J.-K. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.12923
Understanding Minimax Optimization in Modern Machine Learning
Zhang, G. (2021) · UWSpace (University of Waterloo) · Cited by 4
Sparsity and structure exploiting diagonally dominant relaxation of the OPF problem
Mubaslat, L. (2020) · eScholarship@McGill (McGill) · doi:10.82308/11265
AM/GM-based optimization : gheometry and generalizations
Naumann, H. (2021) · Publication Server of Goethe University Frankfurt am Main (Goethe University Frankfurt) · doi:10.21248/gups.64529
Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points
Eftekhari, A. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3139213 · Cited by 1
“Such peculiarities are not uncommon in nonconvex optimization [41].”
BackgroundThe problems of non-convex quadratic programming related to phased antenna arrays optimization
Tyunin, N. N. (2021) · Diskretnyi analiz i issledovanie operatsii · doi:10.33048/daio.2021.28.694
Polinomiális optimalizálási feladatok és relaxációik
Papp, D. (2021) · Alkalmazott Matematikai Lapok · doi:10.37070/aml.2021.38.1.07
Quadratic Programming with Bound Constraints
Angelis, P. L. D., & Toraldo, G. (2001) · Springer eBooks · doi:10.1007/0-306-48332-7_409
(2016) · Auerbach Publications eBooks · doi:10.1201/b19572-13
Johnson, C. R., Smith, R. L., & Tsatsomeros, M. J. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108778619.001
Johnson, C. R., Smith, R. L., & Tsatsomeros, M. J. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108778619.002
Johnson, C. R., Smith, R. L., & Tsatsomeros, M. J. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108778619.004
Johnson, C. R., Smith, R. L., & Tsatsomeros, M. J. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108778619.007
Johnson, C. R., Smith, R. L., & Tsatsomeros, M. J. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108778619.006
Ye, Y. (1997) · Wiley eBooks · doi:10.1002/9781118032701.biblio
Johnson, C. R., Smith, R. L., & Tsatsomeros, M. J. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108778619.005
Johnson, C. R., Smith, R. L., & Tsatsomeros, M. J. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108778619.003
Topics in nonlinear conic optimization and applications
Mito, L. M. (2022) · Digital Library of Theses and Dissertations (Universidade de São Paulo) · doi:10.11606/t.45.2022.tde-30032022-212754
Understanding topological phases of matter with statistical methods
Mertz, T. (2022) · Publication Server of Goethe University Frankfurt am Main (Goethe University Frankfurt) · doi:10.21248/gups.67179 · Cited by 1
Saat, S., Nguang, S. K., & Nasiri, A. (2017) · Elsevier eBooks · doi:10.1016/b978-0-08-101901-6.00001-3
Johnson, C. R., Smith, R. L., & Tsatsomeros, M. J. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108778619.008
Hogben, L., & Shaked-Monderer, N. (2019) · Electronic Journal of Linear Algebra · doi:10.13001/1081-3810.3747
“Since P is positive semidefinite, so is P [2, 3, 4, 5].”
BackgroundGass, S. I., & Harris, C. M. (1996) · Springer eBooks · doi:10.1007/978-1-4613-0459-3_17
Murty, K. G. (2001) · Springer eBooks · doi:10.1007/1-4020-0611-x_838
Self-citationYajima, Y. (2001) · Springer eBooks · doi:10.1007/0-306-48332-7_407
First-Order Algorithms for Nonlinear Structured Optimization
Zhang, M. (2023) · Louisiana State University · doi:10.31390/gradschool_dissertations.6098
HOUDINI: Escaping from Moderately Constrained Saddles
Avdiukhin, D., & Yaroslavtsev, G. (2023) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2023/383
Zhang, J. (2023) · International Conference on Electronics and Communication, Network and Computer Technology (ECNCT) · doi:10.1109/ecnct59757.2023.10281038
“…problem (22) can be reformulated as where the auxiliary function , ˆ ( ) k j F ρ For simplicity of the objective function ˆ f , we make the following definitions: where Ψ and ξ satisfies [ ] Observe that problem (26) is a 0-1 QP problem with linear constraints, which is proved to be NP-hard [6].”
BackgroundModeling, Estimation, and Feedback Techniques in Type 2 Diabetes
Ahdab, M. A. (2023) · VBN Forskningsportal (Aalborg Universitet) · doi:10.54337/aau614554303
Static Output Feedback for a Certain Class of Systems of Order Four
August, E., Piccini, J., & Papachristodoulou, A. (2024) · European Control Conference (ECC) · doi:10.23919/ecc64448.2024.10590890
“However, finding matrices K and P , where P ≻ 0 , such that the inequality given by (3) holds, requires to solve a so-called bilinear matrix inequality, which is known to be NP-hard to solve [15], [16], [17].”
BackgroundA new primal-dual hybrid gradient scheme for solving minimax problems with nonlinear term
Wu, R., & Liu, Z. (2024) · Applied Numerical Mathematics · doi:10.1016/j.apnum.2024.12.010
Tang, J., Sheng, Z., & Li, X. (2025) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2025.116716
On Polynomial Stochastic Barrier Functions: Bernstein Versus Sum-of-Squares
Amorese, P., & Lahijanian, M. (2025) · IEEE Control Systems Letters · doi:10.1109/lcsys.2025.3580356
“However, bounding an arbitrary nonlinear, potentially non-convex function over a set is NP-hard [6], even for polynomials.”
A Simplex Algorithm for the Local Minimization of a Box-Constrained Concave Quadratic Program
Bentobache, M., Telli, M., & Mokhtari, A. (2024) · International Conference of the African Federation of Operational Research Societies (AFROS) · doi:10.1109/afros62115.2024.11037212 · Cited by 1
Wang, C., & Zhao, J. (2025) · Acta Applicandae Mathematicae · doi:10.1007/s10440-025-00739-5
“However, it is indicated in [8, 13] that it is NP-hard to judge the nonnegativity of a given polynomial (1) if the degree of such a polynomial is larger than or equal to 4.”
Nishijima, M., Poirion, P., & Takeda, A. (2026) · Journal of Global Optimization · doi:10.1007/s10898-026-01623-8
“If we apply the subgradient algorithm in [45, Equation (3.2.24)] to the convex semi-infinite programming problem directly, we have to solve the subproblem exactly to find a constraint that attains the maximal violation.”
InfluentialMizohata–Takeuchi inequalities for orthonormal systems
Bennett, J. M., Bez, N., Gutiérrez, S., Nakamura, S., & Oliveira, I. (2026) · Journal of the London Mathematical Society · doi:10.1112/jlms.70666
“𝑗 supp(ˆ𝑢 𝑗,0 ).”
Dong, H. (2011) · doi:10.17077/etd.kzq65y36
“Generally, even testing whether a matrix is in C∗ is co-NP-complete [58].”
BackgroundHollender, A. (2021) · Oxford University Research Archive (ORA) (University of Oxford) · doi:10.5287/ora-2aa4nv5r0
Ionescu, A. (2025) · Annals of the Academy of Romanian Scientists Series on Mathematics and Its Application · doi:10.56082/annalsarscimath.2025.3.245
“More details on this point can be found in [12].”
Why Machine Learning Needs Theoretical Guidance To Support Future Theory Building
Xu, H., Zhang, N., & Wang, M. (2025) · MIS Quarterly · doi:10.25300/misq/2025/18900
Nagy, P. T. (2026) · Nonlinear Dynamics · doi:10.1007/s11071-025-12123-x
“Unfortunately, verifying the non-negativity of a polynomial is generally NP-hard [1].”
Positive definiteness of symmetric tensors with zero, plus or minus one entries
Ye, L., & Song, Y. (2026) · Numerical Algebra Control and Optimization · doi:10.3934/naco.2026013
Heterogeneous Server Deployment with Task Classification in Mobile Edge Computing
Zhang, Y., Weng, J., Wang, W., Li, H., & Wei, M. (2025) · Globecom · doi:10.1109/globecom59602.2025.11432023
“Since general MINLP are NP-hard problem [12], the theorem holds.”
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.