Title | **Efficiency improvement in an systems approach to polynomial optimization** |

Author(s) | Ivo Bleylevens, Bernard Hanzon, Ralf Peeters |

Type | Article in Journal |

Abstract | The problem of finding the global minimum of a so-called Minkowski-norm dominated polynomial can be approached by the matrix method of Stetter and Möller, which reformulates it as a large eigenvalue problem. A drawback of this approach is that the matrix involved is usually very large. However, all that is needed for modern iterative eigenproblem solvers is a routine which computes the action of the matrix on a given vector. This paper focuses on improving the efficiency of computing the action of the matrix on a vector. To avoid building the large matrix one can associate the system of first-order conditions with an n D system of difference equations. One way to compute the action of the matrix efficiently is by setting up a corresponding shortest path problem and solving it. It turns out that for large n the shortest path problem has a high computational complexity, and therefore some heuristic procedures are developed for arriving cheaply at suboptimal paths with acceptable performance. |

Keywords | Global polynomial optimization, Gröbner basis, Stetter–Möller matrix method, n D systems, Large eigenvalue problem |

ISSN | 0747-7171 |

URL |
http://www.sciencedirect.com/science/article/pii/S0747717106000630 |

Language | English |

Journal | Journal of Symbolic Computation |

Volume | 42 |

Number | 1–2 |

Pages | 30 - 53 |

Year | 2007 |

Note | Effective Methods in Algebraic Geometry (MEGA 2005) |

Edition | 0 |

Translation |
No |

Refereed |
No |