Traditional approaches for accommodating such combinatorial constraints have been to introduce binary variables and solve the resulting mixed-integer programming problem. Here we instead construct a semidefinite programming problem relaxation for (QPO); we denote this relaxation (rSDP). For (rSDP), a symmetric lifting procedure for homogenized linear equalities has been developed. With a general set of orthogonality relationships, the optimal objective function value of (rSDP) serves as a lower bound on (QPO). Also, placing (rSDP) into an enumerative algorithm is shown to be a useful strategy for limiting the search space.
Finally a financial application of (QPO), the portfolio rebalancing problem in the presence of transaction costs, is fully explored and computational results are presented. In this application, pairwise orthogonality constraints are imposed between buying and selling decisions. Information about the optimal portfolio is deduced from the (rSDP) solution matrix and the geometry of the feasible region.
Download the thesis, postscript or pdf or gzipped postscript.