Jean B Lasserre
email: lasserre@laas.fr

INVERSE POLYNOMIAL OPTIMIZATION

Keywords: 1991 Mathematics Subject Classification. 90C26 47J07 65J22 49K30 90C22 Inverse optimization, positivity certificate, mathematical programming, global optimization, semidefinite programming

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

Introduction

Let P be the optimization problem f * = min {f (x) : x ∈ K }, where (1.1) K := {x ∈ R n : g j (x) ≥ 0, j = 1, . . . , m}, for some polynomials f, (g j ) ⊂ R[x]. This framework is rather general as it encompasses a large class of important optimization problems, including non convex and discrete optimization problems. Problem P is in general NP-hard and one is often satisfied with a local minimum which can be obtained by running some local minimization algorithm among those available in the literature. Typically in such algorithms, at a current iterate (i.e. some feasible solution y ∈ K), one checks whether some optimality conditions (e.g. the Karush-Kuhn-Tucker (KKT) conditions) are satisfied within some ǫ-tolerance. However, as already mentioned those conditions are only valid for a local minimum, and in fact, even only for a stationary point of the Lagrangian. Moreover, in many practical situations the criterion f to minimize is subject to modeling errors or is questionable. In such a situation, the practical meaning of a local (or global) minimum f * (and local (or global) minimizer) also becomes questionable. It could well be that the current solution y is in fact a global minimizer of an optimization problem P ′ with same feasible set as P but with a different criterion f . Therefore, if f is close enough to f , one might not be willing to spend an enormous computing time and effort to find the global (or even local) minimum f * because one might be already satisfied with the current iterate y as a global minimizer of P ′ .

Inverse Optimization is precisely concerned with the above issue of determining a criterion f as close to f as possible, and for which the current solution y is an optimal solution of P ′ with this new criterion f . Pioneering work in Control dates back to Freeman and Kokotovic [START_REF] Freeman | Inverse optimality in robust stabilization[END_REF] for optimal stabilization. Whereas it was known that every value function of an optimal stabilization problem is also a Lyapunov function for the closed-loop system, in [START_REF] Freeman | Inverse optimality in robust stabilization[END_REF] the authors show the converse, that is, every Lyapunov function for every stable closed-loop system is also a value function for a meaningful optimal stabilization problem. In optimization, pioneering works in this direction date back to Burton and Toint and [START_REF] Burton | On an instance of the inverse shortest path problem[END_REF] for shortest path problems, and Zhang and Liu [START_REF] Zhang | Calculating some inverse linear programming problems[END_REF][START_REF] Zhang | A further study on inverse linear programming problems[END_REF], Huang and Liu [START_REF] Huang | On the inverse problem of linear programming and its application to minimum weight perfect k-matching[END_REF], and Ahuja and Orlin and [START_REF] Ahuja | Inverse optimization[END_REF] for linear programs in the form min{c ′ x : Ax ≥ b; r ≤ x ≤ s} (and with the ℓ 1 -norm). For the latter, the inverse problem is again a linear program of the same form. Similar results also hold for inverse linear programs with the ℓ ∞ -norm as shown in Ahuja and Orlin [START_REF] Ahuja | Inverse optimization[END_REF] while Zhang et al. [START_REF] Zhang | A column generation method for inverse shortest path problems[END_REF] provide a column generation method for the inverse shortest path problem. In Heuberger [START_REF] Heuberger | Inverse combinatorial oprtimization: A survey on problems, methods and results[END_REF] the interested reader will find a nice survey on inverse optimization for linear programming and combinatorial optimization problems. For integer programming, Schaefer [START_REF] Schaefer | Inverse integer programming[END_REF] characterizes the feasible set of cost vectors c ∈ R n that are candidates for inverse optimality. It is the projection on R n of a (lifted) convex polytope obtained from the super-additive dual of integer programs. Unfortunately and as expected, the dimension of of the lifted polyhedron (before projection) is exponential in the input size of the problem. Finally, for linear programs Ahmed and Guan [START_REF] Ahmed | The inverse optimal value problem[END_REF] have considered the variant called inverse optimal value problem in which one is interested in finding a linear criterion c ∈ C ⊂ R n for which the optimal value is the closest to a desired specified value. Perhaps surprisingly, they proved that such a problem is NP-hard.

As the reader may immediately guess, in inverse optimization the main difficulty lies in having a tractable characterization of global optimality for a given current point y ∈ K and some candidate criterion f . This is why most of all the above cited works address linear programs or combinatorial optimization problems for which some characterization of global optimality is available and can be (sometimes) effectively used for practical computation. For instance, the characterization of global optimality for integer programs described in Schaefer [START_REF] Schaefer | Inverse integer programming[END_REF] is via the superadditive dual of Wolsey [19, §2] which is exponential in the problem size, and so prevents from its use in practice.

This perhaps explains why inverse (non linear) optimization has not attracted much attention in the past, and it is a pity since inverse optimality could provide an alternative stopping criterion at a feasible solution y obtained by a (local) optimization algorithm.

The novelty of the present paper is to provide a systematic numerical scheme for computing an inverse optimal solution associated with the polynomial program P and a given feasible solution y ∈ K. It consists of solving a semidefinite program 1 whose size can be adapted to the problem on hand, and so is tractable (at least for moderate size problems and possibly for larger size problems if sparsity is taken into account). Moreover, if one uses the ℓ 1 -norm then the inverse-optimal objective function exhibits a simple and remarkable canonical (and sparse) form. 1 A semidefinite program is a convex (conic) optimization problem that can be solved efficiently.

For instance, up to arbitrary (fixed) precision and using some interior point algorithms, it can be solved in time polynomial in the input size of the problem. For more details the interested reader is referred to e.g. Wolkowicz et al. [START_REF] Wolkowicz | Handbook of Semidefinite Programming: Theory, Algorithms, and Applications[END_REF] and the many references therein.

Contribution. In this paper we investigate the inverse optimization problem for polynomial optimization problems P as in (1.1), i.e., in a rather general context which includes nonlinear and nonconvex optimization problems and in particular, 0/1 and mixed integer nonlinear programs. Fortunately, in such a context, Putinar's Positivstellensatz [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF] provides us with a very powerful certificate of global optimality that can be adapted to the actual computational capabilities for a given problem size. More precisely, and assuming y = 0 (possibly after a change of variable x ′ = x-y), in the methodology that we propose, one computes the coefficients of a polynomial fd ∈ R[x] of same degree d 0 as f (or possibly larger degree if desired and/or possibly with some additional constraints), such that:

• 0 is a global minimizer of the related problem min x { fd (x) : x ∈ K}, with a Putinar's certificate of optimality with degree bound d (to be explained later).

• fd minimizes f -f k (where depending on k, • k is the ℓ 1 , ℓ 2 or ℓ ∞ -
norm of the coefficient vector) over all polynomals f of degree d 0 , having the previous property.

Assuming K is compact (hence K ⊆ [-1, 1] n possibly after a change of variable), it turns out that the optimal value ρ d := fd -f k also measures how close is f (0) to the global optimum f * of P, as we also obtain that

f * ≤ f (0) ≤ f * + ρ d if k = 1 and similarly f * ≤ f (0) ≤ f * + ρ d n+d0 n if k = ∞.
In addition, for the ℓ 1 -norm we prove that fd has a simple canonical form, namely

fd = f + b ′ x + n i=1 λ i x 2 i ,
for some vector b ∈ R n , and nonnegative vector λ ∈ R n , optimal solutions of a semidefinite program. (For 0/1 problems it further simplifies to fd = f + b ′ x only.) This canonical form is sparse as fd differs from f in at most 2n entries only (≪ n+d0 n

). It illustrates the sparsity properties of optimal solutions of ℓ 1norm minimization problems, already observed in other contexts (e.g., in some compressed sensing applications).

Importantly, to compute fd , one has to solve a semidefinite program of size parametrized by d, where d is chosen so that the size of semidefinite program associated with Putinar's certificate (with degree bound d) is compatible with current semidefinite solvers available. (Of course, even if d is relatively small, one is still restricted to problems of relatively modest size.) Moreover, when K is compact, generically fd is an optimal solution of the "ideal inverse optimization problem" provided that d is sufficiently large! In addition, one may also consider several additional options:

• Instead of looking for a polynomial f of same degree as f , one might allow polynomials of higher degree, and/or restrict certain coefficients of f to be the same as those of f (e.g. for structural modeling reasons).

• One may restrict f to a certain class of functions, e.g., quadratic polynomials and even convex quadratic polynomials. In the latter important case and if the g j 's that define K are concave, the procedure to compute an optimal solution f (x) = b′ x + x ′ Qx simplifies and reduces to solving separately a linear program (for computing b) and a semidefinite program (for computing Q).

The paper is organized as follows. In a first introductory section we present the notation, definitions, and the ideal inverse optimization problem. We then describe how a practical inverse optimization problem reduces to solving a semidefinite program and exhibit the canonical form of the optimal solution for the ℓ 1 -norm. We also provide additional results, e.g., an asymptotic analysis when the degree bound in Putinar's certificate increases and also the particular case where one searches for a convex candidate criterion.

