Solving Cardinality Constrained Quadratic Optimization Problems Using the Framework of Interval Branch and Bound

Many real-world problems in engineering, statistics, social sciences, and economics can be modeled as continuous global optimization problems. Sometimes, problems also require us to choose only a handful of parameters from a large number of available parameters, resulting in a cardinality-constraint ensuring that we only select a small number of parameters in the final optimal solution. These problems can be modeled as mixed integer optimization problems by introducing some binary variables to handle the cardinality-constraint. But sometimes this re-formulation may not be equivalent to the original problem with cardinality-constraint. The following two problems can be formulated as global optimization problems subject to a cardinality-constraint.Best Subset Selection is a classical problem in statistics that requires choosing a subset from a larger number of available variables to be included in the model which minimizes the residual sum of squares in the linear regression. Sparse Portfolio Selection requires choosing optimal proportions of the assets to be included in the portfolio while restricting the number of assets included, to minimize the risk for a desired return. In this thesis, we solve the above two problems by dealing with cardinality-constraint in the original primal space itself, using the framework of interval branch and bound. Interval branch and bound is a well-known method to solve global optimization problems even when the feasible set is non-convex and the goal is to find all the minimizers of the problem. Firstly, we modified the main features of the interval branch and bound to treat the cardinality-constraint effectively. The resulting algorithm gives a procedure to enumerate all the candidate solutions and discard the sub-optimal nodes by using deletion conditions to find an optimal solution. The algorithm converges in a finite number of iterations. Secondly, we introduced a procedure to find the lower bound of a convex quadratic function for a given node by solving the linear system resulting from the first-order necessary conditions. The procedure incorporates a strategy of recycling the parent node's echelon form to find the function's lower bounds for a sequence of child nodes while maintaining the global convergence of the algorithm. We also proposed a sub-optimal algorithm to solve the Best Subset Selection problem at a low computational cost. The proposed algorithm has also been used as a feasibility sampling procedure to get good-quality upper bounds within the interval branch and bound.Lastly, we extended our framework to include special linear constraints from the Sparse Portfolio Selection problem and demonstrated the applicability of our procedure to solve it. The numerical experiments validate the effectiveness of our methods to solve these problems.