Optimization under uncertainty: understanding orders and testing programs with specifications
This work addresses foundational challenges in optimization for fields like climate science, economics, and engineering, but it appears incremental as it builds on existing concepts of orders and uncertainty.
The paper tackles the problem of optimization under uncertainty, where functions may have multiple objectives, return sets of results, or probability distributions, by developing a functional programming approach to specify and test solution methods for value and functorial uncertainty, demonstrating generalizations of standard minimization to partial orders.
One of the most ubiquitous problems in optimization is that of finding all the elements of a finite set at which a function $f$ attains its minimum (or maximum). When the codomain of $f$ is equipped with a total order, it is easy to specify, implement, and verify generic solutions to this problem. But what if $f$ is affected by uncertainties? What if one seeks values that minimize more than one objective, or if $f$ does not return a single result but a set of possible results, or even a probability distribution? Such situations are common in climate science, economics, and engineering. Developing trustworthy solution methods for optimization under uncertainty requires formulating and answering these questions rigorously, including deciding which order relations to apply in different cases. We show how functional programming can support this task, and apply it to specify and test solution methods for cases where optimization is affected by two conceptually different kinds of uncertainty: value and functorial uncertainty. We analyze the interplay of orders in these contexts, demonstrate how standard minimization generalizes to partial orders in the multi-objective setting and how it can be lifted via monotonicity conditions to handle functorial uncertainty.