Determining the best course of action in a setting where details are uncertain is extraordinarily difficult. Researchers have found an efficient method for doing so in two of the most common problems found in energy systems, supply chain management and finance.
Two popular approaches to problems involving uncertainty are “robust optimization,” which finds the solution most resilient against the “worst case scenario” realization of parameters, and “distributionally robust optimization,” which finds the solution most resilient against the “worst case probability distribution” for the uncertain parameters. Both problems become computationally infeasible if the problem is multistage, meaning the settings change over time. In two recent publications, University of Illinois Urbana-Champaign industrial & enterprise systems engineering professor Grani Hanasusanto has demonstrated that, under certain conditions, both problems may be efficiently solved using the well-studied methods of copositive programming and decision rule approximations.
“Multistage problems are infinite-dimensional, so they’re very difficult to approach even in theory,” Hanasusanto said. “To make progress for practical applications, we show that they can be transformed into equivalent finite-dimensional problems. The nice thing is that the equivalent reformulation has been extensively studied and we can use very good approximations to solve it.”
The goal of both robust and distributionally robust programs is to identify a “policy” – a mathematical function that determines the course of action to follow from the observed conditions. Since the set of possible mathematical functions is so vast and the function must satisfy a continuum of possible uncertainty constraints, both problems are infinite-dimensional. It is common to instead employ the decision rule approximation, in which the policy is assumed to be a linear or quadratic function. This greatly reduces the complexity of the problem, but it is still intractable because the continuum of constraints must still be satisfied.
Hanasusanto and his coauthors demonstrated in their articles that the decision rule approximations to both programs can be transformed into a copositive program.
“Since the problems are equivalent, one is just as difficult as the other to solve,” Hanasusanto said. “However, there are very good approximate methods available for copositive programming. This allowed us to go much further than generic methods.”
When applied to robust optimization, the copositive method could study up to 24 stages at once, compared to the two or three stages possible with other methods. In the case of distributionally robust optimization, the researchers showed that, in the case of two stages, the copositive technique could solve problems much faster than other methods and performed better when used to make decisions from observed data.
Hanasusanto is particularly excited about the progress in distributionally robust optimization, and he is planning future work to further extend his current results.
“Distributionally robust optimization is a fairly recent development that blends features of the ‘classical’ paradigms of robust optimization and stochastic programming, where one uses more conventional probability and statistics to optimize performance against a predetermined distribution,” he said. “It has become very popular, and I expect that the methods we have developed for these limited cases can be generalized to really make progress on the general problem of arbitrary stages.”
***
The article on robust optimization, “Improved Decision Rule Approximations for Multistage Robust Optimization via Copositive Programming,” was written with Guanglin Xu. It is published in the journal Operations Research and is available online. DOI: 10.1287/opre.2018.0505
The article on distributionally robust optimization, “A Decision Rule Approach for Two-Stage Data-Driven Distributionally Robust Optimization Problems with Random Recourse,” was written with Xiangyi Fan. It is published in the INFORMS Journal on Computing and is available online. DOI: 10.1287/ijoc.2021.0306