:= {β ∈ N n : j β j ≤ d} whose cardinal is s(d) = n+d n . A polynomial f ∈ R[x] is written x → f (x) = α∈N n f α x α ,
and f can be identified with its vector of coefficients f = (f α ) in the canonical basis (x α ), α ∈ N n . Denote by S t ⊂ R t×t the space of real symmetric matrices, and for any A ∈ S t the notation A 0 stands for A is positive semidefinite. For

f ∈ R[x] d , let f k =            α∈N n d |f α | if k = 1, α∈N n d f 2 α if k = 2, max {|f α | : α ∈ N n d } if k = ∞. A real sequence z = (z α ), α ∈ N n ,
has a representing measure if there exists some finite Borel measure µ on R n such that

z α = R n x α dµ(x), ∀ α ∈ N n .
Given a real sequence z = (z α ) define the linear functional L z : R[x] → R by:

f (= α f α x α ) → L z (f ) = α f α z α , f ∈ R[x].
Moment matrix. The moment matrix associated with a sequence z = (z α ), α ∈ N n , is the real symmetric matrix M d (z) with rows and columns indexed by N n d , and whose entry (α, β) is just z α+β , for every α, β ∈ N n d . Alternatively, let v d (x) ∈ R s(d) be the vector (x α ), α ∈ N n d , and define the matrices (B α ) ⊂ S s(d) by (2.1)

v d (x) v d (x) T = α∈N n 2d B α x α , ∀x ∈ R n . Then M d (z) = α∈N n 2d z α B α . If z has a representing measure µ then M d (z) 0 because f , M d (z)f = f 2 dµ ≥ 0, ∀ f ∈ R s(d) .
Localizing matrix. With z as above and g ∈ R[x] (with g(x) = γ g γ x γ ), the localizing matrix associated with z and g is the real symmetric matrix M d (g z) with rows and columns indexed by N n d , and whose entry (α, β) is just γ g γ z α+β+γ , for every α, β ∈ N n d . Alternatively, let C α ∈ S s(d) be defined by: (2.2)

g(x) v d (x) v d (x) T = α∈N n 2d+deg g C α x α , ∀x ∈ R n . Then M d (g z) = α∈N n 2d+degg z α C α . If z has a representing measure µ whose support is contained in the set {x : g(x) ≥ 0} then M d (g z) 0 because f , M d (g z)f = f 2 g dµ ≥ 0, ∀ f ∈ R s(d) .
With K as in (1.1), let g 0 ∈ R[x] be the constant polynomial x → g 0 (x) = 1, and for every j = 0, 1, . . . , m, let v j := ⌈(deg g j )/2⌉.

Definition 2.1. With d, k ∈ N and K as in (1.1), let Q k (g) ⊂ R[x] and Q d k ⊂ R[x] d be the convex cones: Q(g) := m k=0 σ j g j : σ j ∈ Σ[x] j = 1, . . . , m . (2.3) Q k (g) := m k=0 σ j g j : σ j ∈ Σ[x] k-vj , j = 1, . . . , m . (2.4) Q d k (g) := Q k (g) ∩ R[x] d (2.5)
We say that every element h ∈ Q k (g) has a Putinar's certificate of nonnegativity on K, with degree bound k.

The cone Q(g) is called the quadratic module associated with the g j 's. Obviously, if h ∈ Q(g) the associated s.o.s. polynomials σ j 's provide a certificate of nonnegativity of h on K. The cone Q(g) is said to be Archimedean if and only if (2.6) x → Mx 2 ∈ Q(g) for some M > 0.

Let Psd d (K) ⊂ R[x] d be the convex cone of polynomials of degree at most d, nonnegative on K. The name "Putinar's certificate" is coming from the following Putinar's Positivstellensatz.

