Higher-Order Continuous Formulations For Discrete Optimization Problems

Abstract

This dissertation is focused on the developing a set of novel mathematical programming formulations for a class of problems related to community detection in networks. The proposed approach is based on the extension of quadratic formulations that were proposed by Motzkin and Strauss in 1967. These formulations are related to the Maximum Clique problem, which asks to find the largest complete subgraph. The main result is the establishing of a family of higher-order polynomial optimization problems which exhibits a hierarchical structure of local and global optima, different from previously known hierarchies in the field of optimization. Additional results obtained include a tighter description for the set of local and global maxima of the proposed formulations, improving the previously obtained results for the original Motzkin-Strauss problem as a side-result. The second part of the thesis is dedicated to a discussion on the regularized version of the proposed formulations, analogous to what was established by Bomze in 1997 for the original Motzkin-Strauss formulation. We discuss the required properties of the regularization and analyze the different options regarding the selection of the regularization term. A set of conditions is established for the regularization term, so that the required properties are satisfied. Finally, a set of computational experiments is presented to evaluate the performance of the proposed formulations over the set of standard benchmarks.