Copositive programming approaches for robust optimization and Löwner-John ellipsoid problems

This thesis primarily focuses on studying the copositive programming reformulations of difficult optimization problems, using them to approximate the original problem, and comparing the performance of the resulting approximations with other approximation schemes. We first study the robust quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under reasonable assumptions, we show that these problems are amenable to exact copositive programming reformulations. The resultant convex optimization problems are NP-hard but admit a conservative semidefinite programming (SDP) approximation that can be solved efficiently. We prove that this approximation is stronger than the popular S-Procedure for problem instances with only continuous uncertainty. We also show that all results can be extended to the two-stage robust optimization setting if the problem has complete recourse. We assess the effectiveness of our proposed SDP reformulations and demonstrate their superiority over the state-of-the-art solution schemes for least squares, project management, and multi-item newsvendor problems. Next, we study the problem of finding Lowner-John ellipsoid, i.e., an ellipsoid with minimum volume that contains a given convex set. We reformulate the problem as a generalized copositive program, and use that reformulation to derive tractable SDP approximations for instances where the set is defined by affine and quadratic inequalities. We prove that our method always provides an ellipsoid of the same or lower volume than the one obtained by scaling the maximum volume inscribed ellipsoid, as well as the one provided by the application of the S-procedure. We provide empirical comparisons with the exact solution scheme, as well as other state-of-the-art approximation schemes. We apply our method to find improved decision rules for two-stage robust optimization problems, and to find ellipsoidal approximations to the set of reachable states in a linear dynamical system. The final problem that we consider is performing marginal inference in graphical models. Graphical models are used to represent probabilistic relations between different uncertain parameters. Marginal inference refers to computing the marginal distribution of each uncertain parameter in the graphical model. The complexity of exact marginal inference algorithms in graphical models is exponential in the treewidth of the underlying graph. We develop a method to perform approximate marginal inference on discrete graphical models by modifying the graph to a new graph of lower treewidth. We prove error bounds on the approximate inference solution compared to the exact solution. We formulate the problem of finding parameters of the new graph which gives the tightest error bounds as a linear program (LP). The number of constraints in the LP grows exponentially with the number of nodes. To solve this issue, we develop a row generation algorithm to solve the LP.Operations Research and Industrial Engineerin