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

  • 翁 之翊

Student thesis: Master's Thesis


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 Award2014 Jul 25
Original languageEnglish
SupervisorRuey-Lin Sheu (Supervisor)

Cite this