Inverse Polynomial Optimization

We consider the inverse optimization problem associated with the polynomial program $f^{*}=\min \{f(bx):bx\in K\}$ and a given current feasible solution $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 the 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 $\parallel f-\tilde{f}\parallel$ (which can be the l 1, l 2 or l ∞‐norm of the coefficients) over all polynomials with such properties. Computing $\widetilde{f_{\text{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 $\tilde{f}$ takes a simple and explicit canonical form. Some variations are also discussed.