On the complexity of finding a local minimizer of a quadratic function over a polytope

• URL: http://arxiv.org/abs/2008.05558v5
• Date: Thu, 14 Sep 2023 01:22:30 GMT
• Title: On the complexity of finding a local minimizer of a quadratic function over a polytope
• Authors: Amir Ali Ahmadi, Jeffrey Zhang
• Abstract summary: We show that unless P=NP, there cannot be a Euclidean-time algorithm that finds a point within $cn$ of a local minimizer of an $n$ quadratic function over a polytope. Our proof technique also implies that the problem of deciding whether a quadratic function has a local minimizer over anunbounded polyhedron, and that of deciding if a quartic has a local minimizer are NP-hard.
• Score: 1.0048921884287543
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance $c^n$ (for any constant $c \ge 0$) of a local minimizer of an $n$-variate quadratic function over a polytope. This result (even with $c=0$) answers a question of Pardalos and Vavasis that appeared in 1992 on a list of seven open problems in complexity theory for numerical optimization. Our proof technique also implies that the problem of deciding whether a quadratic function has a local minimizer over an (unbounded) polyhedron, and that of deciding if a quartic polynomial has a local minimizer are NP-hard.

Related papers

• Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
  We revisit certain problems of pose estimation based on 3D--2D correspondences between features which may be points or lines. We show experimentally that the resulting solvers are numerically stable and fast.
  arXiv  Detail & Related papers  (2024-04-25T12:09:16Z)
• Approximate Integer Solution Counts over Linear Arithmetic Constraints [2.28438857884398]
  We propose a new framework to approximate the lattice counts inside a polytope with a new random-walk sampling method. Our algorithm could solve polytopes with dozens of dimensions, which significantly outperforms state-of-the-art counters.
  arXiv  Detail & Related papers  (2023-12-14T09:53:54Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [77.8485863487028]
  In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization. In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
  arXiv  Detail & Related papers  (2023-01-10T20:43:29Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• On the energy landscape of symmetric quantum signal processing [1.5301252700705212]
  We prove that one particular global (called the global minimum) solution belongs to a $0$ on which the cost function is on which the cost function is a global. We provide an explanation of a partial explanation of optimization algorithms.
  arXiv  Detail & Related papers  (2021-10-11T04:16:48Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• Complexity Aspects of Fundamental Questions in Polynomial Optimization [3.42658286826597]
  We show that unless P=NP, there cannot be a SDP that finds a point within Euclidean distance of a local minimum of a quadratic program. We also show that testing whether aally constrained program with a finite optimal value has an optimal solution is NP-hard. In our final chapter, we present an characterization of coercives that lends itself to a hierarchy of SDPs.
  arXiv  Detail & Related papers  (2020-08-27T14:58:02Z)
• Complexity aspects of local minima and related notions [3.42658286826597]
  We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariates. We show that it is strongly NP-hard to decide if a cubic has a critical point. We briefly present a potential application of finding local minima cubics to the design of a third-order Newton method.
  arXiv  Detail & Related papers  (2020-08-14T00:50:13Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  We show that the average-case teaching complexity is $Theta(d)$, which is in sharp contrast to the worst-case teaching complexity of $Theta(n)$. Our insights allow us to establish a tight bound on the average-case complexity for $phi$-separable dichotomies.
  arXiv  Detail & Related papers  (2020-06-25T19:59:24Z)
• Learning sums of powers of low-degree polynomials in the non-degenerate case [2.6109033135086777]
  We give a learning algorithm for an arithmetic circuit model from a lower bound for the same model, provided certain non-degeneracy conditions hold. Our algorithm is based on a scheme for obtaining a learning algorithm for an arithmetic circuit model from a lower bound for the same model.
  arXiv  Detail & Related papers  (2020-04-15T06:18:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.