Condition number based complexity estimate for computing local extrema

• Autores: Zhikun She, Zhiming Zheng
• Localización: Journal of computational and applied mathematics, ISSN 0377-0427, Vol. 230, Nº 1, 2009, págs. 233-242
• Idioma: inglés
• DOI: 10.1016/j.cam.2008.11.003
• Texto completo no disponible (Saber más ...)
• Resumen

  • In this paper, we present a new algorithm for computing local extrema by modifying and combining algorithms in symbolic and numerical computation. This new algorithm improves the classical steepest descent method that may not terminate, by combining a Sturm�s theorem based separation method and a sufficient condition on infeasibility. In addition, we incorporate a grid subdivision method into our algorithm to approximate all local extrema. The complexity of our algorithm is polynomial in a newly defined condition number, and singly exponential in the number of variables.