Some NP-complete problems in quadratic and nonlinear programming

By K. G. Murty, S. Kabadi. 1987

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, background): “Even further, finding (or testing) a local optimum is NP-hard in many cases [Murty and Kabadi, 1987].”
Irreducible elements of the copositive cone (2013, background): “Linear Algebra and its Applications 439 (2013) 1605–1626 Contents lists available at SciVerse ScienceDirect Linear Algebra and its Applications journal homepage: www.elsevier .com/locate/ laa Irreducible elements of the copositive cone Peter J.C. Dickinsona, Mirjam Dürb,∗, Luuk Gijbena, Roland Hilde”
Gradient Descent Converges to Minimizers (2016, background): “Keywords: Gradient descent, smooth optimization, saddle points, local minimum, dynamical systems.”
Vacuum stability conditions from copositivity criteria (2012, background): “In general, testing for copositivity is NP-hard [8].”
Almost Global Convergence to Global Minima for Gradient Descent in Deep Linear Networks (2018, background): “In general ﬁnding a global minimum of a generic non-convex function is an NP-complete problem [20] and it is unfortunately the case for neural networks as it was shown in [3] that even training a very simple network is indeed NP-complete.”
Algorithms and Software for Convex Mixed Integer Nonlinear Programs (2012, background): “…and Software for Convex Mixed Integer Nonlinear Programs Pierre Bonami Mustafa Kilinc Jeff Linderoth Technical Report #1664 October 2009 ha l-0 04 23 41 6, v er si on 2 - 15 O ct 2 00 9 ALGORITHMS AND SOFTWARE FOR CONVEX MIXED INTEGER NONLINEAR PROGRAMS PIERRE BONAMI∗, MUSTAFA KILINÇ† ,…”
Adjustable robust solutions of uncertain linear programs (2004, background): “But the latter problem is equivalent to the problem of checking copositivity, a problem known to be NP-hard (see, e.g., [15, 16 ]).”
A tutorial on sum of squares techniques for systems analysis (2005, background): “Nevertheless, checking nonnegativity of p(x) is an NP-hard problem when the degree of p(x) is at least 4 [28], whereas as argued in the previous paragraph, checking whether p(x) can be written as an SOS is computationally tractable — it can be formulated as a semidefinite program, which has worst-ca”
On Cones of Nonnegative Quadratic Functions (2003, unknown): “, testing whether it does not belong to the co-positive cone is NP-hard; see Murty and Kabadi [12].”
Sums of Squares, Moment Matrices and Optimization Over Polynomials (2009, background): “Testing whether a matrix is not copositive is an NP-complete problem [94].”