Theorem 2.2 (Putinar's Positivstellensatz [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF]). Let K be as in (1.1) and assume that Q(g) is Archimedean. Then every polynomial f ∈ R[x] strictly positive on K belongs to Q(g). In addition,

(2.7) cl ∞ k=0 Q d k (g) = Psd d (K), ∀d ∈ N.
The first statement is just Putinar's Positivstellensatz [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF] whereas the second statement is an easy consequence. Indeed let

f ∈ Psd d (K). If f > 0 on K then f ∈ Q d k (g) for some k. If f (x) = 0 for some x ∈ K, let f n := f + 1/n, so that f n > 0 on K for every n ∈ N. But then f n ∈ ∪ ∞ k=0 Q d k (g) and the result follows because f n -f 1 → 0 as n → ∞.
In fact, by results from Marshall [START_REF] Marshall | Representation of non-negative polynomials, degree bounds and applications to optimization[END_REF] and more recently Nie [START_REF] Nie | Optimality Conditions and Finite Convergence of Lasserre's Hierarchy[END_REF], membership in Q(g) is also generic for polynomials that are only nonnegative on K. And so Putinar's Positivstellensatz is particularly useful to certify and enforce that a polynomial is nonnegative on K, and in particular the polynomial x → f (x) -f (y) for the inverse optimization problem associated with a feasible solution y ∈ K.

Notice that one may also be less demanding and ask y to be only a global ǫminimizer for some fixed ǫ > 0. Again Putinar's Positivstellensatz is exactly what we need to certify (global) ǫ-optimality by requiring f ( d0) , one may and will identify R[x] d0 with the vector space R s(d0 d0) . So in the sequel, and unless if necessary, we will not distinguish between f and f .

•) -f (y) + ǫ ∈ Q k (g).
:= deg f . Identifying a polynomial f ∈ R[x] d0 with its vector of coefficients f = (f α ) ∈ R s(
) , i.e., R[x] d0 ∋ f ↔ f ∈ R s(d0) . Similarly, the convex cone Psd d0 (K) ⊂ R[x] d0 can be identified with the convex cone {h ∈ R s(d0) : h ↔ h ∈ Psd d0 (K)} of R s(
Next, let y ∈ K and k ∈ {1, 2, ∞} both fixed, and consider the following optimization problem P (2.8)

P : ρ k = min f ∈R[x] d 0 { f -f k : x → f (x) -f (y) ∈ Psd d0 (K) }. Theorem 2.3. Let K ⊂ R n be with nonempty interior. Problem (2.8) has an optimal solution f * ∈ R[x] d0 .
In addition, ρ k = 0 if and only if y is an optimal solution of P.

Proof. Obviously the constant polynomial x → f (x) := 1 is a feasible solution with associated value δ := f -f k . Moreover the optimal value of (2.8) is bounded below by 0. Observe that

• k defines a norm on R[x] d0 . Consider a minimizing sequence ( f j ) ⊂ R[x] d0 , j ∈ N, hence such that f j -f k → ρ k as j → ∞.
As we have f j -f k ≤ δ for every j, the sequence ( f j ) belongs to the ℓ k -ball

B k (f ) := { f ∈ R[x] d0 : f -f k ≤ δ}, a compact set. Therefore, there is an element f * ∈ B k (f ) and a subsequence (j t ), t ∈ N, such that f jt → f * as t → ∞. Let x ∈ K be fixed arbitrary. Obviously (0 ≤) f jt (x) -f jt (y) → f * (x) -f * (y)
as t → ∞, which implies f * (x) -f * (y) ≥ 0, and so, as x ∈ K was arbitrary, f * -f * (y) ≥ 0 on K, i.e., f * -f * (y) ∈ Psd d0 (K). Finally, we also obtain the desired result

ρ k = lim j→∞ f j -f k = lim t→∞ f jt -f k = f * -f k .
Next, if y is an optimal solution of P then f := f is an optimal solution of P with value ρ k = 0. Conversely, if ρ k = 0 then f * = f , and so by feasibility of f * (= f ) for (2.8), f (x) ≥ f (y) for all x ∈ K, which shows that y is an optimal solution of P.

Theorem 2.3 states that the ideal inverse optimization problem is well-defined. However, even though Psd d0 (K) is a finite dimensional convex cone, it has no simple and tractable characterization to be used for practical computation. Therefore one needs an alternative and more tractable version of problem P. Fortunately, we next show that in the polynomial context such a formulation exists, thanks to the powerful Putinar's Positivstellensatz (Theorem 2.2 above).

Main result

As the ideal inverse problem is intractable, we here provide tractable formulations whose size depends on a parameter d ∈ N. If the polynomial f * in Theorem 2.3 belongs to Q(g) then when d increases the associated optimal value ρ k d converges in finitely many steps to the optimal value ρ k of the ideal problem (2.8), and f * can be obtained by solving finitely many semidefinite programs. And in fact this situation is generic.

With no loss of generality, i.e., up to some change of variable x ′ = xy we may and will assume that y = 0 ∈ K.

P d : ρ k d := min f ,σj ∈R[x] f -f k s.t. f (x) -f (0) = m j=0 σ j (x) g j (x), ∀x ∈ R n f ∈ R[x] d0 ; σ j ∈ Σ[x] d-vj , j = 0, 1, . . . , m,
where d 0 = deg f , and

v j = ⌈(deg g j )/2⌉, j = 1, . . . , m.
The parameter d ∈ N impacts (3.1) by the maximum degree allowed for the s.o.s. weights (σ j ) ⊂ Σ[x] in Putinar's certificate for the polynomial x → f (x) -f (0), and so the higher d is, the lower ρ k d . Next, observe that in (3.1), the constraint (2.5). Therefore, in particular, f (x) ≥ f (0) for all x ∈ K, and so 0 is a global minimizer of f on K. So P d is a strengthtening of P in that one has replaced the constraint ff (0) ∈ Psd d0 (K) with the stronger condition ff (0) ∈ Q d0 d (g). And so ρ k ≤ ρ k d for all d ∈ N. However, as we next see, P d is a tractable optimization problem with nice properties. Indeed, P d is a convex optimization problem and even a semidefinite program. For instance, if k = 1 one may rewrite P d as:

f (x) -f (0) = m j=0 σ j (x) g j (x), ∀x ∈ R n , is equivalent to stating that f (x)-f (0) ∈ Q d0 d (g), with Q d0 d (g) as in
(3.2)

ρ 1 d := min λα≥0, f,Zj α∈N n d 0 \{0} λ α s.t. λ α + fα ≥ f α , ∀α ∈ N n d0 \ {0} λ α -fα ≥ -f α , ∀α ∈ N n d0 \ {0} Z 0 , B α + m j=1 Z j , C j α = fα , if 0 < |α| ≤ d 0 0, if α = 0 or |α| > d 0 Z j 0, j = 0, 1, . . . , m.
with B α as in (2.1) and C j α as in (2.2) (with g j in lieu of g). If k = ∞ then one may rewrite P d as:

(3.3) ρ ∞ d := min λ≥0, f ,Zj λ s.t. λ + fα ≥ f α , ∀α ∈ N n d0 \ {0} λ -fα ≥ -f α , ∀α ∈ N n d0 \ {0} Z 0 , B α + m j=1 Z j , C j α = fα , if 0 < |α| ≤ d 0 0, if α = 0 or |α| > d 0 Z j 0, j = 0, 1, . . . , m,
and finally, if k = 2 then one may rewrite P d as:

(3.4)

ρ 2 d := min λ≥0, f ,Zj α∈N n d 0 \{0} λ α s.t. λ α fα -f α fα -f α 1 0, ∀α ∈ N n d0 \ {0} Z 0 , B α + m j=1 Z j , C j α = fα , if 0 < |α| ≤ d 0 0, if α = 0 or |α| > d 0 Z j 0, j = 0, 1, . . . , m. Remark 3.1.
Observe that in any feasible solution ( f , λ, Z j ) in all formulations (3.2)-(3.4), f0 plays no role in the constraints of (3.1), but since we minimize f -

f k then it is always optimal to set f0 = f 0 . That is, fd (0) = f0 = f 0 = f (0).
Sparsity. The semidefinite program (3.1)-(3.2) has m + 1 Linear Matrix Inequalities (LMI's) Z j 0 of size O(n d ), which limits its application to problems P of modest size. However large scale problems usually exhibit sparsity patterns which sometimes can be exploited. For instance, in [START_REF] Lasserre | Convergent SDP-relaxations in polynomial optimization with sparsity[END_REF] we have provided a specialized "sparse" version of Theorem 2.2 for problems with structured sparsity as described in Waki et al. [START_REF] Waki | Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity[END_REF]. Hence, with this specialized version of Putinar's Positivstellensatz, one obtains a sparse positivity certificate which when substituted in (3.1), would permit to solve (3.1) for problems of much larger size. Typically, in [START_REF] Waki | Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity[END_REF] the authors have applied the "sparse semidefinite relaxations" to problem P with up to 1000 variables! Moreover, the running intersection property that must satisfy the sparsity pattern for convergence guarantee of such relaxations [START_REF] Lasserre | Convergent SDP-relaxations in polynomial optimization with sparsity[END_REF], is not needed in the present context of inverse optimization. This is because one imposes f to satisfy this specialized Putinar's Positivstellensatz.

Duality. The semidefinite program dual of (3.2) reads

                 max u,v≥0,z α∈N n d 0 \{0} f α (u α -v α ) (= L z (f (0) -f )) s.t. u α + v α ≤ 1, ∀ α ∈ N n d0 \ {0} u α -v α + z α = 0, ∀α ∈ N n d0 \ {0} α∈N n d z α B α 0 α∈N n d z α C j α 0, j = 1, . . . , m,
which, recalling the respective definitions (2.1) and (2.2) of the moment and localizing matrix, is the same as

(3.5)            max u,v≥0,z α∈N n d 0 \{0} f α (u α -v α ) (= L z (f (0) -f )) s.t. u α + v α ≤ 1, ∀ α ∈ N n d0 \ {0} u α -v α + z α = 0, ∀α ∈ N n d0 \ {0} M d (z), M d-vj (g j z) 0, j = 1, . . . , m.
Similarly, the semidefinite program dual of (3.3) reads

(3.6)                  max u,v≥0,z α∈N n d 0 \{0} f α (u α -v α ) (= L z (f (0) -f )) s.t. α∈N n d 0 \{0} u α + v α ≤ 1 u α -v α + z α = 0, ∀α ∈ N n d0 \ {0} M d (z), M d-vj (g j z) 0, j = 1, . . . , m,
and the semidefinite program dual of (3.4) reads

(3.7)                              max z,∆α α∈N n d 0 \{0} ∆ α , 0 f α f α -1 s.t. ∆ α , 1 0 0 0 ≤ 1, ∀α ∈ N n d0 \ {0} ∆ α , 0 1 1 0 + z α = 0, ∀α ∈ N n d0 \ {0} M d (z), M d-vj (g j z) 0, j = 1, . . . , m ∆ α 0, ∀α ∈ N n d0 \ {0}.
One may show that one may replace the criterion in (3.7) with the equivalent concave criterion Proof. The proof is detailed for the case k = 1 and omitted for the cases k = 2 and k = ∞ because it is very similar. Observe that ρ 1 d ≥ 0 and the constant polynomial f (x) = 0 for all x ∈ R n , is an obviously feasible solution of (3.1) (hence of (3.2)). Therefore ρ 1 d being finite, it suffices to prove that Slater's condition 2 holds for the 2 Slater's condition holds if there exists a strictly feasible solution, and so for the dual (3.5), if there exists z such that M d (z), M d-v j (g j z) ≻ 0, j = 1, . . . , m, and uα + vα < 1, ∀α ∈ N n d 0 \ {0}. Then from a standard result in convex optimization, there is no duality gap between (3.2) and (3.5), and if the values are bounded then (3.2) has an optimal solution. dual (3.5). Then the conclusion of Lemma 3.2 follows from a standard result of convex optimization. Let µ be the finite Borel measure defined by

max z    L z (f (0) -f )) - 1 4 α∈N n d 0 \{0} z 2 α    . Lemma 3.2. Assume that K ⊂ R n has
µ(B) := B∩K e -x 2 dx, ∀B ∈ B
(where B is the usual Borel σ-field), and let z = (z α ), α ∈ N n 2d , with

z α := κ K x α dµ(x), α ∈ N n 2d ,
for some κ > 0 sufficiently small to ensure that

(3.8) κ x α dµ(x) < 1, ∀α ∈ N n 2d \ {0}. Define u α = max[0, -z α ] and v α = max[0, z α ], α ∈ N n d0 \ {0}, so that u α + v α < 1, α ∈ N n 2d \ {0}. Hence (u α , v α , z
) is a feasible solution of (3.5). In addition, M d (z) ≻ 0 and M d-vj (g j z) ≻ 0, j = 1, . . . , m, because K has nonempty interior, and so Slater's condition holds for (3.5), the desired result.

If k = ∞ one chooses z such that

κ α∈N n d 0 \{0} x α dµ(x) < 1,
and if k = 2 then one chooses z as in (3.8) and

∆ α := 1/2 κ α κ α 1 ≻ 0, for all α ∈ N n d0 \ {0}, such that 2κ α := κ x α dµ(x), ∀α ∈ N n 2d \ {0}.
Theorem 3.3. Assume that K in (1.1) has nonempty interior, and let x * ∈ K be a global minimizer of P with optimal value f * , and let fd ∈ R[x] d0 be an optimal solution of P d in (3.1) with optimal value ρ k d . Then: (a) 0 ∈ K is a global minimizer of the problem f * d = min x { fd (x) : x ∈ K}. In particular, if ρ k d = 0 then fd = f and 0 is a global minimizer of P.

(b) If k = 1 then f * ≤ f (0) ≤ f * + ρ 1 d sup α∈N n d 0 |(x * ) α |. In particular, if K ⊆ [-1, 1] n then f * ≤ f (0) ≤ f * + ρ 1 d . (c) If k = ∞ then f * ≤ f (0) ≤ f * + ρ ∞ d α∈N n d 0 |(x * ) α |. In particular if K ⊆ [-1, 1] n then f * ≤ f (0) ≤ f * + s(d 0 ) ρ ∞ d .
Proof. (a) Existence of fd is guaranteed by Lemma 3.2. From the constraints of (3.1) we have: fd (x) -f (0) = m j=0 σ j (x) g j (x) which implies that fd (x) ≥ f (0) for all x ∈ K, and so 0 is a global minimizer of the optimization problem P ′ : min x { fd (x) : x ∈ K}.

(b) Let x * ∈ K be a global minimizer of P. Observe that with k = 1,

f * = f (x * ) = f (x * ) -fd (x * ) + fd (x * ) -fd (0) ≥0 + fd (0) ≥ fd (0) -| fd (x * ) -f (x * )| ≥ fd (0) -fd -f 1 × sup α∈N n d 0 |(x * ) α | ≥ f (0) -ρ 1 d sup α∈N n d 0 |(x * ) α | (3.9) since fd (0) = f (0); see Remark 3.1.
(c) The proof is similar to that of (b) using that with k = ∞,

| fd (x) -f (x)| ≥ sup α∈N n d 0 | fdα -f α | × α∈N n d 0 |x α |.
So not only Theorem 3.3 states that 0 is the global optimum of the optimization problem min{ fd (x) : x ∈ K}, but it also states that the optimal value ρ k d also measures how far is f (0) from the optimal value f * of the initial problem P. Moreover, observe that Theorem 3.3 merely requires existence of a minimizer and nonemptyness of K. In particular, K may not be compact.

3.3.

A canonical form for the ℓ 1 -norm. When K is compact and if one uses the ℓ 1 -norm then the optimal solution fd ∈ R[x] d0 in Theorem 3.3 (with k = 1) takes a particularly simple canonical form:

As K is compact we may and will assume (possibly after some scaling) that K ⊆ [-1, 1] n and so in the definition of (1.1) we may and will add the n redundant quadratic constraints g m+i (x) ≥ 0, i = 1, . . . , n, with x → g m+i (x) = 1 -x 2 i for every i, that is,

(3.10) K = {x ∈ R n : g j (x) ≥ 0, j = 1, . . . , m + n}, and
Q d (g) =    n+m j=0 σ j g j : σ j ∈ Σ[x] d-vj , j = 0, . . . , m + n    ,
which is obviously Archimedean.

Theorem 3.4. Assume that K in (3.10) has a nonempty interior and let fd ∈ R[x] d0 be an optimal solution of P d in (3.1) (with m + n instead of m) with optimal value ρ 1 d for the ℓ 1 -norm. Then: (i) fd is of the form

(3.11) fd (x) = f (x) + b ′ x if d 0 = 1 f (x) + b ′ x + n i=1 λ * i x 2 i if d 0 > 1,
for some vector b ∈ R n and some nonnegative vector λ * ∈ R n , optimal solution of the semidefinite program:

(3.12)

ρ 1 d := min λ,b b 1 + n i=1 λ i s.t. f -f (0) + b ′ x + n i=1 λ i x 2 i ∈ Q d (g), λ ≥ 0.
(ii) The vector b is of the form -∇f (0) + j∈J(0) θ j ∇g j (0) for some nonnegative scalars (θ j ) (where j ∈ J(0) if and only if g j (0) = 0).

Proof. (i) Notice that the dual (3.5) of (3.2) is equivalent to:

(3.13)    max z L z (f (0) -f )) s.t. M d (z), M d-vj (g j z) 0, j = 1, . . . , m + n, |z α | ≤ 1, ∀ α ∈ N n d0 \ {0}. Next, since M d (z) 0
M d (z) 0 ⇒ |z α | ≤ max i=1,...,n {max[L z (x 2 i ), L z (x 2d i )]}.
Moreover the constraint M d-1 (g m+i z) 0 implies M d-1 (g m+i z)(ℓ, ℓ) ≥ 0 for all ℓ, and so in particular, one obtains

