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 301–400 of 1,000
An effective iterated tabu search for the maximum bisection problem
Ma, F., Hao, J., & Wang, Y. (2016) · Computers & Operations Research · doi:10.1016/j.cor.2016.12.012 · Cited by 26
“Max-bisection is a classical NP-hard combinatorial optimization problem and cannot be solved exactly in polynomial time unless P = NP [31].”
BackgroundLin, Y., Zhang, R., Yang, L., Li, C., & Hanzo, L. (2019) · IEEE Vehicular Technology Magazine · doi:10.1109/mvt.2019.2903741 · Cited by 26
“In general, this is a discontinuous, nondifferentiable, and highly nonlinear NP-complete problem and may have numerous local optima [12].”
BackgroundGlobal Stability of Fluid Flows Despite Transient Growth of Energy
Fuentes, F., Goluskin, D., & Chernyshenko, S. I. (2022) · Physical Review Letters · doi:10.1103/physrevlett.128.204502 · Cited by 26
“Verifying that a polynomial is nonnegative is computationally intractable (NP-hard) in general [31].”
BackgroundInfluentialConvergent Infeasible Interior-Point Trust-Region Methods for Constrained Minimization
Tseng, P. (2002) · SIAM Journal on Optimization · doi:10.1137/s1052623499357945 · Cited by 26
“2 In fact, for quadratic f with rational coefficients and g(x) = −x, it is NP-complete to decide whether the origin satisfies the strong 2nd-order necessary condition [23].”
BackgroundMultiple Objectives Satisficing Under Uncertainty
Lam, S., Ng, T. S., Sim, M., & Song, J.-H. (2013) · Operations Research · doi:10.1287/opre.1120.1132 · Cited by 30
“Unfortunately, for any ã ∈ A, b ∈ < the problem inf P∈F EP ( min i∈N {ãi, b} ) (4) is generally NP -hard, as in the case when the family of distributions F is given by F(µ,Σ,W); see Murty and Kabadi (1987).”
BackgroundA deterministic annealing algorithm for approximating a solution of the min-bisection problem
Dang, C., Ma, W., & Liang, J. (2008) · Neural Networks · doi:10.1016/j.neunet.2008.09.008 · Cited by 26
Algebraic Relaxations and Hardness Results in Polynomial Optimization and Lyapunov AnalysisPreprint
Ahmadi, A. A. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1201.2892 · Cited by 26
“, gradient descent) can find a global minimum—a task that is in general NP-hard in the absence of convexity [124], [109].”
BackgroundResultInfluentialContinuous quadratic programming formulations of optimization problems on graphs
Hager, W. W., & Hungerford, J. T. (2014) · European Journal of Operational Research · doi:10.1016/j.ejor.2014.05.042 · Cited by 25
“The edge separator problem is NP-hard (Fukuyama, 2006).”
BackgroundInfluentialThe copositive completion problem
Hogben, L., Johnson, C. R., & Reams, R. (2005) · Linear Algebra and its Applications · doi:10.1016/j.laa.2005.06.019 · Cited by 25
“Checking a given matrix may be carried out de(cid:12)nitively [8], [9], [10], [11] but is generally computationally time-consuming.”
The Boosted DC Algorithm for Linearly Constrained DC Programming
Artacho, F. J. A., Campoy, R., & Vuong, P. T. (2022) · Set-Valued and Variational Analysis · doi:10.1007/s11228-022-00656-x · Cited by 25
“Both problems are known to be NP-hard [20], and the first was already heuristically investigated in [7] using DCA.”
InfluentialA Study of Piecewise Linear-Quadratic Programs
Cui, Y., Chang, T., Hong, M., & Pang, J. (2020) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-020-01716-8 · Cited by 25
Bomze, I. M. (2015) · SIAM Journal on Optimization · doi:10.1137/140987997 · Cited by 25
“Contrasting to positivesemidefiniteness, checking copositivity is NP-hard, see [22, 37].”
BackgroundEnergy-Efficient On-Demand Resource Provisioning in Cloud Radio Access Networks
Liu, Q., Han, T., & Ansari, N. (2019) · IEEE Transactions on Green Communications and Networking · doi:10.1109/tgcn.2019.2926287 · Cited by 26
“The non-convex objective function and integer variables make problem P1 a highly complex mixed integer non-linear programming problem, which lacks efficient solutions [24].”
BackgroundA branch and bound algorithm for bound constrained optimization problems without derivatives
Jansson, C., & Kn�ppel, O. (1995) · Journal of Global Optimization · doi:10.1007/bf01279453 · Cited by 25
A unified dissipativity approach for stability analysis of piecewise smooth systems
Samadi, B., & Rodrigues, L. (2011) · Automatica · doi:10.1016/j.automatica.2011.09.018 · Cited by 25
“Although verifying nonnegativity of a polynomial is an NP-hard problem (see Murty and Kabadi (1987)), the SOS condition can be formulated as a convex problem in polynomial coefficients (see Prajna et al. (2005)).”
BackgroundComplexity and algorithms for convex network optimization and other nonlinear problems
Hochbaum, D. S. (2005) · 4OR · doi:10.1007/s10288-005-0078-6 · Cited by 25
The impact of accelerating tools on the interval subdivision algorithm for global optimization
Csendes, T., & Pintér, J. D. (1993) · European Journal of Operational Research · doi:10.1016/0377-2217(93)90110-9 · Cited by 25
Canonical Dual Solutions for Fixed Cost Quadratic Programs
Gao, D. Y., Ruan, N., & Sherali, H. D. (2010) · Springer optimization and its applications · doi:10.1007/978-0-387-89496-6_7 · Cited by 24
Sum of Squares Certificates for Stability of Planar, Homogeneous, and Switched Systems
Ahmadi, A. A., & Parrilo, P. A. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2647253 · Cited by 24
“In fact, even deciding if a given polynomial V of degree four or larger satisfies (2) is NP-hard [17], [2, Prop.”
On the computation of C* certificates
Jarre, F., & Schmallowsky, K. (2008) · Journal of Global Optimization · doi:10.1007/s10898-008-9374-y · Cited by 24
“[ 11 ]), and likewise the problem of determining complete positivity of a matrix B is dicult.”
BackgroundSymmetric Tensor Approximation Hierarchies for the Completely Positive Cone
Dong, H. (2013) · SIAM Journal on Optimization · doi:10.1137/100813816 · Cited by 24
Active constraints, indefinite quadratic test problems, and complexity
Hager, W. W., Pardalos, P. M., Roussos, I. M., & Sahinoglou, H. (1991) · Journal of Optimization Theory and Applications · doi:10.1007/bf00940067 · Cited by 24
A note on the convergence of barrier algorithms to second-order necessary points
Gould, N. I. M., & Toint, P. L. (1999) · Mathematical Programming · doi:10.1007/s101070050066 · Cited by 24
“Indeed, even establishing that the strong second-order conditions are satisfied is, in general, an NP-hard problem (see Murty and Kabadi [16], and Vavasis [18]).”
BackgroundGuisewite, G. M. (1995) · Nonconvex optimization and its applications · doi:10.1007/978-1-4615-2025-2_11 · Cited by 24
Using copositivity for global optimality criteria in concave quadratic programming problems
Danninger, G., & Bomze, I. M. (1993) · Mathematical Programming · doi:10.1007/bf01585185 · Cited by 24
“solution is also NP-hard [ 14 ].”
BackgroundMethodInfluentialFinding the Sparsest Vectors in a Subspace: Theory, Algorithms, and ApplicationsPreprint
Qu, Q., Zhu, Z., Li, X., Tsakiris, M. C., Wright, J. N., & Vidal, R. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2001.06970 · Cited by 25
“However, for general nonconvex problems, even finding a local minimizer is NP-hard [3].”
BackgroundSolving Non-Convex Non-Differentiable Min-Max Games Using Proximal Gradient Method
Barazandeh, B., & Razaviyayn, M. (2020) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp40776.2020.9054474 · Cited by 23
“Unfortunately, finding/checking such Nash equilibria is hard in general [12] for non-convex objective functions.”
BackgroundGao, D. Y., Watson, L. T., Easterling, D. R., Thacker, W. I., & Billups, S. C. (2011) · Optimization methods & software · doi:10.1080/10556788.2011.641125 · Cited by 23
“…by Replacing the feasible set X b by its vertices the problem ( P b ) is reduced to the well-known integer programming problem Due to the nonconvexity of the quadratic function P ( x ) , quadratic minimization problems with either box or integer constraints are considered to be NP-hard [15,16].”
BackgroundDistributionally robust mixed integer linear programs: Persistency models with applications
Li, X., Natarajan, K., Teo, C., & Zheng, Z. (2013) · European Journal of Operational Research · doi:10.1016/j.ejor.2013.07.009 · Cited by 23
“The separation problem is difficult for Ω = +n since it is equivalent to testing if a matrix is copositive (see Murty and Kabadi [58]).”
BackgroundInfluentialCanonical duality approach for non-linear dynamical systems
Ruan, N., & Gao, D. Y. (2012) · IMA Journal of Applied Mathematics · doi:10.1093/imamat/hxs067 · Cited by 23
Event Popularity Prediction Using Influential Hashtags From Social Media
Chen, X., Zhou, X., Chan, J., Chen, L., Sellis, T., & Zhang, Y. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.3048428 · Cited by 23
“We will prove that the Optimal Seed Set Selection is an NP-complete problem by a two-step reduction from the classic NP-complete problem, Subset Sum problem [26].”
MethodNadeem, L., Amin, Y., Loo, J., Azam, M. A., & Chai, K. K. (2021) · IEEE Access · doi:10.1109/access.2021.3114629 · Cited by 26
“Therefore, finding a solution for such a problem is unfea-sible [55], [56].”
BackgroundDetecting all evolutionarily stable strategies
Bomze, I. M. (1992) · Journal of Optimization Theory and Applications · doi:10.1007/bf00941470 · Cited by 23
Liu, Z., Guan, Y. L., & Mow, W. H. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2684740 · Cited by 23
“It is noted that indefinite quadratic programming (QP) is NP-hard [23], even it has one negative eigenvalue only [24].”
BackgroundInfluentialA new technique for generating quadratic programming test problems
Calamai, P. H., Vicente, L. N., & Júdice, J. J. (1993) · Mathematical Programming · doi:10.1007/bf01582148 · Cited by 23
“References [7, 9, 12, 16 , 17, 19-21] provide a discussion of these issues.”
MethodLocal minima for indefinite quadratic knapsack problems
Vavasis, S. A. (1992) · Mathematical Programming · doi:10.1007/bf01586048 · Cited by 23
Conditional Gradient Method for Stochastic Submodular Maximization: Closing the GapPreprint
Mokhtari, A., Hassani, H., & Karbasi, A. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1711.01660 · Cited by 54
“However, it is well known that in general finding the global optimum of a non-convex optimization problem is NP-hard (Murty and Kabadi, 1987).”
BackgroundHong, M., Lee, J. D., & Razaviyayn, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.08941 · Cited by 24
“(13) It is worth mentioning that checking both of the above sufficient and necessary conditions can be done in polynomial time, but when there are inequality constraints, checking second-order conditions can be NP-hard; see [13].”
BackgroundLower Bounds for Smooth Nonconvex Finite-Sum OptimizationPreprint
Zhou, D., & Gu, Q. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.11224 · Cited by 23
“It is known that finding an (cid:15) -suboptimal solution in such nonconvex setting is NP-hard (Murty and Kabadi, 1987).”
Bounding extrema over global attractors using polynomial optimisation
Goluskin, D. (2020) · Nonlinearity · doi:10.1088/1361-6544/ab8f7b · Cited by 22
An Efficient Memetic Algorithm for theMax-Bisection Problem
Lin, G., & Zhu, W. (2013) · IEEE Transactions on Computers · doi:10.1109/tc.2013.7 · Cited by 22
“The max-bisection problem is known to be NP-hard [1].”
BackgroundInfluentialComputing Probabilistic Bounds on State Trajectories for Uncertain Systems
Shen, X., Ouyang, T., Zhang, Y., & Zhang, X. (2020) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2020.3019040 · Cited by 22
“Obviously, due to the probabilistic constraint, the program (1) is NP hard [21], [22].”
BackgroundBramburger, J. J., & Fantuzzi, G. (2023) · Journal of Nonlinear Science · doi:10.1007/s00332-023-09990-2 · Cited by 22
“Such inequalities are NP-hard to verify in general [53], but can be strengthened by requiring that any polynomial to be non-negative is a sum of squares (SOS).”
BackgroundInfluentialFactorization and cutting planes for completely positive matrices by copositive projection
Sponsel, J., & Dür, M. (2012) · Mathematical Programming · doi:10.1007/s10107-012-0601-4 · Cited by 22
“For the cones C or C∗, however, such a straightforward method is unlikely to exist in view of the NP-complexity results [18,32]: Being able to compute the projections onto C or C∗ would allow to check copositivity (resp.”
MethodAlternative SDP and SOCP approximations for polynomial optimization
Kuang, X., Ghaddar, B., Naoum‐Sawaya, J., & Zuluaga, L. (2018) · EURO Journal on Computational Optimization · doi:10.1007/s13675-018-0101-2 · Cited by 22
“In general, solving (PP-P) is NP-hard [24].”
On the complexity of finding a local minimizer of a quadratic function over a polytope
Ahmadi, A. A., & Zhang, J. (2022) · Mathematical Programming · doi:10.1007/s10107-021-01714-2 · Cited by 22
“To point out some of the subtle differences between these variations of the problem more specifically, we briefly review the reduction of Murty and Kabadi [10], which shows the NP-hardness of deciding if a given point is a local minimizer of a quadratic program.”
BackgroundInfluentialOptimization over Nonnegative and Convex Polynomials With and Without Semidefinite ProgrammingPreprint
Hall, G. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.06996 · Cited by 28
“In this section, we show that, unless P=NP, one has no hope of doing this in a tractable fashion as even the problem of testing if a given polynomial has these properties is NP-hard.”
BackgroundInfluentialAssessing Solution Quality of 3SAT on a Quantum Annealing Platform
Gabor, T., Zielinski, S., Feld, S., Roch, C., Seidel, C., Neukart, F., Galter, I., Mauerer, W., & Linnhoff-Popien, C. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-14082-3_3 · Cited by 21
Distributionally Robust Chance Constrained Geometric Optimization
Liu, J., Lisser, A., & Chen, Z. (2022) · Mathematics of Operations Research · doi:10.1287/moor.2021.1233 · Cited by 21
Proof-Carrying Cloud Computation: The Case of Convex Optimization
Xu, Z. H., Wang, C., Ren, K., Wang, L., & Zhang, B. (2014) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2014.2352457 · Cited by 21
The Computational Complexity of Duality
Friedland, S., & Lim, L. (2016) · SIAM Journal on Optimization · doi:10.1137/16m105887x · Cited by 21
“It is well-known that deciding mem for the cone of copositive matrices is NP-hard [11].”
BackgroundMapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem
Zhi-dong, Z. (2023) · Mathematics · doi:10.3390/math11010237 · Cited by 21
Genetic engineering via negative fitness:Evolutionary dynamics for global optimization
Bomze, I. M., & Stix, V. (1999) · Annals of Operations Research · doi:10.1023/a:1018935925761 · Cited by 30
“Of course, QPs like (1) ‐ even regarding the detection of local solutions ‐ are NP-hard, see [ 26 ] or [16].”
BackgroundStability of Polynomial Differential Equations: Complexity and Converse Lyapunov QuestionsPreprint
Ahmadi, A. A., & Parrilo, P. A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1308.6833 · Cited by 21
“(This is due to the fact that even the task of checking if a given quartic polynomial is nonnegative is NP-hard [50], [56]).”
Adaptive Sampling for Stochastic Risk-Averse LearningPreprint
Curi, S., Levy, K. Y., Jegelka, S., & Krause, A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.12511 · Cited by 58
“The non-convex case is more challenging as solving a non-convex optimization problem is in general NP-hard (Murty & Kabadi, 1987).”
BackgroundStability analysis of power systems using network decomposition and local gain analysis
Anghel, M., Anderson, J., & Papachristodoulou, A. (2013) · IREP Symposium on Bulk Power System Dynamics and Control (IREP) · doi:10.1109/irep.2013.6629365 · Cited by 20
“This is a serious limitation, which renders the proposed algorithm impractical in its current formulation, as many systems of interest are of significantly higher dimension.”
BackgroundA new rectangle branch-and-reduce approach for solving nonconvex quadratic programming problems
Gao, Y., Xue, H., & Shen, P. (2004) · Applied Mathematics and Computation · doi:10.1016/j.amc.2004.10.024 · Cited by 20
Sum-of-squares chordal decomposition of polynomial matrix inequalities
Zheng, Y., & Fantuzzi, G. (2021) · Mathematical Programming · doi:10.1007/s10107-021-01728-w · Cited by 20
“Verifying polynomial matrix inequalities is generally an NP-hard problem [29], which makes (1.”
BackgroundOn the Identification of Local Minimizers in Inertia-Controlling Methods for Quadratic Programming
Forsgren, A. L., Gill, P. E., & Murray, W. (1991) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0612057 · Cited by 20
“The difficulty arises because the verification of such a point as a local minimizer of (1.1) is an NP-hard problem—see Murty and Kabadi [12] and Pardalos and Schnitger [13].”
BackgroundInfluentialDepth-first simplicial partition for copositivity detection, with an application to MaxClique
Žilinskas, J., & Dür, M. (2011) · Optimization methods & software · doi:10.1080/10556788.2010.544310 · Cited by 20
“More precisely, checking whether a given matrix is copositive is a co-NP-complete problem 22 .”
BackgroundGlobal Escape Strategies for Maximizing Quadratic Forms over a Simplex
Bomze, I. M. (1997) · Journal of Global Optimization · doi:10.1023/a:1008297330705 · Cited by 20
“Of course, quadratic optimization problems like (1.1) ‐ even the detection of their local solutions ‐ are NP-hard [11], [ 12 ].”
BackgroundInfluentialUncertain Context: Uncertainty Quantification in Machine Learning
Jalaian, B. A., Lee, M., & Russell, S. (2019) · AI Magazine · doi:10.1609/aimag.v40i4.4812 · Cited by 19
“Two, the feasible set, when given a generic function space without any structure, is mathematically impossible to fully optimize over (Murty and Kabadi 1987).”
BackgroundLiquid Hopfield model: Retrieval and localization in multicomponent liquid mixtures
Teixeira, R. B., Carugno, G., Neri, I., & Sartori, P. (2024) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2320504121 · Cited by 19
“If J ij has negative eigenvalues, then the zero temperature minimisation problem is an NP-hard problem [37– 39], which implies a rugged low-temperature free-energy landscape akin to a spin glass phase [40, 41].”
Luenberger, D. G., & Ye, Y. (2015) · International series in management science/operations research/International series in operations research & management science · doi:10.1007/978-3-319-18842-3_6 · Cited by 19
A General Regularized Continuous Formulation for the Maximum Clique Problem
Hungerford, J. T., & Rinaldi, F. (2019) · Mathematics of Operations Research · doi:10.1287/moor.2018.0954 · Cited by 19
“In general, verifiying whether a first-order point of a quadratic program is even locally optimal is an NPhard problem [16, 17].”
BackgroundHong, M., Razaviyayn, M., & Lee, J. D. (2018) · Cited by 19
Lakshmi, M. V., Fantuzzi, G., Fernández-Caballero, J. D., Hwang, Y., & Chernyshenko, S. I. (2020) · SIAM Journal on Applied Dynamical Systems · doi:10.1137/19m1267647 · Cited by 19
“Numerical solution of this problem to global optimality is difficult because polynomial inequalities are NP–hard except for a few special cases, such as univariate or quadratic polynomials [48].”
BackgroundCoordinate descent algorithms for phase retrieval
Zeng, W., & So, H. C. (2019) · Signal Processing · doi:10.1016/j.sigpro.2019.107418 · Cited by 20
On the difficulty of deciding asymptotic stability of cubic homogeneous vector fields
Ahmadi, A. A. (2012) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2012.6315687 · Cited by 19
“form q is positive definite if q(x) > 0 for all x 6= 0 in Rn. (Note that forms necessarily vanish at the origin.) It is well-known that deciding nonnegativity of quartic forms is NP-hard; see e.g. [33] and [34]. For reasons that will become clear shortly, we are interested instead in showing hardness of deciding pos…”
Backgroundℒ 2 -gain analysis for switched systems with a state-dependent switching signal
Soodavi, M., Ghaisari, J., & Sheikholeslam, F. (2011) · IET Control Theory and Applications · doi:10.1049/iet-cta.2010.0421 · Cited by 18
Arima, N., Kim, S., Kojima, M., & Toh, K.-C. (2018) · Cited by 18
Biswas, S., Dey, S., & Shirazinia, A. (2019) · IEEE Transactions on Cognitive Communications and Networking · doi:10.1109/tccn.2019.2908860 · Cited by 18
“It is well known that (see [42], [43]) determining of a global solution of the non-convex MINLP problem is NP-hard.”
BackgroundSrikantha, P., & Kundur, D. (2019) · IEEE Signal Processing Magazine · doi:10.1109/msp.2018.2877001 · Cited by 19
“If the feasible set is not convex, then solving the associated optimization problem will be NP-hard [10].”
BackgroundImproved Sample Complexity for Stochastic Compositional Variance Reduced Gradient
Lin, T., Fan, C., Wang, M., & Jordan, M. I. (2020) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc45564.2020.9147515 · Cited by 18
“In general, finding such global optimal solution is NPhard [5] but standard for convex optimization.”
Scaling of symmetric matrices by positive diagonal congruence
Johnson, C. R., & Reams, R. (2008) · Linear and Multilinear Algebra · doi:10.1080/03081080600872327 · Cited by 18
“Since testing whether a matrix is copositive is NP-complete [28], we do not expect that deciding in general whether a matrix is scalable would be any easier.”
BackgroundScheduling parallel CNC machines with time/cost trade-off considerations
Gürel, S., & Aktürk, M. S. (2005) · Computers & Operations Research · doi:10.1016/j.cor.2005.10.018 · Cited by 18
“Although the complexity of the problem is open, this lemma supports the difficulty of the problem since Murty and Kabadi [15] states that, in general, computing a global minimum in a non-convex NLP is an NP-hard problem.”
BackgroundPreserving Privacy of AC Optimal Power Flow Models in Multi-Party Electric Grids
Wu, D., Lesieutre, B. C., Ramanathan, P., & Kakunoori, B. (2016) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2016.2544179 · Cited by 18
“Equation (26) is a sixth-order multivariable polynomial, it is generically non-convex, hence solving Equation (26) is NPhard [21], [22] even without the global optimality requirement.”
BackgroundFirst-Order Methods for Fast Feasibility Pursuit of Non-convex QCQPs
Konar, A., & Sidiropoulos, N. D. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2736516 · Cited by 19
“While it is NP–hard in general to establish convergence to a local minimizer of a non-convex cost function [24], in the special case where F (x) possesses the strict saddle property5 and X = R , it has been shown [45] that GD with a constant step-size < 1/L converges almost surely to a local minimizer.”
BackgroundMethodAssimilation of Biophysical Neuronal Dynamics in Neuromorphic VLSI
Wang, J., Breen, D., Akinin, A., Broccard, F. D., Abarbanel, H. D. I., & Cauwenberghs, G. (2017) · IEEE Transactions on Biomedical Circuits and Systems · doi:10.1109/tbcas.2017.2776198 · Cited by 18
“finding the global minimum for a nonlinear objective functions such as A(X) is known, in general, to be NP-complete [27].”
BackgroundInfluentialAnalytical expressions of copositivity for fourth-order symmetric tensors
Song, Y., & Qi, L. (2020) · Analysis and Applications · doi:10.1142/s0219530520500049 · Cited by 18
Note on combinatorial optimization with max-linear objective functions
Chung, S., Hamacher, H. W., Maffioli, F., & Murty, K. G. (1993) · Discrete Applied Mathematics · doi:10.1016/0166-218x(93)90043-n · Cited by 18
Self-citationAn optimality criterion for global quadratic optimization
Neumaier, A. (1992) · Journal of Global Optimization · doi:10.1007/bf00122055 · Cited by 18
“This shows that global quadratic optimization is a computationally hard problem (see also Murty & Kabadi [ 4 ]).”
BackgroundAlerci, A. L., Vagnoni, E., & Paolone, M. (2023) · Renewable Energy · doi:10.1016/j.renene.2023.119341 · Cited by 17
“To treat such non-linear optimization problems described by polynomials several non-linear programming (NLP) methods exist [36], considering also integer variables in the case of mixed-integer non-linear programming (MINLP) methods [37] to be implemented for use in a branch-and-bound framework, or…”
MethodReward-Oriented Task Offloading in Energy Harvesting Collaborative Edge Computing Systems
Ni, Z., Chen, H., Gao, B., Lin, K., Wu, L., & Yu, J. (2024) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2024.3443868 · Cited by 17
“Similarly, if there are no integer variables, MINLP can be also reduced to the non-linear programming (NLP) which is known to be NP-hard [31].”
BackgroundTrajectory enclosures for nonlinear systems with uncertain initial conditions and parameters
August, E., Lu, J., & Koeppl, H. (2012) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2012.6314741 · Cited by 17
Analytical solutions to general anti-plane shear problems in finite elasticity
Gao, D. Y. (2015) · Continuum Mechanics and Thermodynamics · doi:10.1007/s00161-015-0412-y · Cited by 17
“Due to the lacking of global optimality condition, most of nonconvex optimization problems are considered to be NP-hard in nonconvex optimization and computer science [30, 55].”
BackgroundSemidefinite Relaxations for Integer Programming
Rendl, F. (2009) · Springer eBooks · doi:10.1007/978-3-540-68279-0_18 · Cited by 17
“certificate, given e.g., through the Cholesky decompositio n of X, it is NP-hard to decide whether X / ∈ C , see [ 59 ].”
BackgroundMareček, J., & Takáč, M. (2017) · Optimization methods & software · doi:10.1080/10556788.2017.1288729 · Cited by 24
“Indeed, in generic non-convex quadratic programming, the test whether a stationary point is a local optimum [49] is NP-Hard.”
BackgroundTesting copositivity via mixed–integer linear programming
Anstreicher, K. M. (2020) · Linear Algebra and its Applications · doi:10.1016/j.laa.2020.09.002 · Cited by 17
Tian, Y. (2012) · Linear Algebra and its Applications · doi:10.1016/j.laa.2012.03.021 · Cited by 20
Global Continuous Optimization with Error Bound and Fast Convergence
Kawaguchi, K., Maruyama, Y., & Zheng, X. (2016) · Journal of Artificial Intelligence Research · doi:10.1613/jair.4742 · Cited by 23
“Note that the optimization problems discussed in this paper are practically relevant yet inherently difficult to scale up for higher dimensions, i.e., NP-complete (Murty & Kabadi, 1987).”
BackgroundRelative Robust Portfolio Optimization with benchmark regret
Simões, G., McDonald, M., Williams, S., Fenn, D. J., & Hauser, R. (2018) · Quantitative Finance · doi:10.1080/14697688.2018.1453940 · Cited by 17
“Unfortunately, this is not the case in general— in fact for some (cid:7) the problem of deciding whether a matrix A is in FC + ((cid:7)) is co-NP-complete, see Murty and Kabadi (1987).”
BackgroundConstruction of quasipotentials for stochastic dynamical systems: An optimization approach
Brackston, R. D., Wynn, A., & Stumpf, M. P. H. (2018) · Physical review. E · doi:10.1103/physreve.98.022136 · Cited by 17
“Finding a Lyapunov function for nonlinear dynamical systems is generally a difficult problem[27, 32], and is known to be NP-hard in the case where U is a polynomial [33]: i.e. given a possible function U , even checking that it satisfies the requirements may be very computationally expensive.”
BackgroundA geometric approach of gradient descent algorithms in linear neural networks
Chitour, Y., Laboratoire des Signaux et Systèmes, C., Liao, Z., & Couillet, R. (2022) · Mathematical Control and Related Fields · doi:10.3934/mcrf.2022021 · Cited by 17
“In general, finding a global minimum of a generic non-convex function is an NP-complete problem [24] which is the case for neural networks as shown in [5] on a very simple network.”
BackgroundAn Algorithm for Global Minimization of Linearly Constrained Quadratic Functions*
Barrientos, O., & Corrêa, R. (2000) · Journal of Global Optimization · doi:10.1023/a:1008306625093 · Cited by 17
Humes, C., Ou, J., & Kumar, P. R. (1997) · Mathematics of Operations Research · doi:10.1287/moor.22.4.921 · Cited by 17
“We note that copositive matrices have been extensively studied (see Cottle, Habetler and Lemke (1970), Murty and Kabadi (1987), and Andersson, Chang and Elfving (1993)), e.g., in linear complementarity theory.”
BackgroundInfluentialGlobal and Local Quadratic Minimization
Best, M. J., & Ding, B. (1997) · Journal of Global Optimization · doi:10.1023/a:1008278114178 · Cited by 17
Scheduling Queueing Networks: Stability, Performance Analysis and Design
Kumar, P. R. (1995) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4757-2418-9_2 · Cited by 17
Optimization over Polynomials: Selected Topics
Laurent, M., Jang, S. Y., Kim, Y. R., Lee, D.-W., & Yie, I. (2014) · Data Archiving and Networked Services (DANS) · Cited by 17
O’Leary-Roseberry, T., Alger, N., & Ghattas, O. N. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.06738 · Cited by 20
“Because of feature 3, finding global minimizers is computationally intractible (NP-hard), and instead one has to settle for local minima [4, 25].”
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.