Inverse polynomial optimization

Abstract: We consider the inverse optimization problem associated with the polynomial program f^*=min {f(x): xin K}

a n d a g i v e n c u r r e n t f e a s i b l e s o l u t i o n

yin K

. W e p r o v i d e a s y s t e m a t i c n u m e r i c a l s c h e m e t o c o m p u t e a n i n v e r s e o p t i m a l s o l u t i o n . T h a t i s, w e c o m p u t e a p o l y n o m i a l

ilde{f}

(w h i c h m a y b e o f s a m e d e g r e e a s

f

i f d e s i r e d) w i t h t h e f o l l o w i n g p r o p e r t i e s : (a)

y

i s a g l o b a l m i n i m i z e r o f

ilde{f}

o n

K

w i t h a P u t i n a r^{'} s c e r t i f i c a t e w i t h a n a p r i o r i d e g r e e b o u n d

d

f i x e d, a n d (b),

ilde{f}

m i n i m i z e s

Vert f- ilde{f}Vert

(w h i c h c a n b e t h e

ell_1

,

ell_2

o r

ell_infty

- n o r m o f t h e c o e f f i c i e n t s) o v e r a l l p o l y n o m i a l s w i t h s u c h p r o p e r t i e s . C o m p u t i n g

ilde{f}_d

r e d u c e s t o s o l v i n g a s e m i d e f i n i t e p r o g r a m w h o s e o p t i m a l v a l u e a l s o p r o v i d e s a b o u n d o n h o w f a r i s

f(y)

f r o m t h e u n k n o w n o p t i m a l v a l u e

f^*

. T h e s i z e o f t h e s e m i d e f i n i t e p r o g r a m c a n b e a d a p t e d t o t h e c o m p u t a t i o n a l c a p a b i l i t i e s a v a i l a b l e . M o r e o v e r, i f o n e u s e s t h e

ell_1

- n o r m, t h e n

ilde{f}$ takes a simple and explicit canonical form. Some variations are also discussed.

Recommendations

Cited in

(6)

This page was built for publication: Inverse polynomial optimization