LAGRANGIAN-CONIC RELAXATIONS, PART I: A UNIFIED FRAMEWORK AND ITS APPLICATIONS TO QUADRATIC OPTIMIZATION PROBLEMS
- 주제(키워드) Lagrangian-conic relaxation , completely positive programming relaxation , doubly nonnegative relaxation , convexification , quadratic optimization problems , exploiting sparsity
- 주제(기타) 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
- 발행년도 2018
- URI http://www.dcollection.net/handler/ewha/000000151385
- 본문언어 영어
초록/요약
In Part I of a series of study on Lagrangian-conic relaxations, we introduce a unified framework for conic and Lagrangian-conic relaxations of quadratic optimization problems (QOPs) and polynomial optimization problems (POPs). The framework is constructed with a linear conic optimization problem (COP) in a finite dimensional Hilbert space, where the cone used is not necessarily convex. By imposing a copositive condition on the COP, we establish fundamental theoretical results for the COP, its (convex hull) conic relaxations, its Lagrangian-conic relaxations, and their duals. A linearly constrained QOP with complementarity constraints and a general POP can be reduced to the COP satisfying the copositivity condition. Thus the conic and Lagrangian-conic relaxations of such a QOP and POP can be discussed in a unified manner. The Lagrangian-conic relaxation takes a particularly simple form involving only a single equality constraint together with the cone constraint, which is very useful for designing efficient numerical methods. As demonstration of the elegance and power of the unified framework, we present the derivation of the completely positive programming relaxation, and a sparse doubly nonnegative relaxation for a class of a linearly constrained QOPs with complementarity constraints. The unified framework is applied to general POPs in Part II.
more