UC Berkeley

Conic quadratic functions arise often when modeling uncertainty and risk-aversion, and are used in many fields including finance, machine-learning and robotics. Such functions are convex, and thanks to substantial efforts over the past two decades in developing techniques for convex problems, large conic quadratic optimization problems can be solved efficiently in practice. However, many decision-making problems involving logical choices are discrete in nature, and thus non-convex. Despite considerable improvements in our ability to solve mixed-integer linear optimization problems (MILO), their nonlinear and conic counterparts are still poorly understood and considered intractable.

Most of the advances in solving mixed-integer nonlinear optimization (MINLO) were obtained by adapting techniques used for linear discrete optimization. One of the first approaches proposed was to construct a linearization of the nonlinear terms and solving the optimization problem as a MILO, but since such approaches solve a relaxation of the original problem, they may fail to find optimal solutions. More recent approaches that have proved successful involve using linear outer approximations with extended formulations, or using mixed-integer rounding and lift-and-project cuts, which where original proposed for MILO. However, such approaches based on previous results for MILO may fail to consider and exploit the specific structure of the nonlinear discrete problems.

In this dissertation, we study the structures specific to nonlinear mixed-integer optimization. Moreover, we propose a variety of novel algorithms for conic discrete optimization. The algorithms, despite exploiting the nonlinear structure of the problems, are similar to algorithms commonly used for the linear case.

In Chapter 2 we study the problem of maximizing a class of nonlinear utility functions over the vertices of an integral polytope, and propose an approximation algorithm for the problem. The algorithm exploits the fact that there exists an optimal solution to the natural convex relaxation of the problem in an edge of the polytope, and rounds the solution to a vertex.

One of the principal approaches for solving discrete optimization problems to optimality are branch-and-bound algorithms. For linear problems, branch-and-bound algorithms are typically implemented using the simplex method, which allows to use warm-starts to efficiently solve the convex subproblems at each node of the branch-and-bound tree. In Chapter 3 we present a simplex method for conic quadratic minimization over polyhedra, and show that the algorithm outperforms existing methods in both convex and discrete instances.

In Chapter 4 we study strong formulations for general mixed-binary conic quadratic optimization. In particular, we give a complete description of the convex hull of the lower level set of a mixed-integer conic quadratic function. The convex hull can be described in an extended formulation using a single conic quadratic constraint and exponentially many linear inequalities. Thus, the inequalities can be implemented as cutting planes using existing techniques. Our computational experiments indicate that the inequalities strengthen the formulation considerably, and often result in order-of-magnitude improvements over commercial software.

In Chapter 5 we consider binary quadratic problems, which are a special case of conic quadratic problems. We propose an approach based on the decomposition of binary quadratic functions into a submodular component and a component with a convex relaxation. Then, by linearizing only the submodular component, we obtain formulations stronger than the natural convex relaxation of the problem and the formulation obtained from the full linearization of the quadratic expression. Preliminary computational experiments indicate that the proposed approach can result in considerable faster branch-and-bound algorithms. Finally, in Chapter 6 we give an overview of the main contributions in the dissertation, and provide promising directions for future research.