Name
Abstract | ||
|---|---|---|
Let F be a compact subset of the n-dimensional Euclidean space Rn represented by (finitely or infinitely many) quadratic inequalities. We propose two methods, one based on successive semidefinite programming (SDP) relaxations and the other on successive linear programming (LP) relaxations. Each of our methods generates a sequence of compact convex subsets Ck (k = 1, 2, . . .) of Rn such that (a) the convex hull of $F \subseteq C_{k+1} \subseteq C_k$ (monotonicity), (b) $\cap_{k=1}^{\infty} C_k = \text{the convex hull of F (asymptotic convergence). Our methods are extensions of the corresponding Lovász--Schrijver lift-and-project procedures with the use of SDP or LP relaxation applied to general quadratic optimization problems (QOPs) with infinitely many quadratic inequality constraints. Utilizing descriptions of sets based on cones of matrices and their duals, we establish the exact equivalence of the SDP relaxation and the semi-infinite convex QOP relaxation proposed originally by Fujie and Kojima. Using this equivalence, we investigate some fundamental features of the two methods including (a) and (b) above. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1137/S1052623498336450 | SIAM Journal on Optimization |
Keywords | Field | DocType |
convex hull,sdp relaxation,linear ma- trix inequality,nonconvex quadratic optimization problem,nonconvex sets,successive convex relaxations,semidefinite programming,lp relaxation,quadratic inequality,exact equivalence,bilinear matrix inequality,general quadratic optimization problem,global optimization,compact convex,semi-infinite programming,compact subset,semi-infinite convex qop relaxation,quadratic inequality constraint,linear program,euclidean space,quadratic optimization,linear matrix inequality | Monotonic function,Discrete mathematics,Mathematical optimization,Combinatorics,Semi-infinite programming,Convex hull,Quadratic programming,Linear programming relaxation,Successive linear programming,Linear matrix inequality,Mathematics,Semidefinite programming | Journal |
Volume | Issue | ISSN |
10 | 3 | 1052-6234 |
Citations | PageRank | References |
35 | 5.81 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Masakazu Kojima | 1 | 1603 | 222.51 |
| Levent Tunçel | 2 | 429 | 72.12 |