Solving a quadratic programing problem subject to orthogonality constraints

Steve Braun

PhD Thesis, December 2001

Rensselaer Polytechnic Institute

Advisor: John Mitchell

Download the thesis, postscript or pdf or gzipped postscript.

Abstract:

This thesis considers quadratic programming problems where combinatorial constraints are directly imposed on the continuous decision variables using a set of pairwise orthogonality relationships; we denote this problem (QPO). These orthogonality constraints are non-convex in nature, meaning that the resulting combinatorial optimization problem is NP-hard. The addition of orthogonality constraints on continuous variables is shown to encompass a wide range of modeling choices.

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.

Library listing