Theoretical Advances in Robust Optimization, Feature Selection, and Biomarker Discovery

Abstract

This dissertation advances the field of optimization by providing theoretical advances in robust optimization, feature selection, and biomarker discovery.

A number of bounds and expressions are derived for probabilistic robust optimization, many of which extend the scope of the methodology. A priori and a posteriori bounds are derived for constraints with parameters subject to unknown distributions with bounded support. Cases include distributions with limited information about their expected values, possibly asymmetric distributions with known expected values, and symmetric distributions with known expected values. A priori bounds are derived for constraints with parameters subject to known or conservatively attributed distributions which are possibly unbounded and symmetric or asymmetric. A posteriori expressions are derived for constraints with parameters subject to normal, uniform, discrete, gamma, chi-squared, Erlang, or exponential distributions. The theoretical and computational behaviors of the bounds are thoroughly explored, and computational case studies demonstrate the stark improvements gained by utilizing the bounds at low probabilities of constraint violation as compared to worst-case robust optimization or existing bounds. A framework for formulating cone representable uncertainty sets and deriving their associated robust counterparts for robust optimization is also presented. The robust counterparts for constraints subject to uncertainty sets with halfspace constraints are derived and used to introduce linear cuts to existing uncertainty sets. Appropriate robust counterparts for constraints with both bounded and unbounded uncertain parameters are provided.

Feature selection through the use of support vector machines is reexamined in the context of global optimization theory. Insights from using global optimization lead to the development of new feature selection criteria for various SVM formulations and a new reductive algorithm; computational experiments on benchmark datasets for classification demonstrate that the new criterion outperforms current state-of-the-art methods using existing algorithms and with the new algorithm. Feature selection is then performed by formulated and solving a new mixed-integer linear optimization model. Computational experiments which evaluate selection accuracy and stability are discussed which display the high performance of the new approach. An application of feature selection methods to the experimental and computational determination of protein biomarkers for temporal analysis and clinical endpoints of chronic periodontitis is also presented.