L z (x 2k-2 i ) ≥ L z (x 2k i ) for all k = 1, . . . , d and all i = 1, . . . , n. Hence |z α | ≤ max i=1,...,n L z (x 2 i ) for every α ∈ N n 2d with |α| > 1.
Therefore in (3.13) one may replace the constraint |z α | ≤ 1 for all α ∈ N n d0 \ {0} with the 2n inequality constraints ±L z (x i ) ≤ 1, i = 1, . . . , n, if d 0 = 1 and the 3n inequality constraints: (3.13) is the same as the semidefinite program

(3.14) ±L z (x i ) ≤ 1, L z (x 2 i ) ≤ 1, i = 1, . . . , n if d 0 > 1. Consequently,
(3.15)    max z L z (f (0) -f )) s.t. M d (z), M d-vj (g j z) 0, j = 1, . . . , m + n, ±L z (x i ) ≤ 1, L z (x 2 i ) ≤ 1, i = 1, . . . , n. Let b 1 = (b 1 i ) (resp. b 2 = (b 2 i
)) be the nonnegative vector of dual variables associated with the constraints L z (x i ) ≤ 1 (resp. -L z (x i ) ≤ 1), i = 1, . . . , n. Similarly, let λ i be the dual variable associated with the constraint L z (x 2 i ) ≤ 1. Then the dual of (3.15) is the semidefinite program:

             max b 1 ,b 2 ,λ n i=1 (b 1 i + b 2 i ) + λ i s.t. f -f (0) + (b 1 -b 2 ) ′ x + n i=1 λ i x 2 i ∈ Q d (g) b 1 , b 2 , λ ≥ 0
which is equivalent to (3.12).

(ii) Let (b, λ) be an optimal solution of (3.12), so that

f -f (0) + b ′ x + n i=1 λ i x 2 i = σ 0 + m+n j=1 σ j g j ,
for some SOS polynomials σ j . Evaluating at x = 0 yields σ 0 (0) = 0; σ j (0) θj ≥0

g j (0) = 0, j = 1, . . . , m + n.

Differentiating and evaluating at x = 0 and using that σ j is SOS and σ j (0)g j (0) = 0, j = 1, . . . , n + m, yields:

∇f (0) + b = n+m j=1 σ j (0) ∇g j (0) = j∈J(0)
θ j ∇g j (0), which is the desired result.

From the proof of Theorem 3.4, this special form of fd is specific to the ℓ 1 -norm, which yields the constraint |z α | ≤ 1, α ∈ N n d0 \ {0} in the dual (3.5) and allows its simplification (3.14) thanks to a property of the moment matrix described in [START_REF] Lasserre | SOS approximations of nonnegative polynomials via simpla high degree perturbation[END_REF]. Observe that the canonical form (3.11) of fd is sparse since fd differs from f in at most 2n entries only (recall that f has n+d0 n entries). This is another example of sparsity properties of optimal solutions of ℓ 1 -norm minimization problems, already observed in contexts (e.g., in some compressed sensing applications). Moreover, it has the following consequence for nonlinear 0/1 programs.

Corollary 3.5. Let K = {0, 1} n , f ∈ R[x]
(3.16) fd (x) = f (x) + b T (x -y), for some coefficient vector b ∈ R n such that b i ≥ 0 if i ∈ I 1 and b i ≤ 0 if i ∈ I 2 , i = 1, . . . , n.
Moreover, b is an optimal solution of the semidefinite program:

min b,λ,γ i∈I1 b i - i∈I2 b i (= |b|) s.t. f (x) -f (y) + b T (x -y) = σ 0 + n i=1 (x 2 i -x i ) σ i b i ≥ 0, i ∈ I 1 ; b i ≤ 0, i ∈ I 2 ; σ 0 ∈ Σ[x] d ; σ i ∈ R[x] d-1 , i = 1, . . . , n.
Proof. We briefly sketch the proof which is very similar to that of Theorem 3.4 even though K does not have a nonempty interior and d 0 is not required to be even. Recall that y ∈ K could be assumed to be 0 and so if K = {0, 1} n then the new feasible set after the change of variable u := x-y is now K = i∈I1 ({0, 1}) i∈I2 ({-1, 0}). Similarly, let f ′ ∈ R[x] d be the polynomial f in the new coordinates u, i.e., f ′ (u) = f (u + y). So for every α ∈ N n , define ᾱ ∈ {0, 1} n and ∆ α ⊂ I 2 by: ᾱi := 1 if α i > 0 and 0 otherwise, i = 1, . . . , n

∆ α := {i ∈ I 2 : 0 < α i is even},
and let |∆ α | denotes the cardinality of ∆ α . Then because of the boolean constraints

