Inverse Polynomial Optimization

• 成果类型: Article
• 署名作者: Lasserre, Jean B.
• 署名单位: Universite de Toulouse; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1120.0578
• 发表日期: 2013
• 页码: 418-436
• 关键词: nonnegative polynomials; relaxations; moments

摘要

We consider the inverse optimization problem associated with the polynomial program f* = min{f(x): x is an element of K} and a given current feasible solution y is an element of K. We provide a systematic numerical scheme to compute an inverse optimal solution. That is, we compute a polynomial (f) over tilde (which may be of the same degree as f, if desired) with the following properties: (a) y is a global minimizer of (f) over tilde on K with a Putinar's certificate with an a priori degree bound d fixed, and (b) (f) over tilde minimizes parallel to f - (f) over tilde parallel to (which can be the l(1), l(2) or l(infinity)-norm of the coefficients) over all polynomials with such properties. Computing (f) over tilde (d) reduces to solving a semidefinite program whose optimal value also provides a bound on how far f(y) is from the unknown optimal value f*. The size of the semidefinite program can be adapted to the available computational capabilities. Moreover, if one uses the l(1)-norm, then (f) over tilde takes a simple and explicit canonical form. Some variations are also discussed.