Introduction
Many real-world operational challenges—ranging from power grid management to industrial supply chain logistics—require a sequence of decisions made under uncertainty. These problems are formally modeled as Stochastic Programming (SP). A significant hurdle in SP is the "curse of dimensionality," where the computational complexity grows exponentially with the number of time steps or state variables.
In many practical scenarios, the "cost-to-go" (the expected future cost) is a convex function. Exploiting this mathematical structure is key to efficient solving. This paper introduces Adaptive Max-Affine Partitioning (AMAP), a novel convex regression algorithm designed to approximate complex cost functions accurately while maintaining the necessary convexity constraints.
The AMAP Algorithm
The core of the AMAP approach is the use of max-affine estimators, which represent a convex function as the upper envelope of a set of hyperplanes. This ensures that the "physics" of the problem—its inherent convexity—is baked directly into the machine learning model, allowing for better generalization from limited data.
Key Technical Innovations
AMAP improves upon previous methods through several strategic innovations:
- Hybrid Partitioning: It combines the "cell splitting" logic of Convex Adaptive Partitioning (CAP) with the "least squares refinement" of the Least Squares Partition algorithm (LSPA). By splitting data at the median and using iterative LSPA steps to refine sub-optimal splits, AMAP achieves high efficiency in high-dimensional spaces.
- Rotational Invariance via thin-SVD: To handle variables with vastly different scales or high correlations, the authors implement a pre-processing step using thin Singular Value Decomposition (thin-SVD). This ensures the algorithm remains robust regardless of the input data's orientation.
- Automated Complexity Control: The algorithm employs cross-validation to determine the optimal number of hyperplanes, striking a balance between underfitting (too few planes) and overfitting (too many planes).
These estimators are integrated into a full Approximate Dynamic Programming (fADP) framework, which utilizes a forward pass to sample decision spaces and a backward pass to recursively estimate costs.
Experimental Evaluation
The researchers evaluated AMAP against existing benchmarks in two complex simulated environments.
Energy Storage Optimization
This task involves a 48-hour planning horizon for a facility managing renewable energy. The agent must decide how to route energy flows between a renewable source, a local demand center, a storage battery, and the external electrical grid while accounting for fluctuating prices and weather conditions.
As shown in the system diagram above, the model must manage constraints such as storage capacity ($s \le s_{max}$) and charge/discharge rates ($r_c, r_d$). In this benchmark, AMAP significantly outperformed standard heuristic rules-of-thumb, particularly as the volume of training data increased.
Beer Brewery Operation
This 16-dimensional problem simulates a 48-week production cycle. It is characterized by "delayed" states, as different products (like ales versus lagers) require varying fermentation times. In this high-dimensional setting, AMAP demonstrated superior performance, generating a revenue of over 4100 units, compared to the 3600 units achieved by the CAP algorithm.
Discussion and Future Work
While AMAP provides significant accuracy gains, it introduces a trade-off regarding computational scaling. Because AMAP often utilizes a larger number of hyperplanes to achieve higher accuracy, the subsequent Linear Programming (LP) tasks required for decision-making become more computationally expensive. For instance, in the brewery simulation, training times extended into several hours as the model complexity grew.
Future research directions include exploring sum-max-affine maps, which may represent complex surfaces with fewer planes, and investigating ensemble methods like bagging to further enhance the stability and speed of the estimators.
Summary updated