u 2 i = u i , i ∈ I 1 and u 2 i = -u i , i ∈ I 2 , in the definition of K, (3.13) reads      max z L z (f ′ (0) -f ′ ) s.t. M d (z) 0; z α = (-1) |∆α| z ᾱ, α ∈ N n 2d |z α | ≤ 1, ∀ α ∈ N n d0 \ {0}.
But this combined with M d (z) 0 implies that M d (z) can be simplified to a smaller real symmetric matrix M d (z) with rows and columns indexed by only the square-free monomials x ᾱ, α ∈ N n 2d . Indeed, every column α of M d (z) is exactly identical to ± the column of M d (z) indexed by ᾱ. Also, invoking [START_REF] Lasserre | SOS approximations of nonnegative polynomials via simpla high degree perturbation[END_REF] and with similar arguments, |z α | ≤ max [max i∈I1 L z (u i ), max i∈I2 -L z (u i )] for all α, and so (3.17) is equivalent to:

(3.17)

       max z L z (f ′ (0) -f ′ ) s.t. M d (z) 0; z α = (-1) |∆α| z ᾱ, α ∈ N n 2d L z (x i ) ≤ 1, i ∈ I 1 -L z (x i ) ≤ 1, i ∈ I 2 .
Finally, let µ be a Borel measure with support exactly K, and scaled to satisfy | u i dµ| < 1, i = 1, . . . , n. Its associated vector of moment z = ( u α dµ), α ∈ N n , is feasible in (3.17) and M d (z) ≻ 0. Hence Slater's condition holds for (3.17), which in turn implies that there is no duality gap with its dual which reads:

min b,λ,γ n i=1 b i s.t. f ′ (u) -f ′ (0) + i∈I1 b i u i - i∈I2 b i u i = σ 0 (u) + n i∈I1 σ i (u) (u 2 i -u i ) + n i∈I2 σ i (u) (u 2 i + u i ) b ≥ 0; σ 0 ∈ Σ[u] d ; σ i ∈ R[u] d-1 , i = 1, . . . , n.
Moreover, the dual has an optimal solution because the optimal value is bounded below by zero. Recalling that u = xy and f ′ (u) = f (x), we retrieve the semidefinite program of the Corollary and so fd is indeed of the form (3.16).

Structural constraints. It may happen that the initial criterion f ∈ R[x]

has some structure that one wishes to keep in the inverse problem. For instance, in MAXCUT problems on K = {-1, 1} n , f is a quadratic form x → x ′ Ax for some real symmetric matrix A associated with a graph (V, E), where A ij = 0 if and only if (i, j) ∈ E. Therefore, in the inverse optimization problem, one may wish that f in (3.1) is also a quadratic form associated with the same graph (V, E), so that f (x) = x ′ Ãx with Ãij = 0 for all (i, j) ∈ E. So if ∆ f ⊂ N n d0 denotes the subset of (structural) multi-indices for which f and f should have same coefficient, then in (3.1) one includes the additional constraint fα = f α for all α ∈ ∆ f . Notice that 0 ∈ ∆ f because f0 = f 0 ; see Remark 3.1. For instance, with K as in (3.10) and k = 1, (3.2) reads (3.18)

ρ 1 d := min f ,λα,Zj α∈N n d 0 \{0} λ α s.t. λ α + fα ≥ f α , ∀α ∈ N n d0 \ ∆ f λ α -fα ≥ -f α , ∀α ∈ N n d0 \ ∆ f Z 0 , B α + m+n j=1 Z j , C j α =    f α , if α ∈ ∆ f \ {0} fα , if α ∈ N n d0 \ ∆ f 0, if α = 0 or |α| > d 0 Z j 0, j = 0, 1, . . . , m + n,
and its dual has the equivalent form,

(3.19)    max z L z (f (0) -f )) s.t. M d (z), M d-vj (g j z) 0, j = 1, . . . , m + n, |z α | ≤ 1, ∀ α ∈ N n d0 \ (∆ f ∪ {0}
). However now (3.18) may not have a feasible solution. In problems where d 0 is even and ∆ f does not contain the monomials α ∈ N n d0 such that x α = x 2 i , or x α = x d0 i , i = 1, . . . , n, and if (3.18) has a feasible solution, then there is an optimal solution f with still the special form described in Theorem 3.4, but with b k = 0 if α = e k ∈ ∆ f (where all entries of e k vanish except the one at position k).

3.5.

Asymptotics when d → ∞. We now relate P d , d ∈ N, with the ideal inverse problem P in (2.8) when d increases.

Proposition 3.6. Let K be as in (1.1) with nonempty interior. For every

k = 1, 2, ∞, let fd ∈ R[x] d0 (resp. f * ∈ R[x] d0
) be an optimal solution of (3.1) (resp. (2.8)) with associated optimal value ρ k d (resp. ρ k ). The sequence (ρ k d ), d ∈ N, is monotone nonincreasing and converges to ρk ≥ ρ k . Moreover, every accumulation point

f ∈ R[x] d0 of the sequence ( fd ), d ∈ N, is such that f -f (0) ∈ Psd d0 (K) and f -f k = ρk . Finally, if f * -f * (0) is in Q(g), then ρ k d = ρk = ρ k for some d. Proof. Observe that the sequence ( fd ), d ∈ N, is contained in the ball {h : h - f k ≤ ρ k d0 } ⊂ R[x] d0
, for some d 0 ∈ N. So let f be an accumulation point of ( fd ). Since fdf (0) ≥ 0 on K for all d, a simple continuity argument yields ff (0) ≥ 0 on K, i.e., ff (0) ∈ Psd d0 (K). Moreover, the sequence (ρ k d ) is obviously monotone nonincreasing and bounded below by zero. Hence lim d→∞ ρ k d =: ρk ≥ ρ k , and by continuity f

-f k = ρk . Finally, if f * -f (0) ∈ Q(g) then f * -f (0) ∈ Q d0 d (
g) for some d, and so f * is a feasible solution of (3.1) but with value ρ k ≤ ρ k d . Therefore, we conclude that f * is an optimal solution of (3.1). Proposition 3.6 relates ρ k d and ρ k in a strong sense when f * -f (0) ∈ Q(g). However, we would like to know how restrictive is the constraint f

* -f (0) ∈ Q(g) compared to f * -f (0) ∈ Psd d0 (K). Indeed, even though Psd d0 (K) = cl (∪ ∞ ℓ=0 )Q d0 ℓ
when K satisfies the assumptions of Theorem 2.7, in general an approximating sequence (f ℓ ) ⊂ Q(g), ℓ ∈ N (with f ℓ -f * k → 0), does not have the property that f ℓ (x) -f ℓ (0) ≥ 0 for all x on K.

3.6. Q(g) versus Psd d0 (K). Therefore the question is: How often a polynomial nonnegative on K (and with at least one zero in K) is an element of Q(g)? This question can be answered in a number of cases which suggest that f ≥ 0 on K and f ∈ Q(g) can be true in very specific cases only (at least when K is compact and Q(g) is Archimedean). Indeed f ≥ 0 on K implies f ∈ Q(g) whenever:

• f and -g j are convex, j = 1, . . . , n, Slater's condition holds and ∇ 2 f (x * ) ≻ 0 at the unique global minimizer x * ∈ K; see e.g., de Klerk and Laurent [START_REF] Klerk | On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problem[END_REF]. • K ⊆ {0, 1} n , i.e., for 0/1 polynomial programs, and more generally for all discrete polynomial optimization problems.

• Q(g) is Archimedean, f has finitely many zeros in K and the Boundary Hessian Condition (BHC) holds at every zero of f in K; see e.g. Marshall [START_REF] Marshall | Representation of non-negative polynomials, degree bounds and applications to optimization[END_REF]. That is, the BHC holds at a zero x * ∈ K of f if there exists 0 ≤ k ≤ n, and some 1

≤ v 1 ≤ • • • ≤ v k ≤ m, such that: g v1 , .
. . , g v k are part of a system of local parameters at x * , and the standard sufficient conditions for x * to be local minimizer of f on {x : g vj (x) ≥ 0, j = 1, . . . , k} hold. Equivalently, if (t 1 , . . . , t n ) are local parameters at x * with t j = g vj , j = 1, . . . , k, then f can be written as a formal power series

f 0 + f 1 + f 2 . . . in R[[t 1 , . . . , t n ]],
where each f j is an homogeneous form of degree j,

f 1 = a 1 t 1 + • • • + a k t k with a i > 0, i = 1, . . . , k,
and the quadratic form f 2 (0, . . . , 0 k times , t k+1 , . . . , t n ) is positive definite.

For instance, if all the (finitely many) zeros x * of f are in the interior of K, one may take k = 0 and

