Duality Gap Estimation for Box Constrained Quadratic Programs via Weighted Distance Measures

Abstract

In this thesis we estimate the gap between a box constrained quadratic program and its SDP relaxation The problem includes the binary quadratic program as a special case and is thus in general NP-hard Applying the saddle point theorem we show that the duality gap can be estimated by a function $delta_{W}( heta)$ measuring a weighted distance between an affine subspace $C^*$ and some parametrized box $Lambda^{*}( heta)$ Incorporating a technique called the hyperplane arrangement in discrete geometry with various choices of parameters and weights we are able to tighten the bound for the gap Illustrative examples based on heuristic strategies show how a better bound can be chosen

Date of Award	2014 Jul 25
Original language	English
Supervisor	Ruey-Lin Sheu (Supervisor)