LAGRANGIAN-CONIC RELAXATIONS, PART II: APPLICATIONS TO POLYNOMIAL OPTIMIZATION PROBLEMS
- 주제(키워드) polynomial optimization problem , moment cone relaxation , SOS relaxation , a hierarchy of the Lagrangian-SDP relaxations
- 주제(기타) Operations Research & Management Science; Mathematics, Applied
- 설명문(일반) [Arima, Naohiko] Chuo Univ, Res & Dev Initiat, Bunkyo Ku, 1-13-27 Kasuga, Tokyo 1128551, Japan; [Arima, Naohiko] Chuo Univ, JST CREST, Bunkyo Ku, 1-13-27 Kasuga, Tokyo 1128551, Japan; [Kim, Sunyoung] Ewha W Univ, Dept Math, 52 Ewhayeodae Gil, Seoul 120750, South Korea; [Kojima, Masakazu] Chuo Univ, Dept Ind & Syst Engn, Tokyo 1920393, Japan; [Toh, Kim-Chuan] Natl Univ Singapore, Dept Math, 10 Lower Kent Ridge Rd, Singapore 119076, Singapore
- 관리정보기술 faculty
- 등재 SCIE
- 발행기관 YOKOHAMA PUBL
- 발행년도 2019
- 총서유형 Journal
- URI http://www.dcollection.net/handler/ewha/000000165998
- 본문언어 영어
초록/요약
We present a moment cone (MC) relaxation and a hierarchy of Lagrangian-SDP relaxations of polynomial optimization problems (POPs) using the unified framework established in Part I. The MC relaxation is derived for a POP of minimizing a polynomial subject to a nonconvex cone constraint and polynomial equality constraints. It is an extension of the completely positive programming relaxation for QOPs. Under a copositivity condition, we characterize the equivalence of the optimal values between the POP and its MC relaxation. A hierarchy of Lagrangian-SDP relaxations, which is parameterized by a positive integer w, is proposed for an equality constrained POP. It is obtained by combining Lasserre's hierarchy of SDP relaxation of POPs and the basic idea behind the conic and Lagrangian-conic relaxations from the unified framework. We prove under a certain assumption that the optimal value of the Lagrangian-SDP relaxation with the Lagrangian multiplier lambda and the relaxation order w in the hierarchy converges to that of the POP as lambda ->infinity and omega ->infinity The hierarchy of Lagrangian-SDP relaxations is designed to be used in combination with the bisection and 1-dimensional Newton methods, which was proposed in Part I, for solving large-scale POPs efficiently and effectively.
more