t i (x) = x i -x * i for all i. Then f ∈ Q(g) if f 2 is positive definite.
It turns out that under a technical condition on the polynomials that define K, the BHC holds generically, i.e., the set of polynomials f ∈ R[x] d for which the BHC holds at every global minimizer on K, is dense in R[x] d ; see Marshall [START_REF] Marshall | Representation of non-negative polynomials, degree bounds and applications to optimization[END_REF]Corollary 4.5]. Finally, and in the same vein, a recent result of Nie [START_REF] Nie | Optimality Conditions and Finite Convergence of Lasserre's Hierarchy[END_REF] states that if the standard constraint qualification, strict complementarity and second-order sufficiency condition hold at every global minimizer of f on K, then f -f * ∈ Q(g). Moreover this property is also generic in the sense that it does not hold only if the coefficients of the polynomials f and g j , j = 1, . . . , m, satisfy a set of polynomial equations! In other words the three conditions hold in a Zariski open set; for more details see Nie [14, Theorem 1.1, Theorem 1.2 and §4.2].

So in view of Proposition 3.6, one may expect that lim d→∞ ρk d = ρ k generically. On the other hand, given d ∈ N, identifying whether ρ k d = ρ k (or whether |ρ k d -ρ k | < ǫ for some given ǫ > 0, fixed) is a open issue. For instance, ρ k d = ρ k d+1 (as is the case in Examples 2 and 3 below) is not a guarantee that ρ k d = ρ k . We will also see in Section §4 that one may also approach as closely as desired an optimal solution of the ideal inverse problem (2.8) by asking y to be only a global ǫ-minimizer (with ǫ > 0 fixed), provided that ǫ is small enough.

In addition, more can be said by looking at the dual of (2.8).

The dual of the ideal inverse problem P. We now provide an explicit interpretation of the dual problems P * d in (3.5)-(3.6). Let M (K) be the space of finite Borel measures on K. Then obviously (3.5) is a relaxation of the following problem:

(3.20)      r 1 = max µ∈M(K) K (f (0) -f (x)) dµ(x) s.t. ± K x α dµ(x) ≤ 1, ∀ α ∈ N n d0 \ {0},
which, denoting by δ 0 the Dirac measure at x = 0, and by P (K) the space of Borel probability measures on K, can be rewritten as max

ν∈P (K),γ≥0 γ (δ 0 (f ) -ν(f )) s.t. ±γ (ν(x α ) -δ 0 (x α )) ≤ 1, ∀ α ∈ N n d0 ; ν(K) = γ.
Similarly, (3.6) is a relaxation of the following problem:

(3.21) r ∞ = max µ∈M(K)    K (f (0) -f (x)) dµ(x) : α∈N n d 0 \{0} K x α dµ ≤ 1    ,
or, again, equivalently, max

ν∈P (K),γ≥0    γ (δ 0 (f ) -ν(f )) : γ α∈N n d 0 |ν(x α ) -δ 0 (x α )| ≤ 1; ν(K) = γ    .
Hence, in the dual problems (3.20) and (3.21) one searches for a finite Borel measure µ which concentrates as much as possible on the set {x ∈ K : f (x) ≤ f (0)}, and such that its moments up to order d 0 are not too far from those of a measure supported at {0} ∈ K.

In fact, and as one might have expected, (3.20) (resp. (3.21)) is the dual of P in (2.8) with k = 1 (resp. with k = ∞). For instance, with k = 1, to see that weak duality holds, let f ∈ R[x] d0 and µ ∈ M (K) be an arbitrary feasible solution of (2.8) and (3.20), respectively. Then:

K (f (0) -f ) dµ = K ( f (0) -f )dµ ≤0 + K ( f -f ) dµ ≤ α∈N n d 0 \{0} | fα -f α | • K x α dµ(x) ≤ f -f 1 ,
i.e., weak duality holds and r 1 ≤ ρ 1 . We even have the following: Lemma 3.7. Let K in (1.1) be with nonempty interior and assume that Q(g) is Archimedean. Let ρ k be as in (2.8) with k = 1, ∞, and let z d = (z d α ) ∈ R s(d) be a nearly optimal solution of (3.5) (or (3.13)), e.g., with value L z (f (0

)-f ) ≥ ρ k d -1/d, for all d ∈ N. If lim inf d→∞ z d 0 < ∞ then lim d→∞ ρ k d = ρ k and (3.20
) has an optimal solution µ * ∈ M (K) which is supported on the set of global minimizers on K of the optimal solution f * ∈ R[x] d0 of (2.8) (which contains {0}). Hence either ρ k = 0 in which case 0 is an optimal solution of P, or ρ k > 0 and f * has a another global minimizer x = 0 on K with f (x) < f (0).

Proof. The proof for the case k = ∞ is omitted as very similar to that of the case k = 1. Consider the subsequence d i , i ∈ N, such that lim inf

d→∞ z d 0 = lim i→∞ z di 0 < ∞.
Using the Archimedean property (2.6) of Q(g), we proceed exactly as in the proof of Theorem 3.2 in [10, p. 57-59 ]. There is a infinite sequence z * = (z * α ), α ∈ N n , and a subsequence (still denoted d i for notational convenience), such that for every α ∈ N n , z di α → z * α . Moreover, from the convergence z di → z * , M d (g j z * ) 0 for every d ∈ N and every j = 0, 1, . . . , m; hence by Putinar's Theorem [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF], z * is the sequence of moments of a finite Borel measure µ * supported on K. Moreover, since |z di α | ≤ 1 for all α ∈ N n d0 \ {0}, we obtain

| K x α dµ * | = |z * α | = lim i→∞ |z di α | ≤ 1 ∀α ∈ N n d0 \ {0},
which proves that µ * is feasible for (3.20). Finally, by monotonicity of the sequence (ρ 1 d ), d ∈ N, and using ρ 1 d ≥ ρ 1 ≥ r 1 for all d,

r 1 ≤ ρ 1 ≤ lim d→∞ ρ 1 d = lim i→∞ ρ 1 di = lim i→∞ L z d i (f (0) -f ) = L z * (f (0) -f ) = K (f (0) -f )dµ * ,
which proves that µ * is an optimal solution of (3.20), and so r 1 = ρ 1 . Finally, since f * (0) = f (0),

ρ 1 = K (f (0) -f ) dµ * = K ( f * (0) -f * ) dµ * ≤0 + K ( f * -f ) dµ * ≤ f * -f 1 = ρ 1 ,
which implies µ * ({x : f * (x) -f * (0) > 0}) = 0, that is, the support of µ * is contained in the set of global minimizers of f * (which contains {0}). Therefore, if ρ 1 > 0 then necessarily there is another global minimizer 0 = x ∈ K of f * with f (x) < f (0), otherwise ρ 1 = (f (0) -f )dµ * = 0.

3.7. Convexity. One may wish to restrict to search for convex polynomials f ∈ R[x] d0 (no matter if f itself is convex). For instance if the g j 's are concave (so that K is convex) but f is not, one may wish to find the convex optimization problem whose y ∈ K is an optimal solution and with convex polynomial criterion f x T Ax + b T x + c for some real symmetric matrix A ∈ R n×n , some vector b ∈ R n and some scalar c ∈ R, then f (x) = 1 2 x T Ãx + bT x + c for some real symmetric matrix à ∈ R n×n , some b ∈ R n and some c ∈ R. In that case, in (3.1) it suffices to add constraint ∇ 2 f (x) = à 0, which is just a Linear Matrix Inequality (LMI). And therefore, again, (3.1) can be rewritten as a semidefinite program, namely (3.2)-(3.4) with the additional LMI constraint à 0.

