TL;DR
This paper tackles the computationally challenging problem of "chance-constrained programming," where decisions must satisfy constraints with a certain probability under uncertainty. The authors propose a novel two-phase approach using a neural network to approximate the violation probability and then a randomized algorithm to find optimal solutions within the feasible region, showing improved performance over existing methods.
What Problem Does This Paper Address?
Many real-world optimization problems involve uncertainty. In "chance-constrained programming," we aim to minimize an objective function subject to constraints that might not always hold true due to random disturbances. For example, in engineering, a component's strength might vary, and we need to ensure it holds with a high probability. The core difficulty is that these "chance constraints" make the problem NP-hard, meaning finding an exact solution becomes computationally infeasible as the problem size grows. Existing methods like the "scenario approach" and "sample average approximation" have limitations, such as being overly conservative or requiring too many assumptions. This paper seeks to develop a more efficient and accurate approximation method.
Methods
The proposed solution is a two-phase approach:
- Violation Probability Map Approximation:
- The authors use a Single Layer Feedforward Neural Network (SLFN) to learn a mapping from the decision variable space to the probability of constraint violation.
- They employ the Extreme Learning Machine (ELM) algorithm, specifically a sequential version, to train the SLFN's parameters. ELM is known for its speed and simplicity in training SLFNs.
- The network is trained using samples of decision variables and disturbance parameters, learning to predict the likelihood that a given decision will violate a constraint.
- Optimizer Exploration Algorithm:
- Once the violation probability map is approximated, a randomized optimization algorithm is used to find the optimal decision within the probabilistically feasible domain.
- This algorithm first samples decision points.
- It then uses the trained SLFN to estimate the violation probability for each sample.
- Samples with a violation probability exceeding a predefined threshold (slightly more conservative than the target) are discarded.
- The optimizer is then sought among the remaining "feasible" samples by minimizing the objective function. This process is iterated to refine the search.
Datasets
Not discussed in the paper. The paper focuses on a synthetic "targeted problem" for numerical validation, which is a non-convex program with chance constraints.
Key Insights and Ideas
- Neural Networks for Probabilistic Constraints: The core innovation is using SLFNs trained with ELM to create an accurate and efficient "violation probability map." This map is crucial for understanding the probabilistic feasible domain without explicitly enumerating all possibilities.
- Two-Phase Approach: Separating the problem into learning the feasible region (violation probability map) and then searching within it (optimizer exploration) provides a structured way to tackle the complexity.
- Balancing Conservatism and Optimality: The method aims to find a better trade-off between satisfying chance constraints (avoiding overly conservative solutions) and achieving a good objective function value. The use of a slightly more conservative threshold (αε) in discarding samples helps manage potential errors in the violation probability estimation.
- ELM's Efficiency: Leveraging ELM for training the neural network contributes to the overall efficiency of the approximation process.
Key Results
- Probabilistic Feasible Domain Approximation: The proposed method, using Algorithm 4, effectively approximates the violation probability map. Figure 5 shows that as the number of disturbance samples increases (N(δ) ≥ 1000), the approximation converges to the "real" boundary of the 5% violation probability.
- Optimizer Exploration: In numerical simulations, the proposed method demonstrated improved performance compared to the "scenario approach" and "parallel randomized algorithm."
- Figure 8 shows that the proposed method converges to the 5% violation boundary where the cost is minimal.
- Figure 9 indicates that the proposed method achieves a good balance between satisfying chance constraints (high probability of satisfying them) and achieving a low mean cost value.
- The scenario approach was found to be too conservative, while the parallel randomized algorithm had poorer accuracy in estimating violation probability.
Limitations and Future Work
- Randomness in Optimization: The current randomized optimization algorithm is entirely random. Future work could focus on improving its convergence speed by making it less random or more guided.
- Sample Number Dependency: The accuracy of the violation probability map is dependent on the number of disturbance samples (Ns) and decision samples (Nu). Quantitative analysis is needed to understand the precise relationship between accuracy and sample size.
- Parameter Selection: The choice of the conservative threshold (αε) for discarding samples is currently heuristic. Theoretical investigation into the optimal selection of this parameter is suggested.
- Generalization: While validated on a non-convex problem, further exploration of its performance on other types of problems would be beneficial.
Summary updated