Some Fundamental Properties of Successive Convex Relaxation Methods on LCP and Related Problems

被引：0
作者：
Masakazu Kojima
Levent Tunçel
机构：
[1] Tokyo Institute of Technology,Department of Mathematical and Computing Sciences
[2] University of Waterloo,Department of Combinatorics and Optimization, Faculty of Mathematics
来源：
Journal of Global Optimization | 2002年 / 24卷
关键词：
Nonconvex quadratic optimization; Linear complementarity problem; Semidefinite programming; Global optimization; SDP relaxation; Convex relaxation; Lift-and-project procedures;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
General successive convex relaxation methods (SRCMs) can be used to compute the convex hull of any compact set, in an Euclidean space, described by a system of quadratic inequalities and a compact convex set. Linear complementarity problems (LCPs) make an interesting and rich class of structured nonconvex optimization problems. In this paper, we study a few of the specialized lift-and-project methods and some of the possible ways of applying the general SCRMs to LCPs and related problems.
引用
收藏
页码：333 / 348
页数：15
相关论文
共 23 条
  • [1] Balas E.S.(1993)A lift-and-project cutting plane algorithm for mixed 0-1 programs Mathematical Programming 58 295-323
  • [2] Ceria S.(2001)Elementary closures for integer programs Operations Research Letters 28 1-8
  • [3] Cornuéjols G.(2000)Cones of matrices and successive convex relaxations of nonconvex sets SIAM J. Optimization 10 750-778
  • [4] Cornuéjols G.(2000)Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization problems Mathematical Programming 89 79-111
  • [5] Li Y.(1991)Cones of matrices and set-functions and 0-1 optimization SIAM J. Optimization 1 166-190
  • [6] Kojima M.(1988)Global optimization approach to the linear complementarity problem SIAM J. Scientific and Statistical Computing 9 341-353
  • [7] Tunçel L.(1990)A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems SIAM J. Discrete Mathematics 3 411-430
  • [8] Kojima M.(1998)Enumeration approach for linear complementarity problems based on a reformulation-linearization technique J. of Optim. Theory and Applications 99 481-507
  • [9] Tunçel L.(1997)Centers of monotone generalized complementarity problems Mathematics of Operations Research 22 969-976
  • [10] Lovász L.(1999)A branch-and-cut method for 0-1 mixed convex programming Mathematical Programming 86 515-532
123