An algorithm for semi-infinite polynomial optimization

Publication date 20 February 2013

Abstract: We consider the semi-infinite optimization problem:

f^{*} := m i n_{x i n X} : f (x) : g (x, y), l e q, 0, : f o r a l l y i n Y_{x}

, where

f, g

are polynomials and

X s u b s e t R^{n}

as well as

Y_{x} s u b s e t R^{p}

,

x i n X

, are compact basic semi-algebraic sets. To approximate

f^{*}

we proceed in two steps. First, we use the "joint+marginal" approach of the author to approximate from above the function

x m a p s t o P h i (x) = s u p g (x, y) : y i n Y_{x}

by a polynomial

P h i_{d} g e q P h i

, of degree at most

2 d

, with the strong property that

P h i_{d}

converges to

P h i

for the

L_{1}

-norm, as

d o i n f t y

(and in particular, almost uniformly for some subsequence

(d_{e} l l)

,

e l l i n N

). Then we solve the polynomial optimization problem

f_{d}^{*} = m i n_{x i n X} f (x) : P h i_{d} (x) l e q 0

via a (by now standard) hierarchy of semidefinite relaxations. It turns out that the optimal value

f_{d}^{*} g e q f^{*}

converges to

f^{*}

as

d o i n f t y

. In practice we let

d

be fixed, small, and relax the constraint

P h i_{d} l e q 0

to

P h i_{d} (x) l e q e p s i l o n

with

e p s i l o n > 0

, allowing to change

e p s i l o n

dynamically.

Recommendations

Cites work

Cited in

(17)

Describes a project that uses

Uses Software

This page was built for publication: An algorithm for semi-infinite polynomial optimization