Optimizing \(n\)-variate \((n+k)\)-nomials for small \(k\)

DOI10.1016/j.tcs.2010.11.053zbMath1215.65111OpenAlexW1971367839WikidataQ107634185 ScholiaQ107634185MaRDI QIDQ633624

David C. Thompson, Philippe Pébay, J. Maurice Rojas

Publication date: 29 March 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.11.053

zbMATH Keywords

NP-completepolynomial time\(n\)-variate \((n+k)\) nomialapproximate condition numberoptimization sparse model

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonlinear programming (90C30) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Amoebas of genus at most one ⋮ Approximating Nonnegative Polynomials via Spectral Sparsification

Uses Software

• RAGlib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A closed-form solution to the minimum \(\Delta V_{\text{tot}}^{2}\) Lambert's problem
• Factoring bivariate sparse (lacunary) polynomials
• A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones
• Semidefinite programming relaxations for semialgebraic problems
• Counting real connected components of trinomial curve intersections and \(m\)-nomial hypersurfaces
• On solving univariate sparse polynomials in logarithmic time
• The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete.
• Testing sign conditions on a multivariate polynomial and applications
• Faster real feasibility via circuit discriminants
• Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields
• Complexity estimates depending on condition and round-off error
• On the Complexity of Numerical Analysis
• Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials
• Fast Multiple-Precision Evaluation of Elementary Functions
• Computation of π Using Arithmetic-Geometric Mean
• Fast Parallel Matrix Inversion Algorithms
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Asymptotic acceleration of solving multivariate polynomial systems of equations
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
• Symbolic-numeric sparse interpolation of multivariate polynomials
• Algorithms in real algebraic geometry
• Complexity of cylindrical decompositions of sub-Pfaffian