reformulation-linearization technique

Semidefinite Programming versus the Reformulation-Linearization Technique for Nonconvex Quadratically Constrained Quadratic Programming

Categories Global Optimization Theory, Semi-definite Programming Tags , ,

We consider relaxations for nonconvex quadratically constrained quadratic programming (QCQP) based on semidefinite programming (SDP) and the reformulation-linearization technique (RLT). From a theoretical standpoint we show that the addition of a semidefiniteness condition removes a substantial portion of the feasible region corresponding to product terms in the RLT relaxation. On test problems we show that … Read more

Computable representations for convex hulls of low-dimensional quadratic forms

Categories Bound-constrained Optimization, Global Optimization Theory Tags , ,

Let C be the convex hull of points {(1;x)(1,x’)| x \in F\subset R^n}. Representing or approximating C is a fundamental problem for global optimization algorithms based on convex relaxations of products of variables. If n