∈ R[x] d0 closest to f . If d 0 > 2 then in (3.
Notice that for k = 1, 2, it also makes sense to search for f

∈ R[x] 2 even if f has degree d 0 > 2, i.e., if f (x) = c + b T x + 1 2 x T Ax + h(x) where h ∈ R[x]
does not contains monomials of degree smaller than 3. This means that one searches for the convex program with quadratic cost closest to f . So for instance, in the case where one searches for f ∈ R[x] 2 , and given y ∈ K let J(y) := {j ∈ {1, . . . , m} : g j (y) = 0} be the set of constraints that are active at y. If the g j 's that define K are concave then one may simplify (3.1). Writing f = 1 2 x T Ãx + bT x + c, and with k = 1, 2, (3.1) now reads:

ρ k := min Ã, b,λ f -f k s.t. Ã y + b = j∈J(y)
λ j ∇g j (y) Ã 0; λ j ≥ 0, j ∈ J(y).

So, as we did in the previous section, and possibly after the change of variable x ′ := xy, with no loss of generality one may and will assume that y = 0, in which case (3.23) simplifies to (3.23)

ρ k := min Ã, b,λ f -f k s.t. b = j∈J(0)
λ j ∇g j (0) Ã 0; λ j ≥ 0, j ∈ J(0), which in turn simplifies to (3.24)

ρ 1 = min à 0 à -A 1 + min λ≥0 b - j∈J(0) λ j ∇g j (0) 1 ρ ∞ = sup   min à 0 à -A ∞ , min λ≥0 b - j∈J(0) λ j ∇g j (0) ∞   .
Observe that (3.24) can be solved in two steps. One first solves the problem min λ≥0 b -j∈J(0) λ j ∇g j (0) k , which is a linear program with finite value, hence with an optimal solution. One next solves the problem min à 0 à -A k which computes the ℓ k -projection of A onto the closed convex cone of positive semidefinite matrices (a semidefinite program with an optimal solution). Lemma 3.8. Let K ⊂ R n be as in (1.1) with g j being concave for every j = 1, . . . , m. Then (3.23) has an optimal solution f * ∈ R[x] 2 and 0 is an optimal solution of the convex optimization problem P ′ : min{ f * (x) : x ∈ K}.

Proof. Let ( f , λ) (with f ∈ R[x] 2 ) be any feasible solution of (3.23). The constraint in (3.23) states that ∇L(0) = 0, where L ∈ R[x] is the Lagrangian polynomial x → L(x) := f (x) -j∈J(0) λ j g j (x), which is convex on K because the g j 's are concave, the λ j 's are nonnegative, and f is convex. Therefore ∇L(0) = 0 implies that 0 is a global minimizer of L on R n and a global minimizer of f on K because

(3.25) f (x) ≥ L(x) ≥ L(0) = f (0), ∀ x ∈ K.
It remains to prove that (3.23) has an optimal solution f * . But we have seen that (3.23) is equivalent to (3.24) for which an optimal solution can be found by solving a linear program and a semidefinite program.

So in this case where the g j 's are concave (hence K is convex), one obtains the convex programming problem with quadratic cost, whose criterion is the closest to f for the ℓ k -norm.

Global ǫ-optimality

One may be less demanding and ask y ∈ K (or 0 ∈ K after a change of variable) to be only a global ǫ-minimizer. That is, one searches for a polynomial f ∈ R[x] d0 as close as possible to f and such that f (x) -f (0) ≥ -ǫ for all x ∈ K and some ǫ > 0 fixed. Then we will see that one may approach as closely as desired an optimal solution of the ideal inverse problem (2.8). With K ⊂ [-1, 1] n as in (3.10), the analogue of Problem (3.1) reads: (4.1)

ρ k dǫ := min f ,σj ∈R[x] f -f k s.t. f (x) -f (0) + ǫ = m+n j=0 σ j (x) g j (x), ∀x ∈ R n f ∈ R[x] d0 ; σ j ∈ Σ[x] d-vj , j = 0, 1, . . . , m + n.
For instance, with k = 1 (3.2) now reads (4.2)

ρ 1 dǫ := min λ≥0, f ,Zj α∈N n d 0 \{0} λ α s.t. λ α + fα ≥ f α , ∀α ∈ N n d0 \ {0} λ α -fα ≥ -f α , ∀α ∈ N n d0 \ {0} Z 0 , B α + m+n j=1 Z j , C j α =    fα , if 0 < |α| ≤ d 0 0, if |α| > d 0 ǫ, if α = 0 Z j 0, j = 0, 1, . . . , m + n.
while its dual reads

(4.3)            (ρ 1 dǫ ) * = max u,v≥0,z -ǫz 0 + α∈N n d 0 \{0} f α (u α -v α ) (= L z (f (0) -f -ǫ)) s.t. u α + v α ≤ 1, ∀ α ∈ N n d0 \ {0} u α -v α + z α = 0, ∀α ∈ N n d0 \ {0} M d (z), M d-vj (g j z) 0, j = 1, . . . , m + n.
Again with no loss of generality and possibly after a change of variable, we assume that y = 0 ∈ K.

Lemma 4.1. Let K be as in (3.10) and let ρ k be the optimal value of the ideal inverse problem P in (2.8). Then for every fixed ǫ > 0 there exists

d ǫ ∈ N such that ρ k dǫ ≤ ρ k for all d ≥ d ǫ . Proof. Let f * ∈ R[x]
d0 be an optimal solution of the ideal inverse problem P with value ρ k = f -f * k . Observe that the polynomial x → f * (x) -f * (0) + ǫ is strictly positive on K and so by Theorem 2.2 it belongs to Q(g); and so it belongs to Q d (g) as soon as d ≥ d ǫ (for some d ǫ ∈ N). Hence f * is a feasible solution of (4.1) which implies the desired result ρ k ≥ ρ k dǫ for all d ≥ d ǫ . The following analogue of Theorem 3.3 shows that the optimal value ρ k dǫ of (4.1) is still helpful to bound the quantity f (0) -f * (where f * is the global optimum of problem P). Theorem 4.2. Assume that K in (3.10) has nonempty interior and let x * ∈ K be a global minimizer of P with optimal value f * . For every ǫ > 0 fixed, let fdǫ ∈ R[x] d0 be an optimal solution of (4.1) with optimal value ρ k dǫ . Then:

(a) 0 ∈ K is a global ǫ-minimizer of the problem f * dǫ = min x { fdǫ (x) : x ∈ K}. In particular, if ρ k dǫ = 0 then fdǫ = f and 0 is a global ǫ-minimizer of P.

(b) If k = 1 then f * ≤ f (0) ≤ f * + ǫ + ρ 1 dǫ . (c) If k = ∞ then f * ≤ f (0) ≤ f * + ǫ + s(d 0 ) ρ ∞ dǫ .
The proof is omitted as being a verbatim copy of that of Theorem 3.3 and using

f * = f (x * ) = f (x * ) -fd (x * ) + fd (x * ) -fd (0) ≥-ǫ + fd (0).
Concerning the canonical form associated with the ℓ 1 -norm we also have the following analogue of Theorem 3.4. Theorem 4.3. Assume that K in (3.10) has a nonempty interior and for every ǫ > 0, let fdǫ ∈ R[x] d0 be an optimal solution of (4.1) with optimal value ρ 1 dǫ for the ℓ 1 -norm. Then fdǫ is of the form:

(4.4) fdǫ (x) = f (x) + b ′ x + n i=1 λ * i x 2 i ,
for some vector b ∈ R n and some nonnegative vectors λ * ∈ R n , optimal solution of the semidefinite program:

ρ 1 dǫ := min λ,γ,b b 1 + n i=1 λ i s.t. f -f (0) + b ′ x + i=1 n λ i x 2 i + ǫ ∈ Q d (g), λ ≥ 0.
(And λ * = 0 if d 0 = 1.)

We end up with the analogue of Proposition 3.6 for the asymptotics as d → ∞. For every ǫ > 0, let us call P ǫ the analogue of problem P (= P 0 ), i.e., (4.5)

P ǫ : ρ k ǫ = min f ∈R[x] d 0 { f -f k : x → f (x) -f (y) + ǫ ∈ Psd d0 (K) }.
Proposition 4.4. For every ǫ > 0 fixed, Problem (4.5) has an optimal solution f * ǫ ∈ R[x] d0 , and ρ k ǫ = 0 if and only if y is a global ǫ-minimizer of P. The proof is similar to that of Theorem 2.8. Next, interestingly, we are able to relate (4.1) and the ideal inverse problem (2.8) as ǫ → 0. Proposition 4.5. Let K in (3.10) be with nonempty interior. Let y = 0 ∈ K and ρ k be the optimal value of the ideal inverse problem P in (2.8) and let fdǫ ∈ R[x] d0 (resp. f * ǫ ∈ R[x] d0 ) be any optimal solution of (4.1) (resp. (4.5)). (i) Let ǫ ℓ > 0, ℓ ∈ N, be such that ǫ ℓ → 0 as ℓ → ∞. Then every accumulation point f ∈ R[x] d0 of the sequence ( f * ǫ ℓ ) ⊂ R[x] d0 , ℓ ∈ N, is an optimal solution of the ideal inverse problem (2.8).

(ii) If for every ǫ ℓ > 0, d ℓ ∈ N is sufficiently large, every accumulation point of the sequence ( fd ℓ ǫ ℓ ) ⊂ R[x] d0 is an optimal solution of the ideal inverse problem (2.8).

Proof. (i) As f * ǫ ℓ -f k ≤ ρ k for all ℓ, the sequence ( f * ǫ ℓ ) ⊂ R[x] d0 , ℓ ∈ N, has accumulation points. So consider an arbitrary converging subsequence (still denoted ( f * ǫ ℓ ) for notational convenience) f * ǫ ℓ → f ∈ R[x] d0 , as ℓ → ∞. Observe that f * ǫ ℓ (x) -f * ǫ ℓ (0) + ǫ ℓ ≥ 0 for all x ∈ K and all ℓ ∈ N. With x ∈ K fixed, arbitrary, letting ℓ → ∞ yields f (x) -f (0) ≥ 0, and so x → f (x) -f (0) ∈ Psd d0 (K). Moreover, ρ k ǫ ℓ ≤ ρ k for all ℓ yields f -f k ≤ ρ k , which in turn implies that f is an optimal solution of the inverse problem (2.8). As the accumulation point f was arbitrary the result follows. The proof of (ii) is similar if one recalls that by Lemma 4.1, ρ k dǫ ℓ = f -fdǫ ℓ k ≤ ρ k for all ℓ and all d sufficiently large, say d ≥ d ℓ .

Hence, by asking y (= 0) ∈ K to be only a global ǫ-minimizer, one may obtain a polynomial fdǫ ∈ R[x] d0 as close as desired to an optimal solution of the ideal inverse problem provided that ǫ is sufficiently small and d is sufficiently large.

K = {x ∈ R 2 : x 1 x 2 ≥ 1; 1/2 ≤ x ≤ 2 }.
The polynomial f is convex and the set K is convex as well, but the polynomials that define K are not all concave. That is, P is a convex optimization problem, but not a convex programming problem. The point y = (1, 1) ∈ K is a global minimizer and the KKT conditions at y are satisfied with λ = (1, 0, 0) ∈ R 3 , i.e., ∇f (x) -λ 1 ∇g 1 (x) = 0 with x = (1, 1) and λ 1 = 1. However, the Lagrangian x → L(x) := f (x) -f * -λ 1 g 1 (x) = x 1 + x 2 -1 -x 1 x 2 , is not convex and (1, 1) is not a global minimizer of L on R 2 . This example just illustrates the fact that even in the convex case where the g j 's are not concave, the KKT conditions do not provide a certificate of global optimality, contrary to "convex programming" where since L is now convex, obviously using L(x) ≥ L(y) = 0 (because ∇L(y) = 0), f (x) -f * ≥ L(x) ≥ L(y) = 0, whenever x ∈ K, and so f (x) ≥ f * for all x ∈ K, the desired certificate of global optimality.

Next, if we now use the test of inverse optimality with d = 1, one searches for a polynomial fd of degree at most d 0 = 1, and such that fd (x) -fd (1, 1) = σ 0 (x) + σ 1 (x)(x 1 x 2 -1) + 2 i=1 ψ i (x)(2 -x i ) + φ i (x)(x i -1/2), for some s.o.s. polynomials σ 1 , ψ i φ i ∈ Σ[x] 0 and some s.o.s. polynomial σ 0 ∈ Σ[x] 1 . But then necessarily σ 1 = 0 and ψ i , φ i are constant, which in turn implies that σ 0 is a constant polynomial. A straightforward calculation shows that f1 (x) = 0 for σ ∈ Σ[x] 1 , λ, γ ∈ R, and which minimizes the ℓ 1 -norm A -à 1 . This is an inverse optimization problem with structural constraints as described in Section 3.4 (since we search for a quadratic form and not an arbitrary quadratic polynomial f2 ). Hence, solving (3.18) for n = 5 with y as above, we find that à = 1 2       0 2/3 2/3 1 1 2/3 0 2/3 1 1 2/3 2/3 0 1 1

1 1 1 0 1 1 1 1 1 0      
, that is, only the entries (i, j) ∈ {(1, 2), (1, 3), (2, 3)} are modified from 1/2 to 1/3.

Conclusion

We have presented a paradigm for inverse polynomial optimization. Crucial is Putinar's Positivstellensatz which provides us with the desired certificate of global optimality for a given feasible point y ∈ K and a candidate criterion f . In addition, to some extent, the size of the certificate can be adapted to the computational capabilities available. Finally, and remarkably, when using the ℓ 1 -norm the resulting inverse optimal criterion f has a simple and explicit canonical form. We hope that the concept of inverse optimization will receive more attention from the optimization community as it could even provide an alternative stopping criterion at the current iterate y ∈ K of any local optimization algorithm for solving the original problem P.

2. 2 .

 2 The ideal inverse problem. Let P be the global optimization problem f * = min x {f (x) : x ∈ K} with K ⊂ R n as in (1.1), and f ∈ R[x] d0 where d 0

3. 1 .

 1 A practical inverse problem. With d ∈ N fixed, consider the following optimization problem P d : (3.1)

  nonempty interior. Then there is no duality gap between the semidefinite programs (3.2) and (3.5), (3.3) and (3.6), and (3.4) and (3.7). Moreover, all semidefinite programs (3.2), (3.3) and (3.4) have an optimal solution fd ∈ R[x] d0 .

  d and let y ∈ K with I 1 := {i : y i = 0} and I 2 := {i : y i = 1}. Then an optimal solution fd ∈ R[x] d0 of the inverse problem (3.1) for the ℓ 1 -norm, is of the form

1 )

 1 it suffices to add the additional Putinar's certificate(3.22) (x, u) → u T ∇ 2 f (x) u = m j=0 ψ j (x, u) g j (x) + ψ m+1 (x, u)(1u 2 ), with ψ m+1 ∈ R[x, u] and ψ j ∈ Σ d-vj [x,u], for all j = 0, 1, . . . , m. Indeed, (3.22) is a Putinar's certificate of convexity for f on K, with degree bound d. As the coefficients of the polynomial (x, u) → u T ∇ 2 f (x)u are linear in the coefficients of f , (3.22) will translate into additional semidefinite constraints in (3.2). If d 0 ≤ 2, i.e. if f (x) = 1 2

