INVARIANCE UNDER AFFINE TRANSFORMATION IN SEMIDEFINITE PROGRAMMING RELAXATION FOR POLYNOMIAL OPTIMIZATION PROBLEMS

被引：0
作者：
Waki, Hayato [1 ]
Muramatsu, Masakazu [1 ]
Kojima, Masakazu [2 ]
机构：
[1] Univ Electrocommun, Dept Comp Sci, Chofu, Tokyo 1828585, Japan
[2] Tokyo Inst Technol, Dept Math & Comp Sci, Meguro Ku, Tokyo 1528552, Japan
来源：
PACIFIC JOURNAL OF OPTIMIZATION | 2009年 / 5卷 / 02期
关键词：
polynomial optimization problem; semidefinite programming relaxation; sum of squares relaxation; invariance; affine transformation; polynomial SDP; SQUARES RELAXATIONS; GLOBAL OPTIMIZATION; SUMS; MINIMUM; MATLAB;
D O I：
暂无
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
Given a polynomial optimization problem (POP), any nonsingular affine transformation on its variable vector induces an equivalent POP. Applying Lasserre's SDP relaxation (SIAM J.Opt. 11:796-817, 2001] to the original and the transformed POPs, we have two SDPs. This paper shows that these two SDPs are isomorphic to each other under a nonsingular linear transformation, which maps the feasible region of one SDP onto that of the other isomorphically and preserves their objective values. This fact means that the SDP relaxation is invariant under any nonsingular affine transformation.
引用
收藏
页码：297 / 312
页数：16
相关论文
共 23 条
[1]  
de Klerk E, 2006, 2006026 TILB U CTR E
[2]   Convergent relaxations of polynomial matrix inequalities and static output feedback [J].
Henrion, D ;
Lasserre, JB .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2006, 51 (02) :192-202
[3]   GloptiPoly: Global optimization over polynomials with Matlab and SeDuMi [J].
Henrion, D ;
Lasserre, JB .
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2003, 29 (02) :165-194
[4]  
Henrion D., 2005, LECT NOTES CONTROL I
[5]  
Hol C.W., 2004, P S MATH THEOR NETW
[6]   Generalized Lagrangian duals and sums of squares relaxations of sparse polynomial optimization problems [J].
Kim, S ;
Kojima, M ;
Waki, H .
SIAM JOURNAL ON OPTIMIZATION, 2005, 15 (03) :697-719
[7]   Recognizing underlying sparsity in optimization [J].
Kim, Sunyoung ;
Kojima, Masakazu ;
Toint, Philippe .
MATHEMATICAL PROGRAMMING, 2009, 119 (02) :273-303
[8]   A general framework for convex relaxation of polynomial optimization problems over cones [J].
Kojima, M ;
Kim, S ;
Waki, H .
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, 2003, 46 (02) :125-144
[9]  
KOJIMA M, 2003, D397 TOK I TECHN DEP, P152
[10]   An extension of sums of squares relaxations to polynomial optimization problems over symmetric cones [J].
Kojima, Masakazu ;
Muramatsu, Masakazu .
MATHEMATICAL PROGRAMMING, 2007, 110 (02) :315-336
123