Uncertain nonconvex quadratic optimization: conic approaches

Optimization problems consist of taking decisions on certain quantities (input) in order to optimize a certain output. E.g., to design a good investment portfolio in order to maximize revenue (output), you need to know how much to invest in each individual stock, at what time to invest etc., and also selecting what stocks to include in the portfolio. Two major difficulties in optimization arise here: nonconvexity and uncertainty. Convex problems are like finding the deepest point in a valley or a bathtub: if you follow the path of a marble rolling downwards, you will eventually find the deepest point. Nonconvex problems are like finding the deepest point in the Sahara: the marble will get caught in a sink that is deeper than where you started, but is it the deepest sink? You need check all other valleys first! Thus nonconvex problems are much harder to solve than convex ones. The portfolio optimization problem is an easy convex one. However, if we restrict the number of stocks in a portfolio, the optimal selection problem becomes nonconvex and hard to solve, because there is a large number of possible combinations. When choosing 100 stocks from 1000, the number of possible combinations dwarves the number of atoms in the universe, and for each of these combinations, we still have to determine the optimal investment proportions. The second difficulty is data uncertainty. If we do not know all the data needed for the optimal choice precisely, we can predict the outcome (e.g. stock returns) only with limited accuracy. If we know their distribution (possible scenarios and their probability), we can optimize for doing well on average. In faithful models of real uncertainty, the number of all possible scenarios is often huge. Additional complications arise for making future adjustments of a solution, a two-stage decision where you aim to make a choice today allowing for a good adjustment once we have more data. Then we not only need think about the optimal choices in each scenario, but also about how these impact our decision tomorrow, for nonconvex problems an obvious challenge. A recently developed theory called copositive optimization theory allows us to turn a nonconvex problem into a convex one, at the price of introducing many additional variables, along with other difficulties. But then we can use the large toolbox developed for convex optimization problems, e.g., to dissect one big problem into many small ones. Solving the small problems gives you information about the original problem which you can stitch together for a solution of the original problem (which is generally impossible without convexity). While this sounds simple, the details are not, and we have to combine knowledge on the problem, the nature of the uncertainty, and the advantages of the copositive approach. The goal of this project is to produce efficient algorithms for a difficult class of uncertain nonconvex optimization models, flexible enough to tackle many real-world problems.