4. 1 .

 1 Illustrative examples and discussion. We here provide some simple illustrative examples and show that the representation of the set K may be important for getting a Putinar certificate faster.Example 1. Let n = 2 and consider the optimization problem P : f * = min x {f (x) :x ∈ K} with x → f (x) = x 1 + x 2 , and

2 .

 2 Notation, definitions and preliminaries 2.1. Notation and definitions. Let R[x] (resp. R[x] d ) denote the ring of real polynomials in the variables x = (x 1 , . . . , x n ) (resp. polynomials of degree at most d), whereas Σ[x] (resp. Σ[x] d ) denotes its subset of sums of squares (s.o.s.) polynomials (resp. of s.o.s. of degree at most 2d). For every α ∈ N n the notation x α stands for the monomial x α1 1 • • • x αn n and for every i ∈ N, let N p d

  one may invoke same arguments as those used in Lasserre and Netzer [12, Lemma 4.1, 4.2], to obtain that for very α ∈ N n 2d with |α| > 1,

all x, and so ρ 1 1 = 2. And indeed this is confirmed when solving 3 (3.5) with d = 1. Solving again (3.5) with now d = 2 yields ρ 1 2 = 2 (no improvement) and with d = 3 we obtain the desired result ρ 1 3 = 0. On the other hand, if now K has the representation:

then the situation differs because in fact

i.e., f -f * has a Putinar's certificate with degree bound d = 1. Hence the test of inverse optimality yields ρ 1 1 = 0 with f1 = f . The above example illustrates that the representation of K may be important.

Example 2. Again consider Example 1 but now with y = (1.1, 1/1.1) ∈ K, which is not a global optimum of f on K any more. By solving (3.5) with d = 1 we still find ρ 1 1 = 2 (i.e., f1 = 0), and with d = 2 we find ρ 2 ≈ 0.1734 and f2 (x) ≈ 0.8266 x 1 + x 2 . And indeed by solving (using GloptiPoly) the new optimization problem with criterion f2 we find the global minimizer (1.1, 0.9091) ≈ y. With d = 3 we obtains the same value ρ 1 3 = 0.1734, suggesting (but with no guarantee) that f2 is already an optimal solution of the ideal inverse problem.

Example 3. Consider now the disconnected set

2 <= 3} and the non convex criterion x → f (x) := -x 1 -x 2 2 for which x * = (-0.618, -1/0.618) ∈ ∂K is the unique global minimizer. Let y := (-0.63, -1/0.63) ∈ ∂K for which the constraint x 1 x 2 ≥ 1 is active. At steps d = 2 and d = 3 one finds that fd = 0 and ρ 1 d = f 1 . That is, y is a global minimizer of the trivial criterion f(x) = 0 for all x, and cannot be a global minimizer of some non trivial polynomial criterion. Now let y = (-0.63, -√ 3 -0.63 2 ) so that the constraint x 2 1 + x 2 2 <= 3 is active. With obtain ρ 1 1 = f 1 and f1 = 0. With d = 2 we obtain f2 = 1.26 x 1 -x 2 2 . With d = 3 we obtain the same result, suggesting (but with no guarantee) that f2 is already an optimal solution of the ideal inverse optimization problem.

Example 4. Consider the MAXCUT problem max{x ′ Ax : x 2 i = 1, i = 1, . . . , n} where A = A ′ ∈ R n×n and A ij = 1/2 for all i = j. For n odd, an optimal solution is y = (y j ) with y j = 1, j = 1, . . . ⌈n/2⌉, and y j = -1 otherwise. However, the first semidefinite relaxation max {λ :

provides the lower bound -n/2 (with famous Goemans-Williamson ratio guarantee). So y cannot be obtained from the first semidefinite relaxation even though it is an optimal solution. The inverse optimization problem reads: Find the quadratic form x → x ′ Ãx such that x ′ Ãxy ′ Ãy = σ + n j=1 γ i (x 2 i -1), for some 3 To solve (3.5) we have used the GloptiPoly software of Henrion et al. [START_REF] Henrion | Gloptipoly 3: moments, optimization and semidefinite programming[END_REF], and dedicated to solving the Generalized Problem of Moments whose problem (3.5) is only a special case.