Inverse polynomial optimization

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